海边别墅

# LeetCode 5

2021.8 ~ 2021.10

# 1337. 矩阵中战斗力最弱的 K 行

优先队列

class Solution {
    public int[] kWeakestRows(int[][] mat, int k) {
        // int[0] = count; int[1] = index
        PriorityQueue<int[]> pq = new PriorityQueue<>(
            new Comparator<int[]>() {
                public int compare(int[] a, int[] b) {
                    return a[0] == b[0] ? a[1]-b[1] : a[0]-b[0];
                }
            }
        );

        for (int i = 0; i < mat.length; i++) {
            int cnt = 0;
            for (int j = 0; j < mat[0].length; j++) {
                if (mat[i][j] == 0) break;

                cnt++;
            }
            pq.offer(new int[]{cnt, i});
        }

        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = pq.poll()[1];
        }

        return res;
    }
}

# 743. 网络延迟时间

优先队列+BFS：

class Solution {
    Set<Integer> set = new HashSet<>();
    public int networkDelayTime(int[][] times, int n, int k) {
        Map<Integer, List<int[]>> map = new HashMap<>();
        for (int[] t : times) {
            List<int[]> list = map.getOrDefault(t[0], new ArrayList<>());
            list.add(new int[]{t[1], t[2]});
            map.put(t[0], list);
        }   
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> {
            return a[1] == b[1] ? a[0]-b[0] : a[1]-b[1];
        });
        q.offer(new int[]{k, 0});

        while (q.size()>0) {
            int[] cur = q.poll();
            if (set.contains(cur[0])) continue;
            set.add(cur[0]);
            if (set.size() == n) return cur[1];

            List<int[]> list = map.getOrDefault(cur[0], new ArrayList<>());
            for (int[] t : list) {
                if (set.contains(t[0])) continue;
                q.offer(new int[]{t[0], t[1]+cur[1]});
            }
        }

        return -1;
    }

}

# 581. 最短无序连续子数组

class Solution {
    int INF = 0x3f3f3f3f;
    public int findUnsortedSubarray(int[] nums) {
        Stack<int[]> stack = new Stack<>();
        stack.push(new int[]{-1*INF, 0});
        int l = nums.length, r = -1;
        int cnt = 0;
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] < stack.peek()[0]) {
                l = Math.min(l, stack.pop()[1]);
                cnt--;
            }
            stack.push(new int[]{nums[i], i});
            cnt++;
        }
        if (cnt == nums.length) return 0;

        Stack<int[]> s2 = new Stack<>();
        s2.push(new int[]{INF, 0});
        for (int i = nums.length-1; i >= 0; i--) {
            while (nums[i] > s2.peek()[0]) {
                r = Math.max(r, s2.pop()[1]);
            }
            s2.push(new int[]{nums[i], i});
        }

        return r-l+1;
    }
}

# 611. 有效三角形的个数

排序+二分：

class Solution {
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int cnt = 0;
        for (int i = 0; i < n-2; i++) {
            for (int j = i+1; j < n-1; j++) {
                cnt += search(nums, j+1, n-1, nums[i], nums[j]);
            }
        }
        return cnt;
    }

    public int search(int[] nums, int left, int right, int a, int b) {
        int start = left;
        while (left < right) {
            int mid = left + ((right-left+1)>>1);
            if (a+b > nums[mid]) {
                left = mid;
            } else if (a+b <= nums[mid]) {
                right = mid-1;
            }
        }
        return a+b > nums[right] ? right-start+1 : 0;
    }
}

排序+双指针：

class Solution {
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        if (n < 3) return 0;
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i+1, k = i+1; j < n; j++) {
                while (k < n && nums[i]+nums[j] > nums[k]) {
                    k++;
                }
                cnt += Math.max(k-j-1, 0);
            }
        }
        return cnt;
    }
}

# 802. 找到最终的安全状态

暴力迭代，超时：

class Solution {
    Set<Integer> repeat = new HashSet<>();
    public List<Integer> eventualSafeNodes(int[][] graph) {
        int n = graph.length;
        for (int i = 0; i < n; i++) {
            Set<Integer> visited = new HashSet<>();
            visited.add(i);
            search(graph, visited, i);
        }

        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (repeat.contains(i)) continue;
            res.add(i);
        }
        return res;
    }

    private void search(int[][] graph, Set<Integer> visited, int node) {
        int[] ns = graph[node];
        for (int i = 0; i < ns.length; i++) {
            if (repeat.contains(ns[i]) || visited.contains(ns[i]) || ns[i] == node) {
                repeat.addAll(visited);
                continue;
            }
            visited.add(ns[i]);
            search(graph, visited, ns[i]);
            visited.remove(ns[i]);
        }
    }
}

暴力优化+三色标记：

class Solution {
    Set<Integer> repeat = new HashSet<>();
    public List<Integer> eventualSafeNodes(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];
        for (int i = 0; i < n; i++) {
            search(graph, color, i);
        }
        // 可以进一步优化，去掉循环
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (color[i] == 2) res.add(i);
        }
        // 优化代码：
        // for (int i = 0; i < n; i++) {
        //     if (search(graph, color, i)) {
        //         res.add(i);
        //     }
        // }
        return res;
    }

    private boolean search(int[][] graph, int[] color, int node) {
        if (color[node] == 1) {
            return false;
        } else if (color[node] == 2) {
            return true;
        }

        color[node] = 1;
        int[] ns = graph[node];
        boolean allSafe = true;
        for (int i = 0; i < ns.length; i++) {
            boolean safe = search(graph, color, ns[i]);
            if (!safe) {
                allSafe = false;    
                color[node] = 1;
            }
        }
        if (allSafe) color[node] = 2;
        return allSafe;
    }
}

拓扑排序：

class Solution {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        int n = graph.length;
        List<List<Integer>> rg = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            rg.add(new ArrayList<Integer>());
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < graph[i].length; j++) {
                rg.get(graph[i][j]).add(i);
            }
        }

        int[] in = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < rg.get(i).size(); j++) {
                in[rg.get(i).get(j)]++;
            }
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (in[i] == 0) q.offer(i);
        }

        while (!q.isEmpty()) {
            int node = q.poll();
            List<Integer> ns = rg.get(node);
            for (int i = 0; i < ns.size(); i++) {
                int k = ns.get(i);
                in[k]--;
                if (in[k] == 0) q.offer(k);
            }
        }

        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (in[i] == 0) res.add(i);
        }
        return res;
    }
}

拓扑排序+细节优化：

class Solution {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        int n = graph.length;
        List<List<Integer>> rg = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            rg.add(new ArrayList<Integer>());
        }
        int[] in = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < graph[i].length; j++) {
                rg.get(graph[i][j]).add(i);
            }
            in[i] = graph[i].length;
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (in[i] == 0) q.offer(i);
        }

        while (!q.isEmpty()) {
            int node = q.poll();
            List<Integer> ns = rg.get(node);
            for (int i = 0; i < ns.size(); i++) {
                int k = ns.get(i);
                in[k]--;
                if (in[k] == 0) q.offer(k);
            }
        }

        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (in[i] == 0) res.add(i);
        }
        return res;
    }
}

# 457. 环形数组是否存在循环

递归+剪枝+哈希表： 代码存在很多优化地方

class Solution {
    // index of nums
    Set<Integer> invalid = new HashSet<>();
    public boolean circularArrayLoop(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            recursive(nums, i, new HashSet<>(), nums[i] > 0);
        }
        return circle;
    }

    boolean circle = false;
    private void recursive(int[] nums, int pos, Set<Integer> path, boolean positive) {
        if (circle) return;
        
        // check
        if (invalid.contains(pos)) {
            return;
        }
        if ((nums[pos] > 0 && !positive) || (nums[pos] < 0 && positive)) {
            invalid.addAll(path);
            return;
        }

        if (path.contains(pos)) {
            if (path.size() == 1) {
                invalid.add(pos);
                return;
            }
            circle = true;
            return;
        }
        path.add(pos);
        int n = nums.length;
        // next
        int next = nums[pos] % n + pos;
        if (next >= n) {
            next %= n;
        } else if (next < 0) {
            next += n;
        }
        if (next == pos) {
            invalid.addAll(path);
            return;
        }
        recursive(nums, next, path, positive);
    }
}

拓扑排序判断是否存在环： 存在优化点：

  1. 每个节点最多只会指向一个节点，可以优化成List<Integer>结构
  2. 若移动后的位置与当前方向不一致，不作为一条边加入到邻接表中
class Solution {
    // 
    List<List<Integer>> adj = new ArrayList<>();
    int n;
    int[] nums;
    public boolean circularArrayLoop(int[] nums) {
        this.n = nums.length;
        this.nums = nums;
        // init
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }

        // positive 统计正向边
        for (int i = 0; i < n; i++) {
            if (nums[i] < 0) continue;
            int end = ((nums[i] % n + i) + n) % n;
            if (i == end) continue;
            adj.get(i).add(end);
        }
        if (toposort()) return true;

        // 重新初始化
        adj.clear();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        
        // negetive 统计反向边
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) continue;
            int end = ((nums[i] % n + i) + n) % n;
            if (i == end) continue;
            adj.get(i).add(end);
        }
        if (toposort()) return true;

        return false;
    }

    private boolean toposort() {
        int[] in = new int[n];
        for (int i = 0; i < n; i++) {
            List<Integer> list = adj.get(i);
            if (list.size() != 0) {
                in[list.get(0)]++;
            }
        }
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (in[i] == 0) q.offer(i);
        }

        while (!q.isEmpty()) {
            int cur = q.poll();
            List<Integer> list = adj.get(cur);
            
            if (list.size() != 0) {
                int next = list.get(0);
                in[next]--;
                if (in[next] == 0) q.offer(next);
            }
        }

        for (int i = 0; i < n; i++) {
            if (in[i] != 0) return true;
        }

        return false;
    }
}

优化后：

class Solution {
    int[] adj;
    int n;
    int[] nums;
    public boolean circularArrayLoop(int[] nums) {
        this.n = nums.length;
        this.nums = nums;
        adj = new int[n];
        int[] in = new int[n];
        for (int i = 0; i < n; i++) {
            int end = ((nums[i] % n + i) + n) % n;
            if (i == end || nums[i] * nums[end] < 0) continue;
            adj[i] = end+1;
            in[end]++;
        }
        
        if (toposort(in)) return true;
        return false;
    }

    private boolean toposort(int[] in) {
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (in[i] == 0) q.offer(i);
        }

        while (!q.isEmpty()) {
            int cur = q.poll();
            int next = adj[cur]-1;
            
            if (next >= 0) {
                in[next]--;
                if (in[next] == 0) q.offer(next);
            }
        }

        for (int i = 0; i < n; i++) {
            if (in[i] != 0) return true;
        }

        return false;
    }
}

利用数组本身的空间优化空间复杂度：

class Solution {
    public boolean circularArrayLoop(int[] nums) {
        int offset = 100000;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] >= offset) continue;
            int cur = i;
            int last = -1;
            boolean positive = nums[cur] > 0;
            int tag = i + offset;
            while (true) {
                int next = ((nums[cur] % n + cur) + n) % n;
                last = nums[cur];
                nums[cur] = tag;
                cur = next;
                if (cur == i) break;
                if (nums[cur] >= offset) break;
                if (nums[cur] > 0 && !positive) break;
                if (nums[cur] < 0 && positive) break;
            }
            if (last % n != 0 && nums[cur] == tag) return true;

        }
        return false;
    }
}

快慢指针：

class Solution {
    public boolean circularArrayLoop(int[] nums) {
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            int slow = i;
            int fast = next(nums, i);

            while (nums[slow] * nums[fast] > 0 && nums[slow] * nums[next(nums, fast)] > 0) {
                if (slow == fast) {
                    if (slow != next(nums, slow)) return true;
                    break;
                }
                slow = next(nums, slow);
                fast = next(nums, next(nums, fast));
            }

            // set 0
            int zero = i;
            while (nums[zero] * nums[next(nums, zero)] > 0) {
                nums[zero] = 0;
                zero = next(nums, zero);
            }
        }

        return false;
    }

    private int next(int[] nums, int cur) {
        int n = nums.length;
        return ((cur + nums[cur]) % n + n ) % n;
    }
}

# 1137. 第 N 个泰波那契数

class Solution {
    public int tribonacci(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        int[] init = new int[n+1];
        init[0] = 0;
        init[1] = 1;
        init[2] = 1;

        for (int i = 3; i <= n; i++) {
            init[i] = init[i-1]+init[i-2]+init[i-3];
        }
        return init[n];
    }
}

# 313. 超级丑数

优先队列：

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        PriorityQueue<Long> pq = new PriorityQueue<>();
        pq.offer(1L);
        Set<Long> set = new HashSet<>();

        long cur = 0;
        for (int i = 1; i <= n; i++) {
            cur = pq.poll();
            for (int p : primes) {
                long multi = p * cur;
                if (!set.contains(multi)) {
                    set.add(multi);
                    pq.offer(multi);
                }
            }
        }
        return (int) cur;
    }
}

多指针，或者说动态规划：

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        if (n == 1) return 1;
        int m = primes.length;

        int[] pointers = new int[m];
        Arrays.fill(pointers, 1);

        int[] dp = new int[n+1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int[] nums = new int[m];
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < m; j++) {
                nums[j] = dp[pointers[j]] * primes[j];
                min = Math.min(min, nums[j]);
            }

            dp[i] = min;

            for (int j = 0; j < m; j++) {
                if (nums[j] == min) pointers[j]++;
            }
        }
        return dp[n];
    }
}

# 413. 等差数列划分

差分数组：

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        
        int[] diff = new int[n];
        for (int i = 1; i < n; i++) {
            diff[i] = nums[i] - nums[i-1];
        }
        
        int[] cnt = new int[n];
        for (int i = 2; i < n; i++) {
            cnt[i] = diff[i] - diff[i-1];
        }

        int count = 0;
        int res = 0;
        for (int i = 2; i < n; i++) {
            if (cnt[i] != 0) {
                if (count != 0) {
                    count += 2;
                    res += (count-1)*(count-2)/2;
                }
                count = 0;
            } else {
                count++;
            }
        }
        if (count != 0) {
            count += 2;
            res += (count-1)*(count-2)/2;
        }
        return res;
    }
}

找到差分规律，用更少空间：

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        if (n < 3) return 0;
        int res = 0;
        int cnt = 0;

        for (int i = 2; i < n; i++) {
            if (nums[i]-nums[i-1] == nums[i-1]-nums[i-2]) {
                cnt++;
                res += cnt;
            } else {
                cnt = 0;
            }
        }
        return res;
    }
}

动态规划：

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int cnt = 0;
        for (int i = 2; i < n; i++) {
            int d = nums[i-1] - nums[i-2];
            int d2 = nums[i] - nums[i-1];
            if (d == d2) {
                dp[i] = dp[i-1] + 1;
                cnt += dp[i];
            }
        }
        return cnt;
    }
}

动态规划，空间优化：

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int cnt = 0, pre = 0;
        for (int i = 2; i < nums.length; i++) {
            int d = nums[i-1] - nums[i-2];
            int d2 = nums[i] - nums[i-1];
            if (d == d2) {
                pre = pre + 1;
                cnt += pre;
            } else {
                pre = 0;
            }
        }
        return cnt;
    }
}

# 446. 等差数列划分 II - 子序列

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        Map<Long, Integer>[] dp = new HashMap[n];
        for (int i = 0; i < n; i++) {
            dp[i] = new HashMap<>();
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                long diff = 1L * nums[i] - nums[j];
                int cnt = dp[j].getOrDefault(diff, 0);
                res += cnt;
                dp[i].put(diff, dp[i].getOrDefault(diff, 0) + cnt + 1);
            }
        }
        return res;
    }
}

# 1583. 统计不开心的朋友

哈希表+模拟：

class Solution {
    public int unhappyFriends(int n, int[][] preferences, int[][] pairs) {
        Map<Integer, Integer> pmap = new HashMap<>();
        for (int[] p : pairs) {
            pmap.put(p[0], p[1]);
            pmap.put(p[1], p[0]);
        }
        // <i, map<value, index>>
        Map<Integer, Map<Integer, Integer>> prefMaps = new HashMap<>();
        for (int i = 0; i < n; i++) {
            Map<Integer, Integer> prefM = prefMaps.getOrDefault(i, new HashMap<Integer, Integer>());
            for (int j = 0; j < n-1; j++) {
                prefM.put(preferences[i][j], j);
            }
            prefMaps.put(i, prefM);
        }

        Set<Integer> set = new HashSet<>();
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (set.contains(i)) continue;

            int x = i;
            int y = pmap.get(i);
            int[] prefX = preferences[x];

            for (int j = 0; j < n-1; j++) {
                int u = prefX[j];
                if (u == y) break;

                int v = pmap.get(u);
                Map<Integer, Integer> prefM = prefMaps.get(u);
                if (prefM.get(x) < prefM.get(v)) {
                    set.add(x);
                    cnt += 1;
                    break;
                }
            }
        }

        return cnt;
    }
}

# 576. 出界的路径数

dfs+备忘录：

class Solution {
    int[] dr = new int[]{1, 0, -1, 0};
    int[] dc = new int[]{0, 1, 0, -1};
    int row;
    int col;
    int[][][] cache;
    int mod = (int) 1e9+7;
    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        row = m;
        col = n;
        cache = new int[m][n][maxMove+1];
        return dfs(startRow, startColumn, maxMove);
    }

    private int dfs(int r, int c, int step) {
        if (r < 0 || r >= row || c < 0 || c >= col) {
            return 1;
        }
        if (step == 0) return 0;
        int cval = cache[r][c][step];
        if (cval == -1) return 0;
        if (cval != 0) return cval;

        long res = 0;
        for (int i = 0; i < 4; i++) {
            res += dfs(r+dr[i], c+dc[i], step-1);
        }

        int ans = (int) (res % mod);
        cache[r][c][step] = ans == 0 ? -1 : ans;
        return ans;
    }
}

动态规划：todo

# 526. 优美的排列

class Solution {
    int cnt = 0;
    public int countArrangement(int n) {
        int[] arr = new int[n+1];
        boolean[] visited = new boolean[n+1];
        recursive(arr, visited, 1);
        return cnt;
    }

    private void recursive(int[] arr, boolean[] visited, int index) {
        if (index >= arr.length) {
            cnt++;
            return;
        }
        for (int i = 1; i < arr.length; i++) {
            if (visited[i]) continue;
            if (i % index == 0 || index % i == 0) {
                arr[index] = i;
                visited[i] = true;
                recursive(arr, visited, index+1);
                // back
                visited[i] = false;
            }
        }
    }
}

# 551. 学生出勤记录 I

class Solution {
    public boolean checkRecord(String s) {
        char[] cs = s.toCharArray();
        int absent = 0;
        int late = 0;
        for (char c : cs) {
            if ('A' == c) {
                absent++;
                late = 0;
            } else if ('L' == c) {
                late++;
            } else {
                late = 0;
            }

            if (absent >= 2 || late >= 3) {
                return false;
            }
        }
        return true;
    }
}

