LeetCode

7、整数反转

我们想重复“弹出”x的最后一位数字,并将它“推入”到rev的后面。最后,rev将与x相反。

要在没有辅助堆栈/数组的帮助下“弹出”和“推入”数字,我们可以使用数学方法。

//pop operation:
pop = x % 10;
x /= 10;

//push operation:
temp = rev * 10 + pop;
rev = temp;

当temp = rev * 10 + pop;时可能导致溢出(超出int所能表示的最大范围),解决方法:

1、声明rev为long类型,返回前判断rev是否超出int所能表示的最大范围:

if (rev > Integer.MAX_VALUE || rev < Integer.MIN_VALUE) {
    return 0;
} else {
    return (int)rev;
}

2、在rev * 10前对rev和pop进行判断:

if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;

if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;

3、用try/catch处理

8、字符串转换整数 (atoi)

char类型的‘0’ – ‘9’与int类型0 – 9之间本来就存在映射关系,不需要特地存在Map中。

三次循环遍历:

  1. 能有效解析的字符串开头只有三种可能:①‘0’ – ‘9’,②‘+’和‘-’,③‘ ’(空格)。因此第一次循环首先判断是否为数字,是的话退出循环,此时的i为数字的起始位置;否则判断是否为正负号,是的话记录符号的正负,i+1并退出循环;否则判断是否为空格,不是的话直接return 0,是的话继续循环。
  2. 第二次循环挑出字符串中的有效数字部分,判断i后面几位是否为数字,一旦不是数字,跳出循环,用j记录数字的结束位置。
  3. 此时有效数字和正负号信息都已经获取,第三循环从i遍历到j,计算有效数字的int值。

9、回文数

① 字符串法:

通过在int类型变量后面+””将其转换成String类型,利用StringBuilder类型的reverse()方法将字符串反转,与原字符串比较是否相同。

class Solution {
    public boolean isPalindrome(int x) {
        String reversedStr = (new StringBuilder(x + "")).reverse().toString();
        return (x + "").equals(reversedStr);
    }
}

或者将整数转为字符串 ,然后将字符串分割为数组,只需要循环数组的一半长度进行判断对应元素是否相等即可。

② 首尾比较法:

通过取整和取余操作获取整数中对应的数字进行比较。

举个例子:1221 这个数字。

  • 通过计算1221 / 1000,得首位1
  • 通过计算1221 % 10,可得末位1
  • 进行比较
  • 再将22取出来继续比较
class Solution {
    public boolean isPalindrome(int x) {
        //边界判断
        if (x < 0) return false;
        int div = 1;
        
        while (x / div >= 10) div *= 10;
        while (x > 0) {
            int left = x / div;
            int right = x % 10;
            if (left != right) return false;
            x = (x % div) / 10;
            div /= 100;
        }
        return true;
    }
}

③ 反转一半数字

直观上来看待回文数的话,就感觉像是将数字进行对折后看能否一一对应。

所以这个解法的操作就是取出后半段数字进行翻转

这里需要注意的一个点就是由于回文数的位数可奇可偶,所以当它的长度是偶数时,它对折过来应该是相等的;当它的长度是奇数时,那么它对折过来后,有一个的长度需要去掉一位数(除以10并取整)

  • 每次进行取余操作( %10),取出最低的数字:y = x % 10
  • 将最低的数字加到取出数的末尾:revertNum = revertNum * 10 + y
  • 每取一个最低位数字,x都要自除以10
  • 判断x是不是小于revertNum ,当它小于的时候,说明数字已经对半或者过半了
  • 最后,判断奇偶数情况:如果是偶数的话,revertNum和x相等;如果是奇数的话,最中间的数字就在revertNum的最低位上,将它除以10以后应该和x相等
class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) return false;
        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }
        return x == revertedNumber || x == revertedNumber / 10;
    }
}

13、罗马数字转整数

一个罗马数字只有一个字符和两个字符两种情况,把所有可能出现的组合存放在HashMap中:

Map<String, Integer> map = new HashMap<>();
map.put("I", 1);
map.put("IV", 4);
map.put("V", 5);
map.put("IX", 9);
map.put("X", 10);
map.put("XL", 40);
map.put("L", 50);
map.put("XC", 90);
map.put("C", 100);
map.put("CD", 400);
map.put("D", 500);
map.put("CM", 900);
map.put("M", 1000);

然后对字符串进行遍历,优先匹配两个字符:先判断两个字符的组合在哈希表中是否存在,存在则将值取出加到结果ans中,并向后移2个字符。不存在则将判断当前1个字符是否存在,存在则将值取出加到结果ans中,并向后移1个字符。遍历结束返回结果 ans:

int ans = 0;
for(int i = 0;i < s.length();) {
    if(i+1 < s.length() && map.containsKey(s.substring(i, i+2))) {
        ans += map.get(s.substring(i, i+2));
        i += 2;
    } else {
        ans += map.get(s.substring(i, i+1));
        i++;
    }
}
return ans;
Map.containsKey(Object k);   //此映射是否包含指定键的映射关系 
Map.put(Object k, Object v);  //将指定的值与此映射中的指定键关联
Map.get(Object k);  //返回指定键所映射的值

String.substring(int i, int j);  //返回一个新字符串,它是此字符串的一个子字符串 

20、有效的括号

用Map存放开闭括号对,Stack存放遍历到的开括号,并在遍历到闭括号时弹出栈顶的开括号:

  1. 初始化栈S。
  2. 依次处理表达式的每个括号。
  3. 如果遇到开括号,我们只需将其推到栈上即可。这意味着我们将稍后处理它,让我们简单地转到前面的子表达式。
  4. 如果我们遇到一个闭括号,那么我们检查栈顶的元素。如果栈顶的元素是一个相同类型的左括号,那么我们将它从栈中弹出并继续处理。否则,这意味着表达式无效。
  5. 如果到最后我们剩下的栈中仍然有元素,那么这意味着表达式无效。
  • 字符串字符个数为奇数时,直接返回false
  • 遍历到闭括号但栈为空时,返回false
  • 遍历结束栈不为空时,返回false
如果一次循环需要处理字符串中多个字符,则用String.toCharArray()转为字符数组。
如果一次循环只需处理字符串中1个字符,则用String.charAt(int i)获取字符。

Stack.isEmpty()和Stack.empty()没有本质区别。

28、实现strStr()

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仍为“”

发表评论

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