一、算法框架
二、数据结构
三、数学运算技巧
四、字符串
- 4.1 最长回文子串
五、双指针
- 5.1 盛最多水的容器
六、二叉树
七、链表
八、前缀和
九、差分数组
end、clutter解题思路

一、算法框架

1.1 DFS框架(回溯算法)

result = [] 
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

1.2 BFS框架

// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
    LinkedList<Node> q = new LinkedList<>(); // 核心数据结构
    Set<Node> visited = new HashSet<>(); // 避免走回头路

    q.addLast(start); // 将起点加入队列
    visited.add(start);
    int step = 0; // 记录扩散的步数

    while (!q.isEmpty()) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            /* 划重点：这里判断是否到达终点 */
            if (cur == target) return step;
            /* 将 cur 的相邻节点加入队列 */
            for (Node x : cur.adj())
                if (!visited.contains(x)) {
                    q.addLast(x);
                    visited.add(x);
                }
        }
        /* 划重点：更新步数在这里 */
        step++;
    }
    return step;
}

1.3 滑动窗口

public String slidingWindow(String s, String t) {
    MyMap<Character> window = new MyMap<>(), need = new MyMap<>();

    //初始化t，加快访问速度
    for (char c : t.toCharArray()) need.add(c);

    int left = 0, right = 0;
    int valid = 0;
    int start = 0, ans = Integer.MAX_VALUE;
    while (right < s.length()) {
        char c = s.charAt(right); //c是将移入窗口的字符
        right++; //窗口右移

        //todo ... 进行窗口内右移后的一系列更新的代码

        System.out.printf("win:[%d,%d)", left, right); //debug

        //判断左侧窗口是否要收缩
        while (window need shrink) {
            char d = s.charAt(left); //d是移除窗口的字符
            left++; //左移窗口
            
            //todo ... 进行窗口内左移后的一系列更新的代码
        }
    }
}

public class MyMap<K> extends HashMap<K, Integer> {
    public void add(K key) {
        this.put(key, this.getOrDefault(key, 0) + 1);
    }

    public void sub(K key) {
        this.put(key, this.getOrDefault(key, 0) - 1);
    }
}

1.4 状态机(股票买卖)

https://labuladong.gitbook.io/algo/bi-du-wen-zhang/tuan-mie-gu-piao-wen-ti

状态转移方程:
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
              max(   选择 rest  ,             选择 sell      )

# 解释：今天我没有持有股票，有两种可能：
# 要么是我昨天就没有持有，然后今天选择 rest，所以我今天还是没有持有；
# 要么是我昨天持有股票，但是今天我 sell 了，所以我今天没有持有股票了。

dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
              max(   选择 rest  ,           选择 buy         )

# 解释：今天我持有着股票，有两种可能：
# 要么我昨天就持有着股票，然后今天选择 rest，所以我今天还持有着股票；
# 要么我昨天本没有持有，但今天我选择 buy，所以今天我就持有股票了。

--------------------------------------------------------------
base case:
dp[0][k][0] = 0 # 第一天，没有买股票，为0
dp[0][k][1] = -price[0] # 第一天，买了股票，只能买第一个股票
dp[i][0][0] = 0 # k = 0 意味着根本不允许交易，这时候利润当然是 0
dp[i][0][1] = -infinity # 不允许交易的情况下，是不可能持有股票的，用负无穷表示这种不可能。

总结

base case：
dp[0][k][0] = 0 # 第一天，没有买股票，为0
dp[0][k][1] = -price[0] # 第一天，买了股票，只能买第一个股票
dp[i][0][0] = 0 # k = 0 意味着根本不允许交易，这时候利润当然是 0
dp[i][0][1] = -infinity # 不允许交易的情况下，是不可能持有股票的，用负无穷表示这种不可能。

状态转移方程：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])

1.5 二分算法

int binary_search(int[] nums, int target) {
    int left = 0, right = nums.length - 1; 
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1; 
        } else if(nums[mid] == target) {
            // 直接返回
            return mid;
        }
    }
    // 直接返回
    return -1;
}

int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定左侧边界
            right = mid - 1;
        }
    }
    // 最后要检查 left 越界的情况
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}

int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定右侧边界
            left = mid + 1;
        }
    }
    // 最后要检查 right 越界的情况
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}

寻找旋转排序数组中的最小值

输入：nums = [3,4,5,1,2]
输出：1

输入：nums = [4,5,6,7,0,1,2]
输出：0

输入：nums = [11,13,15,17]
输出：11

思路：

1、两种情况，nums[mid] > nums[right]在左半边，num[mid]<=nums[right]在右半边

