236. 二叉树的最近公共祖先

使用DFS解决

124. 二叉树中的最大路径和

215. 数组中的第K个最大元素

297. 二叉树的序列化与反序列化

方法一：DFS

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null)
            return "#";
        String left = serialize(root.left);
        String right = serialize(root.right);
        return root.val + "," + left + "," + right;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] nodes = data.split(",");
        return dfs(nodes);
    }

    int i = 0;

    public TreeNode dfs(String[] nodes) {
        String str = nodes[i++];
        if (str.equals("#"))
            return null;
        TreeNode root = new TreeNode(Integer.valueOf(str));
        root.left = dfs(nodes);
        root.right = dfs(nodes);
        return root;       
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

为什么左边的代码不行，因为如何nodes[i]是节点，i没有自增！

206. 反转链表

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

方法一：滑动窗口 set

用HashSet判断重复，并将左区间滑动到没有重复元素为止

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int length = 0;
        Set<Character> set = new HashSet<>();
        for (int i = 0, left = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            if (set.contains(ch)) {
                while (left < i) {
                    set.remove(s.charAt(left++));
                    if (!set.contains(ch))
                        break;
                }
            }
            set.add(ch);
            length = Math.max(length, i - left + 1);

        }
        return length;
    }
}

方法二：滑动窗口 map

用HashMap存储遍历的字符以及其下标，当出现重复字符，将left赋值为Math.max(left, map.get(ch) + 1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max = 0, left = 0, n = s.length();
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            char ch = s.charAt(i);
            if (map.containsKey(ch)) 
                left = Math.max(left, map.get(ch) + 1);
            map.put(ch, i);
            max = Math.max(max, i - left + 1);
        }
        return max;
    }
}

146. LRU 缓存

方法一：HashMap + ListNode

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
class LRUCache {

    static class ListNode {
        int key;
        int val;
        ListNode next, pre;
        public ListNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    
    ListNode head, tail;
    Map<Integer, ListNode> map;
    int capacity;
    
    public LRUCache(int capacity) {
        head = new ListNode(-1, -1);
        tail = new ListNode(-1, -1);
        head.next = tail;
        tail.pre = head;
        map = new HashMap<>();
        this.capacity = capacity;
    }
    
    public int get(int key) {
        if (!map.containsKey(key))
            return -1;
        moveToTail(key);
        return map.get(key).val;
    }
    
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            moveToTail(key);
            map.get(key).val = value;
        }
        else {
            if (capacity == map.size())  // delete last one
                delete(-1, true);
            // insert new node in the previous of tail
            ListNode node = new ListNode(key, value);
            map.put(key, node);
            insertIntail(key);
        }
    }

    public void moveToTail(int key) {
        delete(key, false);
        insertIntail(key);
    }

    public void delete(int key, boolean isLast) {
        if (isLast) {
            ListNode toBeDelete = head.next;
            map.remove(toBeDelete.key);
            head.next = toBeDelete.next;
            toBeDelete.next.pre = head;
        }
        else {
            ListNode toBeDelete = map.get(key);
            // map.remove(toBeDelete.key);
            toBeDelete.pre.next = toBeDelete.next;
            toBeDelete.next.pre = toBeDelete.pre;
        }
    }
    
    private void insertIntail(int key) {
        ListNode node = map.get(key);
        node.next = tail;
        tail.pre.next = node;
        node.pre = tail.pre;
        tail.pre = node;
    }
    
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

450. 删除二叉搜索树中的节点

方法一：DFS

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
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) 
            return null;
        if (root.val > key)
            root.left = deleteNode(root.left, key);
        else if (root.val < key)
            root.right = deleteNode(root.right, key);
        else {
            if (root.left == null && root.right == null)
                return null;
            else if (root.left == null)
                return root.right;
            else if (root.right == null)
                return root.left;
            else {
                TreeNode cur = root.right;
                while (cur.left != null) 
                    cur = cur.left;
                cur.left = root.left;
                return root.right;
            }
        }
        return root;
    }
}

53. 最大子数组和

方法一：DP

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length, res = nums[0];
        int[] dp = new int[n];
        dp[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            dp[i] = nums[i] + (dp[i - 1] >= 0 ? dp[i - 1] : 0);
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

33. 搜索旋转排序数组

方法一：二分查找

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
29
30
31
32
33
34
35
class Solution {
    public int search(int[] nums, int target) {
        // 首先找到逆序的第一个数的下标x，x~n-1是较小的子数组
        int n = nums.length, targetIdx = -1;
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (nums[mid] <= nums[n - 1])
                right = mid - 1;
            else 
                left = mid + 1;
        }
        // left > right，此时找到了逆序的第一个数的下标left
        // 接着根据target的值来二分，如果target > nums[n - 1]，则在左边较大的子数组中二分查找，否在在右边较小的子数组中二分查找
        if (target > nums[n - 1])
            targetIdx = bisearch(nums, 0, left - 1, target);
        else 
            targetIdx = bisearch(nums, left, n - 1, target);
        return targetIdx;
    }

    public int bisearch(int[] nums, int left, int right, int target) {
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] == target)
                return mid;
            else 
                right = mid - 1;
        }
        return -1;
    }

}

