1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

// 示例1 2 6 5 3 4 7 8
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
    
    // 从左向右，找中间子数组的右边界
    if (nums[i] >= max) {// 对于升序数组，当前元素应大于之前的max
        max = nums[i];// 正常更新max
    } else {// 比当前max小的（说明非升序）都在中子数组范围内
        end = i;
    }
    // 从右向左，找左边界
    if (nums[n - 1 - i] <= min) {// 正常更新min
        min = nums[n - 1 - i];
    } else {
        start = n - 1 - i;
    }
}

 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

public String minWindow(String s, String t) {
    if (s == null || t == null || s.length() < t.length()) {
        return "";
    }

    int[] need = new int[128];
    for (char c : t.toCharArray()) {need[c]++;}
    // 统计t中各字符的频次

    int left = 0, right = 0;
    int count = t.length(); // t总字符数
    int start = 0, minLen = Integer.MAX_VALUE;

    while (right < s.length()) {
        char c = s.charAt(right);

        if (need[c] > 0) {count--;}// 是t中的字符，计数--
        need[c]--;// 对每个字符都执行，
        // 因此即使下面d是无关的字符时，其need的值也不会大于0
        right++;

        while (count == 0) {// 满足条件，收缩窗口
            if (right - left < minLen) {// 先记录开始位置和长度
                minLen = right-left;
                start = left;
            }
            // 收缩窗口
            char d = s.charAt(left);
            if (need[d] == 0) {count++;}// 刚好用到的字符，移出窗口则count需要++
            need[d]++;
            left++;
        }
    }

    return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start+minLen);
}

 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

# 定长
def findAnagrams(self, s, p):
    n, m = len(s), len(p)
    if n < m:
        return []

    need = [0] * 26
    window = [0] * 26

    for ch in p: # p中各字母个数
        need[ord(ch) - ord('a')] += 1

    ans = []

    for index, ch in enumerate(s):
        window[ord(ch) - ord('a')] += 1

        if index >= m:# 移出窗口
            out = s[index - m]
            window[ord(out) - ord('a')] -= 1

        if window == need:
            ans.append(index - m + 1)

    return ans

# 变长
def findAnagrams(self, s, p):
    n, m = len(s), len(p)
    if n < m:
        return []

    need = [0] * 26
    for ch in p: # p中各字母个数
        need[ord(ch) - ord('a')] += 1

    ans = []
    left=0

    for right, ch in enumerate(s):
        need[ord(ch) - ord('a')] -= 1

        while need[ord(ch) - ord('a')]<0:
            need[ord(s[left])-ord('a')] +=1
            left += 1

        if right-left+1 == m:
            ans.append(left)

    return ans

1
2
3
4
5
6

ListNode pA = headA, pB = headB;
while (pA != pB) {
    pA = pA == null ? headB : pA.next;
    pB = pB == null ? headA : pB.next;
}
return pA;

1
2
3
4
5

HashMap<Integer, Integer> map = new HashMap<>();  
for (int i : A) for (int j : B) map.put(i + j, map.getOrDefault(i + j, 0) + 1);  
int count = 0;  
for (int i : C) for (int j : D) count += map.getOrDefault(-(i + j), 0);  
return count;

1
2
3
4
5
6
7
8

for (int i = 0; i < ch.length; i += 2*k) {
    int left = i, right = Math.min(i+k-1, ch.length-1);
    while (left < right) {
        char temp = ch[left];
        ch[left++] = ch[right];
        ch[right--] = temp;
    }
}

1
2
3
4
5
6