2、第一种，mid必不符合，所以left = mid + 1; 第二种，mid可能是最小值，所以right = mid。

3、这种情形，需left < right条件才能不死循环。

public int findMin(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return nums[left];
}

二、数据结构

2.1 并查集

https://blog.skyemperor.top/archives/%E5%B9%B6%E6%9F%A5%E9%9B%86

class UnionFind {
    public int count; //连通分量个数
    public HashMap<Integer, Integer> parent; //储存每个节点的父节点
    public HashMap<Integer, Integer> size; //记录每棵树的重量(节点个数)

    //初始化构造方法
    public UnionFind(int n) {
        this.count = n;
        this.parent = new HashMap<>();
        this.size = new HashMap<>();
        for (int i = 0; i < n; i++) {
            parent.put(i, i);
            size.put(i, 1);
        }
    }

    /* 将p和q连接 */
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) return; //已连通

        //小树接到大树下面，更为平衡
        if (size.get(rootP) > size.get(rootQ)) {
            size.put(rootP, size.get(rootP) + size.get(rootQ));
            parent.put(rootQ, rootP);
        } else {
            size.put(rootQ, size.get(rootP) + size.get(rootQ));
            parent.put(rootP, rootQ);
        }
        count--;
    }

    /* 判断p和q是否连通 */
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    /* 找到x的根节点 */
    private int find(int x) {
        while (parent.get(x) != x) {
            //路径压缩
            parent.put(x, parent.get(parent.get(x)));
            x = parent.get(x);
        }
        return x;
    }
}

2.2 LRU

public class LRUCache {
    int capacity;
    LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    public Integer get(Integer key) {
        if (!map.containsValue(key)) return null;
        //将key变为最近使用
        makeRecently(key);
        return map.get(key);
    }

    public void put(Integer key, Integer val) {
        if (map.containsValue(key)) {
            map.put(key, val);
            makeRecently(key); //设为最近常用
            return;
        }

        if (map.size() >= this.capacity) {
            //链表头部即为最久未使用的key
            Integer head = map.keySet().iterator().next();
            map.remove(head); //移除最老的key
        }
        map.put(key, val); //将新的key添加到链表尾部
    }

    private void makeRecently(Integer key) {
        Integer val = map.get(key);
        //删除key，重新插入到队尾
        map.remove(key);
        map.put(key, val);
    }
}

2.3 单调栈

基本框架

public int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Stack<Integer> s = new Stack<>();

    for (int i = n - 1; i >= 0; i--) {   //可以根据情况选择 从后往前 或 从前往后
        while (!s.empty() && s.peek() <= nums[i]) s.pop();  //可以根据情况选择 大于 或 小于
        res[i] = s.empty() ? -1 : s.peek();
        s.push(nums[i]);
    }
    return res;
}

变种：循环数组

public int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Stack<Integer> s = new Stack<>();

    for (int i = 2 * n - 1; i >= 0; i--) {   //可以根据情况选择 从后往前 或 从前往后
        while (!s.empty() && s.peek() <= nums[i % n]) s.pop();  //可以根据情况选择 大于 或 小于
        res[i % n] = s.empty() ? -1 : s.peek();
        s.push(nums[i % n]);
    }
    return res;
}

2.4 单调队列

/* 单调队列的实现 */
class MonotonicQueue {
    LinkedList<Integer> q = new LinkedList<>();
    public void push(int n) {
        // 将小于 n 的元素全部删除
        while (!q.isEmpty() && q.getLast() < n) {
            q.pollLast();
        }
        // 然后将 n 加入尾部
        q.addLast(n);
    }

    public int max() {
        return q.getFirst();
    }

    public void pop(int n) {
        if (n == q.getFirst()) {
            q.pollFirst();
        }
    }
}

三、数学运算技巧

2.1 位操作

利用或操作 | 和空格将英文字符转换为小写

('a' | ' ') = 'a'
('A' | ' ') = 'a'

利用与操作 & 和下划线将英文字符转换为大写

('b' & '_') = 'B'
('B' & '_') = 'B'

利用异或操作 ^ 和空格进行英文字符大小写互换

('d' ^ ' ') = 'D'
('D' ^ ' ') = 'd'

判断两个数是否异号

int x = -1, y = 2;
boolean f = ((x ^ y) < 0); // true
int x = 3, y = 2;
boolean f = ((x ^ y) < 0); // false

不用临时变量交换两个数

int a = 1, b = 2;
a ^= b;
b ^= a;
a ^= b;
// 现在 a = 2, b = 1

n&(n-1) 消除数字 n 的二进制表示中的最后一个 1