4. 寻找两个正序数组的中位数

题解

方法一：划分数组

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
29
30
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length)
            return findMedianSortedArrays(nums2, nums1);
        int m = nums1.length, n = nums2.length;
        int median1 = 0, median2 = 0; // 如果有m + n是偶数，median2是第二个中位数
        int left = 0, right = m; // i == m时，表示nums1全被划分为前一部分
        while (left <= right) {
            // 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
            // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
            // 当m + n是偶数，规定前一部分和后一部分的长度相同
            // 当m + n是奇数，规定前一部分的长度 == 后一部分的长度 + 1
            // j = (m + n + 1 ) / 2 - i 可以很好地满足，不管m+n是奇数还是偶数
            int i = (left + right) / 2, j = (m + n + 1) / 2 - i;
            int nums_i = i == m ? Integer.MAX_VALUE : nums1[i];
            int nums_im1 = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
            int nums_j = j == n ? Integer.MAX_VALUE : nums2[j];
            int nums_jm1 = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
            if (nums_im1 <= nums_j) {
                median1 = Math.max(nums_im1, nums_jm1);
                median2 = Math.min(nums_i, nums_j);
                left = i + 1;
            }
            else {
                right = i - 1;
            }
        }
        return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;
    }
}

22. 括号生成

方法一：回溯

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 {
    public List<String> generateParenthesis(int n) {
        this.n = n;
        dfs(0, n, n);
        return res;
    }

    private void dfs(int index, int left, int right) {
        if (index == 2 * n) {
            res.add(sb.toString());
            return;
        }
        if (left > 0) {
            sb.append('(');
            dfs(index + 1, left - 1, right);
            sb.deleteCharAt(sb.length() - 1);
        }
        if (right > left) {
            sb.append(')');
            dfs(index + 1, left, right - 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    List<String> res = new LinkedList<>();
    StringBuilder sb = new StringBuilder();
    int n;
}

560. 和为 K 的子数组

方法一：前缀和 + HashMap

题解

可以用这种方法做链接中的题

map.put(0, 1)是为了让第一组满足的子数组map.containsKey(pre - k) = 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 class Solution {
    public int subarraySum(int[] nums, int k) {
        int pre = 0, count = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int i = 0; i < nums.length; ++i) {
            pre += nums[i];
            if (map.containsKey(pre - k)) 
                count += map.get(pre - k);
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }
        return count;
    }
}

103. 二叉树的锯齿形层序遍历

方法一：双队列

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (root == null) 
            return new LinkedList<>();
        boolean nextRight = true;
        Deque<TreeNode> queue = new LinkedList<>(), temp = new LinkedList<>();
        queue.offer(root);
        List<List<Integer>> res = new LinkedList();
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new LinkedList();
            for (int i = 0; i < size; ++i) {
                if (nextRight) {
                    TreeNode cur = queue.pollFirst();
                    list.add(cur.val);
                    if (cur.left != null)
                        temp.offerLast(cur.left);
                    if (cur.right != null)
                        temp.offerLast(cur.right);
                }
                else {
                    TreeNode cur = queue.pollLast();
                    list.add(cur.val);
                    if (cur.right != null)
                        temp.offerFirst(cur.right);
                    if (cur.left != null)
                        temp.offerFirst(cur.left);
                }
            }
            queue = temp;
            temp = new LinkedList<>();
            res.add(list);
            nextRight = !nextRight;
        }
        return res;
    }
}

151. 反转字符串中的单词

方法一：双端队列

用栈实现不是逆序的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public String reverseWords(String s) {
        // 去除首尾空格
        Deque<String> queue = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        int left = 0, right = s.length() - 1;
        while (s.charAt(left) == ' ')
            ++left;
        while (s.charAt(right) == ' ')
            --right;
        while (left <= right) {
            char ch = s.charAt(left++);
            if (ch != ' ')
                sb.append(ch);
            else if (ch == ' ' && sb.length() > 0) {
                queue.offerFirst(sb.toString());
                sb.setLength(0);
            }
        }
        queue.offerFirst(sb.toString());
        return String.join(" ", queue);
    }
}

25. K 个一组翻转链表

方法一：模拟

多debug

使用outOfBound判断最后一部分节点的数量是否少于k，如果少于k就break

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (k == 1)
            return head;
        ListNode dummyHead = new ListNode(-1, head);
        ListNode pre = dummyHead, next = dummyHead, cur = head, start = dummyHead;
        while (cur != null && cur.next != null) {
            boolean outOfBound = false;
            for (int i = 0; i < k - 1; ++i) {
                if (cur.next == null) {
                    outOfBound = true;
                    break;
                }
                cur = cur.next;
                next = cur.next;
            }
            if (outOfBound)
                break;
            cur.next = null;
            start = pre.next;
            pre.next = reverse(start);
            start.next = next;
            pre = start;
            cur = pre.next;
        }
        return dummyHead.next;
    }

    private ListNode reverse(ListNode cur) {
        ListNode pre = null, next;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;;
            pre = cur;
            cur = next;
        }
        return pre;
    }
    
}

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

