LeetCode

2、两数相加

链表结构与树的结构类似,但是链表只有节点值和下一节点两个属性,因此除了递归,也可以通过循环来遍历。

3、无重复字符的最长子串

滑动窗口

237、删除链表中的节点

从链表里删除一个节点node的最常见方法是修改之前节点的next指针,使其指向之后的节点。

因为,我们无法访问我们想要删除的节点之前的节点,我们始终不能修改该节点的next指针。相反,我们必须将想要删除的节点的值替换为它后面节点中的值,然后删除它之后的节点。

因为我们知道要删除的节点不是列表的末尾,所以我们可以保证这种方法是可行的。

461、汉明距离

一、处理二进制的问题一般用位操作,包括&(与)、|(或)、~(非)、^(异或)、<<(左移)、>>(右移)、>>>(无符号右移)。

Java中所有的二进制操作符都是操作数字的补码。

二、Integer.bitCount(int a)用于计算a的二进制中1的个数。

617、合并二叉树

二叉树的结构类似链表,每个节点有值和左右子树三个属性,如果添加一个只有值的节点,不把它作为其他节点的子树,则该节点并不在树上。

657、机器人能否返回原点

一、switch case语句

switch(expression){
    case value :
        //语句
        break;  //可选
    case value :
        //语句
        break;  //可选
    //你可以有任意数量的case语句
    default :  //可选
        //语句
}
  • switch 语句中的变量类型可以是: byte、short、int 或者 char。从 Java SE 7 开始,switch 支持字符串 String 类型了,同时 case 标签必须为字符串常量或字面量。
  • switch 语句可以拥有多个 case 语句。每个 case 后面跟一个要比较的值和冒号。
  • case 语句中的值的数据类型必须与变量的数据类型相同,而且只能是常量或者字面常量。
  • 当变量的值与 case 语句的值相等时,那么 case 语句之后的语句开始执行,直到 break 语句出现才会跳出 switch 语句。
  • 当遇到 break 语句时,switch 语句终止。程序跳转到 switch 语句后面的语句执行。case 语句不必须要包含 break 语句。如果没有 break 语句出现,程序会继续执行下一条 case 语句,直到出现 break 语句。
  • switch 语句可以包含一个 default 分支,该分支一般是 switch 语句的最后一个分支(可以在任何位置,但建议在最后一个)。default 在没有 case 语句的值和变量值相等的时候执行。default 分支不需要 break 语句。

switch case 执行时,一定会先进行匹配,匹配成功返回当前 case 的值,再根据是否有 break,判断是否继续输出,或是跳出判断。

709、转换成小写字母

一、String.toLowerCase()。

二、String.toCharArray()把String转换成char[]。

三、char[]转String

char[] a = {'a', 'b', 'c'};
String s = new String(a);  //s为"abc"

四、ASCII代码

65~90:'A'~'Z'
97~122:'a'~'z'
'a' - 'A' = 32

804、唯一摩尔斯密码词

一、Set:无序,集合中的元素不重复。

计算不同元素的数量可以使用Set
Set.add(E)用来往Set中添加元素,重复的不会被添加进去
Set.size()返回Set中所有元素的数量

832、翻转图像

一、创建栈

Stack stack = new Stack();
stack.pop();  //返回值为Object类型

Stack<Integer> stack = new Stack<>();  //泛型
stack.pop();  //返回值为Integer类型

二、int和Integer

1. int是基本数据类型,Integer是int的包装类,因此Integer可用于泛型,而int不行。
2. 互相转换

int i = 0;
Ingeter j;

j = new Integer(i);  //int转Integer,装箱
System.out.println(i == j);  //false

i = j.intValue();  //Integer转int,拆箱
//Java7以后,可以自动实现int和Integer的转换,即自动装箱和自动拆箱
int i = 0;
Integer j = i;  //int转Integer,自动调用装箱方法
i = j;  //Integer转int,自动调用拆箱方法