其核心逻辑就是，n - 1 一定可以消除最后一个 1，同时把其后的 0 都变成 1，这样再和 n 做一次 & 运算，就可以仅仅把最后一个 1 变成 0 了。

判断一个数是不是 2 的指数

一个数如果是 2 的指数，那么它的二进制表示一定只含有一个 1：

2^0 = 1 = 0b0001
2^1 = 2 = 0b0010
2^2 = 4 = 0b0100

如果使用 n&(n-1) 的技巧就很简单了（注意运算符优先级，括号不可以省略）：

bool isPowerOfTwo(int n) {
    if (n <= 0) return false;
    return (n & (n - 1)) == 0;
}

查找数组只出现一次的数字

可以运用异或运算的性质：一个数和它本身做异或运算结果为 0，即 a ^ a = 0；一个数和 0 做异或运算的结果为它本身，即 a ^ 0 = a。

对于这道题目，我们只要把所有数字进行异或，成对儿的数字就会变成 0，落单的数字和 0 做异或还是它本身，所以最后异或的结果就是只出现一次的元素：

int singleNumber(vector<int>& nums) {
    int res = 0;
    for (int n : nums) {
        res ^= n;
    }
    return res;
}

2.2 阶乘操作

输入一个非负整数 n，计算阶乘n!的结果末尾有几个 0

问题转化为：n! 最多可以分解出多少个因子 2 和 5？

-> n! 最多可以分解出多少个因子 5？

int trailingZeroes(int n) {
    int res = 0;
    long divisor = 5;
    while (divisor <= n) {
        res += n / divisor;
        divisor *= 5;
    }
    return res;
}

给你一个非负整数 K，有多少个 n，使得 n! 结果末尾有 K 个 0

搜索有多少个 n 满足 trailingZeroes(n) == K，其实就是在问，满足条件的 n 最小是多少，最大是多少，最大值和最小值一减，就可以算出来有多少个 n 满足条件了，对吧？那不就是二分查找「搜索左侧边界」和「搜索右侧边界」这两个事儿嘛？

/* 主函数 */
int preimageSizeFZF(int K) {
    // 左边界和右边界之差 + 1 就是答案
    return right_bound(K) - left_bound(K) + 1;
}

/* 搜索 trailingZeroes(n) == K 的左侧边界 */
long left_bound(int target) {
    long lo = 0, hi = LONG_MAX;
    while (lo < hi) {
        long mid = lo + (hi - lo) / 2;
        if (trailingZeroes(mid) < target) {
            lo = mid + 1;
        } else if (trailingZeroes(mid) > target) {
            hi = mid;
        } else {
            hi = mid;
        }
    }

    return lo;
}

/* 搜索 trailingZeroes(n) == K 的右侧边界 */
long right_bound(int target) {
    long lo = 0, hi = LONG_MAX;
    while (lo < hi) {
        long mid = lo + (hi - lo) / 2;
        if (trailingZeroes(mid) < target) {
            lo = mid + 1;
        } else if (trailingZeroes(mid) > target) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }

    return lo - 1;
}

2.3 素数个数

计算从2~n素数的个数

int countPrimes(int n) {
    boolean[] isPrim = new boolean[n];
    Arrays.fill(isPrim, true);
    for (int i = 2; i * i < n; i++) 
        if (isPrim[i]) 
            for (int j = i * i; j < n; j += i) 
                isPrim[j] = false;

    int count = 0;
    for (int i = 2; i < n; i++)
        if (isPrim[i]) count++;

    return count;
}

2.4 快速幂 & 慢速乘

快速求幂，防止爆炸%p

利用十进制数字 n 的二进制表示，可对快速幂进行数学化解释。

a ^ n % p

long poww(long a, long n, long p) {
    long ans = 1;
    while (n > 0) {
        if ((n & 1) != 0) ans = ans * a % p;//若不取模就去掉p
        a = a * a % p;
        n >>= 1;
    }
    return ans;
}

慢速乘

对很大的数取模时，这时计算机的long long进行乘法就会爆掉
将a 或 b 转化为二进制
a*b % p

ll mul(ll a, ll b, ll p) {
    ll ans = 0;
    while (b) {
        if (b & 1) ans += a, ans %= p;
        a *= 2, a %= p;
        b >>= 1;
    }
    return ans;
}

四、字符串

4.1 最长回文子串

String res = "";

public String longestPalindrome(String s) {
    if (s == null || s.length() < 1) return "";

    for (int i = 0; i < s.length(); i++) {
        expandAroundCenter(s, i, i);
        expandAroundCenter(s, i, i + 1);
    }

    return res;
}

public void expandAroundCenter(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    //恢复left、right
    left++;
    right--;
    if (right - left + 1 > res.length()) {
        res = s.substring(left, right + 1);
    }
}