方法一：模拟

判断是否溢出

其中Integer.MAX_VALUE / 10 == res && val > 7，如果是正数val > 7溢出；如果是负数val > 8才溢出，不过等于8时，结果恰好是Integer.MIN_VALUE

[-2147483648,2147483647]

1
2
if (Integer.MAX_VALUE / 10 < res || (Integer.MAX_VALUE / 10 == res && val > 7))
    return positive ? Integer.MAX_VALUE : Integer.MIN_VALUE;

代码

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
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public int myAtoi(String s) {
        int left = 0, n = s.length();
        if (n == 0)
            return 0;
        // 丢弃前导空格
        while (left < n) {
            if (s.charAt(left) != ' ')
                break;
            ++left;
        }
        if (left == n)
            return 0;
        // 判断正负号
        boolean positive = true;
        if (!isDigital(s.charAt(left))) {
            positive = s.charAt(left) == '-' ? false : true;
            if (s.charAt(left) == '-')
                positive = false;
            else if (s.charAt(left) != '+')
                return 0;
            ++left;
        }
        int res = 0;
        for (int i = left; i < n; ++i) {
            char ch = s.charAt(i);
            if (!isDigital(ch))
                break;
            int val = ch - '0';
            if (Integer.MAX_VALUE / 10 < res || (Integer.MAX_VALUE / 10 == res && val > 7))
                return positive ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            res = res * 10 + val;
        }
        return positive ? res : -res;
    }

    private boolean isDigital(char ch) {
        return ch == '0' || ch == '1' || ch == '2' || ch == '3' || ch == '4' || ch == '5' || ch == '6'|| ch == '7'|| ch == '8'|| ch == '9';
    }
}

56. 合并区间

方法一：射气球

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[0], o2[0]);
            }
        });
        List<int[]> list = new LinkedList<>();
        int left = 0;
        for (int i = 1; i < intervals.length; ++i) {
            if (intervals[left][1] >= intervals[i][0])
                intervals[left][1] = Math.max(intervals[left][1], intervals[i][1]);
            else  {
                list.add(intervals[left]);
                left = i;
            }
        }
        intervals[left][1] = Math.max(intervals[left][1], intervals[intervals.length - 1][1]);
        list.add(intervals[left]);
        return list.toArray(new int[list.size()][]);
    }
}

48. 旋转图像

方法一：模拟

别看题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n >> 1; ++i) {
            int len = n - i * 2;
            for (int j = 0; j < len - 1; ++j) {
                int temp = matrix[i][i + j];
                matrix[i][i + j] = matrix[n - i - j - 1][i];
                matrix[n - i - j - 1][i] = matrix[n - i - 1][n - i - j - 1];
                matrix[n - i - 1][n - i - j - 1] = matrix[i + j][n - i - 1];
                matrix[i + j][n - i - 1] = temp;
            }
        }
    }
}

15. 三数之和

方法一：排序 + 双指针

题解

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
29
30
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        List<List<Integer>> res = new LinkedList<>();
        Arrays.sort(nums);
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0)
                return res;
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            int left = i + 1, right = n - 1;
            while (left < right) {
                if (nums[i] + nums[left] + nums[right] == 0) {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while (left < right && nums[left] == nums[left + 1])
                        ++left;
                    while (left < right && nums[right] == nums[right - 1])
                        --right;
                    ++left;
                    --right;
                }
                else if (nums[i] + nums[left] + nums[right] < 0)
                    ++left;
                else 
                    --right;
            }
        }
        return res;
    }
}

1. 两数之和

方法一：HashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        HashMap<Integer, Integer> map = new HashMap<>();
        int[] res = new int[2];
        for (int i = 0; i < n; ++i) {
            if (map.containsKey(target - nums[i])) {
                res[0] = i;
                res[1] = map.get(target - nums[i]);
            }
            map.put(nums[i], i);
                
        }
        return res;
    }
}

5. 最长回文子串

方法一：DP

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 {
    public String longestPalindrome(String s) {
        int n = s.length(), max = 0;
        int[] maxIndex = new int[2];
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = i; j >= 0; --j) {
                if (i - j + 1 == 1)
                    dp[i][j] = 1;
                else if (i - j + 1 == 2)
                    dp[i][j] = s.charAt(i) == s.charAt(j) ? 2 : 0;
                else if (i - j + 1 == 3)
                    dp[i][j] = s.charAt(i) == s.charAt(j) ? 3 : 0;
                else {
                    if (s.charAt(i) != s.charAt(j))
                        dp[i][j] = 0;
                    else
                        dp[i][j] = dp[i - 1][j + 1] > 0 ? dp[i - 1][j + 1] + 2 : 0;
                }
                if (dp[i][j] > max) {
                    max = dp[i][j];
                    maxIndex = new int[]{j, i};
                }
            }
        }
        return s.substring(maxIndex[0], maxIndex[1] + 1);
    }
}

121. 买卖股票的最佳时机

https://leopol1d.github.io/2023/06/28/microsoft/
作者
Leopold
发布于
2023年6月28日
许可协议