# 552. 学生出勤记录 II

Bruce force，超时不通过，用例：10101

class Solution {
    char[] status = new char[]{'A', 'L', 'P'};
    Set<String> set = new HashSet<>();
    int mod = (int)1e9+7;
    public int checkRecord(int n) {
        return (int)recursive(n, ' ', 0, 0);
    }
    
    private long recursive(int n, char cur, int absent, int late) {
        if (cur == 'A') {
            absent++;
        }
        if (cur == 'L') {
            late++;
        } else {
            late = 0;
        }
        if (absent >= 2 || late >= 3) {
            return 0L;
        }
        if (n == 0) return 1L;
        long res = 0L;
        for (char c : status) {
            res = (res + recursive(n-1, c, absent, late)) % mod;
        }
        return res;
    }
}

记忆化也无法通过，用例：99999

class Solution {
    char[] status = new char[]{'A', 'L', 'P'};
    Set<String> set = new HashSet<>();
    int mod = (int)1e9+7;
    Map<String, Long> cache = new HashMap<>();
    public int checkRecord(int n) {
        return (int)recursive(n, 0, 0);
    }
    
    private long recursive(int n, int absent, int late) {
        if (absent >= 2 || late >= 3) {
            return 0L;
        }
        if (n == 0) return 1L;
        String key = n+";"+absent+";"+late+";";
        Long ans = cache.get(key);
        if (ans != null) return ans;
        long res = 0L;
        for (char c : status) {
            int nabsent = absent;
            int nlate = late;
            if (c == 'A') {
                nabsent++;
            }
            if (c == 'L') {
                nlate++;
            } else {
                nlate = 0;
            }
            res = (res + recursive(n-1, nabsent, nlate)) % mod;
        }
        cache.put(key, res);
        return res;
    }
}

继续优化，记忆化递归，通过，很慢：

class Solution {
    char[] status = new char[]{'A', 'L', 'P'};
    Set<String> set = new HashSet<>();
    int mod = (int)1e9+7;
    long[][][] cache;
    public int checkRecord(int n) {
        cache = new long[n+1][3][4];
        return (int)recursive(n, 0, 0);
    }
    
    private long recursive(int n, int absent, int late) {
        if (absent >= 2 || late >= 3) {
            return 0L;
        }
        if (n == 0) return 1L;
        long ans = cache[n][absent][late];
        if (ans != 0L) return ans;
        long res = 0L;
        for (char c : status) {
            int nabsent = absent;
            int nlate = late;
            if (c == 'A') {
                nabsent++;
            }
            if (c == 'L') {
                nlate++;
            } else {
                nlate = 0;
            }
            res = (res + recursive(n-1, nabsent, nlate)) % mod;
        }
        cache[n][absent][late] = res;
        return res;
    }
}

# 345. 反转字符串中的元音字母

双指针：

class Solution {
    char[] meta = new char[]{'A', 'E', 'I', 'O', 'U', 'a', 'e', 'i', 'o', 'u'};
    Set<Character> set = new HashSet<>();
    public String reverseVowels(String s) {
        for (char m : meta) {
            set.add(m);
        }
        char[] cs = s.toCharArray();
        int n = s.length();
        int left = 0, right = n-1;
        while (left < right) {
            while (left < right && !set.contains(cs[left])) {
                left++;
            }
            while (left < right && !set.contains(cs[right])) {
                right--;
            }
            char tmp = cs[left];
            cs[left] = cs[right];
            cs[right] = tmp;

            left++;
            right--;
        }

        return String.valueOf(cs);
    }
}

# 541. 反转字符串 II

class Solution {
    public String reverseStr(String s, int k) {
        char[] cs = s.toCharArray();
        int n = cs.length;
        int i = 0;
        while (i < n) {
            int left = i;
            i += k;
            reverse(cs, left, i);
            i += k;
        }
        return String.valueOf(cs);
    }

    private void reverse(char[] cs, int left, int right) {
        right--;
        if (right >= cs.length) {
            right = cs.length-1;
        }
        while (left < right) {
            char tmp = cs[left];
            cs[left] = cs[right];
            cs[right] = tmp;
            left++;
            right--;
        }
    }

}

# 443. 压缩字符串

模拟：

class Solution {
    public int compress(char[] chars) {
        int index = -1;
        int cnt = 0;
        char pre = '!';
        for (int i = 0; i <= chars.length; i++) {
            char cur = i == chars.length ? '-' : chars[i];
            if (pre != cur) {
                if (cnt > 1) {
                    String cntStr = String.valueOf(cnt);
                    for (int j = 0; j < cntStr.length(); j++) {
                        chars[j+index+1] = cntStr.charAt(j);
                    }
                    index = index+1+cntStr.length();
                } else {
                    index++;
                }
                if (i == chars.length) break;
                chars[index] = cur;
                pre = cur;
                cnt = 1;
            } else {
                cnt++;
            }
        }
        return index;
    }
}

# 789. 逃脱阻碍者

曼哈顿距离：

class Solution {
    public boolean escapeGhosts(int[][] ghosts, int[] target) {
        int your = dist(new int[]{0, 0}, target);
        for (int[] g : ghosts) {    
            if (dist(g, target) <= your) return false;
        }
        return true;
    }

    private int dist(int[] start, int[] target) {
        return Math.abs(start[0]-target[0]) + Math.abs(start[1]-target[1]);
    }
}

# 1646. 获取生成数组中的最大值

class Solution {
    public int getMaximumGenerated(int n) {
        if (n == 0 || n == 1) return n;
        int max = 0;
        int[] nums = new int[n+1];
        nums[0] = 0;
        nums[1] = 1;
        for (int i = 0; i < n+1; i++) {
            if (i % 2 == 0) {
                nums[i] = nums[i/2];
            } else {
                nums[i] = nums[(i-1)/2] + nums[(i+1)/2];
            }
            max = Math.max(max, nums[i]);
        }
        return max;
    }
}

# 787. K 站中转内最便宜的航班

bfs+记忆化：

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        Map<Integer, List<int[]>> adj = new HashMap<>();
        for (int[] f : flights) {
            List<int[]> list = adj.getOrDefault(f[0], new ArrayList<>());
            list.add(f);            
            adj.put(f[0], list);
        }
        int[] prices = new int[n+1];
        for (int i = 0; i < n; i++) {
            prices[i] = Integer.MAX_VALUE;
        }
        Queue<int[]> q = new LinkedList<>();
        int[] start = new int[]{src, 0};
        q.offer(start);
        prices[src] = 0;
        int min = Integer.MAX_VALUE;
        while (!q.isEmpty() && k >= -1) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                int[] cur = q.poll();
                // System.out.println(Arrays.toString(cur));
                if (cur[0] == dst) {
                    min = Math.min(min, cur[1]);
                }
                List<int[]> list = adj.get(cur[0]);
                if (list == null) continue;
                
                for (int[] f : list) {
                    int p = cur[1]+f[2];
                    if (p > prices[f[1]]) continue;
                    prices[f[1]] = p;
                    q.offer(new int[]{f[1],p});
                }
            }
            k--;
        }

        return min == Integer.MAX_VALUE ? -1 : min;
    }
}

继续优化：

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        List<int[]>[] adj = new List[n];
        int[] prices = new int[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
            prices[i] = Integer.MAX_VALUE;
        }
        for (int[] f : flights) {
            List<int[]> list = adj[f[0]];
            list.add(f);            
        }
        Queue<int[]> q = new LinkedList<>();
        int[] start = new int[]{src, 0};
        q.offer(start);
        prices[src] = 0;
        int min = Integer.MAX_VALUE;
        while (!q.isEmpty() && k >= -1) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                int[] cur = q.poll();
                // System.out.println(Arrays.toString(cur));
                if (cur[0] == dst) {
                    min = Math.min(min, cur[1]);
                }
                List<int[]> list = adj[cur[0]];
                if (list == null) continue;
                
                for (int[] f : list) {
                    int p = cur[1]+f[2];
                    if (p > prices[f[1]]) continue;
                    prices[f[1]] = p;
                    q.offer(new int[]{f[1],p});
                }
            }
            k--;
        }

        return min == Integer.MAX_VALUE ? -1 : min;
    }
}

动态规划：

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        // dp[t][i] 从src到i，经过t次中转，最小花费
        int INF = 0x3f3f3f3f;
        int[][] dp = new int[k+2][n];
        for (int i = 0; i < k+2; i++) {
            Arrays.fill(dp[i], INF);
        }
        dp[0][src] = 0;
        for (int t = 1; t < k+2; t++) {
            for (int[] f : flights) {
                int j = f[0], i = f[1], cost = f[2];
                dp[t][i] = Math.min(dp[t][i], dp[t-1][j]+cost);
            }
        }
        int res = INF;
        for (int t = 1; t < k+2; t++) {
            res = Math.min(res, dp[t][dst]);
        }
        return res == INF ? -1 : res;
    }
}

# 797. 所有可能的路径

dfs:

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<Integer> path = new ArrayList<>();
        path.add(0);
        recursive(graph, path, 0, graph.length-1);
        return res;
    }

    private void recursive(int[][] graph, List<Integer> path, int src, int dst) {
        if (src == dst) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int g : graph[src]) {
            path.add(g);
            recursive(graph, path, g, dst);
            path.remove(path.size()-1);
        }
    }
}

# 881. 救生艇

排序+双指针+贪心：

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int n = people.length;
        int left = 0, right = n-1;
        int res = 0;
        while (left <= right) {
            if (people[left]+people[right] <= limit) {
                left++;
            }
            right--;
            res++;
        }
        return res;
    }
}

# 1480. 一维数组的动态和

简直不能作为一道上台面的算法题

class Solution {
    public int[] runningSum(int[] nums) {
        int pre = 0;
        for (int i = 0; i < nums.length; i++) {
            pre = pre + nums[i];
            nums[i] = pre;
        }
        return nums;
    }
}

# 233. 数字 1 的个数

按位分类讨论：

class Solution {
    public int countDigitOne(int _n) {
        String s = String.valueOf(_n);
        int n = s.length();
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            // ab c de
            String pre = "";
            if (i > 0) {
                pre = s.substring(0, i);
            }
            String suffix = "";
            if (i+1 < n) {
                suffix = s.substring(i+1, n);
            }
            // xx < ab
            if (pre.length() > 0) {
                cnt += Integer.valueOf(pre)*Math.pow(10, suffix.length());
            }

            // xx == ab
            int num = s.charAt(i)-'0';
            if (num == 1) {
                if (suffix.length() > 0) {
                    cnt += Integer.valueOf(suffix)+1;
                } else {
                    cnt++;
                }
            } else if (num > 1) {
                cnt += Math.pow(10, suffix.length());
            }
            // xx > ab，不满足大小要求
        }
        return cnt;
    }
}

# 847. 访问所有节点的最短路径

状压DP+BFS：

class Solution {
    public int shortestPathLength(int[][] graph) {
        int n = graph.length;
        int mask = 1 << n;
        int[][] dp = new int[mask][n+1];
        Queue<int[]> q = new LinkedList<>();
        int INF = 0x3f3f3f3f;
        for (int i = 0; i < mask; i++) {
            Arrays.fill(dp[i], INF);
        }

        for (int i = 0; i < n; i++) {
            int m = 1<<i;
            dp[m][i] = 0;
            q.offer(new int[]{m, i});
        }

        int res = INF;
        while (!q.isEmpty()) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                int[] cur = q.poll();
                int visited = cur[0], node = cur[1], dist = dp[visited][node];
                if (visited == mask-1) return dist;
                int[] next = graph[node];
                for (int nt : next) {
                    int state = visited|(1<<nt);
                    if (dp[state][nt] == INF) {
                        dp[state][nt] = dist+1;
                        q.offer(new int[]{state, nt, dp[state][nt]});
                    }
                }
            }
        }
        return -1;
    }
}

# 1588. 所有奇数长度子数组的和

暴力法：

class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int n = arr.length;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            for (int len = 1; len-1 < n-i; len+=2) {
                sum += ac(arr, i, i+len);
            }
        }
        return sum;
    }

    private int ac(int[] arr, int start, int end) {
        int sum = 0;
        while (start < end) {
            sum += arr[start++];
        }
        return sum;
    }
}

前缀和：

class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int n = arr.length;
        int sum = 0;
        int[] pre = new int[n+1];
        for (int i = 0; i < n; i++) {
            pre[i+1] = arr[i] + pre[i];
        }
        for (int i = 0; i < n; i++) {
            for (int len = 1; len-1 < n-i; len+=2) {
                sum += (pre[i+len]-pre[i]);
            }
        }
        return sum;
    }
}

数学解法TODO:

# 165. 比较版本号

分割字符串：

class Solution {
    public int compareVersion(String version1, String version2) {
        String[] v1 = version1.split("\\.");
        String[] v2 = version2.split("\\.");
        // 取小的数组
        int n1 = v1.length;
        int n2 = v2.length;
        int n = n1 < n2 ? n2 : n1;
        for (int i = 0; i < n; i++) {
            int int1 = i < n1 ? Integer.valueOf(v1[i]) : 0;
            int int2 = i < n2 ? Integer.valueOf(v2[i]) : 0;
            if (int1 > int2) {
                return 1;
            } else if (int1 < int2) {
                return -1;
            }
        }
        return 0;
    }
}

# 面试题 17.14. 最小K个数

class Solution {
    public int[] smallestK(int[] arr, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b-a);
        for (int i = 0; i < arr.length && k > 0; i++) {
            if (pq.size() < k) {
                pq.offer(arr[i]);
                continue;
            }
            if (pq.size() == 0 || arr[i] < pq.peek()) {
                pq.poll();
                pq.offer(arr[i]);
            }
        }
        int[] res = new int[pq.size()];
        int index = 0;
        while (pq.size() > 0) {
            res[index++] = pq.poll();
        }
        return res;
    }
}

# 剑指 Offer 10- I. 斐波那契数列

class Solution {
    public int fib(int n) {
        int a = 0, b = 1, N = (int) 1e9+7;
        if (n == 0) return a;
        if (n == 1) return b;
        for (int i = 2; i <= n; i++) {
            int cur = (a + b) % N;
            a = b;
            b = cur;
        }
        return b;
    }
}

# 1221. 分割平衡字符串

class Solution {
    public int balancedStringSplit(String s) {
        int cnt = 0;
        char[] cs = s.toCharArray();
        int sum = 0;
        for (int i = 0; i < cs.length; i++) {
            if (cs[i] == 'L') {
                sum--;
            } else {
                sum++;
            }
            if (sum == 0) cnt++;
        }
        return cnt;
    }
}

# 502. IPO

class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        // sort
        int n = profits.length;
        int[][] np = new int[n][2];
        for (int i = 0; i < n; i++) {
            np[i][0] = capital[i];
            np[i][1] = profits[i];
        }
        Arrays.sort(np, (a, b) -> a[0]-b[0]);
        
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Comparator.reverseOrder());
        int i = 0;
        while (i < n && k > 0 && w >= np[i][0]) {
            while (i < n && w >= np[i][0]) {
                pq.offer(np[i][1]);
                i++;
            }
            // 1.所有的初始所需资本都小于当前拥有资本 i=n-1 从队列取出k个数，累加到w 
            // 2. i<n-1 一直累加到w<need k>0
            while (k > 0 && pq.size() > 0 && (i >= n-1 || w < np[i][0])) {
                w += pq.poll();
                k--;
            }
                     
        }
        return w;
    }
}

# 68. 文本左右对齐

class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        String space = " ";
        // 贪心思路
        List<String> res = new ArrayList<>();
        List<String> line = new ArrayList<>();
        int ll = 0;
        for (int i = 0; i < words.length; i++) {
            String cur = words[i];
            int len = cur.length();
            // 表示一个单词+一个空格
            int nextl = ll+len+1;
            if (nextl-1 == maxWidth) {
                line.add(cur);
                StringBuilder sb = new StringBuilder();
                for (String li : line) {
                    sb.append(li).append(space);
                }
                sb.deleteCharAt(sb.length()-1);
                res.add(sb.toString());
                ll = 0;
                line.clear();
            } else if (nextl-1 < maxWidth) {
                line.add(cur);
                ll = nextl;
            } else if (nextl-1 > maxWidth) {
                i--;
                // 剩余需要补齐空格的长度，去掉单词后面的空格
                int rem = maxWidth - (ll - 1);
                // System.out.println("rem:"+rem);
                // 当前单词中有多少个空格
                int sp = line.size()-1;
                // 每个空格需要补充多少个空格
                int base = sp > 0 ? rem / sp : rem-1;
                // 从左开始，每个空格需要再追加多少个空格
                int incr = sp > 0 ? rem % sp : 0;
                StringBuilder sb = new StringBuilder();
                for (String li : line) {
                    sb.append(li).append(space);
                    int ss = base;
                    if (incr > 0) {
                        ss++;
                        incr--;
                    }
                    while (ss > 0) {
                        sb.append(space);
                        ss--;
                    }
                }
                if (sb.length() > maxWidth) {
                    sb.delete(maxWidth, sb.length());
                }
                // System.out.println(sb.length());
                res.add(sb.toString());
                ll = 0;
                line.clear();
            }
        }
        if (line.size() > 0) {
            StringBuilder sb = new StringBuilder();
            for (String li : line) {
                sb.append(li).append(space);
            }
            sb.deleteCharAt(sb.length()-1);
            int ss = maxWidth - sb.length();
            while (ss > 0) {
                sb.append(space);
                ss--;
            }
            res.add(sb.toString());
        }
        return res;
    }
}

# 600. 不含连续1的非负整数

class Solution {
    public int findIntegers(int n) {
        int[] dp = new int[32];
        dp[0] = dp[1] = 1;
        for (int i = 2; i < 32; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        int pre = 0, res = 0;
        for (int i = 29; i >= 0; i--) {
            int val = 1 << i;
            if ((n&val) != 0) {
                // 有右子树
                // 减去左边的满二叉树
                n = n-val;
                // 将左边的满二叉树累加到结果中
                res += dp[i+1];
                if (pre == 1) {
                    // 如果上一层是1，所以这一次右子树，只能累加上左边的满二叉树，后续不继续计算了。
                    break;
                }
                // 此次为右子树，所以对于下层遍历，pre为1
                pre = 1;
            } else {
                // 无右子树
                pre = 0;
            }
            // 由于dp[1]为1，所以最后会少计数一次，也很多人看不懂这里的原因
            if (i == 0) res++;
        }
        return res;
    }
}

# 678. 有效的括号字符串

class Solution {
    public boolean checkValidString(String s) {
        int max = 0, min = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                max++;
                min++;
            } else if (c == ')') {
                max--;
                min = Math.max(min-1, 0);
                if (max < 0) {
                    return false;
                }
            } else if (c == '*') {
                max++;
                min = Math.max(min-1, 0);
            }
        }
        return min == 0;
    }
}