五、双指针

5.1 盛最多水的容器

在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽底边宽度 −1 变短：

若向内移动短板，水槽的短板 min(h[i], h[j]) 可能变大，因此下个水槽的面积可能增大。
若向内移动长板，水槽的短板 min(h[i], h[j]) 不变或变小，因此下个水槽的面积一定变小。

因此，初始化双指针分列水槽左右两端，循环每轮将短板向内移动一格，并更新面积最大值，直到两指针相遇时跳出；即可获得最大面积。

public int maxArea(int[] height) {
    int res = 0;
    int left = 0, right = height.length - 1;
    while (left < right) {
        res = height[left] < height[right] ?
                Math.max(res, (right - left) * height[left++]) :
                Math.max(res, (right - left) * height[right--]);
    }
    return res;
}

六、二叉树

6.1 遍历

6.1.1 前序遍历

private void preorder(Node<E> node, Visitor<E> visitor) {
	if (node == null) return;
	
	visitor.stop = visitor.visit(node.element);
	preorder(node.left);
	preorder(node.right);
}

public List<Integer> preorderTraversal(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    LinkedList<Integer> ans = new LinkedList<>();
    if (root == null) return ans;
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        ans.add(node.val);
        if (node.right != null)
            stack.add(node.right);
        if (node.left != null)
            stack.add(node.left);
    }
    return ans;
}

6.1.2 中序遍历

ArrayList<Integer> res = new ArrayList<>();
private void inorder(TreeNode node) {
    if (node == null) return;

    inorder(node.left);
    res.add(node.val);
    inorder(node.right);
}

public List<Integer> inorderTraversal(TreeNode root) {
    LinkedList<Integer> ans = new LinkedList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while (cur != null || !stack.empty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        ans.add(cur.val);
        cur = cur.right;
    }
    return ans;
}

6.1.3 后序遍历

private void postorder(TreeNode node) {
    if (node == null) return;

    postorder(node.left);
    postorder(node.right);
    res.add(node.val);
}

//前序遍历反过来入res
public List<Integer> postorderTraversal(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    LinkedList<Integer> ans = new LinkedList<>();
    if (root == null) return ans;
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        ans.addFirst(node.val);
        if (node.left != null)
            stack.add(node.left);
        if (node.right != null)
            stack.add(node.right);
    }
    return ans;
}

6.1.3 层序遍历

public void levelOrder(TreeNode root) {
    if (root == null) return;
    LinkedList<TreeNode> queue = new LinkedList<>();
    queue.addLast(root);

    while (!queue.isEmpty()) {
        TreeNode node = queue.pollFirst();
        if (node.left != null)
            queue.addLast(node.left);
        if (node.right != null)
            queue.addLast(node.right);
    }
}

6.2 二叉树中的最大路径和

递归。方法返回值为以该节点为根的且过该点的最大路径长度。在方法中和res比较内部路径(node.val+dfs(left)+dfs(right))的大小

int res;

public int maxPathSum(TreeNode root) {
    res = Integer.MIN_VALUE;
    dfs(root);
    return res;
}

private int dfs(TreeNode root) {
    if (root == null) return 0;
    int left = dfs(root.left);
    int right = dfs(root.right);

    //内部路径大小
    res = Math.max(root.val + left + right, res);

    int tres = Math.max(root.val, root.val + Math.max(left, right));
    return tres < 0 ? 0 : tres;
}

6.3 路径总和 III

数学归纳法。假设我们已知一棵二叉树的路径数目，反推其父节点的结果。

有两种情况。

路径不经过该根节点，则递归该方法，targetSum不变；
路径经过该根节点，需将targetSum设为targetSum-root.val，且其子节点必须连续才能成为路径。

public int pathSum(TreeNode root, int targetSum) {
    if (root == null) return 0;
    int res = 0;

    if (root.val == targetSum) res += 1;

    if (root.left != null) {
        res += pathSum(root.left, targetSum) + f(root.left, targetSum - root.val);
    }

    if (root.right != null) {
        res += pathSum(root.right, targetSum) + f(root.right, targetSum - root.val);
    }

    return res;
}

private int f(TreeNode node, int target) {
    if (node == null) return 0;
    return (node.val == target ? 1 : 0)
            + f(node.left, target - node.val)
            + f(node.right, target - node.val);
}

6.4 前序与中序遍历构造二叉树

private Map<Integer, Integer> indexMap;
private int[] preorder, inorder;