while (left <= right) {// left为整个串的开头位置，不移动
    int end = right;
    while (left <= right && s.charAt(right) != ' ') { right--; }
    sb.append(s.substring(right+1, end+1)).append(" ");
    while (left <= right && s.charAt(right) == ' ') { right--; }// 去空格
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

public String removeDuplicates(String s) {
    char[] ch = s.toCharArray();
    int fast = 0;
    int slow = 0;
    while(fast < s.length()){
        if(slow > 0 && ch[fast] == ch[slow - 1]) { slow--; }// 当前slow位置未赋值，slow-1为结果串最后一个位置
        else { ch[slow++] = ch[fast]; }
        fast++;
    }
    return new String(ch,0,slow);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int[] next = new int[n];
int j = 0; // 前缀末尾，也是最长公共部分长度
for (int i = 1; i < n; i++) { // 后缀末尾
    while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
        j = next[j - 1];// 回溯到上个匹配位置
    }
    if (pattern.charAt(i) == pattern.charAt(j)) {
        j++;
    }
    next[i] = j;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

int left = 0, right = 0;
while (left < s.length()) {
    if (s.charAt(left) == sub.charAt(right)) {
        right++;
        if (right == sub.length()) { return left-right+1; }
    } else {
        left -= right;// 下面有left++，不用加1
        right = 0;
    }
    left++;
}
return -1;

1
2
3
4
5
6
7
8

int n = s.length(); 
int[] next = new int[n];
for (int i = 1, j = 0; i < n; i++) {// i为后缀末尾，j为前缀末尾
    while(j > 0 && s.charAt(i) != s.charAt(j)) { j = next[j-1]; }
    if (s.charAt(i) == s.charAt(j)) { j++; }
    next[i] = j;
}
if (next[n-1] > 0 && n % (n - next[n-1]) == 0) { return true; }// 注意判断条件，next[n-1]>0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// 核心函数
// 输出栈为空时才将输入栈元素弹出压入输出栈
// 因此中途入队的元素不会影响出队顺序，每个元素都只翻转一次
private void dump() {
    if (stackout.isEmpty()) {
        while (!stackin.isEmpty()) {
            stackout.push(stackin.pop());
        }
    }
}

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

public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    if (n == 0 || k == 0) { return new int[0]; }
    int[] res = new int[n - k + 1];
    Deque<Integer> queue = new ArrayDeque<>();

    for (int i = 0; i < nums.length; i++) {
        while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]) {
            queue.pollLast();
        }// 出队所有比当前位置小的，因此队列中必为降序

        queue.offerLast(i);// 入队
        if (queue.peekFirst() <= i - k) {// 判断队首是否出窗口范围（用<=）
            queue.pollFirst();
        }

        if (i >= k - 1) {
            res[i - k + 1] = nums[queue.peekFirst()];
        }
    }
    return res;
}

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

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }

    // 最小堆：按出现次数排序
    Queue<Map.Entry<Integer, Integer>> pq =
            new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());

    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {// entrySet() 遍历键值对
        pq.offer(entry);
        if (pq.size() > k) {// 个数超过k，弹出优先级最高（最小）元素
            pq.poll();
        }
    }

    int[] result = new int[k];
    for (int i = 0; i < k; i++) {
        result[i] = pq.poll().getKey();
    }
    return result;
}

 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

递归中序遍历，前、后序即改变result.add位置
void dfs(TreeNode root, List<Integer> list) {
    if (root == null) {
        return;
    }
    
    dfs(root.left, result);// 左子树
    result.add(root.val);// 代码处理部分
    dfs(root.right, result);// 右子树
}
层序遍历
// 也可以是Queue<TreeNode> queue = new LinkedList<>(); Deque支持更多操作，性能更好
Deque<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
    int size = queue.size();// size为当前层节点数，避免处理下一层节点
    List<Integer> level = new ArrayList<>();
    for (int i = 0; i < size; i++) {
        TreeNode node = queue.poll();
        level.add(node.val);
        if (node.left != null) { queue.offer(node.left); }
        if (node.right != null) { queue.offer(node.right); }
    }
    result.add(level);
}
return result;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

Stack<TreeNode> stack = new Stack<>();
stack.push(root);

while (!stack.isEmpty()) {
    TreeNode node = stack.pop();
    if (node != null) {
        // 示例：中序
        if (node.right != null) stack.push(node.right); // 右
        stack.push(node); // 中
        stack.push(null); // 标记位
        if (node.left != null) stack.push(node.left);   // 左
    } else {
        // 遇到null，说明下一个节点是需要被处理的根节点
        result.add(stack.pop().val);
    }
}

 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