# 447. 回旋镖的数量

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        Map<Integer, Map<String, Integer>> map = new HashMap<>();
        int n = points.length;
        for (int i = 0; i < n; i++) {
            int[] a = points[i];
            for (int j = i+1; j < n; j++) {
                int[] b = points[j];
                int dist = getDist(a[0], b[0], a[1], b[1]);
                Map<String, Integer> pcount = map.getOrDefault(dist, new HashMap<>());
                String ak = getKey(a);
                String bk = getKey(b);
                pcount.put(ak, pcount.getOrDefault(ak, 0)+1);
                pcount.put(bk, pcount.getOrDefault(bk, 0)+1);
                map.put(dist, pcount);
            }
        }

        int res = 0;
        for (Map<String, Integer> m : map.values()) {
            for (Map.Entry<String, Integer> entry : m.entrySet()) {
                String k = entry.getKey();
                int v = entry.getValue();
                res += v*(v-1);
            }
        }
        return res;
    }

    private int getDist(int x1, int x2, int y1, int y2) {
        int x = x1-x2;
        int y = y1-y2;
        return (x*x)+(y*y);
    }

    private String getKey(int[] p) {
        return p[0] + "-" + p[1];
    }
}

# 524. 通过删除字母匹配到字典里最长单词

class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        int n = s.length();
        String res = "";
        for (String d : dictionary) {
            int i = 0, j = 0;
            int m = d.length();
            while (i < n && j < m) {
                if (s.charAt(i) == d.charAt(j)) {
                    j++;
                }
                i++;
            }
            if (j == m) {
                if (m > res.length() || (m == res.length()&& d.compareTo(res) < 0)) {
                    res = d;
                }
            }
        }
        return res;
    }
}

动态规划，经典字符串dp：

class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        int m = s.length();
        int[][] f = new int[m + 1][26];
        Arrays.fill(f[m], m);

        for (int i = m - 1; i >= 0; --i) {
            for (int j = 0; j < 26; ++j) {
                if (s.charAt(i) == (char) ('a' + j)) {
                    f[i][j] = i;
                } else {
                    f[i][j] = f[i + 1][j];
                }
            }
        }

        // System.out.println(Arrays.deepToString(f));
        String res = "";
        for (String d : dictionary) {
            int n = d.length();
            int k = 0;
            int i = 0;
            while (i < n) {
                // k表示当前字符在s中的什么位置
                k = f[k][d.charAt(i)-'a'];
                if (k >= m) break;
                // k+1表示从下一个位置开始，求在s中下一个位置在哪
                k++;
                i++;
            }
            // System.out.println("d:"+d+"; k:"+k);
            if (i == n) {
                if (n > res.length() || (n == res.length() && d.compareTo(res) < 0)) {
                    res = d;
                }
            }
        }

        return res;
    }
}

# 212. 单词搜索 II

Trie前缀树、字典树： 套用的模板，但效率较低

class Solution {
    int[] dr = new int[]{1, 0, -1, 0};
    int[] dc = new int[]{0, 1, 0, -1};
    Set<String> set = new HashSet<>();
    int row;
    int col;
    public List<String> findWords(char[][] board, String[] words) {
        Trie trie = new Trie();
        for (String w : words) {
            trie.insert(w);
        }
        row = board.length;
        col = board[0].length;
        StringBuilder path = new StringBuilder();
        for (int r = 0 ; r < row; r++) {
            for (int c = 0; c < col; c++) {
                char w = board[r][c];
                board[r][c] = '#';
                path.append(w);
                dfs(board, r, c, trie, path);
                board[r][c] = w;
                path = path.deleteCharAt(path.length()-1);
            }
        }
        return new ArrayList<>(set);
    }

    public void dfs(char[][] board, int r, int c, Trie trie, StringBuilder path) {
        int ans = trie.search(path.toString());
        // System.out.println(path.toString());
        if (ans == -1) {
            // System.out.println("no match");
            return;
        }
        if (ans == 1) {
            set.add(path.toString());
        }

        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr < 0 || nr >= row || nc < 0 || nc >= col || board[nr][nc] == '#') {
                continue;
            }
            char w = board[nr][nc];
            board[nr][nc] = '#';
            path.append(w);
            // System.out.println(path.toString());
            dfs(board, nr, nc, trie, path);
            board[nr][nc] = w;
            path = path.deleteCharAt(path.length()-1);
            // System.out.println(path.toString());
        }

    }

    class TrieNode {
        boolean end;
        TrieNode[] ns = new TrieNode[26];
    }

    class Trie {
        TrieNode root;
        Trie() {
            root = new TrieNode();
        }

        public void insert(String word) {
            TrieNode p = root;
            for (int i = 0; i < word.length(); i++) {
                int c = (int) (word.charAt(i)-'a');
                if (p.ns[c] == null) {
                    p.ns[c] = new TrieNode();
                }
                p = p.ns[c];
            } 
            p.end = true;
        }

        /**
            -1 no exist
            0 prefix match
            1 whole match
         */
        public int search(String word) {
            if (word.equals("")) return 0;
            TrieNode p = root;
            for (int i = 0; i < word.length(); i++) {
                int c = (int) (word.charAt(i)-'a');
                if (p.ns[c] == null) return -1;
                p = p.ns[c];
            }
            return p.end ? 1 : 0;
        }
    }
}

优化，删除trie树中已经找到的word：

class Solution {
    int[] dr = new int[]{1, 0, -1, 0};
    int[] dc = new int[]{0, 1, 0, -1};
    Set<String> set = new HashSet<>();
    int row;
    int col;
    public List<String> findWords(char[][] board, String[] words) {
        Trie trie = new Trie();
        for (String w : words) {
            trie.insert(w);
        }
        row = board.length;
        col = board[0].length;
        StringBuilder path = new StringBuilder();
        for (int r = 0 ; r < row; r++) {
            for (int c = 0; c < col; c++) {
                char w = board[r][c];
                board[r][c] = '#';
                path.append(w);
                dfs(board, r, c, trie, path);
                board[r][c] = w;
                path = path.deleteCharAt(path.length()-1);
            }
        }
        return new ArrayList<>(set);
    }

    public void dfs(char[][] board, int r, int c, Trie trie, StringBuilder path) {
        int ans = trie.search(path.toString());
        // System.out.println(path.toString());
        if (ans == -1) {
            // System.out.println("no match");
            return;
        }
        if (ans == 1) {
            set.add(path.toString());
        }

        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr < 0 || nr >= row || nc < 0 || nc >= col || board[nr][nc] == '#') {
                continue;
            }
            char w = board[nr][nc];
            board[nr][nc] = '#';
            path.append(w);
            // System.out.println(path.toString());
            dfs(board, nr, nc, trie, path);
            board[nr][nc] = w;
            path = path.deleteCharAt(path.length()-1);
            // System.out.println(path.toString());
        }

    }

    class TrieNode {
        boolean end;
        TrieNode[] ns = new TrieNode[26];
        int count = 0;
    }

    class Trie {
        TrieNode root;
        Trie() {
            root = new TrieNode();
        }

        public void insert(String word) {
            TrieNode p = root;
            for (int i = 0; i < word.length(); i++) {
                int c = (int) (word.charAt(i)-'a');
                if (p.ns[c] == null) {
                    p.ns[c] = new TrieNode();
                }
                p = p.ns[c];
            } 
            p.end = true;
            root.ns[(int) (word.charAt(0)-'a')].count++;
        }

        /**
            -1 no exist
            0 prefix match
            1 whole match
         */
        public int search(String word) {
            if (word.equals("")) return 0;
            TrieNode p = root;
            
            for (int i = 0; i < word.length(); i++) {
                int c = (int) (word.charAt(i)-'a');
                if (p.ns[c] == null || root.ns[(int) (word.charAt(0)-'a')].count == 0) return -1;
                p = p.ns[c];
            }
            int ans = p.end ? 1 : 0;
            if (p.end) {
                p.end = false;
                root.ns[(int) (word.charAt(0)-'a')].count--;
            }
            return ans;
        }
    }
}

# 292. Nim 游戏

博弈论：

class Solution {
    public boolean canWinNim(int n) {
        return n % 4 != 0;
    }
}

# 650. 只有两个键的键盘

分解质因数：

class Solution {
    public int minSteps(int n) {
        int[] dp = new int[n+1];
        for (int i = 2; i <= n; i++) {
            if (dp[i] == 0)  dp[i] = i;
            for (int j = 2*i, k = 2; j <= j*j && j <= n; j+=i, k++) {
                dp[j] = dp[i] + 1 + (k-1);
            }
        }
        return dp[n];
    }
}

试除法，累加最小质因数：

class Solution {
    public int minSteps(int n) {
        int res = 0;
        for (int i = 2; i*i <= n; i++) {
            while (n % i == 0) {
                res += i;
                n /= i;
            }
        }
        if (n != 1) res += n;
        return res;
    }
}

# 713. 乘积小于K的子数组

暴力：

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int n = nums.length;
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            int ans = 1;
            for (int j = i; j < n; j++) {
                if (ans*nums[j] >= k) {
                    break;
                }
                cnt++;
                ans *= nums[j];
            }
        }
        return cnt;
    }
}

滑动窗口：关键是需要遍历right的边界，这样计算不会重复。

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int n = nums.length;
        int cnt = 0, sum = 1, l = 0;
        for (int r = 0; r < n; r++) {
            sum *= nums[r];
            while (sum >= k && l <= r) {
                sum /= nums[l++];
            }
            if (sum < k) cnt += r-l+1;
        }
        return cnt;
    }
}

# 673. 最长递增子序列的个数

动态规划，时间复杂度为n^2：

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int[] count = new int[n];
        int max = 0;
        int res = 0;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            int cnt = 1;
            for (int j = i-1; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    int cmax = dp[j]+1;
                    if (cmax > dp[i]) {
                        cnt = count[j];
                        dp[i] = cmax;
                    } else if (cmax == dp[i]) {
                        cnt += count[j];
                    }
                }
            }
            count[i] = cnt;
            if (dp[i] > max) {
                max = dp[i];
                res = cnt;
            } else if (dp[i] == max){
                res += cnt;
            }
        }
        return res;
    }
}

更优的dp方案，但实现起来比较复杂，时间复杂度为nlogn： 动态规划+二分

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        List<List<Integer>> dp = new ArrayList<>();
        List<List<Integer>> cnt = new ArrayList<>();
        cnt.add(0, Arrays.asList(1));
        dp.add(0, Arrays.asList(0, 0));
        for (int i = 0; i < n; i++) {
            insert(dp, cnt, nums[i]);
        }

        int sum = 0;
        for (int i : cnt.get(dp.size()-1)) {
            sum += i;
        }
        return sum;
    }

    public void insert(List<List<Integer>> dp, List<List<Integer>> cnt, int t) {
        int n = dp.size();
        int left = 1, right = n-1;
        while (left <= right) {
            // System.out.println("left:"+left+"; right:"+right);
            int mid = left + ((right-left)>>1);
            List<Integer> dpList = getDefault(dp, mid);
            if (t > dpList.get(dpList.size()-1)) {
                left = mid+1;
            } else {
                right = mid-1;
            }
        }
        
        
        List<Integer> list2 = getDefault(dp, left);
        list2.add(t);

        
        // 去dp的left-1行搜索可累加的计数
        List<Integer> row = getDefault(dp, left-1);
        int rl = 0, rr = row.size()-1;
        while (rl <= rr && row.size() > 0 && left > 1) {
            int mid = rl + ((rr-rl)>>1);
            if (t <= row.get(mid)) {
                rl = mid+1;
            } else {
                rr = mid-1;
            }
        } 

        int size = 0;
        List<Integer> sumList = getDefault(cnt, left-1);
        for (int i = sumList.size()-1; i >= rl; i--) {
            size += sumList.get(i);
            
        }
        
        List<Integer> cntList = getDefault(cnt, left);
        cntList.add(size);

        // System.out.println("rl:"+rl);
        // System.out.println(dp);
        // System.out.println(cnt);
        // System.out.println(left);
    }

    public List<Integer> getDefault(List<List<Integer>> list, int index) {
        int size = list.size();
        List<Integer> res;
        if (index >= size) {
            res = new ArrayList<>();
            list.add(index, res);
        } else {
            res = list.get(index);
        }
        return res;
    }
}

继续优化，利用前缀和加快计算：

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        List<List<Integer>> dp = new ArrayList<>();
        List<List<Integer>> cnt = new ArrayList<>();
        cnt.add(0, Arrays.asList(1));
        dp.add(0, Arrays.asList(0, 0));
        for (int i = 0; i < n; i++) {
            insert(dp, cnt, nums[i]);
        }
        List<Integer> sumList = cnt.get(dp.size()-1);
        return sumList.get(sumList.size()-1);
    }

    public void insert(List<List<Integer>> dp, List<List<Integer>> cnt, int t) {
        int n = dp.size();
        int left = 1, right = n-1;
        while (left <= right) {
            int mid = left + ((right-left)>>1);
            List<Integer> dpList = getDefault(dp, mid);
            if (t > dpList.get(dpList.size()-1)) {
                left = mid+1;
            } else {
                right = mid-1;
            }
        }
        
        List<Integer> list2 = getDefault(dp, left);
        list2.add(t);

        
        // 去dp的left-1行搜索可累加的计数
        List<Integer> row = getDefault(dp, left-1);
        int rl = 0, rr = row.size()-1;
        while (rl <= rr && row.size() > 0 && left > 1) {
            int mid = rl + ((rr-rl)>>1);
            if (t <= row.get(mid)) {
                rl = mid+1;
            } else {
                rr = mid-1;
            }
        } 

        // 计算前一行的前缀和
        List<Integer> sumList = getDefault(cnt, left-1);
        int size;
        if (left > 1) {
            size = sumList.get(sumList.size()-1) - (rl == 0 ? 0 : sumList.get(rl-1));
        } else {
            size = 1;
        }

        // 累加到当前行的前缀和上
        List<Integer> cntList = getDefault(cnt, left);
        size += cntList.size() > 0 ? cntList.get(cntList.size()-1) : 0;
        cntList.add(size);

        // System.out.println("rl:"+rl);
        // System.out.println(dp);
        // System.out.println(cnt);
        // System.out.println(left);
    }

    public List<Integer> getDefault(List<List<Integer>> list, int index) {
        int size = list.size();
        List<Integer> res;
        if (index >= size) {
            res = new ArrayList<>();
            list.add(index, res);
        } else {
            res = list.get(index);
        }
        return res;
    }
}

# 58. 最后一个单词的长度

class Solution {
    public int lengthOfLastWord(String s) {
        int n = s.length(), len = 0;
        for (int i = n-1; i >= 0; i--) {
            if (s.charAt(i) == ' ') {
                continue;
            } else {
                while (i >= 0) {
                    if (s.charAt(i) == ' ') {
                        return len;
                    } else {
                        len++;
                    }
                    i--;
                }
            }
        }
        return len;
    }
}

# 438. 找到字符串中所有字母异位词

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        Map<Integer, Integer> match = new HashMap<>();
        Map<Integer, Integer> cur = new HashMap<>();
        for (int i = 0; i < 26; i++) {
            match.put(i, 0);
            cur.put(i, 0);
        }
        for (char pc : p.toCharArray()) {
            int pi = (int) (pc-'a');
            match.put(pi, match.get(pi)+1);
        }

        int sn = s.length(), pn = p.length(), l = 0, r = 0;
        List<Integer> res = new ArrayList<>();
        if (pn > sn) return res;

        while (r < sn) {
            int ri = (int) (s.charAt(r)-'a');
            cur.put(ri, cur.get(ri)+1);
            r++;

            if (r-l > pn) {
                int li = (int) (s.charAt(l)-'a');
                cur.put(li, cur.get(li)-1);
                l++;
            }

            if (match.equals(cur)) {
                res.add(l);
            }
        }
        return res;
    }
}

# 117. 填充每个节点的下一个右侧节点指针 II

class Solution {
    public Node connect(Node root) {
        if (root == null) return null;
        Queue<Node> q = new LinkedList<>();
        q.offer(root);

        while (!q.isEmpty()) {
            int n = q.size();
            Node pre = null;
            for (int i = 0; i < n; i++) {
                Node cur = q.poll();
                if (cur.left != null) q.offer(cur.left);
                if (cur.right != null) q.offer(cur.right);
                // System.out.print(cur.val);
                if (pre == null) {
                    pre = cur;
                    continue;
                }
                pre.next = cur;
                pre = cur;
            }
        }
        return root;
    }
}

# 572. 另一棵树的子树

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) return false;

        if (root.val == subRoot.val) {
            if (sub(root, subRoot)) {
                return true;
            }
        }

        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    public boolean sub(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) return true;
        if (root == null && subRoot != null) return false;
        if (root != null && subRoot == null) return false;
        if (root.val != subRoot.val) {
            return false;
        }
        return sub(root.left, subRoot.left) && sub(root.right, subRoot.right);
    }
}

# 725. 分隔链表

class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        int sum = 0;
        ListNode se = head;
        while (se != null) {
            sum++;
            se = se.next;
        }

        int num = sum/k;
        int re = sum%k;
        
        ListNode[] res = new ListNode[k];
        int index = 0;
        se = head;
        while (k > 0) {
            int cnum = num;
            ListNode end = se;
            while (cnum > 0) {
                if (res[index] == null) {
                    res[index] = se;
                }
                end = se;
                se = se.next;
                cnum--;
            }
            if (re > 0) {
                if (res[index] == null) {
                    res[index] = se;
                }
                end = se;
                se = se.next;
                re--;
            }
            if (end != null) {
                end.next = null;
            }
            index++;
            k--;
        }

        // System.out.println(num);
        return res;
    }
}

# 1091. 二进制矩阵中的最短路径

class Solution {
    int[] dr = new int[]{1, 1, 0, -1, -1, -1, 0, 1};
    int[] dc = new int[]{0, 1, 1, 1, 0, -1, -1, -1};
    public int shortestPathBinaryMatrix(int[][] grid) {
        if (grid[0][0] != 0) return -1;
        int row = grid.length;
        int col = grid[0].length;
        int[][] visited = new int[row][col];
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{0, 0});
        visited[0][0] = 1;
        int len = 1;
        while (!q.isEmpty()) {
            int n = q.size();
            for (int i = 0; i < n; i++) {
                int[] cur = q.poll();
                if (cur[0] == row-1 && cur[1] == col-1) {
                    return len;
                }
                for (int k = 0; k < 8; k++) {
                    int r = cur[0] + dr[k];
                    int c = cur[1] + dc[k];
                    if (r >= 0 && r < row && c >= 0 && c < col && grid[r][c] == 0 && visited[r][c] != 1) {
                        q.offer(new int[]{r, c});
                        visited[r][c] = 1;
                    }
                }
            }
            len++;
        }
        return -1;
    }
}