938、二叉搜索树的范围和

一、二叉搜索树:它或者是一棵空树,或者是具有下列性质的二叉树:若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也分别为二叉搜索树。

二、二叉树遍历:二叉树有前、中、后三种遍历方式,因为树本身是根据递归来定义的,所以采用递归的方法实现三种遍历,不仅代码简洁且容易理解,但其开销也比较大,而若采用非递归方法实现三种遍历,则要用来模拟实现(递归也是用栈实现的)。

1. 前序遍历通俗的说就是从二叉树的根结点出发,当第一次到达结点时就输出结点数据,按照先向左在向右的方向访问。(根节点-左孩子-右孩子)

从根结点出发,则第一次到达结点A,故输出A;
继续向左访问,第一次访问结点B,故输出B;
按照同样规则,输出D,输出H;
当到达叶子结点H,返回到D,此时已经是第二次到达D,故不在输出D,进而向D右子树访问,D右子树不为空,则访问至I,第一次到达I,则输出I;
I为叶子结点,则返回到D,D左右子树已经访问完毕,则返回到B,进而到B右子树,第一次到达E,故输出E;
向E左子树,故输出J;
按照同样的访问规则,继续输出C、F、G;

则上图所示二叉树的前序遍历输出为:
ABDHIEJCFG

2. 中序遍历就是从二叉树的根结点出发,当第二次到达结点时就输出结点数据,按照先向左在向右的方向访问。(左孩子-根节点-右孩子)

从根结点出发,则第一次到达结点A,不输出A,继续向左访问,第一次访问结点B,不输出B;继续到达D,H;
到达H,H左子树为空,则返回到H,此时第二次访问H,故输出H;
H右子树为空,则返回至D,此时第二次到达D,故输出D;
由D返回至B,第二次到达B,故输出B;
按照同样规则继续访问,输出J、E、A、F、C、G;

则上图所示二叉树的中序遍历输出为:
HDIBJEAFCG

3. 后序遍历就是从二叉树的根结点出发,当第三次到达结点时就输出结点数据,按照先向左在向右的方向访问。(左孩子-右孩子-根节点)

从根结点出发,则第一次到达结点A,不输出A,继续向左访问,第一次访问结点B,不输出B;继续到达D,H;
到达H,H左子树为空,则返回到H,此时第二次访问H,不输出H;
H右子树为空,则返回至H,此时第三次到达H,故输出H;
由H返回至D,第二次到达D,不输出D;
继续访问至I,I左右子树均为空,故第三次访问I时,输出I;
返回至D,此时第三次到达D,故输出D;
按照同样规则继续访问,输出J、E、B、F、G、C,A;

则上图所示二叉树的中序遍历输出为:
HIDJEBFGCA

三、栈:栈是一种“先进后出”的一种数据结构,有压栈出栈两种操作方式,只能操作栈顶元素。

四、递归:自己调用自己,需要递归出口(递归终止的条件)和递归表达式(规律)。

977、有序数组的平方

一、Arrays.sort(int[] a)用于对指定的int型数组按数字升序进行排序。

二、^为异或,平方只能用*号

1021、删除最外层的括号

一、String.length()获取字符串长度。

二、String.charAt(int index)获取字符串第index位的字符,返回值为char类型。

三、String.Substring(int beginIndex, int endIndex)返回字符串的子字符串,beginIndex为起始索引(包括), 索引从 0 开始,endIndex为结束索引(不包括)。

四、String.concat(String s)用于将指定的字符串参数连接到字符串上。

String s1 = null;
String s2 = "";
String s3 = "abc";

s1.concat(s3);  //会报空指针异常
s3.concat(s2);  //因为s2为空,不会new一个新的String对象,返回s3指向的对象
s2.concat(s3);  //concat创建一个新的String对象,不改变s2的指向
s1 = s2.concat(s3);  //s1变为“abc”,s2仍为“”

发表评论

电子邮件地址不会被公开。 必填项已用*标注