public TreeNode buildTree(int[] preorder, int[] inorder) {
    this.preorder = preorder;
    this.inorder = inorder;
    int n = preorder.length;
    // 构造哈希映射，帮助我们快速定位根节点
    indexMap = new HashMap<>();
    for (int i = 0; i < n; i++) {
        indexMap.put(inorder[i], i);
    }

    return buildTreeHelp(0, n - 1, 0, n - 1);
}

public TreeNode buildTreeHelp(int preStart, int preEnd, int inStart, int inEnd) {
    if (preStart > preEnd) return null;

    int preRoot = preStart;
    int inRoot = indexMap.get(preorder[preStart]);
    int leftSize = inRoot - inStart;

    TreeNode node = new TreeNode(preorder[preStart]);
    node.left = buildTreeHelp(preStart + 1, preStart + leftSize, inStart, inRoot - 1);
    node.right = buildTreeHelp(preStart + leftSize + 1, preEnd, inRoot + 1, inEnd);
    
    return node;
}

七、链表

7.1 删除倒数第K个节点

快慢指针，快指针比慢指针快K个。

public void deleteKndNode(ListNode node, int k) {
    ListNode slow = node, fast = node;
    for (int i = 1; i <= k + 1; i++) {
        fast = fast.next;
    }
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
}

7.2 判断环形链表

快慢指针，如果是环形链表，那么快慢指针一定会相交。

public ListNode hasLoop(ListNode head) {
    if (head == null || head.next == null) return null;

    ListNode slow = head;
    ListNode fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow == fast) return slow;
    }
    return null;
}

//定位环入口，首先找到相遇的点，然后头结点和相遇点同时移动，再次相遇是就是相交点
public ListNode getIntersectionNode(ListNode node) {
    ListNode p1 = hasLoop(node);
    if (p1 == null) return null;

    ListNode p2 = node;
    while (p1 != p2) {
        p1 = p1.next;
        p2 = p2.next;
    }
    return p1;
}

7.3 翻转链表

// 递归
public ListNode reverse(ListNode node) {
    if (node == null || node.next == null) return node;

    ListNode newHead = reverse(node.next);
    node.next.next = node;
    node.next = null;
    return newHead;
}

//非递归
public ListNode reverse2(ListNode node) {
    if (node == null || node.next == null) return node;

    ListNode newHead = null, cur = node;
    while (cur != null) {
        ListNode tmp = cur.next;
        cur.next = newHead;
        newHead = cur;
        cur = tmp;
    }
    return newHead;
}

7.4 相交链表

消除两个链表的长度差

指针 pA 指向 A 链表，指针 pB 指向 B 链表，依次往后遍历
如果 pA 到了末尾，则 pA = headB 继续遍历
如果 pB 到了末尾，则 pB = headA 继续遍历

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode a = headA, b = headB;
    while (a != b) {
        a = a == null ? headB : a.next;
        b = b == null ? headA : b.next;
    }
    return a;
}

7.5 链表划分

给定一个单链表和数值x，划分链表使得所有小于x的节点排在大于等于x的节点之前。

只需维护两个链表small 和large 即可，small 链表按顺序存储所有小于 x 的节点，large 链表按顺序存储所有大于等于 x 的节点。遍历完原链表后，我们只要将 small 链表尾节点指向 large 链表的头节点即能完成对链表的分隔。

public ListNode partition(ListNode head, int x) {
    ListNode small = new ListNode(0);
    ListNode smallHead = small;
    ListNode large = new ListNode(0);
    ListNode largeHead = large;
    while (head != null) {
        if (head.val < x) {
            small.next = head;
            small = small.next;
        } else {
            large.next = head;
            large = large.next;
        }
        head = head.next;
    }
    large.next = null;
    small.next = largeHead.next;
    return smallHead.next;
}

7.6 归并排序链表

归并排序，递归循环。

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null)
        return head;
    ListNode fast = head.next, slow = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode tmp = slow.next;
    slow.next = null;
    ListNode left = sortList(head);
    ListNode right = sortList(tmp);
    ListNode h = new ListNode(0);
    ListNode res = h;
    while (left != null && right != null) {
        if (left.val < right.val) {
            h.next = left;
            left = left.next;
        } else {
            h.next = right;
            right = right.next;
        }
        h = h.next;
    }
    h.next = left != null ? left : right;
    return res.next;
}

八、前缀和

传送https://blog.skyemperor.top/archives/%E5%89%8D%E7%BC%80%E5%92%8C

九、差分数组

假设你有⼀个⻓度为 n 的数组，初始情况下所有的数字均为 0，你将会被给出 k 个更新的操作。其中，每个操作会被表示为⼀个三元组：[startIndex, endIndex, inc]，你需要将⼦数组 A[startIndex ... endIndex]（包括 startIndex 和 endIndex）增加 inc。请你返回 k 次操作后的数组。