# 383. 赎金信

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] a = new int[26];
        int[] b = new int[26];
        for (char c : ransomNote.toCharArray()) {
            a[c-'a']++;
        }
        for (char c : magazine.toCharArray()) {
            b[c-'a']++;
        }
        for (int i = 0; i < 26; i++) {
            if (a[i] - b[i] > 0) return false;
        }
        return true;
    }
}

几个月后的每日一题，代码写得更清晰了

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] set = new int[26];
        for (char c : magazine.toCharArray()) {
            set[c-'a']++;
        }
        for (char c : ransomNote.toCharArray()) {
            if (set[c-'a'] == 0) {
                return false;
            } else {
                set[c-'a']--;
            }
        }
        return true;
    }
}

# 653. 两数之和 IV - 输入 BST

class Solution {
    public boolean findTarget(TreeNode root, int k) {
        List<Integer> list = new ArrayList<>();
        dfs(root, list);
        // System.out.println(list);
        int l = 0, r = list.size()-1;
        while (l < r) {
            int sum = list.get(l) + list.get(r);
            if (sum > k) {
                r--;
            } else if (sum < k) {
                l++;
            } else {
                return true;
            }
        }
        return false;
    }

    public void dfs(TreeNode node, List<Integer> list) {
        if (node == null) {
            return;
        }
        dfs(node.left, list);
        list.add(node.val);
        dfs(node.right, list);
    }
}

# 112. 路径总和

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        return dfs(root, 0, targetSum);
    }

    public boolean dfs(TreeNode node, int sum, int t) {
        if (node == null) {
            return false;
        }
        sum += node.val;
        if (node.left == null && node.right == null) {
            return sum == t;
        } else {
            return dfs(node.left, sum, t) || dfs(node.right, sum, t);
        }
    }
}

# 18. 四数之和

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] == nums[i-1]) {
                continue;
            }
            int a = nums[i];
            for (int j = i+1; j < n; j++) {
                if (j > i+1 && nums[j] == nums[j-1]) {
                    continue;
                }
                int b = nums[j];
                int t = target - (a + b);
                int l = j+1, r = n-1;
                while (l < r) {
                    while (l < r && l > j+1 && nums[l] == nums[l-1]) {
                        l++;
                    }
                    while (l < r && r < n-1 && nums[r] == nums[r+1]) {
                        r--;
                    }
                    if (l >= r) break;
                    int sum = nums[l] + nums[r];
                    if (sum > t) {
                        r--;
                    } else if (sum < t) {
                        l++;
                    } else {
                        res.add(Arrays.asList(a, b, nums[l], nums[r]));
                        l++;
                        r--;
                    }
                }
            }
        }
        return res;
    }
}

# 496. 下一个更大元素 I

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < nums2.length; i++) {
            while (!stack.empty() && nums2[i] > stack.peek()) {
                int p = stack.pop();
                map.put(p, nums2[i]);
            }
            stack.push(nums2[i]);
        }
        while (!stack.empty()) {
            map.put(stack.pop(), -1);
        }
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            res[i] = map.get(nums1[i]);
        }
        return res;
    }
}

# 430. 扁平化多级双向链表

class Solution {
    public Node flatten(Node head) {
        if (head == null) return null;
        Node parent = new Node();
        parent.child = head;
        dfs(parent, head);
        Node res = parent.next;
        res.prev = null;
        return res;
    }

    public Node dfs(Node parent, Node head) {
        parent.next = head;
        head.prev = parent;
        parent.child = null;
        Node pre = null;
        while (head != null) {
            if (head.child != null) {
                Node next = head.next;
                pre = dfs(head, head.child);
                pre.next = next;
                if (next != null) next.prev = pre;
                head = pre.next;
            } else {
                pre = head;
                head = head.next;
            }
        }
        return head == null ? pre : head;
    }
}

重刷再写，并没有将代码简化，对于递归，思路还是不够清晰

class Solution {
    public Node flatten(Node head) {
        if (head == null) return head;
        Node res = head;
        flatten(null, head);
        return res;
    }

    private Node flatten(Node parent, Node head) {
        if (parent != null) {
            parent.next = head;
        }
        head.prev = parent;
        Node pre = head;
        while (head != null) {
            if (head.child != null) {
                Node next = head.next;
                Node last = flatten(head, head.child);
                head.child = null;
                if (next != null) {
                    last.next = next;
                    next.prev = last;
                }
                head = last;
            }
            pre = head;
            head = head.next;
        }
        return pre;
    }
}

# 720. 词典中最长的单词

class Solution {
    public String longestWord(String[] words) {
        Map<Integer, List<String>> map = new HashMap<>();
        int max = 0;
        for (String w : words) {
            int len = w.length();
            List<String> list = map.getOrDefault(len, new ArrayList<>());
            list.add(w);
            map.put(len, list);
            max = Math.max(max, len);
        }

        Trie t = new Trie();
        for (int i = 1; i <= max; i++) {
            List<String> list = map.get(i);
            if (list == null) continue;
            for (String s : list) {
                t.insert(s);
            }
        }

        return t.res;
    }

    class Trie {
        String res = "";
        int max = 0;
        class TrieNode {
            boolean end;
            TrieNode[] tns = new TrieNode[26];
        }
        TrieNode root;
        public Trie() {
            root = new TrieNode();
        }
        public void insert(String s) {
            TrieNode p = root;
            boolean onlyOne = true;
            for (int i = 0; i < s.length(); i++) {
                int u = s.charAt(i)-'a';
                if (!onlyOne) return;
                if (p.tns[u] == null && onlyOne) {
                    onlyOne = false;
                    p.tns[u] = new TrieNode();
                } else if (p.tns[u] != null && !p.tns[u].end) {
                    return;
                }
                p = p.tns[u];
            }
            p.end = true;
            if (s.length() > max) {
                max = s.length();
                res = s;
            } else if (s.length() == max) {
                res = s.compareTo(res) < 0 ? s : res;
            }
        }
    }
}

# 583. 两个字符串的删除操作

动态规划：

class Solution {
    public int minDistance(String word1, String word2) {
        int n1 = word1.length();
        int n2 = word2.length();
        int[][] dp = new int[n1+1][n2+1];
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (word1.charAt(i-1) == word2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }
        int len = dp[n1][n2];
        return (n1-len) + (n2-len);
    }
}

# 1042. 不邻接植花

class Solution {
    public int[] gardenNoAdj(int n, int[][] paths) {
        Map<Integer, List<Integer>> adj = new HashMap<>();
        for (int i = 0; i < paths.length; i++) {
            List<Integer> x = adj.getOrDefault(paths[i][0], new ArrayList<>());
            List<Integer> y = adj.getOrDefault(paths[i][1], new ArrayList<>());
            x.add(paths[i][1]);
            y.add(paths[i][0]);
            adj.put(paths[i][0], x);
            adj.put(paths[i][1], y);
        }
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            boolean[] used = new boolean[5];
            List<Integer> list = adj.get(i+1);
            if (list != null) {
                for (int j : list) {
                    used[res[j-1]] = true;
                }
            }
            for (int j = 1; j <= 4; j++) {
                if (!used[j]) {
                    res[i] = j;
                    break;
                }
            }
        }
        return res;
    }
}

# 97. 交错字符串

动态规划：

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int n = s3.length();
        int n1 = s1.length();
        int n2 = s2.length();
        if (n1+n2 != n) return false;
        boolean[][] dp = new boolean[n1+1][n2+1];
        dp[0][0] = true;
        for (int i = 0; i <= n1; i++) {
            for (int j = 0; j <= n2; j++) {
                int p = i+j-1;
                if (i > 0) {
                    dp[i][j] |= s1.charAt(i-1) == s3.charAt(p) && dp[i-1][j];
                }
                if (j > 0) {
                    dp[i][j] |= s2.charAt(j-1) == s3.charAt(p) && dp[i][j-1];
                }
            }
        }
        return dp[n1][n2];
    }
}

# 639. 解码方法 II

动态规划 全是条件分支，一座屎山：

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        long[] dp = new long[n+1];
        dp[0] = 1;
        int mod = (int)1e9+7;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == '0') {
                if (i == 0) {
                    return 0;
                } else {
                    char pre = s.charAt(i-1);
                    if (pre != '1' && pre != '2' && pre != '*') {
                        return 0;
                    } else if (pre == '1' || pre == '2'){
                        dp[i+1] = dp[i-1];
                    } else if (pre == '*') {
                        dp[i+1] = dp[i-1]*2;
                    }
                }
            } else {
                // c != '0'
                dp[i+1] = (dp[i] * (c=='*'?9:1)) % mod;
                if (i == 0) continue;
                char pre = s.charAt(i-1);
                if (c == '*') {
                    int multi = 0;
                    if (pre == '2') {
                        multi = 6;
                    } else if (pre == '1') {
                        multi = 9;
                    } else if (pre == '*') {
                        multi = 15;
                    }
                    dp[i+1] = (dp[i+1] + dp[i-1]*multi) % mod;
                } else if (pre == '*') {
                    if (c-'0' <= 6) {
                        dp[i+1] = (dp[i+1] + dp[i-1]*2) % mod;
                    } else {
                        dp[i+1] = dp[i+1] + dp[i-1];
                    }
                } else if (pre != '0' && (pre-'0')*10+(c-'0') <= 26) {
                    dp[i+1] = dp[i+1] + dp[i-1];
                }
            }
        }

        return (int)dp[n];
    }
}

# 47. 全排列 II

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        dfs(nums, new ArrayList<>(), used);
        return res;
    }
    public void dfs(int[] nums, List<Integer> path, boolean[] used) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i-1] && !used[i] && !used[i-1]) {
                continue;
            }
            if (used[i]) continue;
            path.add(nums[i]);
            used[i] = true;
            dfs(nums, path, used);
            path.remove(path.size()-1);
            used[i] = false;
        }
    }
}

# 437. 路径总和 III

class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    int res = 0;
    public int pathSum(TreeNode root, int targetSum) {
        map.put(0, 1);
        dfs(root, targetSum, 0);
        return res;
    }
    public void dfs(TreeNode node, int t, int sum) {
        if (node == null) {
            return;
        }
        sum += node.val;
        res += map.getOrDefault(sum-t, 0);
        map.put(sum, map.getOrDefault(sum, 0)+1);
        dfs(node.left, t, sum);
        dfs(node.right, t, sum);
        map.put(sum, map.get(sum)-1);

    }
}

# 419. 甲板上的战舰

class Solution {
    public int countBattleships(char[][] board) {
        int row = board.length;
        int col = board[0].length;
        int cnt = 0;
        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                if (board[r][c] == 'X') {
                    boolean up = r == 0 || board[r-1][c] == '.';
                    boolean left = c == 0 || board[r][c-1] == '.';
                    if (up && left) {
                        cnt++;
                    }
                }
            }
        }
        return cnt;
    }
}

class Solution {
    public int countBattleships(char[][] board) {
        int cnt = 0;
        int row = board.length, col = board[0].length;
        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                if (board[r][c] == 'X') {
                    if (!(r > 0 && board[r-1][c] == 'X') && !(c > 0 && board[r][c-1] == 'X')) {
                        cnt++;
                    }
                }
            }
        }
        return cnt;
    }
}

# 517. 超级洗衣机

class Solution {
    public int findMinMoves(int[] machines) {
        int n = machines.length, sum = 0;
        for (int m : machines) {
            sum += m;
        }
        if (sum % n != 0) return -1;
        int avg = sum / n;
        int res = 0, pre = 0;
        for (int i = 0; i < n; i++) {
            pre += machines[i];
            res = Math.max(res, Math.max(machines[i]-avg, Math.abs(pre-(i+1)*avg)));
        }
        return res;
    }
}

# 405. 数字转换为十六进制数

class Solution {
    public String toHex(int num) {
        if (num == 0) return "0";
        StringBuilder sb = new StringBuilder();
        for (int i = 7; i >= 0; i--) {
            int val = (num >> (4*i)) & 0xf;
            if (sb.length() > 0 || val > 0) {
                char c = val >= 10 ?(char)(val-10+'a') : (char)(val+'0');
                sb.append(c);
            }
        }
        return sb.toString();
    }
}

class Solution {
    private static char[] map;
    static {
        map = new char[16];
        map[10] = 'a';
        map[11] = 'b';
        map[12] = 'c';
        map[13] = 'd';
        map[14] = 'e';
        map[15] = 'f';
    }
    public String toHex(int num) {
        int mask = 15;
        int i = 1;
        StringBuilder res = new StringBuilder();
        while (i <= 8) {
            int t = (num >>> 28) & mask;
            if (res.length()>0 || t != 0) {
                char c = (char)(t + '0');
                if (t > 9) c = map[t];
                res.append(c);
            }
            num = num << 4;
            i++;
        }
        if (res.length()==0) res.append('0');
        return res.toString();
    }
}

# 1436. 旅行终点站

class Solution {
    public String destCity(List<List<String>> paths) {
        Map<String, Integer> map = new HashMap<>();
        for (List<String> p : paths) {
            map.put(p.get(0), map.getOrDefault(p.get(0), 0)+1);
            map.put(p.get(1), map.getOrDefault(p.get(1), 0)-1);
        }

        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (entry.getValue() < 0) {
                return entry.getKey();
            }
        }
        return null;
    }
}

接近一遍循环：

class Solution {
    public String destCity(List<List<String>> paths) {
        Set<String> s1 = new HashSet<>();
        Set<String> s2 = new HashSet<>();
        for (List<String> p : paths) {
            if (s2.contains(p.get(0))) {
                s2.remove(p.get(0));
            }
            s1.add(p.get(0));
            
            if (!s1.contains(p.get(1))) {
                s2.add(p.get(1));
            }
        }
        for (String s : s2) {
            return s;
        }
        return null;
    }
}

另一种的思路，更清晰，耗时更少：

class Solution {
    public String destCity(List<List<String>> paths) {
        Map<String, Integer> map = new HashMap<>();
        for (List<String> p : paths) {
            map.put(p.get(0), 1);
        }
        for (List<String> p : paths) {
            if (map.get(p.get(1)) == null) {
                return p.get(1);
            }
        }
        return null;
    }
}

# 482. 密钥格式化

class Solution {
    public String licenseKeyFormatting(String s, int k) {
        int num = 0;
        char[] cs = s.toCharArray();
        for (int i = 0; i < cs.length; i++) {
            if (cs[i] == '-') continue;
            if (cs[i] >= 97) {
                cs[i] = (char) (cs[i]-32);
            }
            num++;
        }
        s = new String(cs);
        StringBuilder res = new StringBuilder();
        int rem = num % k;
        int group = num / k;
        int index = 0;
        if (rem > 0) {
            while (rem > 0) {
                if (s.charAt(index) == '-') {
                    index++;
                    continue;
                }
                res.append(s.charAt(index));
                rem--;
                index++;
            }
            if (group > 0) res.append('-');
        }

        while (group > 0) {
            int kk = k;
            while (kk > 0) {
                if (s.charAt(index) == '-') {
                    index++;
                    continue;
                }
                res.append(s.charAt(index));
                kk--;
                index++;
            }
            group--;
            if (group > 0) res.append('-');
        }
        return res.toString();
    }
}

# 343. 整数拆分

动态规划：

class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n+1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = i-1; j >= 1; j--) {
                dp[i] = Math.max(dp[i], Math.max((i-j)*dp[j], (i-j)*j));
            }
        }
        return dp[n];
    }
}

打标动规，实质上逻辑没做改动，因为输入条件有限，将其置为静态属性，预先计算好：

class Solution {
    static int[] dp;
    static {
        int n = 58;
        dp = new int[n+1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = i-1; j >= 1; j--) {
                dp[i] = Math.max(dp[i], Math.max((i-j)*dp[j], (i-j)*j));
            }
        }
    }
    public int integerBreak(int n) {
        return Solution.dp[n];
    }
}

# 201. 数字范围按位与

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        while (right > left) {
            right &= (right-1);
        }
        return right;
    }
}

# 284. 顶端迭代器

模拟：

// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html

class PeekingIterator implements Iterator<Integer> {
    Iterator<Integer> iterator;
    Queue<Integer> q;
	public PeekingIterator(Iterator<Integer> iterator) {
	    // initialize any member here.
        this.iterator = iterator;
        this.q = new LinkedList<Integer>();
        getNext();
	}
	
    // Returns the next element in the iteration without advancing the iterator.
	public Integer peek() {
        return q.peek();
	}
	
	// hasNext() and next() should behave the same as in the Iterator interface.
	// Override them if needed.
	@Override
	public Integer next() {
        getNext();
        return q.poll();
	}
	
	@Override
	public boolean hasNext() {
	    return !q.isEmpty();
	}

    private void getNext() {
        if (iterator.hasNext()) {
            this.q.offer(iterator.next());
        }
    }
}

# 746. 使用最小花费爬楼梯

入门的动态规划：

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n+3];
        for (int i = 0; i <= n; i++) {
            dp[i+2] = Math.min(dp[i+1], dp[i]);
            if (i < n) dp[i+2] += cost[i];
        }
        return dp[n+2];
    }
}

优化空间

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int res = Integer.MIN_VALUE;
        int n = cost.length;
        int a = 0, b = 0;
        for (int i = 0; i <= n; i++) {
            int min = Math.min(a, b);
            int c = i < n ? cost[i] : 0;
            c += min;
            a = b;
            b = c;
        }
        return b;
    }
}

# 256. 粉刷房子

动态规划：

class Solution {
    public int minCost(int[][] costs) {
        int n = costs.length;
        int[][] dp = new int[n][3];
        dp[0] = costs[0].clone();
        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + costs[i][0];
            dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + costs[i][1];
            dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + costs[i][2];
        }
        return Math.min(dp[n-1][0], Math.min(dp[n-1][1], dp[n-1][2]));
    }
}

# 265. 粉刷房子 II

O(nk^2)

class Solution {
    public int minCostII(int[][] costs) {
        int n = costs.length, k = costs[0].length;
        int[][] dp = new int[n][k];
        dp[0] = costs[0].clone();
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < k; j++) {
                dp[i][j] = Integer.MAX_VALUE;
                for (int l = 0; l < k; l++) {
                    if (j == l) continue;
                    dp[i][j] = Math.min(dp[i][j], dp[i-1][l]);
                }
                dp[i][j] += costs[i][j];
            }
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < k; i++) {
            min = Math.min(min, dp[n-1][i]);
        }
        return min;
    }
}

O(n2k)

class Solution {
    public int minCostII(int[][] costs) {
        int n = costs.length, k = costs[0].length, N = Integer.MAX_VALUE;
        int[][] dp = new int[n][k];
        dp[0] = costs[0].clone();
        int[] p1 = new int[]{N, 0}, p2 = new int[]{N, 0};
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < k && i != 0; j++) {
                if (j != p1[1]) {
                    dp[i][j] = costs[i][j] + p1[0];
                } else {
                    dp[i][j] = costs[i][j] + p2[0];
                }
            }
            p1 = new int[]{N, 0};
            p2 = new int[]{N, 0};
            for (int j = 0; j < k; j++) {
                if (dp[i][j] < p1[0]) {
                    put(p2, p1[0], p1[1]);
                    put(p1, dp[i][j], j);
                } else if (dp[i][j] < p2[0]) {
                    put(p2, dp[i][j], j);
                }
            }
        }      
        return p1[0];
    }

    private void put(int[] p, int a, int b) {
        p[0] = a;
        p[1] = b;
    }
}