private int maxDepth = 0;
private int leftmostValue;
public int findBottomLeftValue(TreeNode root) {
    dfs(root, 1);
    return leftmostValue;
}
private void dfs(TreeNode node, int depth) {
    if (node == null) { return; }
    if (depth > maxDepth) {
        maxDepth = depth;
        leftmostValue = node.val;
    }
    dfs(node.left, depth + 1);// 先访问左子节点，该函数会更新maxDepth，因此访问同一层右子节点时不会覆盖结果。
    dfs(node.right, depth + 1);
}


方法2：层序遍历
调换左右节点入队顺序，每层最后一个被弹出的节点为最左节点，就无需额外的判断了。

public int findBottomLeftValue(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        root = queue.poll();
        if (root.right != null) queue.offer(root.right);
        if (root.left != null) queue.offer(root.left);
    }
    return root.val; // 最后一个被弹出的就是最左下角的
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// 层序遍历：当遇到第一个叶子节点时，当前层数即为最小深度。
while (!queue.isEmpty()){
    int size = queue.size();
    depth++;
    TreeNode cur = null;
    for (int i = 0; i < size; i++) {
        cur = queue.poll();
        if (cur.left == null && cur.right == null){ //直接返回最小深度
            return depth;
        }
        if (cur.left != null) queue.offer(cur.left);
        if (cur.right != null) queue.offer(cur.right);
    }
}
// 递归
public int minDepth(TreeNode root) {
    if (root == null) return 0;
    int m1 = minDepth(root.left);
    int m2 = minDepth(root.right);
    // 注意：如果有一个子树为空，判断语句返回0，会导致结果错误，需要特殊处理。
    // 如果有一个子树为空，返回 m1 + m2 + 1 （m1或m2有一个为0）
    // 如果都不为空，返回 min(m1, m2) + 1
    return (root.left == null || root.right == null) ? (m1 + m2 + 1) : Math.min(m1, m2) + 1;
}

1
2

curSum - oldSum = targetSum
oldSum = curSum - targetSum

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

public int pathSum(TreeNode root, int targetSum) {
    Map<Long, Integer> map = new HashMap<>();
    map.put(0L, 1);
    return dfs(root, 0L, targetSum, map);
}

private int dfs(TreeNode node, long curSum, int targetSum, Map<Long, Integer> map) {
    if (node == null) return 0;

    curSum += node.val;
    int count = map.getOrDefault(curSum - targetSum, 0);

    map.put(curSum, map.getOrDefault(curSum, 0) + 1);
    count += dfs(node.left, curSum, targetSum, map);
    count += dfs(node.right, curSum, targetSum, map);
    map.put(curSum, map.get(curSum) - 1);

    return count;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

private int ans = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
    dfs(root);
    return ans;
}

private int dfs(TreeNode node) {
    if (node == null) return 0;

    int left = Math.max(0, dfs(node.left));
    int right = Math.max(0, dfs(node.right));

    ans = Math.max(ans, node.val + left + right);// 身份2

    return node.val + Math.max(left, right);// 身份1
}

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

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        constructPaths(root,"",res);
        return res;
    }

    private void constructPaths(TreeNode node, String path, List<String> res) {
        if (node!=null) {
            path += Integer.toString(node.val);
            if (node.left == null && node.right == null) {
                res.add(path);
            } else {
                path+="->";
                constructPaths(node.left,path,res);
                constructPaths(node.right,path,res);
            }
        }
    }
}

1
2
3
4
5
6
7
8
9

public boolean isValidBST(TreeNode root) {
    return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);// 注意这里Long大写L
}

private boolean isValidBST(TreeNode node, long min, long max) {
    if (node == null) return true;
    if (node.val <= min || node.val >= max) return false;
    return isValidBST(node.left, min, node.val) && isValidBST(node.right, node.val, max);
}