class Difference {
    // 差分数组
    private int[] diff;

    public Difference(int[] nums) {
        assert nums.length > 0;
        diff = new int[nums.length];
        // 构造差分数组
        diff[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
    }

    /* 给闭区间 [i,j] 增加 val（可以是负数）*/
    public void increment(int i, int j, int val) {
        diff[i] += val;
        if (j + 1 < diff.length) {
            diff[j + 1] -= val;
        }
    }

    public int[] result() {
        int[] res = new int[diff.length];
        // 根据差分数组构造结果数组
        res[0] = diff[0];
        for (int i = 1; i < diff.length; i++) {
            res[i] = res[i - 1] + diff[i];
        }
        return res;
    }
}

end、clutter解题思路

接雨水

每一列的水量即Math.min(左侧最高的墙，右侧最高的墙) - 当前列的墙。

使用两个数组保存每一列左侧最高的墙和右侧最高的墙。

public int trap(int[] height) {
    if (height.length <= 1) return 0;

    int n = height.length - 1;

    int[] maxLeft = new int[height.length];
    int[] maxRight = new int[height.length];

    maxLeft[0] = height[0];
    for (int i = 1; i < height.length; i++) {
        maxLeft[i] = Math.max(maxLeft[i - 1], height[i]);
    }
    maxRight[n] = height[n];
    for (int i = n - 1; i >= 0; i--) {
        maxRight[i] = Math.max(height[i], maxRight[i + 1]);
    }

    int res = 0;
    for (int i = 1; i < n; i++) {
        res += Math.min(maxLeft[i], maxRight[i]) - height[i];
    }

    return res;
}

旋转图像

先水平翻转，再按对角线翻转

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        // 水平翻转
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < n; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - i - 1][j];
                matrix[n - i - 1][j] = temp;
            }
        }
        // 主对角线翻转
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }
}

柱状图中最大的矩形

求出每一列“以此列为最小值扩展的最大矩形面积”，即需求出该列左边和右边小于该列的最大值，使用两个单调递增栈

public int largestRectangleArea(int[] heights) {
    int res = 0;

    int n = heights.length;
    int[] leftMin = new int[n];
    int[] rightMin = new int[n];
    Stack<Integer> lStack = new Stack<>();
    Stack<Integer> rStack = new Stack<>();

    for (int i = 0; i < n; i++) {
        while (!lStack.isEmpty() && heights[lStack.peek()] >= heights[i]) lStack.pop();
        int minIdx = lStack.isEmpty() ? -1 : lStack.peek();
        lStack.push(i);
        leftMin[i] = minIdx + 1;
    }

    for (int i = n - 1; i >= 0; i--) {
        while (!rStack.isEmpty() && heights[rStack.peek()] >= heights[i]) rStack.pop();
        int minIdx = rStack.isEmpty() ? n : rStack.peek();
        rStack.push(i);
        rightMin[i] = minIdx - 1;
    }

    for (int i = 0; i < n; i++) {
        res = Math.max(res, (rightMin[i] - leftMin[i] + 1) * heights[i]);
    }

    return res;
}

最大矩形

利用上一题【柱状图中最大的矩形】，将每一层看做一个height[]，调用上一题的函数。

验证二叉搜索树

right节点不仅需要大于父节点，而且要大于祖先节点；left同理。

因此使用一个函数，标明节点应处的范围。

public boolean isValidBST(TreeNode root) {
    return f(root, null, null);
}

private boolean f(TreeNode node, Integer maxVal, Integer minVal) {
    if (node == null) return true;

    if (maxVal != null && node.val >= maxVal) return false;
    if (minVal != null && node.val <= minVal) return false;

    boolean flag = true;
    if (node.right != null) {
        if (node.right.val > node.val) flag &= f(node.right, maxVal, node.val);
        else return false;
    }

    if (node.left != null) {
        if (node.left.val < node.val) flag &= f(node.left, node.val, minVal);
        else return false;
    }

    return flag;
}

最长连续序列

将数组数字插入到哈希表，每次随便拿出一个，删除其连续的数字(左边连续的和右边连续的)，直至找不到连续的，记录删除的长度，可以找到最长连续序列。

public int longestConsecutive(int[] nums) {
    HashSet<Integer> set = new HashSet<>();
    for (int num : nums) set.add(num);

    int res = 0;
    while (!set.isEmpty()) {
        Integer now = set.iterator().next();
        set.remove(now);
        int left = now - 1;
        while (set.contains(left)) {
            set.remove(left);
            left--;
        }
        int right = now + 1;
        while (set.contains(right)) {
            set.remove(right);
            right++;
        }
        res = Math.max(res, right - left - 1);
    }
    return res;
}