O(nk)

class Solution {
    public int minCostII(int[][] costs) {
        int n = costs.length, k = costs[0].length, N = Integer.MAX_VALUE;
        int[][] dp = new int[n][k];
        dp[0] = costs[0].clone();
        int[] p1 = new int[]{N, 0}, p2 = new int[]{N, 0};
        for (int i = 0; i < n; i++) {
            int[] m1 = new int[]{N, 0};
            int[] m2 = new int[]{N, 0};
            for (int j = 0; j < k; j++) {
                if (i != 0) {
                    if (j != p1[1]) {
                        dp[i][j] = costs[i][j] + p1[0];
                    } else {
                        dp[i][j] = costs[i][j] + p2[0];
                    }
                }

                if (dp[i][j] < m1[0]) {
                    put(m2, m1[0], m1[1]);
                    put(m1, dp[i][j], j);
                } else if (dp[i][j] < m2[0]) {
                    put(m2, dp[i][j], j);
                }
            }
            p1 = m1;
            p2 = m2;
        }      
        return p1[0];
    }

    private void put(int[] p, int a, int b) {
        p[0] = a;
        p[1] = b;
    }
}

O(nk),优化空间：

class Solution {
    public int minCostII(int[][] costs) {
        int n = costs.length, k = costs[0].length, N = Integer.MAX_VALUE;
        int[][] dp = new int[n][k];
        dp[0] = costs[0].clone();
        int p1 = N, p2 = N;
        for (int i = 0; i < n; i++) {
            int m1 = N, m2 = N;
            for (int j = 0; j < k; j++) {
                if (i != 0) {
                    if (dp[i-1][j] != p1) {
                        dp[i][j] = costs[i][j] + p1;
                    } else {
                        dp[i][j] = costs[i][j] + p2;
                    }
                }

                if (dp[i][j] < m1) {
                    m2 = m1;
                    m1 = dp[i][j];
                } else if (dp[i][j] < m2) {
                    m2 = dp[i][j];
                }
            }
            p1 = m1;
            p2 = m2;
        }      
        return p1;
    }
}

# 414. 第三大的数

O(nlogn)

class Solution {
    public int thirdMax(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int N = (int) 1e9+7, cnt = 0, pre = N;
        for (int i = n-1; i >= 0; i--) {
            if (nums[i] != pre) {
                cnt++;
                pre = nums[i];
            }
            if (cnt == 3) return nums[i]; 
        }
        return nums[n-1];
    }
}

O(n)

class Solution {
    public int thirdMax(int[] nums) {
        int n = nums.length;
        long N = Long.MIN_VALUE;
        long a = N, b = N, c = N;
        for (int m : nums) {
            if (m >= a) {
                if (m == a) continue;
                c = b;
                b = a;
                a = m;
            } else if (m >= b) {
                if (m == b) continue;
                c = b;
                b = m;
            } else if (m >= c) {
                if (m == c) continue;
                c = m;
            }
        }
        return c == N ? (int)a : (int)c;
    }
}

优化判断条件，使代码更简洁

class Solution {
    public int thirdMax(int[] nums) {
        int n = nums.length;
        long N = Long.MIN_VALUE, a = N, b = N, c = N;
        for (int m : nums) {
            if (m > a) {
                c = b;
                b = a;
                a = m;
            } else if (m > b && m < a) {
                c = b;
                b = m;
            } else if (m > c && m < b) {
                c = m;
            }
        }
        return c == N ? (int)a : (int)c;
    }
}

# 714. 买卖股票的最佳时机含手续费

动态规划

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]+prices[i]-fee);
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0]-prices[i]);
        }
        return dp[n-1][0];
    }
}

空间优化，如果占用空间特别大，申请空间也是非常耗时的，在这道题的用例中能体现出来

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int p0 = 0;
        int p1 = -prices[0];
        for (int i = 1; i < n; i++) {
            int t0 = Math.max(p0, p1+prices[i]-fee);
            int t1 = Math.max(p1, p0-prices[i]);
            p0 = t0;
            p1 = t1;
        }
        return p0;
    }
}

重刷，状态分析比较少还是可以自主做出来的

class Solution {
    public int maxProfit(int[] prices, int fee) {
        // p1持有 p2非持有
        int p1 = -prices[0], p2 = 0;
        for (int i = 1; i < prices.length; i++) {
            int c1 = Math.max(p2-prices[i], p1);
            int c2 = Math.max(p1+prices[i]-fee, p2);
            p1 = c1;
            p2 = c2;
        }
        return p2;
    }
}

# 487. 最大连续1的个数 II

动态规划

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n+1][2];
        int max = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 1) {
                dp[i+1][0] = dp[i][0] + 1;
                dp[i+1][1]  = dp[i][1] + 1;
            } else {
                dp[i+1][0] = 0;
                dp[i+1][1] = dp[i][0] + 1;
            }
            max = Math.max(max, Math.max(dp[i+1][0], dp[i+1][1]));
        }
        return max;
    }
}

空间优化：

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int n = nums.length;
        int max = 0;
        int p0 = 0, p1 = 0;
        for (int i = 0; i < n; i++) {
            int t0 = 0, t1 = 0;
            if (nums[i] == 1) {
                t0 = p0 + 1;
                t1 = p1 + 1;
            } else {
                t0 = 0;
                t1 = p0 + 1;
            }
            p0 = t0;
            p1 = t1;
            max = Math.max(max, Math.max(p0, p1));
        }
        return max;
    }
}

# 434. 字符串中的单词数

class Solution {
    public int countSegments(String s) {
        int cnt = 0;
        char[] cs = s.toCharArray();
        for (int i = 0; i < cs.length; i++) {
            if (cs[i] != ' ') cnt++;
            while (i < cs.length && cs[i] != ' ') {
                i++;
            }
        }
        return cnt;
    }
}

# 931. 下降路径最小和

动态规划

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix[0].length, N = (int)1e9+7;
        int[] dp = new int[n];
        for (int i = 0; i < matrix.length; i++) {
            int[] t = new int[n];
            for (int j = 0; j < n; j++) {
                t[j] = Math.min(dp[j], Math.min(j-1>=0 ? dp[j-1] : N, j+1<n ? dp[j+1] : N)) + matrix[i][j];
            }
            dp = t;
        }
        int min = N;
        for (int i = 0; i < n; i++) min = Math.min(min, dp[i]);
        return min;
    }
}

# 376. 摆动序列

动态规划

class Solution {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][2];
        int max = 0;
        for (int i = 0; i < n; i++) {
            dp[i][0] = 1;
            dp[i][1] = 1;
            for (int j = i-1; j >= 0; j--) {
                dp[i][0] = Math.max(dp[i][0], nums[j]>nums[i] ? dp[j][1]+1 : 0);
                dp[i][1] = Math.max(dp[i][1], nums[j]<nums[i] ? dp[j][0]+1 : 0);
            }
            max = Math.max(max, Math.max(dp[i][0], dp[i][1]));
        }
        return max;
    }
}

# 1746. 经过一次操作后的最大子数组和

动态规划

class Solution {
    public int maxSumAfterOperation(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][2];
        dp[0][0] = nums[0];
        dp[0][1] = nums[0]*nums[0];
        int max = Math.max(dp[0][0], dp[0][1]);
        for (int i = 1; i < n; i++) {
            if (dp[i-1][0] <= 0) {
                dp[i][0] = nums[i];
                dp[i][1] = nums[i]*nums[i];
            } else {
                dp[i][0] = dp[i-1][0] + nums[i];
                dp[i][1] = dp[i-1][0] + (nums[i]*nums[i]);
            }

            if (dp[i-1][1] <= 0) {
                dp[i][1] = Math.max(dp[i][1], nums[i]);
            } else {
                dp[i][1] = Math.max(dp[i][1], dp[i-1][1]+nums[i]);
            }
            max = Math.max(max, Math.max(dp[i][0], dp[i][1]));
        }
        return max;
    }
}

空间优化：

class Solution {
    public int maxSumAfterOperation(int[] nums) {
        int n = nums.length;
        int p0 = nums[0], p1 = nums[0]*nums[0];
        int max = Math.max(p0, p1);
        for (int i = 1; i < n; i++) {
            int t0 = 0, t1 = 0;
            if (p0 <= 0) {
                t0 = nums[i];
                t1 = nums[i]*nums[i];
            } else {
                t0 = p0 + nums[i];
                t1 = p0 + (nums[i]*nums[i]);
            }

            if (p1 <= 0) {
                t1 = Math.max(t1, nums[i]);
            } else {
                t1 = Math.max(t1, p1+nums[i]);
            }
            p0 = t0;
            p1 = t1;
            max = Math.max(max, Math.max(p0, p1));
        }
        return max;
    }
}

# 1230. 抛掷硬币

动态规划

class Solution {
    public double probabilityOfHeads(double[] prob, int target) {
        int n = prob.length;
        double[][] dp = new double[n][n+1];
        dp[0][0] = 1-prob[0];
        dp[0][1] = prob[0];
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = dp[i-1][j]*(1-prob[i]) + (j-1>=0 ? dp[i-1][j-1]*prob[i] : 0);
            }
        }
        return dp[n-1][target];
    }
}

# 712. 两个字符串的最小ASCII删除和

动态规划

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int n1 = s1.length(), n2 = s2.length();
        int[][] dp = new int[n1+1][n2+1];
        
        for (int i = 1; i <= n1; i++) {
            dp[i][0] = dp[i-1][0] + s1.charAt(i-1);
        }
        for (int i = 1; i <= n2; i++) {
            dp[0][i] = dp[0][i-1] + s2.charAt(i-1);
        }

        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (s1.charAt(i-1) == s2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = Math.min(dp[i-1][j]+s1.charAt(i-1), dp[i][j-1]+s2.charAt(j-1));
                }
            }
        }
        return dp[n1][n2];
    }
}

# 187. 重复的DNA序列

滑动窗口

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        int n = s.length();
        Set<String> set = new HashSet<>();
        Set<String> res = new HashSet<>();
        if (n < 10) return new ArrayList<>();
        int l = 0, r = 9;
        while (r < n) {
            String p = s.substring(l, r+1);
            if (!set.add(p)) {
                res.add(p);
            }
            l++;
            r++;
        }
        return new ArrayList<>(res);
    }
}

# 1048. 最长字符串链

动态规划

class Solution {
    public int longestStrChain(String[] words) {
        Arrays.sort(words, Comparator.comparingInt(String::length));
        int n = words.length;
        int[] dp = new int[n];
        int max = 0;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = i-1; j >= 0; j--) {
                if (words[i].length() == words[j].length()+1 && compare(words[i], words[j])) {
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    private boolean compare(String a, String b) {
        // a.length() = b.length()+1
        int ia = 0, ib = 0, cnt = 1;
        while (ib < b.length() && cnt >= 0) {
            if (a.charAt(ia) == b.charAt(ib)) {
                ia++;
                ib++;
            } else {
                ia++;
                cnt--;
            }
        }
        return ib == b.length();
    }
}

# 646. 最长数对链

动态规划

class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b) -> a[0]-b[0]);
        int n = pairs.length;
        int[] dp = new int[n];
        int max = 0;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = i-1; j >= 0; j--) {
                if (pairs[i][0] > pairs[j][1]) {
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

# 647. 回文子串

动态规划

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
            cnt++;
            for (int j = i-1; j >= 0; j--) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (i == j+1) {
                        dp[j][i] = true;
                    } else {
                        dp[j][i] = dp[j+1][i-1];
                    }
                } else {
                    dp[j][i] = false;
                }
                if (dp[j][i]) cnt++;
            }
        }
        return cnt;
    }
}

# 1055. 形成字符串的最短路径

超时，理解有问题，动规设计不对

class Solution {
    public int shortestWay(String source, String target) {
        int n = target.length(), N = (int)1e9+7;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = isSubsequence(target.substring(i,i+1), source)?1:N;
            dp[0][i] = isSubsequence(target.substring(0,i+1), source)?1:N;
            for (int j = i-1; j >= 0; j--) {
                dp[j+1][i] = isSubsequence(target.substring(j+1,i+1), source)?1:N;
                // System.out.println("left:"+(j+1)+"; right:"+i);
                // System.out.println("dp[j+1][i]:"+dp[j+1][i]);
                dp[0][i] = Math.min(dp[0][i], dp[0][j]+dp[j+1][i]);
                // System.out.println("dp[0][i]:"+dp[0][i]);
            }
        }
        // System.out.println(Arrays.deepToString(dp));
        return dp[0][n-1] == N ? -1 : dp[0][n-1];
    }

    public boolean isSubsequence(String s, String t) {
        int ns = s.length();
        int nt = t.length();
        int is = 0, it = 0;
        while (is < ns && it < nt) {
            if (s.charAt(is) == t.charAt(it)) {
                is++;
            }
            it++;
        }
        return is == ns;
    }
}

动态规划

class Solution {
    public int shortestWay(String source, String target) {
        int n = target.length();
        boolean[] vis = new boolean[26];
        for (char c : source.toCharArray()) vis[c-'a'] = true;
        for (char c : target.toCharArray()) if (!vis[c-'a']) return -1;
        int[] dp = new int[n];
        dp[0] = 1;
        int start = 0;
        String tmp = target.substring(start, 1);
        for (int i = 1; i < n; i++) {
            tmp = target.substring(start, i+1);
            if (isSubsequence(tmp, source)) {
                dp[i] = dp[i-1];
            } else {
                dp[i] = dp[i-1]+1;
                start = i;
            }
        }
        return dp[n-1];
    }

    public boolean isSubsequence(String s, String t) {
        int ns = s.length();
        int nt = t.length();
        int is = 0, it = 0;
        while (is < ns && it < nt) {
            if (s.charAt(is) == t.charAt(it)) {
                is++;
            }
            it++;
        }
        return is == ns;
    }
}

# 392. 判断子序列

滑动窗口

class Solution {
    public boolean isSubsequence(String s, String t) {
        int ns = s.length();
        int nt = t.length();
        int is = 0, it = 0;
        while (is < ns && it < nt) {
            if (s.charAt(is) == t.charAt(it)) {
                is++;
            }
            it++;
        }
        return is == ns;
    }
}

# 352. 将数据流变为多个不相交区间

有序集合

import java.util.NavigableSet;
class SummaryRanges {
    private class Node {
        int left;
        int right;
        public Node (int l, int r) {
            this.left = l;
            this.right = r;
        }
        public String toString() {
            return "left:"+left+";right:"+right;
        }
    }
    private TreeSet<Node> tree;

    public SummaryRanges() {
        tree = new TreeSet<Node>((a, b) -> a.left-b.left);
    }
    
    public void addNum(int val) {
        Node n = new Node(val, val);
        if (tree.contains(n)) return;
        NavigableSet<Node> lo = tree.headSet(n, true);
        NavigableSet<Node> hi = tree.tailSet(n, true);
        // System.out.println(lo+"##"+hi);
        if (!lo.isEmpty() && val >= lo.last().left && val <= lo.last().right) return;
        if (!hi.isEmpty() && val >= hi.first().left && val <= hi.first().right) return;
        
        if (!lo.isEmpty() && val-1 == lo.last().right) {
            Node t = lo.pollLast();
            n.left = t.left;
        }
        if (!hi.isEmpty()&& val+1 == hi.first().left) {
            Node t = hi.pollFirst();
            n.right = t.right;
        }
        tree.add(n);
    }
    
    public int[][] getIntervals() {
        int n = tree.size();
        int[][] res = new int[n][2];
        int i = 0;
        for (Node node : tree) {
            res[i++] = new int[]{node.left, node.right};
        }
        return res;
    }
}

# 504. 七进制数

位运算

class Solution {
    public String convertToBase7(int num) {
        StringBuilder res = new StringBuilder();
        boolean neg = false;
        if (num < 0) {
            neg = true;
            num = Math.abs(num);
        }
        while (num / 7 != 0) {
            res.append(num%7);
            num /= 7;
        }
        if (num != 0) res.append(num);
        if (neg) res.append('-');
        if (res.length() == 0) res.append('0');
        return res.reverse().toString();
    }
}

# 562. 矩阵中最长的连续1线段

动态规划

class Solution {
    public int longestLine(int[][] mat) {
        int row = mat.length;
        int col = mat[0].length;
        int[][] pre = new int[col+2][4];
        int max = 0;
        for (int i = 1; i <= row; i++) {
            int[][] cur = new int[col+2][4];
            for (int j = 1; j <= col; j++) {
                if (mat[i-1][j-1] == 1) {
                    cur[j][0] = 1 + cur[j-1][0];
                    cur[j][1] = 1 + pre[j-1][1];
                    cur[j][2] = 1 + pre[j][2];
                    cur[j][3] = 1 + pre[j+1][3];
                }
                max = Math.max(max, Math.max(cur[j][0], Math.max(cur[j][1], Math.max(cur[j][2], cur[j][3]))));
            }
            pre = cur;
        }
        return max;
    }
}

# 441. 排列硬币

二分查找

class Solution {
    public int arrangeCoins(int n) {
        long l = 1, r = (long)1e9+7;
        while (l < r) {
            long mid = l + ((r-l)>>1);
            long total = calTotal(1, mid);
            if (n == total) {
                return (int)mid;
            } else if (n > total) {
                if (n < calTotal(1, mid+1)) {
                    return (int)mid;
                } else {
                    l = mid+1;
                }
            } else {
                r = mid-1;
            }
        }
        return (int)l;
    }
    private long calTotal(long l, long r) {
        return (l+r)*(r-l+1)/2;
    }
}

# 1182. 与目标颜色间的最短距离

动态规划，两次遍历

