class Solution {
    public int lastStoneWeight(int[] stones) {
        var heap = new PriorityQueue<Integer>((a, b) -> b - a);
        for (int x : stones) heap.offer(x);
        while (heap.size() >= 2) {
            int a = heap.poll(), b = heap.poll();
            if (a != b) heap.offer(a - b);
        }
        return heap.isEmpty() ? 0 : heap.peek();
    }
}

class Solution {
    int N = 100010, P = 131, n, left, right;
    long[] h = new long[N], p = new long[N];

    long get(int l, int r) {
        return h[r] - h[l - 1] * p[r - l + 1];
    }

    boolean check(int mid) {
        Set<Long> set = new HashSet<>();
        for (int i = 1; i + mid - 1 <= n; i++) {
            var v = get(i, i + mid - 1);
            if (set.contains(v)) {
                left = i - 1; right = i + mid - 1;
                return true;
            }
            set.add(v);
        }
        return false;
    }

    public String longestDupSubstring(String s) {
        n = s.length();
        p[0] = 1;
        for (int i = 1; i <= n; i++) {
            p[i] = p[i - 1] * P;
            h[i] = h[i - 1] * P + s.charAt(i - 1);
        }

        int l = 0, r = n;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
        return r == 0 ? "" : s.substring(left, right);
    }
}

/**
 * @param {string} s
 * @return {string}
 */
const removeDuplicates = function(s) {
    const stk = [];
    for (let c of s) {
        if (!stk.length || stk.at(-1) != c) stk.push(c);
        else stk.pop();
    }
    return stk.join("");
};

/**
 * @param {number} n
 * @param {number[][]} paths
 * @return {number[]}
 */
const gardenNoAdj = function(n, paths) {
    const g = Array.from(Array(n), _ => []);
    for (let ver of paths) {
        let a = ver[0] - 1, b = ver[1] - 1;
        g[a].push(b), g[b].push(a);
    }

    const res = Array(n).fill(0);
    for (let i = 0; i < n; i++) {
        let st = Array(5);
        for (let x of g[i])
            st[res[x]] = true;
        for (let j = 1; j <= 4; j++)
            if (!st[j]) {
                res[i] = j;
                break;
            }
    }
    return res;
};

/**
 * @param {string} instructions
 * @return {boolean}
 */
const isRobotBounded = function(instructions) {
    let i = 0, j = 0, dir = 0;
    const dx = [-1, 0, 1, 0], dy = [0, 1, 0, -1];
    for (let c of instructions) {
        if (c == 'L') dir = (dir - 1 + 4) % 4;
        else if (c == 'R') dir = (dir + 1) % 4;
        else i += dx[dir], j += dy[dir];
    }
    // 一圈后回到原点，或者方向不是向上（dir == 0）
    return i == 0 && j == 0 || dir;
};

关联题目：

• AcWing 1069. 凸多边形的划分

class Solution {
    public int minScoreTriangulation(int[] w) {
        int n = w.length;
        int[][] f = new int[n][n];
        // 不能像下边这样初始化，因为区间长度小于等于 2 时 f[i][j] 应为 0
        // for (int i = 0; i < n; i++) Arrays.fill(f[i], 0x3f3f3f3f);
        for (int len = 3; len <= n; len++)
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                if (len == 3) f[i][j] = w[i] * w[i + 1] * w[j];
                else {
                    f[i][j] = 0x3f3f3f3f;
                    for (int k = i + 1; k < j; k++)
                        f[i][j] = Math.min(f[i][j], f[i][k] + f[k][j] + w[i] * w[k] * w[j]);
                }
            }
        return f[0][n - 1];
    }
}

class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.length;
        int f[] = new int[n + 1], mx[][] = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            mx[i][i] = arr[i - 1];
            for (int j = i + 1; j <= n; j++)
                mx[i][j] = Math.max(mx[i][j - 1], arr[j - 1]);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = Math.max(i - k, 0); j <= i - 1; j++)
                f[i] = Math.max(f[i], f[j] + mx[j + 1][i] * (i - j));
        }
        return f[n];
    }
}

参考题解

class Solution {
    public int[] numMovesStonesII(int[] stones) {
        int n = stones.length;
        Arrays.sort(stones);
        // [0, n - 2] 共有 s[n - 2] - s[0] + 1 个位置，减去 n - 1 个石子
        int m1 = stones[n - 2] - stones[0] + 1 - (n - 1),
            m2 = stones[n - 1] - stones[1] + 1 - (n - 1);
        int mx = Math.max(m1, m2);
        if (m1 == 0 || m2 == 0)
            return new int[]{Math.min(2, mx), mx};
        int maxCnt = 0;
        for (int i = 0, j = 0, s = 0; i < n; i++) {
            while (stones[i] - stones[j] + 1 > n)
                j++;
            // 窗口内的石子数量
            maxCnt = Math.max(maxCnt, i - j + 1);
        }
        return new int[]{n - maxCnt, mx};
    }
}

离散化 + bfs，参考题解

class Solution {
    int N = 1000000, M = 610, n, m;
    boolean[][] st = new boolean[M][M];

    void add(List<Integer> list, int p) {
        if (p > 0) list.add(p - 1);
        if (p + 1 < N) list.add(p + 1);
        list.add(p);
    }

    int find(List<Integer> list, int x) {
        return Collections.binarySearch(list, x);
    }

    boolean bfs(int sx, int sy, int ex, int ey) {
        int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
        Deque<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{sx, sy});
        st[sx][sy] = true;

        while (!q.isEmpty()) {
            var t = q.poll();
            for (int i = 0; i < 4; i++) {
                int a = t[0] + dx[i], b = t[1] + dy[i];
                if (a < 0 || a >= n || b < 0 || b >= m || st[a][b]) continue;
                if (a == ex && b == ey) return true;
                q.offer(new int[]{a, b});
                st[a][b] = true;
            }
        }
        return false;
    }

    public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
        List<Integer> xs = new ArrayList<>(), ys = new ArrayList<>();
        add(xs, source[0]); add(xs, target[0]);
        add(ys, source[1]); add(ys, target[1]);
        for (int[] b : blocked) {
            add(xs, b[0]);
            add(ys, b[1]);
        }
        xs = xs.stream().sorted().distinct().toList();
        ys = ys.stream().sorted().distinct().toList();

        n = xs.size(); m = ys.size();
        for (int[] b : blocked) {
            int x = find(xs, b[0]), y = find(ys, b[1]);
            st[x][y] = true;
        }
        return bfs(find(xs, source[0]), find(ys, source[1]), find(xs, target[0]), find(ys, target[1]));
    }
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
const bstToGst = function(root) {
    let s = 0;
    const dfs = (root) => {
        if (!root) return;
        dfs(root.right);
        s += root.val;
        root.val = s;
        dfs(root.left);
    };
    dfs(root);
    return root;
};