单词拆分

动态规划

dp[i] 为字符串前i个字符s[0..i-1]是否能被空格拆分

dp[i]=dp[j] && check(s[j..i−1])

public boolean wordBreak(String s, List<String> wordDict) {
    int n = s.length();
    boolean[] dp = new boolean[n + 1];
    HashSet<String> set = new HashSet<>(wordDict);

    dp[0] = true;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            dp[i] = dp[j] & set.contains(s.substring(j, i));
            if (dp[i]) break;
        }
    }

    return dp[n];
}

dfs

定义方法返回值为从i开始的字符串能否被拆分

HashSet<String> set;
String s;

public boolean wordBreak(String s, List<String> wordDict) {
    set = new HashSet<>(wordDict);
    this.s = s;

    return dfs(0);
}

HashMap<Integer, Boolean> book = new HashMap<>();

private boolean dfs(int start) {
    if (book.containsKey(start))
        return book.get(start);

    boolean flag = false;
    if (start == s.length()) flag = true;
    for (int i = start + 1; i <= s.length(); i++) {
        if (set.contains(s.substring(start, i)) && dfs(i)) {
            flag = true;
            break;
        }
    }

    book.put(start, flag);
    return flag;
}

众数(摩尔投票法)

摩尔投票法，解决的问题是如何在任意多的候选人中，选出票数超过一半的那个人。注意，是超出一半票数的那个人。

假设投票是这样的，[A, C, A, A, B]，ABC 是指三个候选人。

第一张票与第二张票进行对坑，如果票不同则互相抵消掉；

接着第三票与第四票进行对坑，如果票相同，则增加这个候选人的可抵消票数；

这个候选人拿着可抵消票数与第五张票对坑，如果票不同，则互相抵消掉，即候选人的可抵消票数 -1。

如果至多选一个代表，那他的票数至少要超过一半（⌊ 1/2 ⌋）的票数；

如果至多选两个代表，那他们的票数至少要超过 ⌊ 1/3 ⌋ 的票数；

如果至多选m个代表，那他们的票数至少要超过 ⌊ 1/(m+1) ⌋ 的票数。

所以以后碰到这样的问题，而且要求达到线性的时间复杂度以及常量级的空间复杂度，直接套上摩尔投票法。

多数元素

public int majorityElement(int[] nums) {
    int res = nums[0];
    int cnt = 0;
    for (int num : nums) {
        if (cnt > 0 && res == num) {
            cnt++;
        } else if (cnt == 0) {
            res = num;
            cnt = 1;
        } else {
            cnt--;
        }
    }
    return res;
}

求众数 II

public List<Integer> majorityElement(int[] nums) {
    List<Integer> res = new ArrayList<>();

    int num1 = nums[0], num2 = nums[0];
    int cnt1 = 0, cnt2 = 0;

    for (int num : nums) {
        if (cnt1 > 0 && num == num1) {
            cnt1++;
        } else if (cnt2 > 0 && num == num2) {
            cnt2++;
        } else if (cnt1 == 0) {
            num1 = num;
            cnt1 = 1;
        } else if (cnt2 == 0) {
            num2 = num;
            cnt2 = 1;
        } else {
            cnt1--;
            cnt2--;
        }
    }

    cnt1 = cnt2 = 0;
    for (int num : nums) {
        if (num == num1) cnt1++;
        else if (num == num2) cnt2++;
    }

    if (cnt1 > nums.length / 3) res.add(num1);
    if (cnt2 > nums.length / 3) res.add(num2);

    return res;
}

搜索二维矩阵 II

将矩阵看做一棵从左下到右上的二叉树

public boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length;
    int n = matrix[0].length;

    int row = m - 1, col = 0;

    while (row >= 0 && col < n) {
        if (matrix[row][col] == target) {
            return true;
        } else if (matrix[row][col] < target) {
            col++;
        } else {
            row--;
        }
    }
    return false;
}

完全平方数

类似硬币问题，将j * j看做硬币，dp为最少硬币数。

public int numSquares(int n) {
    int[] dp = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        dp[i] = i; // 最坏的情况就是每次+1
        for (int j = 1; j * j <= i; j++) {
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
        }
    }
    return dp[n];
}

移动零

left指针指向左边，right指针指向左边第一个非零数。

swap，指针同时加一。

public void moveZeroes(int[] nums) {
    int n = nums.length, left = 0, right = 0;
    while (right < n) {
        while (right < n && nums[right] == 0) right++;
        if (right != n) {
            swap(nums, left, right);
            left++;
            right++;
        }
    }
}

寻找重复数