class Solution {
    public List<Integer> shortestDistanceColor(int[] colors, int[][] queries) {
        int n = colors.length;
        int[][] dp = new int[n][3];
        int N = (int)1e9+7, p1 = N, p2 = N, p3 = N;
        for (int i = 0; i < n; i++) {
            int cur = colors[i];
            if (cur == 1) {
                p1 = i;
                dp[i][0] = 0;
                dp[i][1] = p2 == N ? N : i-p2;
                dp[i][2] = p3 == N ? N : i-p3;
            } else if (cur == 2) {
                p2 = i;
                dp[i][1] = 0;
                dp[i][0] = p1 == N ? N : i-p1;
                dp[i][2] = p3 == N ? N : i-p3;
            } else {
                p3 = i;
                dp[i][2] = 0;
                dp[i][0] = p1 == N ? N : i-p1;
                dp[i][1] = p2 == N ? N : i-p2;
            }
        }
        p1 = N;
        p2 = N;
        p3 = N;
        for (int i = n-1; i >= 0; i--) {
            int cur = colors[i];
            if (cur == 1) {
                p1 = i;
                dp[i][1] = Math.min(dp[i][1], p2 == N ? N : p2-i);
                dp[i][2] = Math.min(dp[i][2], p3 == N ? N : p3-i);
            } else if (cur == 2) {
                p2 = i;
                dp[i][0] = Math.min(dp[i][0], p1 == N ? N : p1-i);
                dp[i][2] = Math.min(dp[i][2], p3 == N ? N : p3-i);
            } else {
                p3 = i;
                dp[i][0] = Math.min(dp[i][0], p1 == N ? N : p1-i);
                dp[i][1] = Math.min(dp[i][1], p2 == N ? N : p2-i);
            }
        }
        List<Integer> res = new ArrayList<>();
        for (int[] q : queries) {
            int cur = dp[q[0]][q[1]-1];
            res.add(cur == N ? -1 : cur);
        }
        return res;
    }
}

# 361. 轰炸敌人

动态规划

class Solution {
    public int maxKilledEnemies(char[][] grid) {
        int row = grid.length, col = grid[0].length;
        int[][][] dp = new int[row+2][col+2][4];
        int max = 0;
        for (int r = 1; r <= row; r++) {
            for (int c = 1; c <= col; c++) {
                char cur = grid[r-1][c-1];
                if (cur == 'W') {
                    continue;
                }
                if (cur == 'E') {
                    dp[r][c][0] = dp[r-1][c][0] + 1;
                    dp[r][c][3] = dp[r][c-1][3] + 1;
                } else {
                    dp[r][c][0] = dp[r-1][c][0];
                    dp[r][c][3] = dp[r][c-1][3];
                }
            }
        }
        // System.out.println(Arrays.deepToString(dp));
        for (int r = row; r >= 1; r--) {
            for (int c = col; c >= 1; c--) {
                char cur = grid[r-1][c-1];
                if (cur == 'W') continue;
                if (cur == 'E') {
                    dp[r][c][1] = dp[r][c+1][1] + 1;
                    dp[r][c][2] = dp[r+1][c][2] + 1;
                } else {
                    dp[r][c][1] = dp[r][c+1][1];
                    dp[r][c][2] = dp[r+1][c][2];
                    max = Math.max(max, dp[r][c][0]+dp[r][c][1]+dp[r][c][2]+dp[r][c][3]);
                }
            }
        }
        // System.out.println(Arrays.deepToString(dp));
        return max;
    }
}

# 1130. 叶值的最小代价生成树

递归，记忆化

class Solution {
    class Pair {
        int minSum;
        int maxVal;
        public Pair(int a, int b) {
            minSum = a;
            maxVal = b;
        }
    }
    int N = Integer.MAX_VALUE;
    int[][][] cache;

    public int mctFromLeafValues(int[] arr) {
        int n = arr.length;
        cache = new int[n][n][2];
        return recursive(arr, 0, n-1)[0];
    }
    private int[] recursive(int[] arr, int l, int r) {
        if (l == r) {
            return new int[]{0, arr[l]};
        }
        int[] p = cache[l][r];
        if (p[0] != 0) return p;
        int minSum = N, maxVal = 0;
        int mid = l;
        while (mid < r) {
            mid++;
            int[] r1 = recursive(arr, l, mid-1);
            int[] r2 = recursive(arr, mid, r);
            minSum = Math.min(minSum, r1[0]+r2[0]+(r1[1]*r2[1]));
            maxVal = Math.max(r1[1], r2[1]);
        }

        p = new int[]{minSum, maxVal};
        cache[l][r] = p;
        return p;
    }
}

记忆化递归，优化：

class Solution {
    int N = Integer.MAX_VALUE;
    int[][][] cache;
    public int mctFromLeafValues(int[] arr) {
        int n = arr.length;
        cache = new int[n][n][2];
        return recursive(arr, 0, n-1)[0];
    }
    private int[] recursive(int[] arr, int l, int r) {
        if (l == r) {
            return new int[]{0, arr[l]};
        }
        int[] p = cache[l][r];
        if (p[0] != 0) return p;
        int minSum = N, maxVal = 0;
        int mid = l;
        while (mid < r) {
            mid++;
            int[] r1 = recursive(arr, l, mid-1);
            int[] r2 = recursive(arr, mid, r);
            minSum = Math.min(minSum, r1[0]+r2[0]+(r1[1]*r2[1]));
            maxVal = Math.max(r1[1], r2[1]);
        }
        p = new int[]{minSum, maxVal};
        cache[l][r] = p;
        return p;
    }
}

减少计算最大值的计算量，提前计算好

class Solution {
    int N = Integer.MAX_VALUE;
    int[][] cache;
    int[][] maxVal;
    public int mctFromLeafValues(int[] arr) {
        int n = arr.length;
        cache = new int[n][n];
        maxVal = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (i == j) {
                    maxVal[i][j] = arr[i];
                } else {
                    maxVal[i][j] = Math.max(maxVal[i][j-1], arr[j]);
                    maxVal[j][i] = maxVal[i][j];
                }
            }
        }
        // System.out.println(Arrays.deepToString(maxVal));
        return recursive(arr, 0, n-1);
    }
    private int recursive(int[] arr, int l, int r) {
        if (l == r) {
            return 0;
        }
        int p = cache[l][r];
        if (p != 0) return p;
        int minSum = N;
        int mid = l;
        while (mid < r) {
            mid++;
            int r1 = recursive(arr, l, mid-1);
            int r2 = recursive(arr, mid, r);
            minSum = Math.min(minSum, r1+r2+(maxVal[l][mid-1]*maxVal[mid][r]));
        }
        cache[l][r] = minSum;
        return minSum;
    }
}

动态规划，区间dp

class Solution {
    public int mctFromLeafValues(int[] arr) {
        int N = Integer.MAX_VALUE;
        int n = arr.length;
        int[][] dp = new int[n][n];
        int[][] maxVal = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (i == j) {
                    maxVal[i][j] = arr[i];
                } else {
                    maxVal[i][j] = Math.max(maxVal[i][j-1], arr[j]);
                    maxVal[j][i] = maxVal[i][j];
                }
            }
        }

        for (int r = 0; r < n; r++) {
            for (int l = r; l >= 0; l--) {
                dp[l][r] = l == r ? 0 : N;
                for (int k = r-1; k >= l; k--) {
                    dp[l][r] = Math.min(dp[l][r], dp[l][k]+dp[k+1][r]+maxVal[l][k]*maxVal[k+1][r]);
                }
            }
        }
        // System.out.println(Arrays.deepToString(dp));
        return dp[0][n-1];
    }
}

# 273. 整数转换英文表示

todo，未做，不想动

# 254. 因子的组合

暴力递归

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> getFactors(int n) {
        for (int i = 2; i <= (n/2); i++) {
            if (n % i == 0) {
                List<Integer> path = new ArrayList<>();
                path.add(i);
                dfs(n/i, i, path);
            }
        }
        return res;
    }

    private void dfs(int n, int start, List<Integer> path) {
        // System.out.println(n+"; "+start+"; "+path);
        if (n == 1) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i <= n; i++) {
            if (n % i == 0) {
                path.add(i);
                dfs(n/i, i, path);
                path.remove(path.size()-1);
            }
        }
    }
}

# 960. 删列造序 III

动态规划

class Solution {
    public int minDeletionSize(String[] A) {
        int m = A.length, n = A[0].length(), res = n - 1, k;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int j = 0; j < n; ++j) {
            for (int i = 0; i < j; ++i) {
                for (k = 0; k < m; ++k) {
                    if (A[k].charAt(i) > A[k].charAt(j)) break;
                }
                if (k == m && dp[i] + 1 > dp[j])
                    dp[j] = dp[i] + 1;
            }
            res = Math.min(res, n - dp[j]);
        }
        return res;
    }
}

# 剑指 Offer II 069. 山峰数组的顶部

二分法

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int n = arr.length;
        int l = 0, r = n-1;
        while (l < r) {
            int mid = l + ((r-l+1)>>1);
            if (check(arr, mid)) {
                l = mid;
            } else {
                r = mid-1;
            }
        }
        return l;
    }

    private boolean check(int[] arr, int mid) {
        if (arr[mid-1] < arr[mid]) {
            return true;
        } else {
            return false;
        }
    }
}

# 1151. 最少交换次数来组合所有的 1

滑动窗口

class Solution {
    public int minSwaps(int[] data) {
        int one = 0;
        for (int d : data) if (d == 1) one++;

        int l = 0, r = 0, n = data.length, cnt = 0, max = 0;
        while (r < n && l < n) {
            while (r < n && r-l+1 <= one) {
                if (data[r] == 1) cnt++;
                r++;
            }
            max = Math.max(max, cnt);

            if (data[l] == 1) cnt--;
            l++;
        }
        return one-max;
    }
}

# 211. 添加与搜索单词 - 数据结构设计

trie树、字典树

class WordDictionary {
    Trie trie;
    public WordDictionary() {
        trie = new Trie();
    }
    
    public void addWord(String word) {
        trie.insert(word);
    }
    
    public boolean search(String word) {
        return trie.search(word);
    }

    class Trie {
        class TrieNode {
            boolean end;
            TrieNode[] tns = new TrieNode[26];
        }

        TrieNode root;
        public Trie() {
            root = new TrieNode();
        }

        public void insert(String s) {
            TrieNode p = root;
            for(int i = 0; i < s.length(); i++) {
                int u = s.charAt(i) - 'a';
                if (p.tns[u] == null) p.tns[u] = new TrieNode();
                p = p.tns[u]; 
            }
            p.end = true;
        }

        public boolean search(String s) {
            TrieNode p = root;
            Queue<TrieNode> q = new LinkedList<>();
            q.offer(p);
            for(int i = 0; i < s.length(); i++) {
                char cur = s.charAt(i);
                int sz = q.size();
                for (int j = 0; j < sz; j++) {
                    TrieNode[] ts = q.poll().tns;
                    if (cur == '.') {
                        for (TrieNode t : ts) {
                            if (t != null) q.offer(t);
                        }
                    } else {
                        int u = cur-'a';
                        if (ts[u] != null) q.offer(ts[u]);
                    }
                }
            }

            while (!q.isEmpty()) {
                if (q.poll().end) return true;
            }
            return false;
        }

        public boolean startsWith(String s) {
            TrieNode p = root;
            for(int i = 0; i < s.length(); i++) {
                int u = s.charAt(i) - 'a';
                if (p.tns[u] == null) return false;
                p = p.tns[u]; 
            }
            return true;
        }
    }
}

重刷，思路类似，写法上有些许区别

class WordDictionary {
    class TrieNode {
        boolean end;
        TrieNode[] tns = new TrieNode[26];
    }
    TrieNode root;
    public WordDictionary() {
        root = new TrieNode();
    }
    
    public void addWord(String word) {
        TrieNode p = root;
        for (char c : word.toCharArray()) {
            int u = c-'a';
            if (p.tns[u] == null) p.tns[u] = new TrieNode();
            p = p.tns[u];
        }
        p.end = true;
    }
    
    public boolean search(String word) {
        TrieNode p = root;
        Queue<TrieNode> q = new LinkedList<>();
        q.offer(p);
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (q.isEmpty()) return false;
            int sz = q.size();
            for (int k = 0; k < sz; k++) {
                TrieNode cur = q.poll();
                if (c == '.') {
                    for (TrieNode n : cur.tns) {
                        if (n != null) q.offer(n);
                    }
                } else {
                    int u = c-'a';
                    if (cur.tns[u] != null) q.offer(cur.tns[u]);
                }
            }
        }
        while (!q.isEmpty()) {
            TrieNode cur = q.poll();
            if (cur.end) return true;
        }
        return false;
    }
}

# 剑指 Offer 05. 替换空格

调包

class Solution {
    public String replaceSpace(String s) {
        return s.replace(" ", "%20");
    }
}

先计算空格数量，然后创建结果数组，边遍历边输出

class Solution {
    public String replaceSpace(String s) {
        int cnt = 0;
        for (char c : s.toCharArray()) {
            if (c == ' ') {
                cnt++;
            }
        }

        char[] cs = new char[s.length()+(cnt*2)];
        for (int i = 0, j = 0; i < s.length(); i++) {
            char cur = s.charAt(i);
            if (cur != ' ') {
                cs[j++] = cur;
            } else {
                cs[j++] = '%';
                cs[j++] = '2';
                cs[j++] = '0';
            }
        }
        return String.valueOf(cs);
    }
}

# 剑指 Offer 03. 数组中重复的数字

排序

class Solution {
    public int findRepeatNumber(int[] nums) {
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i-1]) return nums[i];
        }
        return -1;
    }
}

# 剑指 Offer 24. 反转链表

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        if (head == null) return null;
        while (head != null) {
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

# 剑指 Offer 06. 从尾到头打印链表

class Solution {
    public int[] reversePrint(ListNode head) {
        Stack<Integer> s = new Stack<>();
        int n = 0;
        while (head != null) {
            s.push(head.val);
            head = head.next;
            n++;
        }
        
        int[] ans = new int[n];
        int i = 0;
        while (!s.empty()) {
            ans[i++] = s.pop();
        }
        return ans;
    }
}

class Solution {
    public int[] reversePrint(ListNode head) {
        List<Integer> result = new ArrayList<Integer>();
        while (head != null) {
            result.add(head.val);
            head = head.next;
        }
        Collections.reverse(result);
        return result.stream().mapToInt(Integer::valueOf).toArray();
    }
}

# 剑指 Offer 30. 包含min函数的栈

class MinStack {
    Stack<Integer> s;
    Stack<Integer> min;
    /** initialize your data structure here. */
    public MinStack() {
        s = new Stack<>();
        min = new Stack<>();
    }
    
    public void push(int x) {
        s.push(x);
        if (min.empty()) {
            min.push(x);
        } else {
            int cur = min.peek();
            if (x < cur) {
                min.push(x);
            } else {
                min.push(cur);
            }
        }
    }
    
    public void pop() {
        if (!s.empty()) {
            s.pop();
            min.pop();
        }
    }
    
    public int top() {
        if (!s.empty()) {
            return s.peek();
        }
        return -1;

    }
    
    public int min() {
        if (!min.empty()) {
            return min.peek();
        }
        return -1;
    }
}

# 剑指 Offer 09. 用两个栈实现队列

class CQueue {
    Stack<Integer> in = new Stack<>();
    Stack<Integer> out = new Stack<>();

    public CQueue() {
    }
    
    public void appendTail(int value) {
        in.push(value);
    }
    
    public int deleteHead() {
        if (!out.empty()) return out.pop();

        while (!in.empty()) {
            out.push(in.pop());
        }

        if (!out.empty()) return out.pop();

        return -1;
    }
}

# 453. 最小操作次数使数组元素相等

数学

class Solution {
    public int minMoves(int[] nums) {
        int min = (int) 1e9+7, sum = 0, n = nums.length;
        for (int i : nums) {
            min = Math.min(min, i);
            sum += i;
        }
        return sum - min*n;
    }
}

# 剑指 Offer 35. 复杂链表的复制

哈希表

class Solution {
    public Node copyRandomList(Node head) {
        Map<Node, Node> map = new HashMap<>();
        Node sentinel = new Node(0), pre = null, h = null;
        pre = sentinel;

        while (head != null) {
            h = map.getOrDefault(head, new Node(head.val));
            pre.next = h;
            map.put(head, h);

            // deal random
            if (head.random != null) {
                Node random = map.getOrDefault(head.random, new Node(0));
                random.val = head.random.val;
                h.random = random;
                map.put(head.random, random);
            }

            pre = h;
            h = null;
            head = head.next;
        }
        return sentinel.next;
    }
}

# 剑指 Offer 58 - II. 左旋转字符串

class Solution {
    public String reverseLeftWords(String s, int n) {
        int len = s.length();
        n %= len;
        if (n > 0) {
            return s.substring(n, len) + s.substring(0, n);
        }
        return s;
    }
}

# 剑指 Offer 53 - II. 0～n-1中缺失的数字

暴力遍历

class Solution {
    public int missingNumber(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (i != nums[i]) return i;
        }
        return nums.length;
    }
}

可以异或，与下标异或，找到下标中唯一多出来的那个数

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int res = 0;
        for (int i = 0; i < n; i++) {
            res ^= nums[i];
            res ^= i;
        }
        res ^= n;
        return res;
    }
}

# 剑指 Offer 04. 二维数组中的查找

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix.length == 0) return false;
        int row = matrix.length, col = matrix[0].length;
        int r = row-1, c = 0;
        while (r >= 0 && c < col) {
            if (matrix[r][c] == target) {
                return true;
            } else if (matrix[r][c] > target) {
                r--;
            } else {
                c++;
            }
        }
        return false;
    }
}

# 剑指 Offer 11. 旋转数组的最小数字

二分查找，O(logn)

class Solution {
    public int minArray(int[] numbers) {
        int n = numbers.length;
        int l = 0, r = n-1;
        if (numbers[r] > numbers[l]) return numbers[l];
        while (l < r) {
            int mid = l + ((r-l)>>1);
            int x = numbers[r];
            if (numbers[mid] > x) {
                l = mid+1;
            } else if (numbers[mid] < x) {
                r = mid;
            } else {
                r--;
            }
        }
        return numbers[r];
    }
}

暴力

class Solution {
    public int minArray(int[] numbers) {
        int res = numbers[0];
        for (int i = 1; i < numbers.length; i++) {
            if (numbers[i-1] > numbers[i]) {
                return numbers[i];
            }
        }
        return res;
    }
}

# 剑指 Offer 50. 第一个只出现一次的字符

两遍遍历

class Solution {
    public char firstUniqChar(String s) {
        int[] cnt = new int[26];
        char[] cs = s.toCharArray();
        for (char c : cs) {
            cnt[c-'a']++;
        }

        for (char c : cs) {
            if (cnt[c-'a'] == 1) return c;
        }
        return ' ';
    }
}

# 剑指 Offer 32 - I. 从上到下打印二叉树

bfs

class Solution {
    public int[] levelOrder(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        if (root == null) return new int[]{};
        q.offer(root);
        
        while (!q.isEmpty()) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                TreeNode cur = q.poll();
                res.add(cur.val);

                if (cur.left != null) q.offer(cur.left);
                if (cur.right != null) q.offer(cur.right);
            }
        }

        int[] ans = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            ans[i] = res.get(i);
        }
        return ans;
    }
}

# 剑指 Offer 32 - II. 从上到下打印二叉树 II

bfs

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        if (root == null) return res;
        q.offer(root);
        
        while (!q.isEmpty()) {
            int sz = q.size();
            List<Integer> line = new ArrayList<>();
            for (int i = 0; i < sz; i++) {
                TreeNode cur = q.poll();
                line.add(cur.val);

                if (cur.left != null) q.offer(cur.left);
                if (cur.right != null) q.offer(cur.right);
            }
            res.add(line);
        }
        return res;
    }
}

