LeetCode刷题笔记——HOT100面试题（4）

算法
, ,

字符串

5. 最长回文子串

使用中心扩展法判断回文子串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {

    int left;
    int right;
    int maxLen;

    public String longestPalindrome(String s) {
        for (int i=0; i<s.length(); i++) {
            getPalindrome(s, i, i);
            getPalindrome(s, i, i+1);
        }
        return s.substring(left, right+1);
    }

    public void getPalindrome(String s, int i, int j) {
        while (i>=0 && j<s.length()) {
            if (s.charAt(i)!=s.charAt(j)) return;
            int t = j - i + 1;
            if (t > maxLen) {
                maxLen = t;
                left = i;
                right = j;
            }
            i--;
            j++;
        }
    }
}

49. 字母异位词分组

把每个字符串排序，按排序后的字符串作为键保存到哈希表中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> map = new HashMap<>();
        for (int i=0; i<strs.length; i++) {
            char[] c = strs[i].toCharArray();
            Arrays.sort(c);
            String key = new String(c);
            List<String> tmp = map.getOrDefault(key, new ArrayList<>());
            tmp.add(strs[i]);
            map.put(key, tmp);
        }
        List<List<String>> res = new ArrayList<>();
        for (String key: map.keySet()) {
            res.add(map.get(key));
        }
        return res;
    }
}

394. 字符串解码

使用两个栈分别保存数字和字符。遍历字符串，遍历到[时，将记录的数字和字符串入栈并重置，此时res保存方括号内的字符串；遍历到]时，将数字栈的顶部元素弹出，它是目前res字符串需要重复的次数，再加上字符栈顶部元素构成新一轮的res。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public String decodeString(String s) {
        Stack<Integer> num = new Stack<>();
        Stack<String> str = new Stack<>();
        StringBuilder res = new StringBuilder();
        int count = 0;
        for (char c: s.toCharArray()) {
            if (c=='[') {
                num.push(count);
                count = 0;
                str.push(res.toString());
                res = new StringBuilder();
            } else if (c==']') {
                StringBuilder tmp = new StringBuilder();
                tmp.append(str.pop());
                int curNum = num.pop();
                for (int i=0; i<curNum; i++) {
                    tmp.append(res.toString());
                }
                res = tmp;
            } else if (c>='0' && c<='9') count = count*10+c-'0';
            else res.append(c);
        }
        return res.toString();
    }
}

647. 回文子串

使用中心扩展法判断回文子串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {

    int res = 0;

    public int countSubstrings(String s) {
        for (int i=0; i<s.length(); i++) {
            isPalindrome(s, i, i);
            isPalindrome(s, i, i+1);
        }
        return res;
    }

    public void isPalindrome(String s, int i, int j) {
        while (i>=0 && j<s.length()) {
            if (s.charAt(i)!=s.charAt(j)) break;
            i--;
            j++;
            res++;
        }
    }
}

位运算

136. 只出现一次的数字

两个相等的数异或为0，0异或任意数等于它本身。利用此性质解本题。

1
2
3
4
5
6
7
8
9
class Solution {
    public int singleNumber(int[] nums) {
        int xor = 0;
        for (int num: nums) {
            xor ^= num;
        }
        return xor;
    }
}

338. 比特位计数

n&(n-1)可以把n的最右边的1去掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] countBits(int num) {
        int[] res = new int[num+1];
        for (int i=0; i<=num; i++) {
            res[i] = count(i);
        }
        return res;
    }

    public int count(int num) {
        int count = 0;
        while (num!=0) {
            count++;
            num &= num-1;
        }
        return count;
    }
}

461. 汉明距离

求两数的异或，结果中为1的位数即为汉明距离。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int hammingDistance(int x, int y) {
        int xor = x^y;
        int res = 0;
        while (xor!=0) {
            res++;
            xor = (xor&(xor-1));
        }
        return res;
    }
}