将数组看做一个环形链表，找到相交的点即为重复数。

public int findDuplicate(int[] nums) {
    int slow = 0, fast = 0;
    slow = nums[slow];
    fast = nums[nums[fast]];

    while (slow != fast) {
        slow = nums[slow];
        fast = nums[nums[fast]];
    }

    int a = 0, b = slow;
    while (a != b) {
        a = nums[a];
        b = nums[b];
    }

    return a;
}

删除无效的括号

我们需要先找出不合法的左括号个数和右括号个数
利用dfs不断删除"（"或者"）"，直到不合法个数为0
检验删除后的括号串是否合法。

List<String> res = new ArrayList<>();

public List<String> removeInvalidParentheses(String s) {
    int left = 0, right = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') left++;
        else if (s.charAt(i) == ')') {
            if (left > 0) left--;
            else right++;
        }
    }
    dfs(s, 0, left, right);
    return res;
}

void dfs(String s, int start, int left, int right) {
    if (left == 0 && right == 0) {
        if (check(s)) res.add(s);
        return;
    }
    for (int i = start; i < s.length(); i++) {
        if (i > start && s.charAt(i) == s.charAt(i - 1)) continue;
        String tmp = s.substring(0, i) + s.substring(i + 1);
        if (s.charAt(i) == '(' && left > 0)
            dfs(tmp, i, left - 1, right);
        if (s.charAt(i) == ')' && right > 0)
            dfs(tmp, i, left, right - 1);
    }
}

boolean check(String s) {
    int left = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') left++;
        else if (s.charAt(i) == ')' && left > 0) left--;
    }
    return left == 0;
}

戳气球(区间dp)

在数组两边添加两个为1的气球
假设dp[i][j]为开区间(i,j)中的最大硬币数量，戳气球只能戳(i, j)，不能戳两边
k为最后一个被戳的气球，则dp[i][j] = dp[i][k] + dp[k][j] + nums[k] * dp[i] * dp[j]

public int maxCoins(int[] nums) {
    int n = nums.length;
    int[] book = new int[n + 2];
    book[0] = book[n + 1] = 1;
    System.arraycopy(nums, 0, book, 1, n);

    int[][] dp = new int[n + 2][n + 2];
    //区间长度
    for (int len = 3; len <= n + 2; len++) {
        // i表示开区间左端点
        for (int i = 0; i <= n + 2 - len; i++) {
            // j为开区间右端点
            int j = i + len - 1;
            // k为区间中间点
            for (int k = i + 1; k < j; k++) {
                dp[i][j] = Math.max(dp[i][j],
                        dp[i][k] + dp[k][j] + book[i] * book[k] * book[j]);
            }
        }
    }

    return dp[0][n + 1];
}

字符串解码

辅助栈法
- 有两个变量mul:倍数，str:重复的字符串
- 若遇数字，则增加mul
- 若遇[，则入栈
- 若遇]，出栈，将str与出栈的mul相乘再与出栈的str相加，作为当前str
递归法
- 使用i表示index
- 若遇数字则增加mul，若遇字符则追加str
- 若遇[，则递归f(i+1)获取需要重复的字符串，重复追加mul次
- 若遇]，则返回i和str

根据身高重建队列

按照身高从小到大进行排序，从小到大将其放入格子里，保证其前面的空格子为Ki，这些空格子用来存放其后的更高的人。因题目要求大于等于，所以可以先按身高升序排列，按Ki降序排列。

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() {
            public int compare(int[] person1, int[] person2) {
                if (person1[0] != person2[0]) {
                    return person1[0] - person2[0];
                } else {
                    return person2[1] - person1[1];
                }
            }
        });
        int n = people.length;
        int[][] ans = new int[n][];
        for (int[] person : people) {
            int spaces = person[1] + 1;
            for (int i = 0; i < n; ++i) {
                if (ans[i] == null) {
                    --spaces;
                    if (spaces == 0) {
                        ans[i] = person;
                        break;
                    }
                }
            }
        }
        return ans;
    }
}

回文子串

动态规划，dp[i][j]表示字符串i到j是否是回文串，使用res表示回文串个数。

若i==j，dp[i][j]=true
若c[i]==c[j]
- 若j-i==1，dp[i][j]=true
- 若j-i>1，dp[i][j]=dp[i+1][j-1]

public int countSubstrings(String s) {
    int n = s.length();
    char[] c = s.toCharArray();
    boolean[][] dp = new boolean[len][len];

    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            if (i == j) {
                dp[i][j] = true;
                res++;
            } else if (c[i] == c[j]) {
                if (j - i == 1 || dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    res++;
                }
            }
        }
    }

    return res;
}