# 剑指 Offer 32 - III. 从上到下打印二叉树 III

bfs

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Deque<TreeNode> q = new LinkedList<>();
        if (root == null) return res;
        q.offer(root);
        boolean odd = true;
        while (!q.isEmpty()) {
            int sz = q.size();
            List<Integer> line = new ArrayList<>();
            for (int i = 0; i < sz; i++) {
                if (odd) {
                    TreeNode cur = q.poll();
                    line.add(cur.val);

                    if (cur.left != null) q.offer(cur.left);
                    if (cur.right != null) q.offer(cur.right);
                } else {
                    TreeNode cur = q.pollLast();
                    line.add(cur.val);

                    if (cur.right != null) q.addFirst(cur.right);
                    if (cur.left != null) q.addFirst(cur.left);
                }
            }
            res.add(line);
            odd = !odd;
        }
        return res;
    }
}

# 229. 求众数 II

摩尔投票

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int a = 0, b = 0, c1 = 0, c2 = 0;
        for (int i : nums) {
            if (c1 != 0 && a == i) {
                c1++;
            } else if (c2 != 0 && b == i) {
                c2++;
            } else if (c1 == 0) {
                a = i;
                c1++;
            } else if (c2 == 0) {
                b = i;
                c2++;
            } else {
                c1--;
                c2--;
            }
        }

        c1 = 0;
        c2 = 0;
        int limit = (int) nums.length / 3;
        for (int i : nums) {
            if (a == i) c1++;
            else if (b == i) c2++;
        }
        List<Integer> res = new ArrayList<>();
        if (c1 > limit) res.add(a);
        if (c2 > limit) res.add(b);
        return res;
    }
}

# 492. 构造矩形

数学

class Solution {
    public int[] constructRectangle(int area) {
        int w = (int) Math.sqrt(area);
        while (area % w != 0) {
            w--;
        }
        return new int[]{area/w, w};
    }
}

# 剑指 Offer 26. 树的子结构

bfs，比较A二叉树上每一个节点，利用队列来操作，效率较低

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) return false;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(A);
        while (!q.isEmpty()) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                TreeNode cur = q.poll();
                if (cur.val == B.val) {
                    if (equals(cur, B)) {
                        return true;
                    }
                }
                if (cur.left != null) q.offer(cur.left);
                if (cur.right != null) q.offer(cur.right);
            }
        }
        return false;
    }

    private boolean equals(TreeNode a, TreeNode b) {
        if (b == null) return true;
        if (b != null && a == null) return false;
        if (a.val != b.val) return false;

        if (equals(a.left, b.left) && equals(a.right, b.right)) {
            return true;
        }
        return false;
    }
}

直接递归处理，效率最高

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) return false;
        return equals(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    private boolean equals(TreeNode a, TreeNode b) {
        if (b == null) return true;
        if (b != null && a == null) return false;
        if (a.val != b.val) return false;

        return equals(a.left, b.left) && equals(a.right, b.right);
    }
}

# 剑指 Offer 27. 二叉树的镜像

递归

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) return null;
        TreeNode left = mirrorTree(root.left);
        root.left = mirrorTree(root.right);
        root.right = left;
        return root;
    }
}

# 剑指 Offer 28. 对称的二叉树

递归

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        if (root.left == null && root.right == null) return true;
        return isSymmetric(root.left, root.right);
    }

    private boolean isSymmetric(TreeNode a, TreeNode b) {
        if (a == null && b == null) return true;
        if (a == null && b != null) return false;
        if (a != null && b == null) return false;
        if (a.val != b.val) return false;
        return isSymmetric(a.left, b.right) && isSymmetric(a.right, b.left);
    }
}

# 638. 大礼包

记忆化搜索，时间复杂度仍然很高，还需要剪枝

class Solution {
    int N = (int) 1e9+7;
    Map<List, Integer> memo = new HashMap<>(); 
    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        int n = price.size();
        for (int i = 0; i < n; i++) {
            Integer[] sp = new Integer[n+1];
            Arrays.fill(sp, 0);
            sp[i] = 1;
            sp[n] = price.get(i);
            special.add(Arrays.asList(sp));
        }
        // System.out.println(special);
        return recursive(price, special, needs);
    }

    private int recursive(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        if (memo.containsKey(needs)) {
            return memo.get(needs);
        }
        int all = 0;
        for (int ne : needs) {
            all += ne;
        }
        if (all == 0) return 0;
        if (all < 0) return N;
        int n = price.size();
        int min = N;
        for (List<Integer> sp : special) {
            List<Integer> newNeeds = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                int re = needs.get(i) - sp.get(i);
                if (re < 0) break;
                newNeeds.add(re);
            }
            if (newNeeds.size() != n) {
                continue;
            }
            int curCost = sp.get(n);
            min = Math.min(min, recursive(price, special, newNeeds) + curCost);
        }

        memo.put(needs, min);
        return min;
    }
}

不将price先加入到special中，否则递归会导致分支数量爆炸

class Solution {
    int N = (int) 1e9+7;
    Map<List, Integer> memo = new HashMap<>();
    Set<Integer> filter = new HashSet<>();
    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        int n = price.size();
        for (int i = 0; i < special.size(); i++) {
            List<Integer> sp = special.get(i);
            for (int j = 0; j < needs.size(); j++) {
                if (sp.get(j) > needs.get(j)) {
                    filter.add(i);
                    break;
                }
            }
        }
        // System.out.println(special);
        return recursive(price, special, needs);
    }

    private int recursive(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        if (memo.containsKey(needs)) {
            return memo.get(needs);
        }
        int all = 0;
        for (int ne : needs) {
            all += ne;
        }
        if (all == 0) {
            memo.put(needs, 0);
            return 0;
        }
        int n = price.size();
        int min = 0;
        for (int i = 0; i < n; i++) {
            min += needs.get(i) * price.get(i);
        }

        for (int j = 0; j < special.size(); j++) {
            if (filter.contains(j)) continue;
            List<Integer> sp = special.get(j);
            List<Integer> newNeeds = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                int re = needs.get(i) - sp.get(i);
                if (re < 0) break;
                newNeeds.add(re);
            }
            if (newNeeds.size() != n) {
                continue;
            }
            int curCost = sp.get(n);
            if (curCost >= min) continue;
            min = Math.min(min, recursive(price, special, newNeeds) + curCost);
        }

        memo.put(needs, min);
        return min;
    }
}

# 剑指 Offer 10- II. 青蛙跳台阶问题

动态规划

class Solution {
    public int numWays(int n) {
        int N = (int) 1e9+7, a = 1, b = 1;
        if (n == 0) return 1;
        if (n == 1) return 1;
        for (int i = 2; i <= n; i++) {
            int c = (a + b) % N;
            a = b;
            b = c;
        }
        return b;
    }
}

# 剑指 Offer 63. 股票的最大利润

dp

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n == 0) return 0;
        int min = prices[0], res = 0;
        for (int i = 1; i < n; i++) {
            res = Math.max(res, prices[i]-min);
            min = Math.min(min, prices[i]);
        }
        return res;
    }
}

写法上优化下，避免一些计算

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n == 0) return 0;
        int min = prices[0], res = 0;
        for (int i = 1; i < n; i++) {
            if (prices[i] < min) {
                min = prices[i];
            } else {
                res = Math.max(res, prices[i]-min);
            }
        }
        return res;
    }
}

# 剑指 Offer 47. 礼物的最大价值

动态规划

class Solution {
    public int maxValue(int[][] grid) {
        int row = grid.length, col = grid[0].length;
        int[][] dp = new int[row+1][col+1];
        for (int r = 1; r <= row; r++) {
            for (int c = 1; c <= col; c++) {
                dp[r][c] = Math.max(dp[r-1][c], dp[r][c-1]) + grid[r-1][c-1];
            }
        }
        return dp[row][col];
    }
}

# 剑指 Offer 46. 把数字翻译成字符串

动态规划

class Solution {
    public int translateNum(int num) {
        char[] cs = String.valueOf(num).toCharArray();
        int p = 1, pp = 1;
        for (int i = 1; i < cs.length; i++) {
            int c = p;
            if (cs[i-1]-'0' == 1) {
                c += pp;
            } else if ((cs[i-1]-'0' == 2) && (cs[i]-'0' <= 5)) {
                c += pp;
            }
            pp = p;
            p = c;
        }
        return p;
    }
}

# 剑指 Offer 48. 最长不含重复字符的子字符串

滑动窗口

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        char[] cs = s.toCharArray();
        int l = 0, r = 0;
        int len = 0;
        while (r < cs.length) {
            while (r < cs.length && !set.contains(cs[r])) {
                set.add(cs[r++]);
            }
            len = Math.max(len, r-l);
            if (r == cs.length) break;
            
            while (l < r && set.contains(cs[r])) {
                set.remove(cs[l++]);
            }
        }
        return len;
    }
}

# 剑指 Offer 18. 删除链表的节点

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        ListNode sentinel = new ListNode(0);
        sentinel.next = head;
        ListNode pre = sentinel;

        while (head != null) {
            if (head.val == val) {
                pre.next = head.next;
            } else {
                pre = head;
            }
            head = head.next;
        }
        return sentinel.next;
    }
}

# 剑指 Offer 22. 链表中倒数第k个节点

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if (k == 0 || head == null) return null;
        ListNode fast = head, slow = head;
        while (k > 1 && fast != null) {
            fast = fast.next;
            k--;
        }
        while (slow.next != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

# 剑指 Offer 25. 合并两个排序的链表

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        int N = (int) 1e9+7;
        ListNode sentinel = new ListNode(0);
        ListNode pre = sentinel;
        while (l1 != null || l2 != null) {
            int v1 = N, v2 = N;
            if (l1 != null) {
                v1 = l1.val;
            }
            if (l2 != null) {
                v2 = l2.val;
            }
            ListNode cur = null;
            if (v1 < v2) {
                cur = new ListNode(l1.val);
                pre.next = cur;
                l1 = l1.next;
            } else {
                cur = new ListNode(l2.val);
                pre.next = cur;
                l2 = l2.next;
            }
            pre = cur;
        }
        return sentinel.next;
    }
}

# 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

class Solution {
    public int[] exchange(int[] nums) {
        int a = 0, b = 0;
        while (b < nums.length) {
            if (nums[b] % 2 != 0) {
                swap(nums, a, b);
                a++;
            }
            b++;
        }
        return nums;
    }
    
    private void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

# 剑指 Offer 57. 和为s的两个数字

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        int l = 0, r = n-1;
        while (l < r) {
            if (nums[l]+nums[r] == target) {
                return new int[]{nums[l], nums[r]};
            } else if (nums[l]+nums[r] < target) {
                l++;
            } else {
                r--;
            }
        }
        return new int[]{};
    }
}

# 剑指 Offer 58 - I. 翻转单词顺序

class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = new StringBuilder();
        char[] cs = s.toCharArray();
        for (int i = cs.length-1; i >= 0; i--) {
            if (cs[i] == ' ') continue;
            int r = i, l = i;
            while (i >= 0 && cs[i] != ' ') {
                l = i;
                i--;
            }
            sb.append(s.substring(l, r+1)).append(" ");
        }
        if (sb.length() > 0) {
            return sb.substring(0, sb.length()-1).toString();
        }
        return sb.toString();
    }
}

# 剑指 Offer 12. 矩阵中的路径

递归

class Solution {
    int[] dr = new int[]{1, 0, -1, 0};
    int[] dc = new int[]{0, 1, 0, -1};
    int row;
    int col;
    public boolean exist(char[][] board, String word) {
        row = board.length;
        col = board[0].length;
        boolean[][] visited = new boolean[row][col];
        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                if (recursive(board, word, r, c, 0, visited)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean recursive(char[][] board, String word, int r, int c, int index, boolean[][] visited) {
        if (board[r][c] != word.charAt(index)) {
            return false;
        }
        if (index == word.length()-1) {
            return true;
        }
        visited[r][c] = true;
        for (int i = 0; i < 4; i++) {
            int nr = r+dr[i];
            int nc = c+dc[i];
            if (nr < 0 || nr >= row || nc < 0 || nc >= col) {
                continue;
            }
            if (visited[nr][nc]) continue;
            if (recursive(board, word, nr, nc, index+1, visited)) {
                return true;
            }
        }
        visited[r][c] = false;
        return false;
    }
}

# 剑指 Offer 34. 二叉树中和为某一值的路径

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        List<Integer> path = new ArrayList<>();
        if (root == null) return res;
        path.add(root.val);
        recursive(root, target, root.val, path);
        return res;
    }

    private void recursive(TreeNode node, int target, int sum, List<Integer> path) {
        if (node == null) {
            return;
        }
        if (node.left == null && node.right == null) {
            if (sum == target) {
                System.out.println(sum);
                res.add(new ArrayList<>(path));
            }
            return;
        }
        if (node.left != null) {
            path.add(node.left.val);
            System.out.println("left:"+node.left.val+"; paht:"+path+"; sum"+sum);
            recursive(node.left, target, sum+node.left.val, path);
            path.remove(path.size()-1);
        }
        if (node.right != null) {
            path.add(node.right.val);
            System.out.println("right:"+node.right.val+"; paht:"+path+"; sum"+sum);
            recursive(node.right, target, sum+node.right.val, path);
            path.remove(path.size()-1);
        }
    }
}

# 剑指 Offer 54. 二叉搜索树的第k大节点

class Solution {
    int cnt = 0;
    int res = 0;
    int k;
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        recursive(root);
        return res;
    }

    private void recursive(TreeNode node) {
        if (node == null || cnt >= k) {
            return;
        }
        
        recursive(node.right);
        
        cnt++;
        if (cnt == k) {
            res = node.val;
        }

        recursive(node.left);
    }
}

# 剑指 Offer 45. 把数组排成最小的数

排序

class Solution {
    public String minNumber(int[] nums) {
        String[] arr = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            arr[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(arr, (a, b)->{
            long ab = Long.valueOf(a+b);
            long ba = Long.valueOf(b+a);
            if (ab < ba) {
                return -1;
            } else if (ab > ba) {
                return 1;
            }
            return 0;
        });
        StringBuilder res = new StringBuilder();
        for (String s : arr) res.append(s);
        return res.toString();
    }
}

# 剑指 Offer 61. 扑克牌中的顺子

class Solution {
    public boolean isStraight(int[] nums) {
        Arrays.sort(nums);
        int zero = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                zero++;
            } else {
                if (i != 0 && nums[i-1] != 0) {
                    while (zero > 0 && nums[i-1] != nums[i]) {
                        nums[i-1]++;
                        zero--;
                    }
                    if (nums[i-1] != nums[i]) {
                        return false;
                    }
                }
                nums[i]++;
            }
        }
        return true;
    }
}

# 剑指 Offer 56 - I. 数组中数字出现的次数

class Solution {
    public int[] singleNumbers(int[] nums) {
        int res = 0;
        for (int i : nums) {
            res = res ^ i;
        }

        int index = 0;
        for (int i = 0; i < 32; i++) {
            int mask = (1 << i);
            if ((res & mask) != 0) {
                index = i;
                break;
            }
        }

        List<Integer> as = new ArrayList<>();
        List<Integer> bs = new ArrayList<>();

        int mask = 1 << index;
        for (int i : nums) {
            if ((i & mask) == 0) {
                as.add(i);
            } else {
                bs.add(i);
            }
        }

        int r1 = 0;
        for (int i : as) {
            r1 ^= i;
        }
        int r2 = 0;
        for (int i : bs) {
            r2 ^= i;
        }
        
        return new int[]{r1, r2};
    }
}

# 剑指 Offer 39. 数组中出现次数超过一半的数字

摩尔投票

class Solution {
    public int majorityElement(int[] nums) {
        int cnt = 0, res = 0;
        for (int i : nums) {
            if (cnt == 0) {
                res = i;
                cnt = 1;
            } else {
                if (res == i) {
                    cnt++;
                } else {
                    cnt--;
                }
            }
        }
        return res;
    }
}

# 剑指 Offer 40. 最小的k个数

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        Arrays.sort(arr);
        int[] res = new int[k];
        for (int i = 0; i < k; i++) res[i] = arr[i];
        return res;
    }
}

# 剑指 Offer 41. 数据流中的中位数

class MedianFinder {
    PriorityQueue<Integer> max = new PriorityQueue<>((a, b) -> b-a);
    PriorityQueue<Integer> min = new PriorityQueue<>();

    public MedianFinder() {
    }
    
    public void addNum(int num) {
        if (max.size() == 0 && min.size() == 0) {
            max.offer(num);
            return;
        }
        int mid = max.peek();
        if (num > mid) {
            min.add(num);
            if (min.size() > max.size()) {
                max.offer(min.poll());
            }
        } else {
            // num <= mid
            max.add(num);
            if (max.size() > min.size()+1) {
                min.offer(max.poll());
            }
        }                
    }
    
    public double findMedian() {
        if (max.size() == 0 && min.size() == 0) return 0d;

        if (max.size() == min.size()) return Double.valueOf(max.peek()+min.peek()) / 2;
        
        return max.peek();
    }
}

# 剑指 Offer 55 - I. 二叉树的深度

class Solution {
    public int maxDepth(TreeNode root) {
        int depth = 0;
        if (root == null) {
            return 0;
        }
        depth++;
        depth = Math.max(maxDepth(root.left)+depth, maxDepth(root.right)+depth);
        return depth;
    }
}

# 剑指 Offer 55 - II. 平衡二叉树

class Solution {
    boolean isBalance = true;
    public boolean isBalanced(TreeNode root) {
        getDepth(root);
        return isBalance;
    }
    private int getDepth(TreeNode node) {
        if (!isBalance) {
            return 0;
        }
        int depth = 0;
        if (node == null) {
            return 0;
        }
        depth++;
        int left = getDepth(node.left);
        int right = getDepth(node.right);
        if (Math.abs(left-right) > 1) {
            isBalance = false;
        }
        return Math.max(left, right) + depth;
    }
}

# 剑指 Offer 64. 求1+2+…+n

class Solution {
    public int sumNums(int n) {
        return sumNums(0, n);
    }
    private int sumNums(int c, int n) {
        if (c > n) {
            return 0;
        }
        return c + sumNums(c+1, n);
    }
}

# 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

class Solution {
    int l;
    int r;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (p.val < q.val) {
            l = p.val;
            r = q.val;
        } else {
            l = q.val;
            r = p.val;
        }
        return recursive(root);
    }
    private TreeNode recursive(TreeNode root) {
        if (root == null) {
            return null;
        }
        if (root.val > l && root.val < r) {
            return root;
        } else if (root.val == l || root.val == r) {
            return root;
        } else if (root.val < l) {
            return recursive(root.right);
        } else if (root.val > r) {
            return recursive(root.left);
        }
        return null;
    }
}

# 剑指 Offer 68 - II. 二叉树的最近公共祖先