1
2
3
4
5
6
7
8
9

public boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    return dfs(root.left, root.right);
}
private boolean dfs(TreeNode left, TreeNode right) {
    if (left == null && right == null) return true;
    if (left == null || right == null || left.val != right.val) return false;
    return dfs(left.left, right.right) && dfs(left.right, right.left);
}

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

class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root)!=-1;
    }

    private int height(TreeNode node) {
        if (node == null) {return 0;}// 递归出口
        
        // 获取左右子树高度并剪枝
        int leftHeight = height(node.left);
        if (leftHeight==-1) {return -1;}// 剪枝
        
        int rightHeight = height(node.right);
        if (rightHeight==-1) {return -1;}// 剪枝
        
        // 对信息进行处理
        if (Math.abs(leftHeight-rightHeight) > 1) {return -1;}
        
        // 返回当前节点高度
        return Math.max(leftHeight,rightHeight)+1;
    }
}

 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

// 1. 递归，不适用于任意形态的二叉树
public Node connect(Node root) {
    if (root == null) { return null; }
    Node leftmost = root;
    while (leftmost.left != null) {
        Node head = leftmost;
        while (head != null) {
            head.left.next = head.right;// 同一父节点的左右子节点连接
            if (head.next != null) {
                head.right.next = head.next.left;// 不同父节点的子节点连接
            }
            head = head.next;// 同一层的下一个父节点
        }
        leftmost = leftmost.left;// 下一层的最左节点
    }
    return root;
}
// 2. 层序遍历，都适用
public Node connect(Node root) {
    if (root == null) return null;
    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        Node prev = null;
        
        for (int i = 0; i < size; i++) {
            Node node = queue.poll();
            if (prev != null) prev.next = node;
            prev = node;
            
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
    return root;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) {return root;}

    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    
    // 对于left/right的四种情况判断（有有、有无、无有、无无）
    if(left == null) return right;
    if(right == null) return left;
    return root;// 两个都非空
}

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

int ans=0;

public int minCameraCover(TreeNode root) {
    if (dfs(root) == 0) {ans++;}
    return ans;
}

// 定义三个状态：0：该节点未被覆盖
// 1：安装了摄像头；2：已被覆盖，但没摄像头
private int dfs(TreeNode node) {
    if (node == null) {return 2;}

    int left =dfs(node.left);
    int right = dfs(node.right);

    if (left == 0 || right == 0) {// 有一个没有就需要安装
        ans++;
        return 1;
    }
    if (left == 1 || right == 1) {return 2;}// 有子节点装了，被覆盖到

    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// 父级预判：通过root.left判断是左叶子。
public int sumOfLeftLeaves(TreeNode root) {
    if (root == null) return 0;
    int sum = 0;
    if (root.left != null && root.left.left == null && root.left.right == null) {
        sum += root.left.val;
    }
    return sum + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
}

// 叶子节点作为递归出口：添加标记
public int sumOfLeftLeaves(TreeNode root) {
    return dfs(root, false); // 根节点不是任何人的左孩子
}

private int dfs(TreeNode node, boolean isLeft) {
    if (node == null) return 0;
    
    if (node.left == null && node.right == null) {
        return isLeft ? node.val : 0;
    }
    // 左true 右false
    return dfs(node.left, true) + dfs(node.right, false);
}

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

public TreeNode constructMaximumBinaryTree(int[] nums) {
    return build(nums,0,nums.length-1);
}

private TreeNode build(int[] nums, int left, int right) {
    if (left>right) {return null;}// 注意等于号

    int maxIndex = left;
    for (int i = left+1; i <= right; i++) {
        if (nums[i] > nums[maxIndex]) {
            maxIndex = i;
        }
    }

    TreeNode root = new TreeNode(nums[maxIndex]);
    // 注意向下传递的左右边界
    root.left = build(nums,left,maxIndex-1);
    root.right = build(nums,maxIndex+1,right);

    return root;
}

 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