class Solution {
    TreeNode res = null;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        recursive(root, p, q);
        return res;
    }
    private boolean[] recursive(TreeNode node, TreeNode p, TreeNode q) {
        if (node == null || res != null) return new boolean[]{false, false};

        boolean[] left = recursive(node.left, p, q);
        boolean[] right = recursive(node.right, p, q);
        boolean hp = left[0] || right[0];
        boolean hq = left[1] || right[1];
        
        if (node.val == p.val) {
            hp = true;
        } else if (node.val == q.val) {
            hq = true;
        }
        
        if (res == null && hp && hq) {
            res = node;
        }

        return new boolean[]{hp, hq};
    }
}

# 剑指 Offer 66. 构建乘积数组

class Solution {
    public int[] constructArr(int[] a) {
        int n = a.length;
        int[] res = new int[n];
        if (n == 0) return res;
        int[] pre = new int[n];
        int[] post = new int[n];
        pre[0] = 1;
        for (int i = 1; i < n; i++) {
            pre[i] = a[i-1] * pre[i-1];
        }
        post[n-1] = 1;
        for (int i = n-2; i >= 0; i--) {
            post[i] = a[i+1] * post[i+1];
        }
        for (int i = 0; i < n; i++) {
            res[i] = pre[i] * post[i];
        }
        return res;
    }
}

# 剑指 Offer 57 - II. 和为s的连续正数序列

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> res = new ArrayList<>();
        int l = 1, r = 2, sum = 1;
        while (r <= target) {
            if (sum == target) {
                int[] t = new int[r-l];
                for (int i = l; i < r; i++) {
                    t[i-l] = i;
                }
                res.add(t);
                sum += r;
                r++;
            } else if (sum < target) {
                sum += r;
                r++;
            } else if (sum > target) {
                sum -= l;
                l++;
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}

# 剑指 Offer 14- I. 剪绳子

class Solution {
    public int cuttingRope(int n) {
        int[] dp = new int[n+1];
        dp[1] = 1;
        for (int j = 2; j <= n; j++) {
            for (int i = j-1; i >= 1; i--) {
                dp[j] = Math.max(dp[j], Math.max(dp[i]*(j-i), i*(j-i)));
            }
        }
        return dp[n];
    }
}

# 剑指 Offer 65. 不用加减乘除做加法

class Solution {
    public int add(int a, int b) {
        int ans = 0, pre = 0;
        for (int i = 0; i < 32; i++) {
            int ai = (a>>i) & 1;
            int bi = (b>>i) & 1;
            int res = ai ^ bi;
            int incr = ai & bi;
            if (pre == 1) {
                if (res == 0) {
                    res = 1;
                } else {
                    res = 0;
                    incr = 1;
                }
            }
            ans = ans | (res << i);
            pre = incr;
        }
        return ans;
    }
}

# 301. 删除无效的括号

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        Set<String> set = new HashSet<>();
        set.add(s);
        List<String> res = new ArrayList<>();
        while (true) {
            for (String cur : set) {
                if (isValid(cur)) {
                    res.add(cur);
                }
            }
            if (res.size() > 0) {
                return res;
            }

            Set<String> next = new HashSet<>();
            for (String cur : set) {
                for (int i = 0; i < cur.length(); i++) {
                    if (i > 0 && cur.charAt(i) == cur.charAt(i-1)) {
                        continue;
                    }
                    if (cur.charAt(i) == '(' || cur.charAt(i) == ')') {
                        next.add(cur.substring(0, i) + cur.substring(i+1));
                    }
                }
            }
            set = next;
        }
    }

    public boolean isValid(String s) {
        char[] cs = s.toCharArray();
        int l = 0, r = 0;
        for (char c : cs) {
            if (c == '(') {
                l++;
            } else if (c == ')') {
                if (l == 0) {
                    r++;
                } else {
                    l--;
                }
            }
        }
        return l == 0 && r == 0;
    }
}

# 剑指 Offer 29. 顺时针打印矩阵

题目很简单，但我代码实现得太复杂了

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if (matrix.length == 0) return new int[]{};
        int row = matrix.length, col = matrix[0].length;
        boolean[][] visited = new boolean[row][col];
        int[][] d = new int[][]{{0,1}, {1,0}, {0,-1}, {-1,0}};
        int sr = 0, sc = 0;
        int[] res = new int[row*col];
        int index = 0;
        while (sr < row && sc < col && !visited[sr][sc]) {
            int r = sr, c = sc;
            for (int i = 0; i < 4; i++) {
                if (i != 0) {
                    r = r+d[i][0];
                    c = c+d[i][1];
                }
                while (r >= 0 && c >= 0 && r < row && c < col && !visited[r][c]) {
                    res[index++] = matrix[r][c];
                    visited[r][c] = true;
                    int tr = r+d[i][0];
                    int tc = c+d[i][1];
                    if (!(tr >= 0 && tc >= 0 && tr < row && tc < col && !visited[tr][tc])) {
                        break;
                    }
                    r = r+d[i][0];
                    c = c+d[i][1];
                }
            }
            sr++;
            sc++;
        }
        return res;
    }
}

# 剑指 Offer 59 - II. 队列的最大值

优先队列

class MaxQueue {
    List<Integer> list = new ArrayList<>();
    PriorityQueue<Integer> pq;
    int l = 0;
    int r = 0;
    public MaxQueue() {
        pq = new PriorityQueue<>((a,b) -> list.get(b)-list.get(a));
    }
    
    public int max_value() {
        while (!pq.isEmpty() && pq.peek() < l) {
            pq.poll();
        }
        if (pq.isEmpty()) {
            return -1;
        }
        return list.get(pq.peek());
    }
    
    public void push_back(int value) {
        list.add(value);
        pq.offer(r++);
    }
    
    public int pop_front() {
        if (l == r) {
            return -1;
        }
        return list.get(l++);
    }
}

# 剑指 Offer 62. 圆圈中最后剩下的数字

class Solution {
    public int lastRemaining(int n, int m) {
        int ans = 0;
        for (int i = 2; i <= n; i++) {
            ans = (ans+m) % i;
        }
        return ans;
    }
}

# 剑指 Offer 49. 丑数

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n+1];
        int a = 1, b = 1, c = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[a]*2, Math.min(dp[b]*3, dp[c]*5));
            if (dp[i] == dp[a]*2) {
                a++;
            }
            if (dp[i] == dp[b]*3) {
                b++;
            }
            if (dp[i] == dp[c]*5) {
                c++;
            }
        }
        return dp[n];
    }
}

# 剑指 Offer 17. 打印从1到最大的n位数

class Solution {
    public int[] printNumbers(int n) {
        int pow = (int) Math.pow(10, n);
        int[] res = new int[pow-1];
        for (int i = 0; i < pow-1; i++) {
            res[i] = i+1;
        }
        return res;
    }
}

# 剑指 Offer 31. 栈的压入、弹出序列

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int a = 0, b = 0;
        Stack<Integer> s = new Stack<>();
        while (a < pushed.length) {
            s.push(pushed[a++]);
            while (!s.empty() && s.peek() == popped[b]) {
                b++;
                s.pop();
            }
        }
        if (s.size() != (popped.length-b)) {
            return false;
        }
        while (!s.empty() && b < popped.length) {
            if (s.pop() != popped[b]) {
                return false;
            } else {
                b++;
            }
        }
        return b == popped.length;
    }
}

# 剑指 Offer 56 - II. 数组中数字出现的次数 II

class Solution {
    public int singleNumber(int[] nums) {
        int ones = 0, twos = 0;
        for (int num : nums) {
            ones = ones ^ num & (~twos);
            twos = twos ^ num & (~ones);
        }
        return ones;
    }
}

# 剑指 Offer 59 - I. 滑动窗口的最大值

优先队列

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n == 0) return new int[]{};
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> nums[b]-nums[a]);
        int[] res = new int[n-k+1];
        int r = 0, i = 0;
        while (r < n) {
            while (r < n && r < k-1) {
                pq.offer(r++);
            }

            pq.offer(r);
            while (pq.peek() < r-(k-1)) {
                pq.poll();
            }
            res[i++] = nums[pq.peek()];
            r++;
        }
        return res;
    }
}

# 剑指 Offer 38. 字符串的排列

class Solution {
    Set<String> res = new HashSet<>();
    int n;
    public String[] permutation(String s) {
        n = s.length();
        dfs(s.toCharArray(), new boolean[n], new StringBuilder());
        return res.toArray(new String[res.size()]);
    }

    private void dfs(char[] cs, boolean[] visited, StringBuilder s) {
        if (s.length() == n) {
            res.add(s.toString());
            return;
        }
        for (int i = 0; i < cs.length; i++) {
            // if (i > 0 && cs[i] == cs[i-1] && !visited[i-1]) continue;
            if (visited[i]) continue;
            visited[i] = true;
            s.append(cs[i]);
            dfs(cs, visited, s);
            visited[i] = false;
            s.deleteCharAt(s.length()-1);
        }
    }
}

# 剑指 Offer 16. 数值的整数次方

class Solution {
    public double myPow(double x, int n) {
        double ans = 1d;
        long nn = n;
        boolean neg = false;
        if (nn < 0) {
            neg = true;
            nn = -nn;
        }
        while (nn != 0) {
            if ((nn&1) == 1) {
                ans *= x;
            }
            nn = nn >> 1;
            x = x*x;
        }
        return neg ? 1/ans : ans;
    }
}

# 剑指 Offer 60. n个骰子的点数

class Solution {
    public double[] dicesProbability(int n) {
        int max = 6*n;
        double[][] dp = new double[n+1][max+1];
        // init
        Arrays.fill(dp[0], 1d);
        for (int i = 1; i <= n; i++) {
            max = 6*(i-1);
            int min = i-1;
            for (int j = min; j <= max; j++) {
                for (int k = 1; k <= 6; k++) {
                    dp[i][j+k] += (dp[i-1][j]*(1d/6d));
                    // System.out.println(dp[i][j+k]);
                }
            }
        }
        // System.out.println(Arrays.deepToString(dp));
        double[] ans = new double[5*n+1];
        for (int i = ans.length-1, j = dp[n].length-1; i >= 0; i--, j--) {
            ans[i] = dp[n][j];
        }
        return ans;
    }
}

# 869. 重新排序得到 2 的幂

class Solution {
    public boolean reorderedPowerOf2(int n) {
        Map<Integer, Integer> origin = new HashMap<>();
        String sn  = String.valueOf(n);
        for (char c : sn.toCharArray()) {
            int ci = c-'0';
            origin.put(ci, origin.getOrDefault(ci, 0)+1);
        }
        for (int i = 0; i < 31; i++) {
            String sk  = String.valueOf(1 << i);
            Map<Integer, Integer> compare = new HashMap<>();
            for (char c : sk.toCharArray()) {
                int ci = c-'0';
                compare.put(ci, compare.getOrDefault(ci, 0)+1);
            }
            if (origin.equals(compare)) return true;
        }
        return false;
    }
}

# 剑指 Offer 14- II. 剪绳子 II

涉及数学，又是一脸懵逼

# 325. 和等于 k 的最长子数组长度

class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int n = nums.length;
        int[] pre = new int[n];
        pre[0] = nums[0];
        for (int i = 1; i < n; i++) {
            pre[i] = nums[i] + pre[i-1];
        }
        // System.out.println(Arrays.toString(pre));
        map.put(0, -1);
        int max = 0;
        for (int i = 0; i < n; i++) {
            Integer index = map.get(pre[i]-k);
            if (index != null) {
                max = Math.max(max, i-index);
                // System.out.println("i"+i+"; index"+index);
            }
            if (map.get(pre[i]) == null) {
                map.put(pre[i], i);
            }
        }
        return max;
    }
}

# 1039. 多边形三角剖分的最低得分

# 剑指 Offer 07. 重建二叉树

class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return recursive(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }

    private TreeNode recursive(int[] preorder, int pl, int pr, int[] inorder, int il, int ir) {
        if (pl == pr) {
            return null;
        }
        if (pl+1 == pr) {
            return new TreeNode(preorder[pl]);
        }
        int rootVal = preorder[pl];
        int rootIndex = map.get(rootVal);       

        TreeNode root = new TreeNode(inorder[rootIndex]);
        root.left = recursive(preorder, pl+1, pl+1+(rootIndex-il), inorder, il, rootIndex);
        root.right = recursive(preorder, pl+1+(rootIndex-il), pr, inorder, rootIndex+1, ir);
        return root;
    }
}

# 剑指 Offer 33. 二叉搜索树的后序遍历序列

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return verifyPostorder(postorder, 0, postorder.length);
    }

    private boolean verifyPostorder(int[] postorder, int left, int right) {
        if (left < 0 || right <= 0 || right-left <= 1) {
            return true;
        }
        int rootVal = postorder[right-1];
        int leftIndex = -1;
        for (int i = right-2; i >= left; i--) {
            if (postorder[i] < rootVal) {
                leftIndex = i;

                for (int j = leftIndex-1; j >= left; j--) {
                    if (postorder[j] > rootVal) {
                        return false;
                    }
                }
                return verifyPostorder(postorder, left, leftIndex+1) && verifyPostorder(postorder, leftIndex+1, right-1);
            }
        }
        return verifyPostorder(postorder, left, right-1);
    }
}

# 剑指 Offer 19. 正则表达式匹配

# 335. 路径交叉

# 剑指 Offer 36. 二叉搜索树与双向链表

class Solution {
    public Node treeToDoublyList(Node root) {
        if (root == null) return null;
        Node[] res = dfs(root);
        res[0].left = res[1];
        res[1].right = res[0];
        return res[0];
    }

    private Node[] dfs(Node root) {
        Node[] res = new Node[]{root, root};
        if (root == null) return res;
        
        if (root.left != null) {
            Node[] left = dfs(root.left);
            res[0] = left[0];
            root.left = left[1];
            left[1].right = root;
        }
        

        if (root.right != null) {
            Node[] right = dfs(root.right);
            res[1] = right[1];
            root.right = right[0];
            right[0].left = root;
        }

        // System.out.println(res[0].val + "; "+ res[1].val);
        return res;
    }
}

# 剑指 Offer 43. 1～n 整数中 1 出现的次数

class Solution {
    public int countDigitOne(int n) {
        int high = n / 10;
        int low = 0;
        int digit = 1;
        int cur = n % 10;
        int cnt = 0;
        while (high != 0 || cur != 0) {
            if (cur == 0) {
                cnt += high*digit;
            } else if (cur == 1) {
                cnt += high*digit+low+1;
            } else {
                cnt += (high+1)*digit;
            }
            low += cur * digit;
            cur = high % 10;
            high /= 10;
            digit *= 10;
        }
        return cnt;
    }
}

# 剑指 Offer 44. 数字序列中某一位的数字

class Solution {
    public int findNthDigit(int n) {
        if (n == 0) return 0;
        int digit = 1;
        long start = 1;
        long cnt = 9;
        while (n > cnt) {
            n -= cnt;
            digit += 1;
            start *= 10;
            cnt = digit * 9 * start;
        }
        long num = start + (n-1)/digit;
        int index = (n-1)%digit;
        return String.valueOf(num).charAt(index)-'0';
    }
}

对于分类讨论的题，总是会做很久，思考得不是很清晰，并且相对来说做得复杂了。

class Solution {
    public int findNthDigit(int n) {
        int digit = 1;
        double minus = 9 * Math.pow(10, digit-1) * digit;

        while (n > minus) {
            n -= (int)minus;
            digit++;
            minus = 9 * Math.pow(10, digit-1) * digit;
        }

        int divide = n / digit;
        int mod = n % digit;
        
        int pow = (int)Math.pow(10, digit-1);
        int val = pow + divide - 1;
        if (mod == 0) {
            return String.valueOf(val).charAt(digit-1)-'0';
        } else {
            return String.valueOf(val+1).charAt(mod-1)-'0';
        }
    }
}

# 剑指 Offer 20. 表示数值的字符串

# 剑指 Offer 67. 把字符串转换成整数

class Solution {
    int bandary = Integer.MAX_VALUE / 10;
    public int strToInt(String str) {
        if (str == null || str.length() == 0) return 0;
        int index = 0;
        while (index < str.length() && str.charAt(index) == ' ') {
            index++;
        }
        if (index >= str.length()) return 0;

        char first = str.charAt(index);
        if (!((first >= 48 && first <= 57) || (first == '+' || first == '-'))) {
            return 0;
        }
        
        boolean neg = false;
        if (first == '+' || first == '-') {
            if (first == '-') neg = true;
            index++;
        }

        if (index >= str.length()) return 0;

        int digit = 0;
        int res = 0;
        while (index < str.length() && str.charAt(index) >= 48 && str.charAt(index) <= 57) {
            if (res > bandary || res == bandary && str.charAt(index) > '7') return (neg ? Integer.MIN_VALUE : Integer.MAX_VALUE);
            res *= 10;
            res += (str.charAt(index)-48);
            index++;
            digit++;
        }

        return neg ? res*-1 : res;
    }
}

# 260. 只出现一次的数字 III

class Solution {
    public int[] singleNumber(int[] nums) {
        int xor = 0;
        for (int i : nums) {
            xor ^= i;
        }
        int pos = 0;
        for (int i = 0; i < 32; i++) {
            if ((xor & 1) == 1) {
                pos = i;
            }
            xor = xor >> 1;
        }
        int a = 0, b = 0;
        for (int i : nums) {
            if (((i >> pos) & 1) == 1) {
                a ^= i;
            } else {
                b ^= i;
            }
        }
        return new int[]{a, b};
    }
}

# 500. 键盘行

暴力解

class Solution {
    static Set<Character>[] sets = new HashSet[3];    
    static {
        String a = "qwertyuiop";
        String b = "asdfghjkl";
        String c = "zxcvbnm";
        Set<Character> set = new HashSet<>();
        for (char cc : a.toCharArray()) {
            set.add(cc);
            set.add((char) (cc-32));
        }
        sets[0] = set;
        set = new HashSet<>();
        for (char cc : b.toCharArray()) {
            set.add(cc);
            set.add((char) (cc-32));
        }
        sets[1] = set;
        set = new HashSet<>();
        for (char cc : c.toCharArray()) {
            set.add(cc);
            set.add((char) (cc-32));
        }
        sets[2] = set;
        // System.out.println(Arrays.toString(sets));
    }
    public String[] findWords(String[] words) {
        List<String> res = new ArrayList<>();
        for (String w : words) {
            char[] cs = w.toCharArray();
            for (Set set : sets) {
                int i = 0;
                for (; i < cs.length; i++) {
                    // char up = (char) (cs[i]-32);
                    if (!set.contains(cs[i])) {
                        // System.out.println(cs[i]);
                        break;
                    }
                }
                if (i == cs.length) {
                    res.add(w);
                }
            }
        }
        return res.toArray(new String[res.size()]);
    }
}
修改于: 8/11/2022, 3:17:56 PM

← LeetCode 6 →