Note for LeetCode in Java (800~1200)

Posted on | Edited on | In | | Views:
Symbols count in article: 173k | Reading time ≈ 3:01

刷题。祝我好运。

802. find-eventual-safe-states

  • 给一个2D array，每一个行数组表示该index的邻居，所有的点和边可以形成directed graph。求所有最终能稳定的点（所有的邻居点都不会陷入一个无限循环的path）。
  • DFS过程中记录当前path的visited情况，一旦回头了就说明当前节点是有环（无限）的。利用memo来提升DFS性能，防止重复DFS。事实上可以利用bucket代替visited的功能，例如赋一个特殊值表示on path。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    class Solution {
        public List<Integer> eventualSafeNodes(int[][] graph) {
            List<Integer> ans = new ArrayList<>();
            if (graph == null || graph.length == 0) {
                return ans;
            }
        
            int[] bucket = new int[graph.length];
            boolean[] visited = new boolean[graph.length];
            for (int i = 0; i < graph.length; i++) {
                if (dfs(graph, i, bucket, visited)) {
                    ans.add(i);
                }
            }
            
            return ans;
        }
        private boolean dfs(int[][] graph, int index, int[] bucket, boolean[] visited) {
            if (bucket[index] > 0) {
                return true;
            } else if (bucket[index] < 0) {
                return false;
            }
            visited[index] = true;
            for (int neighbor : graph[index]) {
                
                if (visited[neighbor] || !dfs(graph, neighbor, bucket, visited)) {
                    bucket[index] = -1;
                    visited[index] = false;
                    return false;
                }
            }
            visited[index] = false;
            bucket[index] = 1;
            return true;
        }
    }

804. unique-morse-code-words

  • 摩斯电码转换，记录总共出现了几种不同的组合。skip.

805. find-mode-in-binary-search-tree

  • 给一个特殊BST（左右子树不是严格小于/大于，可以等于），求节点的众数，可能有多个众树，按任意顺序返回。不能使用Map。
  • inorder + twopass.第一次先求出众数，第二次则是将计数与众数匹配的存入结果。pass。

806. number-of-lines-to-write-string

  • 输出字母求需要占用多少宽度。skip.

807. max-increase-to-keep-city-skyline

  • 给一个二维数组表示各个摩天大楼的高度，从左右两侧和前后两侧看的skyline相同的情况下，最多共可以升高多少。skip.

809. expressive-words

  • 给一个字符串S和一个字符串数组，判断数组中有多少个可以stretch成S. stretch规则是，对于一组相同的字母可以通过扩展得到S中相应的一组、且stretch后S中该组字母组个数不少于3个。
  • 暴力解。通过cache提速。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    class Solution {
        public int expressiveWords(String S, String[] words) {
            if (S == null || S.length() == 0 || words == null || words.length == 0) {
                return 0;
            }
            int count = 0;
            Set<String> matchSet = new HashSet<>();
            Set<String> notMatchSet = new HashSet<>();
            for (String word : words) {
                if (matchSet.contains(word)) {
                    count++;
                } else if (notMatchSet.contains(word)) {
                    continue;
                } else if (isStretchy(S, word)) {
                    count++;
                    matchSet.add(word);
                } else {
                    notMatchSet.add(word);
                }
            }
            return count;
        }
        private boolean isStretchy(String source, String target) {
            char[] sourceCharArray = source.toCharArray(), targetCharArray = target.toCharArray();
            int sourceIndex = 0, targetIndex = 0;
            while (sourceIndex < sourceCharArray.length && targetIndex < targetCharArray.length) {
                char c = sourceCharArray[sourceIndex];
                int sourceCount = 0, targetCount = 0;
                while (sourceIndex < sourceCharArray.length && sourceCharArray[sourceIndex] == c) {
                    sourceCount++;
                    sourceIndex++;
                }
                while (targetIndex < targetCharArray.length && targetCharArray[targetIndex] == c) {
                    targetCount++;
                    targetIndex++;
                }
                if (targetCount > 0 &&
                    (targetCount == sourceCount || (sourceCount > targetCount && sourceCount >= 3))) {
                    continue;   // 注意必须sourceCount超过sourceCount
                } else {
                    return false;
                }
            }
            return sourceIndex == sourceCharArray.length && targetIndex == targetCharArray.length;
        }
    }

814. binary-tree-pruning

  • 给一个只含有1/0的二叉树，如果一个subtree只含有0，需要把这部分消去。返回消去后的树。
  • 递归搞定。pass。

817. linked-list-components

  • 给一个链表表示int之间的链接关系，给一个数组，求数组中在链表中连续出现的团簇数。
  • 将数组的元素放入Set后开始遍历链表，Set中存在该元素就remove掉，不存在则结束统计前一个团簇，开始找下一个团簇，最后return之前还需要判断是否已经找到了团簇。

819. most-common-word

  • 给一段String文本，给一个banned数组作为stopword，求最频繁出现的词。split之后统计频数即可，skip。

821. shortest-distance-to-a-character

  • 给一个字符串S和一个特定字符C，C一定会出现在S中，求各个位置的字符距离最近的字符C的距离。
  • 2-pass的做法，首先从左往右更新，若当前字符为C则将index设为该索引，这样后续的距离就是i - index了。需要注意的是初始化时为了让i - index尽量大，需要初始化为负的数组长度。这一波结束之后，得到的是距离左边最近的C的距离，那么再从右往左更新即可，注意由于index可能比i小，需要取abs。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class Solution {
        public int[] shortestToChar(String S, char C) {
            if (S == null || S.isEmpty()) {
                return new int[0];
            }
            int[] retVal = new int[S.length()];
            char[] charS = S.toCharArray();
            int index = -S.length();    // 保证一开始的字符足够大
            for (int i = 0; i < charS.length; i++) {
                if (charS[i] == C) {
                    index = i;
                }
                retVal[i] = i - index;
            }
            for (int i = charS.length - 1; i >= 0; i--) {
                if (charS[i] == C) {
                    index = i;
                }
                retVal[i] = Math.min(Math.abs(index - i), retVal[i]);
            }
            return retVal;
        }
    }

825. friends-of-appropriate-ages

  • 给一个int数组表示用户的年龄，假设age[B] <= 0.5 * age[A] + 7, age[B] > age[A], age[B] > 100 && age[A] < 100的情况下A都不会给B发好友request，求共有多少个request。
  • 首先把题目条件简化得到「A会给B发好友request」的区间，然后考虑如何快速得到对应年龄范围的人数——runningSum法。之后就是对每一个年龄求他和多少好友会发request，注意for-loop的起始索引。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    class Solution {
        public int numFriendRequests(int[] ages) {
            if (ages == null || ages.length == 0) {
                return 0;
            }
            int[] ageCount = new int[121];  // 每个年龄有多少人
            for (int age : ages) {
                ageCount[age]++;
            }
            
            int[] sums = new int[121];      // runningSum快速求给定年龄区间的人数
            for (int i = 1; i < ageCount.length; i++) {
                sums[i] = sums[i - 1] + ageCount[i];
            }
            
            int ans = 0;
            for (int i = 15; i < sums.length; i++) {    // 注意需要从15开始
                if (ageCount[i] == 0) {
                    continue;
                }
                int count = sums[i] - sums[i / 2 + 7];  // 当前与合适范围年龄的request数
                ans += count * ageCount[i] - ageCount[i];   // 减去自己给自己的request
            }
            return ans;
        }
    }

827. making-a-large-island

  • 给一个只含有0和1的grid，求将其中某一个0替换成1后形成island的最大面积。如果没有0则是整个棋盘的面积。
  • 对于每一个1进行连通上色，同时维护一个colorMap表示每种颜色对应的island有多少。最后再遍历每一个0看看它周围四个方向分别是什么颜色，然后对应取个数即可。用一个getValue的wrapper函数专门用于访问matrix中的值，让代码简洁了不少。BFS和DFS都差不多。BFS需要注意上色时机，在加入queue的时候就需要上色，否则上下左右的时候可能会重复上色。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    class Solution {
        public int largestIsland(int[][] grid) {
            if (grid == null || grid.length == 0 || grid[0].length == 0) {
                return 0;
            }
            int rows = grid.length, cols = grid[0].length;
            List<Integer> colorSize = new ArrayList<>();   // force color starts with 2
            colorSize.add(0);
            colorSize.add(0);
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    if (grid[i][j] == 1) {
                        // colorSize.add(dfs(grid, i, j, colorSize.size()));
                        colorSize.add(bfs(grid, i, j, colorSize.size()));
                    }
                }
            }
            int max = 0;
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    if (grid[i][j] == 0) {
                        Set<Integer> set = new HashSet<>();
                        set.add(getValue(grid, i - 1, j));
                        set.add(getValue(grid, i + 1, j));
                        set.add(getValue(grid, i, j - 1));
                        set.add(getValue(grid, i, j + 1));
                        int curr = 0;
                        for (Integer color : set) {
                            curr += colorSize.get(color);
                        }
                        max = Math.max(curr + 1, max);
                    }
                }
            }
            return max == 0 ? rows * cols : max;
        }
        // wrap到一个函数中去访问cell，省去很多判断
        private int getValue(int[][] grid, int i, int j) {
            return (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) ? 0 : grid[i][j];
        }
        private int dfs(int[][] grid, int i, int j, int color) {
            if (getValue(grid, i, j) != 1) {
                return 0;
            }
            grid[i][j] = color;
            return 1 + dfs(grid, i - 1, j, color) + dfs(grid, i + 1, j, color)
                + dfs(grid, i, j - 1, color) + dfs(grid, i, j + 1, color);
        }
        private int bfs(int[][] grid, int i, int j, int color) {
            Queue<int[]> q = new LinkedList<>();
            q.offer(new int[] {i, j});
            grid[i][j] = color;
            int size = 0;
            while (!q.isEmpty()) {
                int currSize = q.size();
                size += currSize;
                while (currSize-- > 0) {
                    int[] temp = q.poll();
                    int row = temp[0], col = temp[1];
                    if (getValue(grid, row - 1, col) == 1) {
                        q.offer(new int[] {row - 1, col});
                        grid[row - 1][col] = color;
                    }
                    if (getValue(grid, row + 1, col) == 1) {
                        q.offer(new int[] {row + 1, col});
                        grid[row + 1][col] = color;
                    }
                    if (getValue(grid, row, col - 1) == 1) {
                        q.offer(new int[] {row, col - 1});
                        grid[row][col - 1] = color;
                    }
                    if (getValue(grid, row, col + 1) == 1) {
                        q.offer(new int[] {row, col + 1});
                        grid[row][col + 1] = color;
                    }
                }
            }
            return size;
        }
    }

829. consecutive-numbers-sum

  • 给一个正整数N，求它等于多少组连续正整数之和。例如1就它本身1种，9 = 9 = 4 + 5 = 2 + 3 + 4共3种。
  • 数学规律，这里有很好的解释。本质上就是遍历可能的k求模，如果可以整除就说明是一种可能。时间复杂度log(sqrtN).
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution {
        public int consecutiveNumbersSum(int N) {
            if (N < 1) {
                return 0;
            }
            int count = 0;
            for (int k = 1; k < Math.sqrt(2 * N); k++) {
                if ((N - (k - 1) * k / 2) % k == 0) {
                    count++;
                }
            }
            return count;
        }
    }

833. find-and-replace-in-string

  • 给一个原字符串S，给indexes索引数组和两个字符串数组sources和targets，对于indexes中每一个索引判断是否由sources中对应的字符串startsWith，是则替换撑targets。
  • 由于target替换后对原字符串的长度可能有影响，因此不能直接用index来替换。使用一个indexDelta记录每次成功替换之后后续的index需要平移多少。注意需要保证index是从小到大进行替换的，否则后面的平移不应该影响到前面的平移。

834. sum-of-distances-in-tree

  • 给一个共有N个节点的无向连通树，编号为0 ~ N-1，求每一个节点到其他所有节点的距离和。
  • 从一个节点出发到其他所有节点是O(N)，如果暴力求每个节点那就是O(N^2). 但是在遍历的过程中显然有很多重复的计算。观察到一个规律就是从一个parent节点到它的孩子节点时，parent节点到前序节点的距离变长、到后续节点的距离变近。如果给定一个节点能够知道它subtree总共含有多少个节点，那么距离就加/减这部分节点即可。因此解法是，构建图（树）之后，首先进行后序遍历维护一个nodeCounts数组来知道每个节点及其下方有多少节点，采用后序是因为parent需要依赖于所有孩子节点的nodeCounts。遍历过程中可以通过prev来防止往回递归。在后序遍历的同时维护result数组表示每个节点到它所有的孩子节点的距离只和。下一步进行前序遍历，对于每一个孩子节点都依赖于parent节点的距离和，到paernt即前序节点的距离++、到该孩子后序节点的距离–，对应过来就是result[parent] - nodeCounts[child] + (N - nodeCounts[child]).
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    class Solution {
        public int[] sumOfDistancesInTree(int N, int[][] edges) {
            if (edges == null) {
                return new int[0];
            }
            Set<Integer>[] graph = buildGraph(N, edges);
            int[] nodeCounts = new int[N];
            int[] result = new int[N];
            postOrder(-1, 0, graph, nodeCounts, result);
            preOrder(-1, 0, graph, nodeCounts, result);
            return result;
        }
        private void postOrder(int prev, int curr, Set<Integer>[] graph, int[] nodeCounts, int[] result) {
            for (int neighbor : graph[curr]) {
                if (neighbor == prev) {
                    continue;
                }
                postOrder(curr, neighbor, graph, nodeCounts, result);
                nodeCounts[curr] += nodeCounts[neighbor];
                result[curr] += result[neighbor] + nodeCounts[neighbor];
            }
            nodeCounts[curr]++; // curr本身
        }
        private void preOrder(int prev, int curr, Set<Integer>[] graph, int[] nodeCounts, int[] result) {
            for (int neighbor : graph[curr]) {
                if (neighbor == prev) {
                    continue;
                }
                result[neighbor] = result[curr] - nodeCounts[neighbor] + (nodeCounts.length - nodeCounts[neighbor]);
                preOrder(curr, neighbor, graph, nodeCounts, result);
            }
        }
        private Set<Integer>[] buildGraph(int N, int[][] edges) {
            Set<Integer>[] graph = new Set[N];
            for (int i = 0; i < N; i++) {
                graph[i] = new HashSet<>();
            }
            
            for (int[] edge : edges) {
                graph[edge[0]].add(edge[1]);
                graph[edge[1]].add(edge[0]);
            }
            return graph;
        }
    }

835. image-overlap

  • 给两个binary square matrix，只有0和1两个数值，将两个矩阵上下左右移动，问重叠的1最多有多少个。
  • 将二维问题flatten成一维，然后在一维List中遍历每一个cell与另一个矩阵的每一个cell重叠后是否都是1，然后将结果存入map。如何判定是否是相同的平移之后的结果呢？利用一维List的索引之差即可。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    class Solution {
        public int largestOverlap(int[][] A, int[][] B) {
            if (A == null || B == null) {
                return 0;
            }
            int N = A.length;
            List<Integer> listA = new ArrayList<>();
            List<Integer> listB = new ArrayList<>();
            for (int i = 0; i < N * N; i++) {
                if (A[i / N][i % N] == 1) {
                    listA.add(i / N * 100 + i % N);
                }
                if (B[i / N][i % N] == 1) {
                    listB.add(i / N * 100 + i % N);
                }
            }
        
            Map<Integer, Integer> count = new HashMap<>();
            for (int i : listA) {
                for (int j : listB) {
                    count.put(i - j, count.getOrDefault(i - j, 0) + 1);
                }
            }
            int max = 0;
            for (int val : count.values()) {
                max = Math.max(max, val);
            }
            return max;
        }
    }

836. rectangle-overlap

  • 给两个数组表示二维平面中矩形左下角的定点和右上角的定点。判断是否overlap。
  • 转换成一维线段来判断，两个线段有overlap的充分必要条件是left1 < right2 && left2 < right1，那么推广到2D中就是x方向上用一次、y方向上用一次，都满足就一定有overlap了。
    1
    2
    3
    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        return rec1[0] < rec2[2] && rec2[0] < rec1[2] && rec1[1] < rec2[3] && rec2[1] < rec1[3];
    }

838. push-dominoes

  • 给一个只含有R, L, .的字符串，表示往右或者往左推多米诺骨牌，假设所有推都同时发力，求最后的倾斜状态。

  • 方法一：双指针一前一后，如果前后指针指向的是一样的方向，那这段中间直接填满即可；如果恰好是后指针是向右、前指针是向左，则填充中间部分即可。其他情况直接维持原字符串不变。需要在一头一尾加上L、R。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    class Solution {
        public String pushDominoes(String dominoes) {
            if (dominoes == null || dominoes.length() == 0) {
                return dominoes;
            }
            dominoes = "L" + dominoes + "R";
            char[] chars = dominoes.toCharArray();
            int left = 0, right = 0, len = chars.length;
            
            while (left < len - 1) {
                right = left + 1;
                while (right < len && chars[right] == '.') {
                    right++;
                }
                
                if (chars[left] == chars[right]) {
                    Arrays.fill(chars, left, right + 1, chars[left]);
                } else if (chars[left] == 'R' && chars[right] == 'L') {
                    int delta = (right - left - 1) / 2;
                    Arrays.fill(chars, left, left + delta + 1, chars[left]);
                    Arrays.fill(chars, right - delta, right + 1, chars[right]);
                }
                
                left = right;
            }
            return new String(Arrays.copyOfRange(chars, 1, len - 1));
        }
    }

  • 方法二：物理法，需要维护一个force数组，从左到右看看R有多强、从右到左看L有多强，在每一个对应点根据正、负情况来赋字符即可。

839. similar-string-groups

  • 给一个长度相同且互为anagram的String数组，求总共有多少组similar的词。similar指的是A只swap一对儿字符能够equal B。
  • DFS/BFS均可，访问每个word时往后搜只有两位字符不同的标记为visited，这样当前dfs完成后就是一个similar group.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    class Solution {
        public int numSimilarGroups(String[] A) {
            if (A == null || A.length == 0) {
                return 0;
            }
            int count = 0;
            boolean[] visited = new boolean[A.length];
            for (int i = 0; i < A.length; i++) {
                if (!visited[i]) {
                    visited[i] = true;
                    dfs(A, A[i], visited);
                    count++;
                }
            }
            return count;
        }
        public void dfs(String[] A, String str, boolean[] visited) {
            for (int i = 0; i < A.length; i++) {
                if (!visited[i] && isDiffBy2(str, A[i])) {
                    visited[i] = true;
                    dfs(A, A[i], visited);
                }
            }
        }
        private boolean isDiffBy2(String str1, String str2) {
            int diff = 0;
            for (int i = 0; i < str1.length(); i++) {
                if (str1.charAt(i) != str2.charAt(i)) {
                    diff++;
                }
                if (diff > 2) {
                    return false;
                }
            }
            return true;
        }
    }

841. keys-and-rooms

  • 给一个rooms nested list，每一个row list表示该room存放的所有key list，一开始只有room 0可以进入，其余房间都必须有对应钥匙才能进入。判断能否进所有的房间。BFS和DFS都可以搞定。

843. guess-the-word

  • 给一个String数组，每一个词都是6个字符，通过调用给定的API猜其中的一个secret word，每次调用API时都会返回所给词和secret词的match字符数。

  • 通过random的办法，随机选取一个String猜，然后根据返回的字符匹配数，将原List中所有和所给字符串匹配数相等的字符保留下来，然后继续随机取字符串去猜。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    class Solution {
        public void findSecretWord(String[] wordlist, Master master) {
            if (wordlist == null || wordlist.length == 0) {
                return;
            }
            List<String> wordList = Arrays.asList(wordlist);
            for (int i = 0, ret = 0; i < 10 && ret < 6; i++) {
                String input = wordList.get(new Random().nextInt(wordList.size()));
                ret = master.guess(input);
                List<String> wordListNew = new ArrayList<>();
                for (String word : wordList) {
                    if (getMatchCount(word, input) == ret) {
                        wordListNew.add(word);
                    }
                }
                wordList = wordListNew;
            }
        }
        private int getMatchCount(String str1, String str2) {
            int count = 0;
            for (int i = 0; i < str1.length(); i++) {
                if (str1.charAt(i) == str2.charAt(i)) {
                    count++;
                }
            }
            return count++;
        }
    }

  • 纯粹的随机并不是一个最优策略，可以先在给定的String数组内部找到「与其他字符串完全不match最少的」字符串来猜。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    class Solution {
        public void findSecretWord(String[] wordlist, Master master) {
            if (wordlist == null || wordlist.length == 0) {
                return;
            }
            List<String> wordList = Arrays.asList(wordlist);
            for (int i = 0, ret = 0; i < 10 && ret < 6; i++) {
                Map<String, Integer> zeroMatchCount = new HashMap<>();
                for (String str1 : wordList) {
                    for (String str2 : wordList) {
                        if (getMatchCount(str1, str2) == 0) {
                            zeroMatchCount.put(str1, zeroMatchCount.getOrDefault(str1, 0) + 1);
                        }
                    }
                }
                int minZeroCount = Integer.MAX_VALUE;
                String input = "";
                for (String str : wordList) {
                    if (zeroMatchCount.getOrDefault(str, 0) < minZeroCount) {
                        input = str;
                        minZeroCount = zeroMatchCount.getOrDefault(str, 0);
                    }
                }
                ret = master.guess(input);
                List<String> wordListNew = new ArrayList<>();
                for (String word : wordList) {
                    if (getMatchCount(word, input) == ret) {
                        wordListNew.add(word);
                    }
                }
                wordList = wordListNew;
            }
        }
    }

844. backspace-string-compare

  • 给两个字符串，含有#表示backspace回删符号，判断这两个字符串是否相等。
  • 面试原题，从后往前判断即可达到O(1)空间。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    class Solution {
        public boolean backspaceCompare(String S, String T) {
            if (S == null || T == null) {
                return false;
            }
            int indexS = S.length() - 1, indexT = T.length() - 1;
            while (true) {
                indexS = getPrevIndex(S, indexS);
                indexT = getPrevIndex(T, indexT);
                if (indexS < 0 && indexT < 0) {
                    return true;
                }
                if (indexS < 0 || indexT < 0 || S.charAt(indexS) != T.charAt(indexT)) {
                    return false;
                }
                indexS--;
                indexT--;
            }
        }
        private int getPrevIndex(String str, int currIndex) {
            int delCount = 0;
            while (currIndex >= 0) {
                if (str.charAt(currIndex) == '#') {
                    delCount++;
                } else {
                    if (delCount > 0) {
                        delCount--;
                    } else {
                        break;   // 直到找到新的可供对比的字符
                    }
                }
                currIndex--;
            }
            return currIndex;
        }
    }

846. hand-of-straights

  • 给一个int数组表示一手牌，给一个整数W表示每一组牌的个数，判断是否可以重新整理形成顺子，每组顺子size都是W。
  • 对于每一个顺子，每一个数的总出现次数必须比最小的数的出现次数大，才能保证顺子的形成。因此考虑使用一个TreeMap将每个value和count存起来，然后从最小值开始遍历，将顺子中需要的value的count都对应消耗掉与最小值相等的量，一旦不符合就说明顺子断了。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    class Solution {
        public boolean isNStraightHand(int[] hand, int W) {
            if (hand == null || hand.length == 0) {
                return true;
            }
            if (W == 0 || hand.length % W != 0) {
                return false;    
            }
            Map<Integer, Integer> map = new TreeMap<>();
            for (int num : hand) {
                map.put(num, map.getOrDefault(num, 0) + 1);
            }
            
            for (int num : map.keySet()) {
                if (map.get(num) > 0) {
                    for (int i = W - 1; i >= 0; i--) {  // 遍历顺子中每个值
                        if (map.getOrDefault(num + i, 0) < map.get(num)) {
                            return false;
                        }
                        map.put(num + i, map.get(num + i) - map.get(num));  // 必须消耗掉与最小值对应的数量
                    }
                }
            }
            return true;
        }
    }

849. maximize-distance-to-closest-person

  • 给一个只含有0和1的数组，0表示没人坐，1表示有人坐，求某一个0使得离最近的人最远，返回最远距离。
  • 分情况讨论，如果最远出现在两侧以及出现在两个1之间。skip。

853. car-fleet

  • 若干辆车朝着target开，给一个position数组表示开始时车的位置，给一个speed数组表示每台车的速度。若后续车辆追上前面车则融合成一个以前面车的速度继续开。求到达终点的共有几台车。初识时每台车都在不同位置。
  • 利用TreeMap，每台车的剩余距离作为key、每台车的到达终点所需时间作为value，在TreeMap中按照剩余距离从小到大排序后从头遍历剩余时间，若后续车辆剩余时间比前面的短或相等，就说明会追上；若后续车辆所需时间比前面大，必定赶不上，因此它就作为后续集团的leading car。本质就是求有多少个leading car.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class Solution {
        public int carFleet(int target, int[] position, int[] speed) {
            if (position == null || position.length == 0
               || speed == null || speed.length == 0
               || position.length != speed.length) {
                return 0;
            }
            TreeMap<Integer, Double> map = new TreeMap<>();
            for (int i = 0; i < position.length; i++) {
                int distanceRemain = target - position[i];
                map.put(distanceRemain, (double)(distanceRemain) / speed[i]);
            }
            int count = 0;
            double prevTime = 0;
            for (double time : map.values()) {  // values按照distanceRemain从小到大排列
                if (time > prevTime) {          // 若当前所需时间大于前面的时间
                    prevTime = time;            // 则形成新的fleet
                    count++;
                }
            }
            return count;
        }
    }

854. k-similar-strings

  • 给A和B两个字符串，求最少需要swap多少次A中的字符使得最终能得到B。如果不可能则返回Integer.MAX_VALUE。
  • 从头开始遍历两个字符串，一旦遇到不同的字符，就在A中往后寻找B中该位的字符，尝试swap，然后从该位继续往后dfs一路搜下去。利用Map作为memo减少重复计算。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    class Solution {
        public int kSimilarity(String A, String B) {
            if (A == null || B == null || A.length() != B.length()) {
                return 0;
            }
            return dfs(A.toCharArray(), B, 0, new HashMap<String, Integer>());
        }
        private int dfs(char[] charA, String B, int index, Map<String, Integer> memo) {
            String A = new String(charA);
            if (A.equals(B)) {
                return 0;
            }
            if (memo.containsKey(A)) {
                return memo.get(A);
            }
            int i = index;
            while (i < charA.length && charA[i] == B.charAt(i)) {
                i++;
            }
            int min = Integer.MAX_VALUE;
            for (int j = i + 1; j < charA.length; j++) {
                if (charA[j] == B.charAt(i)) {      // 往后找对应字符出现的位置，一个个比较
                    swap(charA, i, j);
                    int nextMin = dfs(charA, B, i + 1, memo);
                    if (nextMin != Integer.MAX_VALUE && nextMin + 1 < min) {
                        min = nextMin + 1;
                    }
                    swap(charA, i, j);
                }
            }
            memo.put(A, min);
            return min;
        }
        private void swap(char[] arr, int i, int j) {
            char temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

855. exam-room

  • 一条线上可以容纳N个学生考试，调用seat()的时候表示需要新插入一个学生，返回与现有相邻学生距离最远的座位index，在相邻距离都一样的情况下，取index较小的available seat；调用leave(index)时则让相应位置的座位空出、之后可以使用。
  • 贪心，想像成切割/合并线段，每次新加入的学生就需要插入到线段两端最长的那个线段中点、如果相同则取index较小的。拿掉学生则是将相邻两个线段合并起来放回available线段集合中。为了每次取线段都能按照插入学生最方便的顺序来取，需要用到treeSet进行logN的插入、删除，排序的标准则是按照线段中点到两端的距离从大到小、相同的情况下按照起点index从小到大。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    class ExamRoom {
        private Map<Integer, int[]> start2Interval;
        private Map<Integer, int[]> end2Interval;
        private TreeSet<int[]> treeSet;
        private int N;
        
        public ExamRoom(int N) {
            start2Interval = new HashMap<>();
            end2Interval = new HashMap<>();
            treeSet = new TreeSet<>((a, b) -> {
                int len1 = getLength(a), len2 = getLength(b);
                return len1 == len2 ? a[0] - b[0] : len2 - len1;
            });
            addInterval(new int[]{-1, N});     // 虚拟线段(-1, N)
            this.N = N;
        }
        
        public int seat() {
            int[] interval = treeSet.first();
            removeInterval(interval);
            int left = interval[0], right = interval[1], seat = 0;
            if (left == -1) {   // 说明当前为空，直接取第一位
                seat = 0;
            } else if (right == N) {    // 说明当前除了第一位都为空，入座最后一位
                seat = N - 1;
            } else {
                seat = left + (right - left) / 2;  // 取中点
            }
            addInterval(new int[] {left, seat});
            addInterval(new int[] {seat, right});
            return seat;
        }
        
        public void leave(int p) {
            int[] right = start2Interval.get(p);
            int[] left = end2Interval.get(p);
            removeInterval(left);
            removeInterval(right);
            addInterval(new int[] {left[0], right[1]}); // 合并两旁的线段
        }
        
        private int getLength(int[] interval) {
            int left = interval[0], right = interval[1];
            if (left == -1) {
                return right;
            }
            if (right == N) {
                return N - 1 - left;
            }
            return (right - left) / 2;
        }
        
        private void removeInterval(int[] interval) {
            treeSet.remove(interval);
            start2Interval.remove(interval[0]);
            end2Interval.remove(interval[1]);
        }
        
        private void addInterval(int[] interval) {
            treeSet.add(interval);
            start2Interval.put(interval[0], interval);
            end2Interval.put(interval[1], interval);
        }
    }

858. mirror-reflection

  • 给整数p和q，p表示正方形空间的边长，q表示初始激光从左下射出的高度，在右下、右上、左上各右一个receptor标号为0、1、2，可以保证一定可以接收到，求接收到的receptor的id。
  • 激光射出后纵向移动达到q时，横向移动一定为p。假设把天花板去掉，无限往上反射x次，最终射到某个corner的时候，纵向上移动的距离恰好是p的某个倍数q*x == y*p，因此问题转换为求p和q的最小公倍数lcm，而lcm = p * q / gcd，用最大公约数可破。若lcm / p % 2 == 0，说明反射到了下面这个receptor，即0；否则再判断lcm / q % 2 == 0看看是否回到了左侧的recptor，即2。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    //   lcm / p % 2 + 1 - lcm / q % 2 
    // = p * q / gcd / p % 2 + 1 - p * q / gcd / q % 2
    // = 1 + q / gcd % 2 - p / gcd % 2
    class Solution {
        public int mirrorReflection(int p, int q) {
            if (p < 1 || q > p) {
                return 0;
            }
            int gcd = getGCD(p, q);
            return 1 + q / gcd % 2 - p / gcd % 2;
        }
        private int getGCD(int p, int q) {
            return q != 0 ? getGCD(q, p % q) : p;
        }
    }

860. lemonade-change

  • 给一个数组表示买柠檬汁的顾客的钱，只有5、10、20三种面额，每个顾客只买一杯柠檬汁，一开始手头没钱，判断按照顺序这样收银能否保证每个顾客都能找到钱。skip。

863. all-nodes-distance-k-in-binary-tree

  • 给一个二叉树和其中的一个节点target，求二叉树中距离target为K的所有节点。
  • 先一波DFS从root到target的backward path，然后从target开始沿三个方向开始BFS。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    class Solution {
        public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
            List<Integer> ans = new ArrayList<>();
            if (root == null || target == null) {
                return ans;
            }
            Map<TreeNode, TreeNode> prevNodeMap = new HashMap<>();
            Set<TreeNode> visited = new HashSet<>();
            if (!buildBackPath(target, root, null, prevNodeMap)) {
                return ans;
            }
            Queue<TreeNode> q = new LinkedList<>();
            q.offer(target);
            visited.add(target);
            int distance = 0;
            while (!q.isEmpty() && distance < K) {    
                int size = q.size();
                while (size-- > 0) {
                    TreeNode curr = q.poll();
                    if (prevNodeMap.containsKey(curr) && !visited.contains(prevNodeMap.get(curr))) {
                        visited.add(prevNodeMap.get(curr));
                        q.offer(prevNodeMap.get(curr));
                    }
                    if (curr.left != null && !visited.contains(curr.left)) {
                        visited.add(curr.left);
                        q.offer(curr.left);
                    }
                    if (curr.right != null && !visited.contains(curr.right)) {
                        visited.add(curr.right);
                        q.offer(curr.right);
                    }
                }
                distance++;
            }
            while (!q.isEmpty()) {
                ans.add(q.poll().val);
            }
            return ans;
        }
        private boolean buildBackPath(TreeNode target, TreeNode node, TreeNode prev, Map<TreeNode, TreeNode> prevNodeMap) {
            if (node == null) {
                return false;
            }
            if (prev != null) {
                prevNodeMap.put(node, prev);
            }
            if (node == target) {
                return true;
            }
            if (buildBackPath(target, node.left, node, prevNodeMap)
               || buildBackPath(target, node.right, node, prevNodeMap)) {
                return true;
            }
            return false;
        }
    }

864. shortest-path-to-get-all-keys

  • 给一个二维的grid，.表示空地、@表示起点（也可以看作空地）、a~f表示锁、A~F表示对应的门，要想到对应的门必须先有对应的钥匙。求从起点最少需要走几步拿到所有钥匙。
  • 这种求graph中最短路径的问题通常用BFS就可以。问题在于这个锁和钥匙的问题，拿到钥匙之后可能需要原路返回，这和通常BFS不走回头路的做法不同。但注意现在的状态区别就是持有钥匙的不同，而且只需要统计每一种钥匙是否出现，可以直接用一个int的bit来表示。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    class Solution {
        class Point {
            int row, col, keyBits;
            public Point(int row, int col, int keyBits) {
                this.row = row;
                this.col = col;
                this.keyBits = keyBits;
            }
        }
        public int shortestPathAllKeys(String[] grid) {
            if (grid == null || grid.length == 0) {
                return 0;
            }
            int rowCount = grid.length, colCount = grid[0].length();
            int rowStart = -1, colStart = -1, keyTotal = 0;
            for (int i = 0; i < rowCount; i++) {
                for (int j = 0; j < colCount; j++) {
                    if (grid[i].charAt(j) == '@') {
                        rowStart = i;
                        colStart = j;
                    } else if (grid[i].charAt(j) >= 'a' && grid[i].charAt(j) <= 'f') {
                        keyTotal++;
                    }
                }
            }
            if (rowStart == -1 || keyTotal == 0) {
                return 0;
            }
            int steps = -1, keyTotalBits = (1 << keyTotal) - 1;
            Set<String> visited = new HashSet<>();
            Queue<Point> q = new LinkedList<>();
            q.offer(new Point (rowStart, colStart, 0));
            visited.add(getStateString(rowStart, colStart, 0));
            while (!q.isEmpty()) {
                int size = q.size();
                steps++;
                while (size-- > 0) {
                    Point curr = q.poll();
                    char currChar = grid[curr.row].charAt(curr.col);
                    if (currChar >= 'a' && currChar <= 'f') {
                        curr.keyBits |= (1 << (currChar - 'a'));
                    }
                    if (curr.keyBits == keyTotalBits) {
                        return steps;
                    }
                    
                    if (validatePos(grid, curr.row - 1, curr.col, visited, curr.keyBits)) {
                        q.offer(new Point(curr.row - 1, curr.col, curr.keyBits));
                        visited.add(getStateString(curr.row - 1, curr.col, curr.keyBits));
                    }
                    if (validatePos(grid, curr.row + 1, curr.col, visited, curr.keyBits)) {
                        q.offer(new Point(curr.row + 1, curr.col, curr.keyBits));
                        visited.add(getStateString(curr.row + 1, curr.col, curr.keyBits));
                    }
                    if (validatePos(grid, curr.row, curr.col - 1, visited, curr.keyBits)) {
                        q.offer(new Point(curr.row, curr.col - 1, curr.keyBits));
                        visited.add(getStateString(curr.row, curr.col - 1, curr.keyBits));
                    }
                    if (validatePos(grid, curr.row, curr.col + 1, visited, curr.keyBits)) {
                        q.offer(new Point(curr.row, curr.col + 1, curr.keyBits));
                        visited.add(getStateString(curr.row, curr.col + 1, curr.keyBits));
                    }
                }
            }
            return -1;
        }
        private char getChar(String[] grid, int row, int col) {
            if (row >= 0 && row < grid.length && col >= 0 && col < grid[row].length()) {
                return grid[row].charAt(col);
            } else {    
                return '#';
            }
        }
        private String getStateString(int row, int col, int keyCount) {
            return row + "," + col + ":" + keyCount;
        }
        private boolean validatePos(String[] grid, int row, int col, Set<String> visited, int keyBits) {
            char currChar = getChar(grid, row, col);
            return ((currChar == '.' || 
                     currChar == '@' ||
                    currChar >= 'a' && currChar <= 'f' || 
                    currChar >= 'A' && currChar <= 'F' && ((keyBits & (1 << (currChar - 'A'))) != 0))
                        && !visited.contains(getStateString(row, col, keyBits)));
        }
    }

865. smallest-subtree-with-all-the-deepest-nodes

  • 给一个二叉树，求包含所有最深节点的最小子树的根。
  • 可以拆解成求深度、然后求LCA的问题，但这样是2-pass。1-pass的做法从根节点出发的同时就求深度，如果左右两边的深度相等则当前这个节点就是LCA了，如果左边的更深则应当返回左边的某个LCA，右边也是同理。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    class Solution {
        class NodeInfo {
            int depth;
            TreeNode root;
            public NodeInfo(int depth, TreeNode root) {
                this.depth = depth;
                this.root = root;
            }
        }
        public TreeNode subtreeWithAllDeepest(TreeNode root) {
            if (root == null) {
                return null;
            }
            return getNodeInfo(root).root;
        }
        private NodeInfo getNodeInfo(TreeNode node) {
            if (node == null) {
                return new NodeInfo(0, null);
            }
            NodeInfo leftInfo = getNodeInfo(node.left), rightInfo = getNodeInfo(node.right);
            if (leftInfo.depth == rightInfo.depth) {
                return new NodeInfo(leftInfo.depth + 1, node);
            } else if (leftInfo.depth > rightInfo.depth) {
                return new NodeInfo(leftInfo.depth + 1, leftInfo.root);     // 保留左边返回回来的LCA
            } else {
                return new NodeInfo(rightInfo.depth + 1, rightInfo.root);
            }
        }
    }

866. prime-palindrome

  • 给一个正整数N(1 <= N <= 10^8)，求大于等于N的、最小的自对称素数(保证ans < 2 * 10^8)。
  • 数学题。所有位数为双数的自对称数都是11的倍数，因此目标只能锁定在位数为奇数的自对称数，再加个判断素数即可。但还有一个更暴力的办法，直接生成下一个最接近的自对称数(可参考564. Find the Closest Palindrome)，再判断是否素数。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    class Solution {
        public int primePalindrome(int N) {
            if (8 <= N && N <= 11) {
                return 11;
            }
            for (int i = 1; i <= 100000; i++) {
                String s = Integer.toString(i), rev = new StringBuilder(s).reverse().toString();
                int pal = Integer.valueOf(s + rev.substring(1));
                if (pal >= N && isPrime(pal)) {
                    return pal;
                }
            }
            return -1;
        }
        private boolean isPrime(int num) {
            if (num < 2 || num % 2 == 0) {
                return num == 2;
            }
            for (int i = 3; i * i <= num; i += 2) {
                if (num % i == 0) {
                    return false;
                }
            }
            return true;
        }
    }

872. leaf-similar-trees

  • 给两个二叉树的root节点，判断他们的叶子节点组成的sequence是否相同。DFS搞定，skip。

873. length-of-longest-fibonacci-subsequence

  • 给一个单调递增的int数组，求其中最长的斐波那契子序列长度。
  • 当前状态依赖于之前的状态，自然想到dp。dp[i][j]表示以A[i]和A[j]结尾的斐波那契数列长度，没到达一个新的索引，如果之前数组中出现过当前索引的值 - 某个索引的值，那当前长度就是之前长度 + 1，否则就默认是2。由于斐波那契数列成立的长度至少是3，最后判断一下再返回。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution {
        public int lenLongestFibSubseq(int[] A) {
            if (A == null || A.length <= 2) {
                return 0;
            }
            int maxLen = 0;
            Map<Integer, Integer> index = new HashMap<>();
            int[][] dp = new int[A.length][A.length];
            for (int last = 0; last < A.length; last++) {
                index.put(A[last], last);
                for (int mid = 0; mid < last; mid++) {
                    int prev = index.getOrDefault(A[last] - A[mid], -1);
                    dp[mid][last] = prev < mid && prev >= 0 ? dp[prev][mid] + 1 : 2;
                    maxLen = Math.max(dp[mid][last], maxLen);
                }
            }
            return maxLen > 2 ? maxLen : 0;
        }
    }

875. koko-eating-bananas

  • 给一个int数组表示若干堆香蕉，假设一个人每个小时能吃K个，每次只能选择一堆持续吃直到吃完，守卫H小时后回来，求最小的K值。例如[3,6,7,11], H = 8时，K = 4.

  • 利用假设二分查找法，假设一个K值，验证吃一波需要多久，与H比较后再换一个K值继续验证。这里同样采用了模版二分查找最左边的match值，需要注意的是invariant condition不是直接根据num[mid] >= target -> right = mid，而是需要转换成当前所需时间和H。时间复杂度为O(NlogM)，其中N为香蕉堆数，M为香蕉个数最大值。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    class Solution {
        public int minEatingSpeed(int[] piles, int H) {
            if (piles == null || piles.length == 0) {
                return 0;
            }
            int right = -1;
            for (int pile : piles) {
                right = Math.max(right, pile);
            }
            
            int left = 0;
            while (left + 1 < right) {
                int mid = left + (right - left) / 2, currentHours = 0;
                for (int pile : piles) {
                    currentHours += (pile + mid - 1) / mid;
                }
                if (currentHours <= H) {  // 注意这里currentHours <= H 等价于TimeToTake(mid) >= target
                    right = mid;
                } else {
                    left = mid;
                }
            }
            return right;
        }
    }

  • 方法二：直接定位到某个很可能的值之后，线性查找。这个很可能的值就是ceil(sum / H)。时间复杂度理论上是O(N*M)，其中M为delta(target - initial)，实际会比二分查找快。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    class Solution {
        public int minEatingSpeed(int[] piles, int H) {
            if (piles == null || piles.length == 0) {
                return 0;
            }
            long sum = 0L;
            for (int pile : piles) {
                sum += pile;
            }
            int bananaPerHour = (int) ((sum + H - 1) / H), currentHours = getHours(piles, bananaPerHour);
            while (currentHours > H) {
                bananaPerHour++;
                currentHours = getHours(piles, bananaPerHour);
            }
            return (int) bananaPerHour;
        }
        private int getHours(int[] piles, int bananaPerHour) {
            int currentHours = 0;
            for (int pile : piles) {
                currentHours += (pile + bananaPerHour - 1) / bananaPerHour;
            }
            return currentHours;
        }
    }

876. middle-of-the-linked-list

  • 给一个链表，求中间节点，若中间节点是两个，返回第二个。
  • 快慢指针搞定。pass。

877. stone-game

  • 给一个int数组表示若干堆石头，两个人每人选择从数组的一侧取数字，最后总共取得多的人获胜，判断先取的人是否可以获胜。

  • DP。假设dp[i][j]表示从i到j的部分，先取的人可以多取多少石头。从头部取piles[i]则对方下一步为dp[i + 1][j]，从尾部取piles[j]则下一步对方多取dp[i][j - 1]，因此状态转移为dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1].

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
        public boolean stoneGame(int[] piles) {
            if (piles == null || piles.length == 0) {
                return true;
            }
            int n = piles.length;
            int[][] dp = new int[n][n];
            for (int i = 0; i < n; i++) {
                dp[i][i] = piles[i];
            }
            for (int len = 1; len < n; len++) {
                for (int i = 0; i < n - len; i++) {
                    dp[i][i + len] = Math.max(piles[i] - dp[i + 1][i + len], piles[i + len] - dp[i][i + len - 1]);
                }
            }
            return dp[0][n - 1] > 0;
        }
    }

  • 优化，这个dp其实每次只需要用到1-D Array即可，因为len变量在外循环，在内层循环看来column是固定的。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    class Solution {
        public boolean stoneGame(int[] piles) {
            if (piles == null || piles.length == 0) {
                return true;
            }
            int n = piles.length;
            int[] dp = Arrays.copyOf(piles, n);
            for (int len = 1; len < n; len++) {
                for (int i = 0; i < n - len; i++) {
                    dp[i] = Math.max(piles[i] - dp[i + 1], piles[i + len] - dp[i]);
                }
            }
            return dp[0] > 0;
        }
    }

  • follow-up: 给一个int数组表示若干堆石头，两个人每人选择从数组的一侧取数字，每个人都能在剩余石头当中做到全局最优，最后总共取得多的人获胜，求先取的人和后取的人能得到分数之差。

  • 还是DP，只不过这次在每一段区间[i, j]内需要存储先手和后手所能得到的石头数。状态转换非常有意思，作为先手选择完左边或者右边的石头后，就相应转变了后手，因此需要取相应段dp的后手值，即dp[i][j].fir = max(piles[i] + dp[i+1][j].sec, piles[j] + dp[i][j-1].sec). 初始状态则是只有一个石头的时候，先手取得全部、后手为0，也就是每一个石头堆对应一个base case，在dp数组中呈对角线. 遍历的方向则需要观察，dp[i][j]需要下方dp[i+1][j]和左方dp[i][j-1]的值，也就需要斜着遍历了。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    class Solution {
        class Pair {
            int fir, sec;
            Pair(int fir, int sec) {
                this.fir = fir;
                this.sec = sec;
            }
        }
        public boolean stoneGameFollowUp(int[] piles) {
            if (piles == null || piles.length == 0) {
                return true;
            }
            int n = piles.length;
            Pair[][] dp = new Pair[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = i; j < n; j++) {
                    dp[i][j] = new Pair(0, 0);
                }
            }
            // 初始化对角线[i, i]，先手取得全部石头，后手为0
            for (int i = 0; i < n; i++) {
                dp[i][i].fir = piles[i];
            }
            for (int len = 1; len < n; len++) {
                for (int i = 0, j = i + len; j < n; i++, j++) {
                    int left = piles[i] + dp[i + 1][j].sec;
                    int right = piles[j] + dp[i][j - 1].sec;
                    if (left > right) {
                        dp[i][j].fir = left;
                        dp[i][j].sec = dp[i + 1][j].fir;
                    } else {
                        dp[i][j].fir = right;
                        dp[i][j].sec = dp[i][j - 1].fir;
                    }
                }
            }
            return dp[0][n - 1].fir - dp[0][n - 1].sec;
        }
    }

881. boats-to-save-people

  • 给一个int表示人的体重，假设一个船最多载2人，给限重limit，求至少需要多少船。
  • 排序后双指针。pass。
  • 可能会问：如果限制k人呢？如果没有限制人数只是看重量呢？感觉也是排序后，猜一个船数N/2，判断是否可行，可行二分继续二分查找。

885. spiral-matrix-iii

  • 给一个行数和列数表示一个矩阵的形状，给起点坐标，求spiral遍历的坐标数组。
  • 发现规律移动的方式是1,1,2,2,3,3...，因此考虑直接从起点这样挪，只将合法的坐标存入数组即可。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    class Solution {
        private final int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        public int[][] spiralMatrixIII(int R, int C, int r0, int c0) {
            if (R <= 0 || C <= 0 || !isValidPosition(R, C, r0, c0)) {
                return new int[0][0];
            }
            int[][] ans = new int[R * C][2];
            int index = 1, directionIndex = 0, r = r0, c = c0, turnCounter = 0, moveCounter = 0;
            ans[0] = new int[] {r0, c0};
            while (index < ans.length) {
                r += directions[directionIndex][0];
                c += directions[directionIndex][1];
                moveCounter++;    // 记录在当前方向上每次移动
                if (isValidPosition(R, C, r, c)) {
                    ans[index++] = new int[] {r, c};
                }
                if (moveCounter == turnCounter / 2 + 1) {   // 得到1,1,2,2,3,3...的数组
                    moveCounter = 0;
                    turnCounter++;
                    directionIndex = (directionIndex + 1) % 4;
                }
            }
            return ans;
        }
        
        private boolean isValidPosition(int rowCount, int colCount, int r, int c) {
            return r >= 0 && c >= 0 && r < rowCount && c < colCount;
        }
    }

886. possible-bipartition

  • 给N个人物之间的关系edges，在一个edges两端的两个人不能在同一个群组中，判断是否可能将这堆人分成两组。
  • 图论经典上色问题，根据edges构建图之后，将起点上色为1、将相邻节点上色为-1，持续递归，一旦出现相邻的节点已经上色且有冲突就不可能了。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    class Solution {
        public boolean possibleBipartition(int N, int[][] dislikes) {
            if (dislikes == null || dislikes.length == 0) {
                return true;
            }
            List<Integer>[] graph = getGraph(N, dislikes);
            int[] colors = new int[N + 1];
            for (int i = 1; i <= N; i++) {
                if (colors[i] == 0 && !dfs(i, colors, -1, graph)) {
                    return false;
                }
            }
            return true;
        }
        private List<Integer>[] getGraph(int N, int[][] dislikes) {
            List<Integer>[] graph = new List[N + 1];
            for (int i = 0; i <= N; i++) {
                graph[i] = new ArrayList<>();
            }
            for (int[] dislike : dislikes) {
                graph[dislike[0]].add(dislike[1]);
                graph[dislike[1]].add(dislike[0]);
            }
            return graph;
        }
        private boolean dfs(int node, int[] colors, int currColor, List<Integer>[] graph) {
            if (colors[node] != 0) {
                return colors[node] == currColor;
            }
            colors[node] = currColor;
            for (int neighbor : graph[node]) {
                if (!dfs(neighbor, colors, -currColor, graph)) {
                    return false;
                }
            }
            return true;
        }
    }

888. fair-candy-swap

  • 给两个int数组，求需要交换其中哪两个int可以使得两个数组的和相等。
  • 对两个数组求和，二者的差/2就是需要给另一方补充的diff。将第一个数组存入set，从第二个数组中逐个元素加上diff看看是否在第一个数组中出现过，出现过则直接交换这两个数组就可以抹平差距了。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
        public int[] fairCandySwap(int[] A, int[] B) {
            if (A == null || B == null || A.length == 0 || B.length == 0) {
                return new int[0];
            }
            int diff = (IntStream.of(A).sum() - IntStream.of(B).sum()) / 2; // A比B多多少
            Set<Integer> setA = new HashSet<>();
            for (int a : A) {
                setA.add(a);
            }
            for (int b : B) {
                if (setA.contains(b + diff)) {      // 若存在，则交换后A - diff, B + diff, 差距就抹平了
                    return new int[] {b + diff, b};
                }
            }
            return new int[0];
        }
    }

889. construct-binary-tree-from-preorder-and-postorder-traversal

  • 给一个树的前序遍历和后续遍历的结果，还原这个树。每个节点的值都不一样，保证一定有对应的树。

  • 方法一：递归。前序遍历特定是第一次接触就输出，后序则是当最后离开这个节点的时候才输出，这意味着见到后序节点的时候，这部分子树就已经构造完成了。因此前序中的每一个元素都可以直接构造成节点，若该节点不是后续节点，则说明还需要构建子树。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution {
        private int preIndex = 0, postIndex = 0;
        public TreeNode constructFromPrePost(int[] pre, int[] post) {
            TreeNode root = new TreeNode(pre[preIndex++]);
            if (root.val != post[postIndex]) {      // 通过与后序遍历比较判断当前根是否完全遍历
                root.left = constructFromPrePost(pre, post);
            }
            if (root.val != post[postIndex]) {
                root.right = constructFromPrePost(pre, post);
            }
            postIndex++;
            return root;
        }
    }

  • 方法二：遍历。利用Stack的思路存放尚未在后序遍历中出现的点，一旦在后序遍历中出现就说明这个节点已经拼装完成，可以直接pop出来。当前节点需要先尝试拼入栈顶节点的左子树，若已经存在再拼入右子树。最终全部拼完后，返回栈最底部的节点。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Solution {
        public TreeNode constructFromPrePost(int[] pre, int[] post) {
            Deque<TreeNode> s = new ArrayDeque<>();
            s.offer(new TreeNode(pre[0]));
            for (int preIndex = 1, postIndex = 0; preIndex < pre.length; preIndex++) {
                TreeNode node = new TreeNode(pre[preIndex]);
                while (s.getLast().val == post[postIndex]) {    // 通过与后序遍历比较判断栈顶是否完全遍历
                    s.pollLast();
                    postIndex++;
                }
                if (s.getLast().left == null) { // 从栈顶的左边开始链接节点
                    s.getLast().left = node;
                } else {
                    s.getLast().right = node;
                }
                s.offer(node);
            }
            return s.getFirst();
        }
    }

890. find-and-replace-pattern

  • 给一个string数组和一个pattern，返回一个string数组，其中每个string都可以转换成pattern的形式，如pattern为cdc则aba, QAQ是符合的，而abb就不符合。

  • 方法一：最朴素的替换存入map的方法，需要一个set来存放pattern判断是否出现过。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    class Solution {
        public List<String> findAndReplacePattern(String[] words, String pattern) {
            List<String> matchedList = new LinkedList<>();
            if (words == null || words.length == 0) {
                return matchedList;
            }
            for (String word : words) {
                if (isMatch(word.toCharArray(), pattern.toCharArray())) {
                    matchedList.add(word);
                }
            }
            return matchedList;
        }
        private boolean isMatch(char[] word, char[] pattern) {
            if (word.length != pattern.length) {
                return false;
            }
            Map<Character, Character> mapping = new HashMap<>();
            Set<Character> patternSet = new HashSet<>();
            for (int i = 0; i < word.length; i++) {
                if (mapping.containsKey(word[i])) {
                    if (mapping.get(word[i]) != pattern[i]) {
                        return false;
                    }
                } else {
                    if (patternSet.contains(pattern[i])) {
                        return false;
                    } else {
                        mapping.put(word[i], pattern[i]);
                        patternSet.add(pattern[i]);
                    }
                }
            }
            return true;
        }
    }

  • 方法二：normalizing word的方法，将pattern先encode成某个形式，如数字数组，再对所有word apply相同的函数即可。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    class Solution {
        public List<String> findAndReplacePattern(String[] words, String pattern) {
            List<String> matchedList = new LinkedList<>();
            if (words == null || words.length == 0) {
                return matchedList;
            }
            int[] patternEncoded = encode(pattern);
            for (String word : words) {
                if (Arrays.equals(encode(word), patternEncoded)) {
                    matchedList.add(word);
                }
            }
            return matchedList;
        }
        private int[] encode(String str) {
            int[] retVal = new int[str.length()];
            Map<Character, Integer> char2Int = new HashMap<>();
            for (int i = 0; i < str.length(); i++) {
                char2Int.putIfAbsent(str.charAt(i), char2Int.size());
                retVal[i] = char2Int.get(str.charAt(i));
            }
            return retVal;
        }
    }

891. sum-of-subsequence-widths

  • 给一个int数组，求所有子序列的width之和。width定义为该部分序列的最大值减最小值。结果可能很大，mod一个1e9 + 7。
  • 本质上就是找所有子序列的最大值和最小值。先对原数组排个序，对于i-th数，总共有2 ^ i个子序列以它为最大值、2 ^ (n - i - 1)个子序列以它为最小值。为了做到one-pass，在从左往右遍历的时候可以同时进行加减，使用c = 1不断c *= 2，以当前元素A[i]为最大值的有c个、以对称处元素A[n - i - 1]为最小值的有c个.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    class Solution {
        public int sumSubseqWidths(int[] A) {
            if (A == null || A.length == 0) {
                return 0;
            }
            Arrays.sort(A);
            long retVal = 0, c = 1, MOD = (long)1e9 + 7;
            for (int i = 0; i < A.length; i++, c = c * 2 % MOD) {
                retVal = (retVal + A[i] * c - A[A.length - i - 1] * c) % MOD;
            }
            return (int) ((retVal + MOD) % MOD);
        }
    }

896. monotonic-array

  • 给一个数组，判断是否单调，直接用一个tone变量标记当前情况即可。pass。

897. increasing-order-search-tree

  • 给一个BST，转换成只有右子树的BST链表，也需要从小到大。需要通过全局变量记录全局的head以及上一次整理之后的prev节点，通过中序遍历递归搞定。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
        private TreeNode head = null, prev = null;
        public TreeNode increasingBST(TreeNode root) {
            if (root == null) {
                return null;
            }
            increasingBST(root.left);       // 先整理左子树
            if (head == null) {             // 若head从未设置，先设head
                head = root;
            } else {                        // head设置则prev一定设置过了
                prev.right = root;
                root.left = null;
            }
            prev = root;                    // 更新prev为当前节点
            increasingBST(root.right);
            return head;
        }
    }

901. online-stock-span

  • 在表示股价的一串int流中，每输入一个新的股价就要返回之前连续几天价格是低于或等于当前价格的。例如[100, 80, 60, 70, 60, 75, 85]返回[1, 1, 1, 2, 1, 4, 6].
  • 用stack解决。stack中存放股价和计数，如果新输入的股价比栈顶大，则弹出并把栈顶的计数累积到当前计数。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    class StockSpanner {
        Stack<int[]> stack;
        public StockSpanner() {
            stack = new Stack<>();
        }
        
        public int next(int price) {
            int count = 1;
            while (!stack.isEmpty() && price >= stack.peek()[0]) {
                count += stack.pop()[1];
            }
            stack.push(new int[] {price, count});
            return stack.peek()[1];
        }
    }
    /**
     * Your StockSpanner object will be instantiated and called as such:
     * StockSpanner obj = new StockSpanner();
     * int param_1 = obj.next(price);
     */

904. fruit-into-baskets

  • 给一个int数组表示水果，假设你只能取两种水果，而且从某一个点开始后就要一直往后取这两种，一旦碰到别的水果就必须停止。求最多可以拿到多少个水果。双指针，本身没啥意思，但是学到了map.remove(key, value)这个操作。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
        public int totalFruit(int[] tree) {
            if (tree == null || tree.length == 0) {
                return 0;
            }
            Map<Integer, Integer> map = new HashMap<>();
            int left = 0, right = 0, retVal = 0;
            for (; right < tree.length; right++) {
                map.put(tree[right], map.getOrDefault(tree[right], 0) + 1);
                while (map.size() > 2) {
                    map.put(tree[left], map.get(tree[left]) - 1);
                    map.remove(tree[left++], 0);
                }
                retVal = Math.max(retVal, right - left + 1);
            }
            return retVal;
        }
    }

905. sort-array-by-parity

  • 给一个数组，要求将所有偶数都挪到奇数前面。双指针前后夹击即可，pass.

907. sum-of-subarray-minimums

  • 给一个数组，求其中所有subarray中的最小值之和。[1,3,2]就有[1], [3], [2], [1,3], [3,2], [1,3,2]这些子数组，求和为1+3+2+1+2+1.
  • 观察规律，以1为最小值的子数组有3个，以3为最小值的子数组有1个，以2为最小值的子数组有2个。对于每一个索引处都需要求它前面和它后面的次小值，或者说需要直到往前和往后多远就会破坏自己是最小值这个条件。因此考虑用monotone stack来维护这样一个单调递增的索引栈，当前索引减去栈顶索引就是距离了。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    class Solution {
        public int sumSubarrayMins(int[] A) {
            if (A == null || A.length == 0) {
                return 0;
            }
            int len = A.length, sum = 0, MOD = 1_000_000_007;
            Stack<Integer> stack = new Stack<>();
            int[] left = new int[len];
            int[] right = new int[len];
            for (int i = 0; i < len; i++) { // 首先假设每个索引自己都是最小值
                left[i] = i + 1;    // 当前到最左共有i + 1个元素
                right[i] = len - i; // 当前到最右共有len - i个元素
            }
            
            for (int i = 0; i < len; i++) {
                while (!stack.isEmpty() && A[i] < A[stack.peek()]) {
                    stack.pop();    // 当前元素更小，需要尽可能丢到栈底
                }
                if (!stack.isEmpty()) {
                    left[i] = i - stack.peek(); // 与前方更小值的距离
                }
                stack.push(i);
            }
            
            stack = new Stack<>();
            for (int i = 0; i < len; i++) {
                while (!stack.isEmpty() && A[i] < A[stack.peek()]) {
                    right[stack.peek()] = i - stack.peek(); // 当前元素更小，则栈顶到当前元素就是后续第一个更小值了
                    stack.pop();
                }
                stack.push(i);
            }
            
            for (int i = 0; i < len; i++) {
                sum = (sum + A[i] * left[i] * right[i]) % MOD;
            }
            return sum;
        }
    }

909. snakes-and-ladders

  • 给一个N*N棋盘，从左下方开始作为1，蛇形向右向上向左向上这样编号，直到N*N. 其中如果是-1就固定，如果是整数则需要跳到该编号对应的位置（只跳一次，不能无穷跳）。假设每次可以从当前位置向后走1～6步，求最短的到达N*N所需步数。
  • 见到棋盘、最短步数就应该想到BFS，只要第一个碰到终点的就是最短步数。比较tricky的是从编号到位置的转化，每次从编号转换成位置再到棋盘里看是否需要继续往后跳。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    class Solution {
        public int snakesAndLadders(int[][] board) {
            if (board == null || board.length == 0 || board[0].length == 0) {
                return 0;
            }
            int N = board.length;
            Map<Integer, Integer> idSteps = new HashMap<>();
            Queue<Integer> q = new LinkedList<>();
            q.offer(1);
            idSteps.put(1, 0);
            
            while (!q.isEmpty()) {
                int currId = q.poll();
                if (currId == N * N) {
                    return idSteps.get(currId);
                }
                
                for (int nextId = currId + 1; nextId <= Math.min(currId + 6, N * N); nextId++) {
                    int[] nextLocation = getLocation(nextId, N);
                    int rowNext = nextLocation[0], colNext = nextLocation[1];
                    int nextIdFinal = board[rowNext][colNext] == -1 ? nextId : board[rowNext][colNext];
                    
                    if (!idSteps.containsKey(nextIdFinal)) {
                        idSteps.put(nextIdFinal, idSteps.get(currId) + 1);
                        q.offer(nextIdFinal);
                    }
                }
            }
            return -1;
        }
        private int[] getLocation(int id, int N) {
            int q = (id - 1) / N;
            int r = (id - 1) % N;
            int row = N - 1 - q;
            int col = row % 2 == N % 2 ? (N - 1 - r) : r;
            return new int[] {row, col};
        }
    }

914. x-of-a-kind-in-a-deck-of-cards

  • 给一个int数组表示一堆牌，判断是否可能将这堆牌划分成若干个子集，使得每个子集每张牌都相同且多于一张。
  • 本质上就是求每种牌面的出现次数是否可以被某个大于2的数整除。主要是不知道怎么写GCD，复习一下。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    class Solution {
        public boolean hasGroupsSizeX(int[] deck) {
            if (deck == null || deck.length == 0) {
                return false;
            }
            int[] bucket = new int[10000];
            for (int num : deck) {
                bucket[num]++;
            }
            
            int gcd = -1;
            for (int i = 0; i < bucket.length; i++) {
                if (bucket[i] > 0) {
                    if (gcd == -1) {
                        gcd = bucket[i];
                    } else {
                        gcd = findGcd(bucket[i], gcd);
                    }
                }
            }
            return gcd >= 2;
        }
        private int findGcd(int a, int b) {
            return b == 0 ? a : findGcd(b, a % b);
        }
    }

915. partition-array-into-disjoint-intervals

  • 给一个数组，假设一定存在一种划分方式使得左半边的所有元素比右半边所有元素小或相等，求最短的左半边长度（保证是两侧都是非空的）。

  • 方法一：维护两个数组，一个求左边到当前位置的最大元素、一个求右边到当前位置的最小元素，只要最大元素都小于右边的最小元素了就是合法划分了。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution {
        public int partitionDisjoint(int[] A) {
            if (A == null || A.length == 0) {
                return 0;
            }
            int len = A.length;
            int[] minRight = new int[len], maxLeft = new int[len];
            minRight[len - 1] = A[len - 1];
            maxLeft[0] = A[0];
            for (int i = 1; i < len; i++) {
                minRight[len - i - 1] = Math.min(minRight[len - i], A[len - i - 1]);
                maxLeft[i] = Math.max(maxLeft[i - 1], A[i]);
            }
            for (int i = 1; i < A.length; i++) {
                if (maxLeft[i - 1] <= minRight[i]) {
                    return i;
                }
            }
            return -1;
        }
    }

  • follow-up如何优化空间？我们不需要track每个位置的最小、最大元素。维护一个partition的index，只要partition左边的最大值小于等于当前所有遍历到的值就可以了，而一旦大于说明当前位置也必须包括在partition里面，同时更新左边最大值为当前遍历过的元素中的最大值。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
        public int partitionDisjoint(int[] A) {
            if (A == null || A.length == 0) {
                return 0;
            }
            int leftPartMax = A[0], currMax = A[0], leftPartEndIndex = 0;
            for (int i = 1; i < A.length; i++) {
                if (leftPartMax > A[i]) {
                    leftPartEndIndex = i;
                    leftPartMax = currMax;
                } else {
                    currMax = Math.max(currMax, A[i]);
                }
            }
            return leftPartEndIndex + 1;
        }
    }

917. reverse-only-letters

  • 将字符串中的letter反转，其余字符都保留。如Test1ng-Leet=code-Q!变成Qedo1ct-eeLg=ntse-T!.
  • 前后指针夹逼即可。pass.

918. maximum-sum-circular-subarray

  • 给一个int数组，假设他是circular的，求最大的非空的subarray的和。
  • circular与以往不同的就是前后可以相连，前后各有一部分的和最大，那么将这个情况转换一下就是「中间部分最小」。因此维护最大和最小两种值，最后用总和减去最小值就得到前后断开的情况的最大值了。corner case就是当所有数都是负数的时候，如果直接返回最大值就是total - sumMin = 0，这就意味着子数组为空了，因此你们媒体本身也要判断，如果最大的子数组之和小于0，就要直接返回这个最大的负数值才是。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public int maxSubarraySumCircular(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        int currMax = 0, currMin = 0, sumMax = -30000, sumMin = 30000, total = 0;
        for (int num : A) {
            currMax = Math.max(num, currMax + num);     // 要么继续取，要么抛弃之前的只从当前开始取
            sumMax = Math.max(sumMax, currMax);         // 保留最大的和
            currMin = Math.min(num, currMin + num);
            sumMin = Math.min(sumMin, currMin);
            total += num;
        }
        return Math.max(sumMax, total - sumMin);
    }

919. complete-binary-tree-inserter

  • 实现一个完全二叉树的插入。在经过初始化后，实现O(1)的插入，返回插入点的parent值。
  • 一开始用了两个queue，但这就没有利用好「完全」二叉树的性质。如果将这些节点都存入一个数组，那么孩子节点的索引就是parent节点索引的2倍(+1)
    .
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class CBTInserter {
        List<TreeNode> nodeList;
        public CBTInserter(TreeNode root) {
            nodeList = new ArrayList<>();
            nodeList.add(root);
            for (int i = 0; i < nodeList.size(); i++) {
                if (nodeList.get(i).left != null) {
                    nodeList.add(nodeList.get(i).left);
                }
                if (nodeList.get(i).right != null) {
                    nodeList.add(nodeList.get(i).right);
                }
            }
        }
        public int insert(int v) {
            int size = nodeList.size();
            TreeNode newNode = new TreeNode(v);
            if (size % 2 == 1) {
                nodeList.get((size - 1) / 2).left = newNode;
            } else {
                nodeList.get((size - 1) / 2).right = newNode;
            }
            nodeList.add(newNode);
            return nodeList.get((size - 1) / 2).val;
        }
        
        public TreeNode get_root() {
            return nodeList.get(0);
        }
    }

921. minimum-add-to-make-parentheses-valid

  • 给一个只有小括号的字符串，可能valid也可能invalid，判断最少需要插入几个小括号才能使它valid。贪心法，直接用一个leftCount算左括号数，右括号来的时候就减，不够就说明要插入。pass.

930. binary-subarrays-with-sum

  • 给一个只含有0和1的数组，给一个targetSum，求有多少个subarray的和等于它。
  • 双指针，右指针一直往后加，一旦超过了targetSum就需要移动左指针。不过需要注意的是由于0的存在，一旦当前的sum == targetSum，左指针指的可能是0，因此需要在此时将左指针往右的部分都算进去。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    class Solution {
        public int numSubarraysWithSum(int[] A, int S) {
            if (A == null || A.length == 0) {
                return 0;
            }
            int left = 0, right = 0, sum = 0, count = 0;
            while (right < A.length) {
                sum += A[right];
                while (left < right && sum > S) {
                    sum -= A[left++];
                }
                if (sum == S) {
                    count++;
                }
                for (int i = left; i < right && sum == S && A[i] == 0; i++) {
                    count++;
                }
                right++;
            }
            return count;
        }
    }

[931.minimum-falling-path-sum] (https://leetcode.com/problems/minimum-falling-path-sum/)

  • 给一个matrix，若每次下坠只能从上方、左上方、右上方下坠，求从最顶上下坠到最下面经过的所有数字和的最小值。
  • DP，每次就根据上方、左上方、右上方来更新。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    class Solution {
        public int minFallingPathSum(int[][] A) {
            if (A == null || A.length == 0 || A[0].length == 0) {
                return 0;
            }
            int rows = A.length, cols = A[0].length, retVal = Integer.MAX_VALUE;
            int[] dp = new int[cols];
            for (int c = 0; c < cols; c++) {
                dp[c] = A[0][c];
            }
            for (int r = 1; r < rows; r++) {
                int[] dpTemp = new int[cols];
                for (int c = 0; c < cols; c++) {
                    int mid = A[r][c] + dp[c];
                    int left = c > 0 ? A[r][c] + dp[c - 1] : Integer.MAX_VALUE;
                    int right = c + 1 < cols ? A[r][c] + dp[c + 1] : Integer.MAX_VALUE;
                    dpTemp[c] = Math.min(mid, Math.min(left, right));
                }
                dp = dpTemp;
            }
            for (int num : dp) {
                retVal = Math.min(retVal, num);
            }
            return retVal;
        }
    }

935. knight-dialer

  • 假设一个knight只能走「日」字，求它在拨号盘上走N步可以走多少种不同的号码。
  • 转换成图论题，就是从一个点到另一个节点有多少种路径。先用数组构图表示当前数字能走到哪里，然后就可以考虑DFS或者DP。dp表示走到当前数字有多少种不同路径，后续的数字就是前序节点的路径数之和。注意取模防止overflow。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    private final int MOD = (int)1e9 + 7;
    private final int[][] graph = new int[][] {{4, 6}, 
                                                {6, 8},
                                                {7, 9},
                                                {4, 8},
                                                {0, 3, 9},
                                                {},
                                                {0, 1, 7},
                                                {2, 6},
                                                {1, 3},
                                                {2, 4}};
    public int knightDialer(int N) {
        if (N <= 0) {
            return 0;
        }
        int[][] memo = new int[N + 1][10];
        for (int i = 0; i <= 9; i++) {
            memo[1][i] = 1;
        }
        for (int i = 2; i <= N; i++) {
            for (int j = 0; j <= 9; j++) {
                for (int k : graph[j]) {
                    memo[i][j] = ((memo[i - 1][k] % MOD) + memo[i][j]) % MOD;
                }
            }
        }
        int sum = 0;
        for (int i = 0; i <= 9; i++) {
            sum = (memo[N][i] + sum) % MOD;
        }
        return sum % MOD;
    }

937. reorder-data-in-log-files

  • 按照规定顺序排序，自己实现comparator即可。pass.

938. range-sum-of-bst

  • 给一个BST和范围[L, R]，求落在范围内的节点值之和。递归搞定，不过需要注意可以通过if省去一些判断。pass。

939. minimum-area-rectangle

  • 给一个二维空间中点坐标的数组，求这些点所能组成的矩形的最小面积，若没有则返回0.
  • 将坐标按照x -> y的映射关系存入map: int -> set，然后O(N^2)两重循环逐个取出点来判断能否组成矩形，然后更新面积。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    public int minAreaRect(int[][] points) {
        if (points == null || points.length == 0) {
            return 0;
        }
        int area = Integer.MAX_VALUE;
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int[] point : points) {
            map.putIfAbsent(point[0], new HashSet<>());
            map.get(point[0]).add(point[1]);
        }
        for (int[] point1 : points) {
            for (int[] point2 : points) {
                if (point1[0] >= point2[0] || point1[1] >= point2[1]) {
                    continue;
                }
                if (map.get(point1[0]).contains(point2[1]) && map.get(point2[0]).contains(point1[1])) {
                    area = Math.min((point2[0] - point1[0]) * (point2[1] - point1[1]), area);
                }
            }
        }
        return area == Integer.MAX_VALUE ? 0 : area;
    }

941. valid-mountain-array

  • 给一个数组，判断它是否严格mountain array，即长度大于等于3且相邻数字严格上升接严格下降。pass.

942. di-string-match

  • 给一个只含有I或者D的字符串s，返回任意的permutation int数组，其中的数字是0 ~ s.length()且满足I上升、D下降的indicator。greedy搞定。pass。

945. minimum-increment-to-make-array-unique

  • 给一个int数组，可以给其中的数字+1，问总共最少加多少能让数组中数字各不相同。

  • 方法一：sort + 前后比较。下一个数字必须是前一个数字 + 1才能保证唯一。排序后从前往后遍历，如果当前数字比需要的数字小，说明有重复了，差值就是需要的inc。需要的数字由当前数字+1或者当前需要的数字+1中最大值得到。时间复杂度O(NlogN)。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution {
        public int minIncrementForUnique(int[] A) {
            if (A == null || A.length == 0) {
                return 0;
            }
            Arrays.sort(A);
            int minInc = 0, need = 0;
            for (int num : A) {
                // 如果num本身都比need大，那不用加了
                minInc += Math.max(need - num, 0);
                // 下一个需要的数字是当前数字和need较大者 + 1才能保证唯一
                need = Math.max(num, need) + 1;
            }
            return minInc;
        }
    }

  • 方法二：用TreeMap统计数字出现的频数顺便排序，然后从小到大取数字。如果当前数字小于need，那么需要inc的就是count个(need - num)，再加上后续的累加。而下一个need就是当前need和num的较大者加上count，因为需要隔开count个才能保证不重复。时间复杂度O(NlogK)，空间O(K)，K为不同的数字个数。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution {
        public int minIncrementForUnique(int[] A) {
            if (A == null || A.length == 0) {
                return 0;
            }
            TreeMap<Integer, Integer> treeMap = new TreeMap<>();
            for (int num : A) {
                treeMap.put(num, treeMap.getOrDefault(num, 0) + 1);
            }
            int minInc = 0, need = 0;
            for (int num : treeMap.keySet()) {
                int count = treeMap.get(num);
                // (1 + count-1) * (count-1) / 2就是从need开始后续需要继续累加的数目
                minInc += count * Math.max(need - num, 0) + count * (count - 1) / 2;
                need = Math.max(need, num) + count;
            }
            return minInc;
        }
    }

  • 方法三：bucket placement。将count丢入木桶中之后，从前往后找空闲的木桶，放进去即可。一个技巧是，当发现有重复元素的时候就直接减去dup，之后找到空闲时再加上空闲的元素free，本质上就还是加上(free - dup).

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    class Solution {
        public int minIncrementForUnique(int[] A) {
            if (A == null || A.length == 0) {
                return 0;
            }
            int[] bucket = new int[100000];
            for (int num : A) {
                bucket[num]++;
            }
            int minInc = 0, dupCount = 0;
            for (int num = 0; num < 100000; num++) {
                if (bucket[num] >= 2) {
                    dupCount += (bucket[num] - 1);
                    minInc -= (bucket[num] - 1) * num;
                } else if (dupCount > 0 && bucket[num] == 0) {
                    dupCount--;
                    minInc += num;
                }
            }
            return minInc;
        }
    }

946. validate-stack-sequences

  • 给两个int数组，一个是push到栈的顺序，另一个是pop出来的顺序，问是否能按push的顺序最后得到pop的结果。
  • 模拟一遍即可。pass.

947. most-stones-removed-with-same-row-or-column

  • 给一系列二维平面上点的坐标，当每个点的横或纵坐标上有其他点的时候它才能被拿掉，求最多拿掉多少点。
  • 抽象问题：当一个点的横或纵坐标上有其他点时，它们可以看作是「一伙的」，问题转换为求总共有多少个这样的独立island，总数减去独立island数即为所求。而算island数量除了DFS，还可以利用并查集来确定每个点所属的根节点，然后。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    class Solution {
        private int[] parents;
        public int removeStones(int[][] stones) {
            if (stones == null || stones.length == 0) {
                return 0;
            }
            parents = new int[stones.length];
            for (int i = 0; i < stones.length; i++) {
                parents[i] = i;
            }
            
            for (int i = 0; i < stones.length; i++) {
                for (int j = i + 1; j < stones.length; j++) {
                    if (shouldUnion(stones[i], stones[j])) {
                        union(i, j);
                    }
                }
            }
            
            int count = stones.length;
            for (int i = 0; i < parents.length; i++) {
                if (parents[i] == i) {
                    count--;
                }
            }
            return count;
        }
        private boolean shouldUnion(int[] a, int[] b) {
            return a[0] == b[0] || a[1] == b[1];
        }
        private void union(int x, int y) {
            int xParent = find(x);
            int yParent = find(y);
            if (xParent != yParent) {
                parents[yParent] = xParent;
            }
        }
        private int find(int x) {
            int retVal = parents[x];
            while (retVal != parents[retVal]) {
                parents[retVal] = parents[parents[retVal]];
                retVal = parents[retVal];
            }
            return retVal;
        }
    }

950. reveal-cards-in-increasing-order

  • 给一副扑克牌，从顶上抽取一张后紧接着塞到最底下，然后继续抽最顶上的，直到所有牌抽完。给一个int数组表示扑克牌，返回适当的顺序使得最后依次抽取所得的是从小到大的顺序。
  • 利用队列模拟之。首先对所给的数组排序，这就是最终抽取出来希望得到的顺序。用队列来模拟取的牌的索引，初始时往队列中存入0~n表示这些牌对应的索引。一开始取的是最顶上的牌，ans[0] = deckSorted[0]，然后将1出队再塞到队尾。接下来应当取的是ans[2] = deckSorted[1]，以此类推。。。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
        public int[] deckRevealedIncreasing(int[] deck) {
            if (deck == null || deck.length == 0) {
                return new int[0];
            }
            Arrays.sort(deck);  // deck从小到大排好序
            Queue<Integer> q = new LinkedList<>();
            for (int i = 0; i < deck.length; i++) {
                q.offer(i); // 先将索引入队，表示最终取出的顺序
            }
            int[] ans = new int[deck.length];
            for (int i = 0; i < deck.length; i++) {
                ans[q.poll()] = deck[i];    // 接下来从ans中取的卡片应该以队首为索引，对应deck[i]
                q.offer(q.poll());          // 将后一个索引重新塞到最底下
            }
            return ans;
        }
    }

951. flip-equivalent-binary-trees

  • 给两个二叉树，判断是否可以通过左右孩子互换的方式从一个树得到另一个树。
  • 直接递归解决。若两个节点val都不一样，直接就false了。如果一样，则可能需要左右孩子互换，抑或不用。
  • 值得注意的是时间复杂度分析。大神们分析这个时间复杂度是O(N^2).)，但我理解中每个节点只会被访问一次，难道不是O(N)吗？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Solution {
        public boolean flipEquiv(TreeNode root1, TreeNode root2) {
            if (root1 == null && root2 == null) {
                return true;
            }
            if (root1 == null || root2 == null || root1.val != root2.val) {
                return false;
            }
            return (flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right)) ||
                (flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left));
        }
    }

953. verifying-an-alien-dictionary

  • 给一个只有小写字母的外星人字典的顺序，给一个String数组，判断这个数组是否符合该字典序。直接用一个数组模拟字符到排名的map，然后前后两个字符串判断是否符合即可。skip.

957. prison-cells-after-n-days

  • 给一个只含有0和1的int数组，若左右两个元素相同，则转换为1，否则转换为0.求N天之后的状态。
  • 实现转换到下一天的方法不难，主要是要注意这个N可能很大，因此猜测其中可能存在环，如果之前出现过当前这个组合，就可以通过模运算省去很多次转换。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    class Solution {
        public int[] prisonAfterNDays(int[] cells, int N) {
            if (cells == null || cells.length == 0 || N < 0) {
                return null;
            }
            Set<String> set = new HashSet<>();
            boolean hasCycle = false;
            for (int i = 0; i < N; i++) {
                int[] next = findNext(cells);
                String encoded = Arrays.toString(next);
                if (set.contains(encoded)) {
                    hasCycle = true;
                    break;
                } else {
                    set.add(encoded);
                    cells = next;
                }
            }
            if (hasCycle) {
                N %= set.size();
                while (N-- > 0) {
                    cells = findNext(cells);
                }
            }
            return cells;
        }
        private int[] findNext(int[] cells) {
            int[] retVal = new int[cells.length];
            for (int i = 1; i + 1 < cells.length; i++) {
                retVal[i] = cells[i - 1] == cells[i + 1] ? 1 : 0;
            }
            return retVal;
        }
    }

958. check-completeness-of-a-binary-tree

  • 给一个二叉树，判断它是否是complete的，即除了最后一层可以不满，其余层都全满，且最后一层节点尽可能靠左。

  • 既然是只有最后一层才可以出现叶子节点，且要尽量靠左，则可以考虑层级遍历的时候将null也放入，这样一旦遍历时出现了null，就说明后续不能再出现非null的节点了，如果后续还有正常节点就返回false。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    public boolean isCompleteTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        boolean end = false;
        while (!q.isEmpty()) {
            TreeNode curr = q.poll();
            if (curr == null) {
                end = true;
            } else {
                if (end) {
                    return false;    
                }
                q.offer(curr.left);
                q.offer(curr.right);
            }
        }
        return true;
    }

  • 递归的一个做法是数节点的个数，然后假设每个节点都处在正确的位置，也就有正确的index。递归遍历时判断实际index是否超过了总节点数，因为一旦之前出现了null，后续的节点就一定会有偏大的index。这个做法的坏处是要pass两次，第一次求得总节点数，第二次是判断index。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    public boolean isCompleteTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        int totalNodes = countNodes(root);
        int startIndex = 1;
        return checkIndex(root, startIndex, totalNodes);
    }
    private boolean checkIndex(TreeNode root, int startIndex, int maxIndex) {
        if (root == null) {
            return true;
        }
        if (startIndex > maxIndex) {
            return false;
        }
        // 左孩子是当前节点*2，右孩子是当前*2+1
        return checkIndex(root.left, startIndex * 2, maxIndex) && checkIndex(root.right, startIndex * 2 + 1, maxIndex);
    }

963. minimum-area-rectangle-ii

  • 给一组点的坐标，求它们所能组成的最小的矩形的面积。
  • 矩形的重要特征是对角线相等，因此考虑即线段两两之间的中心点和距离进行归类存入map，同一个key下的即为距离相等的线段，在其中遍历找最小面积即可。时间复杂度乍一看是O(N^2)但主要瓶颈在最后遍历求最小面积这一步，显然不是单纯的双重循环，因为可能的距离-中点的所有组成线段都得遍历。貌似最坏情况是O(N^4)?
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    class Solution {
        public double minAreaFreeRect(int[][] points) {
            if (points == null || points.length < 4) {
                return 0;
            }
            Map<String, List<int[]>> map = new HashMap<>();
            for (int i = 0; i < points.length; i++) {
                for (int j = i + 1; j < points.length; j++) {
                    long dist = getSqrtDist(points[i], points[j]);
                    long midX = points[i][0] + points[j][0];
                    long midY = points[i][1] + points[j][1];
                    String key = dist + "-" + midX + "," + midY;
                    map.putIfAbsent(key, new ArrayList<>());
                    map.get(key).add(new int[] {i, j});
                }
            }
            double min = Double.MAX_VALUE;
            for (List<int[]> list : map.values()) {
                if (list.size() >= 2) {
                    for (int i = 0; i < list.size() - 1; i++) {
                        for (int j = i + 1; j < list.size(); j++) {
                            int[] point1 = points[list.get(i)[0]];
                            int[] point2 = points[list.get(i)[1]];
                            int[] point3 = points[list.get(j)[0]];
                            double dist1 = getDist(point1, point3);
                            double dist2 = getDist(point2, point3);
                            min = Math.min(dist1 * dist2, min);
                        }
                    }
                }
            }
            return min == Double.MAX_VALUE ? 0 : min;
        }
        private long getSqrtDist(int[] a, int[] b) {
            return (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]);
        }
        private double getDist(int[] a, int[] b) {
            return Math.sqrt(getSqrtDist(a, b));
        }
    }

965. univalued-binary-tree

  • 给一个二叉树，判断其中所有节点是否是一样的value。

968. binary-tree-cameras

  • 给一个二叉树，在一个节点处放置camera可以监控它本身、父节点、子节点。求最少需要放置多少camera可以监控所有的节点。

  • 方法一：贪心。树中如果将camera放置在叶子结点，它只能覆盖parent和叶子本身。如果放到叶子的parent处，则可以覆盖从它的parent到它的叶子三层，因此最佳化就是将camera放在叶子的parent处。因此进行dfs时，尽可能放置到叶子parent处，然后回溯时忽略已经被下层覆盖到的节点，直到回到root. 可以利用状态0表示”叶子”节点（不一定真的是叶子，只是表明它需要上层的cover）、1表示叶子的parent（要把camera放在这里）、2表示叶子parent的parent（已经被下层的cover到了）。如果当前节点为null就当作它已经被覆盖，如果左或者右孩子需要cover则当前就必须放camera，如果左或者右孩子已经有camera了则当前的已经被覆盖了。时间复杂度O(N), 空间复杂度为树的高度O(logN).

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
        private int count = 0;
        public int minCameraCover(TreeNode root) {
            return (dfs(root) < 1 ? 1 : 0) + count;
        }
        private int dfs(TreeNode root) {
            if (root == null) {
                return 2;   // 不需要覆盖
            }
            int left = dfs(root.left), right = dfs(root.right);
            if (left == 0 || right == 0) {
                count++;
                return 1;   // 当前必须放camera
            }
            // 只要下方有一个camera，当前就不需要覆盖了
            return (left == 1 || right == 1) ? 2 : 0;
        }
    }

  • 方法二：DP。和上一个思路一样，每个节点只有三种可能：0需要被覆盖、1放置了camera和2已经被覆盖到了。当前节点如果是0，则下方两个节点必须都是2；如果当前节点是1，则下方两个节点3种情况都有可能；如果当前节点是2，则下方两个节点有一个必须是1.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Solution {
        public int minCameraCover(TreeNode root) {
            int[] ans = solve(root);
            return Math.min(ans[1], ans[2]);
        }
        // retVal有三个值，分别表示当前需要覆盖、当前放了camera、当前已被覆盖的camera数
        private int[] solve(TreeNode root) {
            if (root == null) {
                return new int[] {0, 1001, 0};
            }
            int[] left = solve(root.left), right = solve(root.right);
            int minLeft12 = Math.min(left[1], left[2]);
            int minRight12 = Math.min(right[1], right[2]);
            int count0 = left[2] + right[2];
            int count1 = 1 + Math.min(left[0], minLeft12) + Math.min(right[0], minRight12);
            int count2 = Math.min(left[1] + minRight12, right[1] + minLeft12);
            return new int[] {count0, count1, count2};
        }
    }

969. pancake-sorting

  • 给一个长度为len的、只含有[1, len]的整数数组，求flip的长度组成的数组，使得flip完成后形成有序数组。
  • 很无聊的题。很直接的O(N^2)解法，每次找到当前范围内最大的数字，先flip到最前方，再flip到末尾，直到所有数字都在他们应该在的位置。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    class Solution {
        public List<Integer> pancakeSort(int[] A) {
            List<Integer> ans = new ArrayList<>();
            if (A == null || A.length == 0) {
                return ans;
            }
            for (int i = 0; i < A.length; i++) {
                int index = getIndexOf(A, A.length - i);
                if (index == -1) {
                    return new ArrayList<>();
                }
                if (index != 0) {
                    reverse(A, index);
                    ans.add(index + 1);
                }
                if (i < A.length - 1) {
                    reverse(A, A.length - i - 1);
                    ans.add(A.length - i); 
                }
            }
            return ans;
        }
        private int getIndexOf(int[] A, int target) {
            for (int i = 0; i < A.length; i++) {
                if (A[i] == target) {
                    return i;
                }
            }
            return -1;
        }
        private void reverse(int[] A, int lastIndex) {
            int left = 0, right = lastIndex;
            while (left < right) {
                int temp = A[left];
                A[left++] = A[right];
                A[right--] = temp;
            }
        }
    }

971. flip-binary-tree-to-match-preorder-traversal

  • 给一个二叉树，各个节点值各不相同。给一个int数组表示节点前序遍历的结果，返回一个需要flip（将该节点的左右孩子对调）的节点值的list，不存在则返回[-1].
  • 对二叉树进行前序遍历，用一个全局索引往后遍历voyage数组，如果当前节点和该数字不匹配说明当前这个行不通。如果当前节点有左孩子且值不匹配，则尝试用右孩子去比较。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class Solution {
        private List<Integer> retVal = new ArrayList<>();
        private int index = 0;
        public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
            if (voyage == null || voyage.length == 0) {
                return retVal;
            }
            return dfs(root, voyage) ? retVal : Arrays.asList(-1);
        }
        private boolean dfs(TreeNode root, int[] voyage) {
            if (root == null) {
                return true;
            }
            if (root.val != voyage[index++]) {
                return false;
            }
            if (root.left != null && root.left.val != voyage[index]) {
                retVal.add(root.val);
                return dfs(root.right, voyage) && dfs(root.left, voyage);
            }
            return dfs(root.left, voyage) && dfs(root.right, voyage);
        }
    }

973. k-closest-points-to-origin

  • 给一个含有二维坐标点的数组，求这些点到原点最近的top-k个。返回的顺序无所谓，不用从小到大排。
  • 方法一：max heap，用优先队列从大到小排，若超过k个则poll掉。时间复杂度O(NlogN). 直接排序个序取k个也是一样的。
  • 方法二：要求提升时间复杂度到O(N)，那么就要思考如何利用”返回顺序无所谓”这个条件了。因此可以考虑利用quicksort取第k个元素类似的原理，将原数组「部分排序」，只要保证前K个是最小的即可。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    class Solution {
        public int[][] kClosest(int[][] points, int K) {
            if (points == null || points.length == 0 || K <= 0) {
                return points;
            }
            int len = points.length, left = 0, right = len - 1;
            while (left < right) {
                int mid = partition(points, left, right);
                if (mid == K) {
                    break;
                } else if (mid < K) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return Arrays.copyOfRange(points, 0, K);
        }
        private int partition(int[][] points, int start, int end) {
            int left = start, right = end + 1;
            int[] pivot = points[start];
            while (true) {
                while (compare(points[++left], pivot) < 0) {
                    if (left == end) {
                        break;
                    }
                }
                while (compare(points[--right], pivot) > 0) {
                    if (right == start) {
                        break;
                    }
                }
                if (left >= right) {
                    break;
                }
                swap(points, left, right);
            }
            swap(points, start, right);
            return right;
        }
        private void swap(int[][] points, int i, int j) {
            int[] temp = new int[] {points[i][0], points[i][1]};
            points[i][0] = points[j][0];
            points[i][1] = points[j][1];
            points[j][0] = temp[0];
            points[j][1] = temp[1];
        }
        private double getDist(int[] a) {
            return Math.sqrt((double)a[0] * a[0] + (double)a[1] * a[1]);
        }
        private int compare(int[] point1, int[] point2) {
            return Double.compare(getDist(point1), getDist(point2));
        }
    }

977. squares-of-a-sorted-array

  • 给一个非降序的数组，返回从小到大排好序的各元素平方的数组。双指针搞定，skip.

979. distribute-coins-in-binary-tree

  • 在二叉树中每一个节点都放着若干coins，求将每个节点的coin都变为1总共需要挪动多少步，注意从根到子/从子到根都算作1步。给出根节点，一定有解，求步数。
  • 递归的思路，后序遍历将左子树和右子树能提供的coin数拿到，加上当前节点的coin数减去留下的1枚coin，就是当前节点能提供给上层的coin数。移动数则直接就是左子树和右子树能提供coin数的绝对值。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution {
        private int move = 0;
        public int distributeCoins(TreeNode root) {
            traverse(root);
            return move;
        }
        private int traverse(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int left = traverse(root.left);     // 左边能提供多少coin
            int right = traverse(root.right);   // 右边能提供多少coin
            move += Math.abs(left) + Math.abs(right);
            return root.val + left + right - 1; // 能提供的所有coin数减去要留下的1
        }
    }

981. time-based-key-value-store

  • 实现一个带有timestamp的key-value store，给定key和timestamp，可以返回不超过该时刻的value，若不存在则返回""。
  • 显然需要对每个key维护一个有序的timestamp序列，想到TreeMap，利用floor可以找到「小于等于该时刻」的timestamp了。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    class TimeMap {    
        Map<String, TreeMap<Integer, String>> map;
        /** Initialize your data structure here. */
        public TimeMap() {
            this.map = new HashMap<>();
        }
        
        public void set(String key, String value, int timestamp) {
            map.putIfAbsent(key, new TreeMap<>());
            map.get(key).put(timestamp, value);
        }
        
        public String get(String key, int timestamp) {
            TreeMap<Integer, String> treeMap = map.get(key);
            if (treeMap == null) {
                return null;
            }
            Map.Entry<Integer, String> entry = treeMap.floorEntry(timestamp);
            if (entry == null) {    // 没有比timestamp早的值，返回空
                return "";
            }
            return entry.getValue();
        }
    }

983. minimum-cost-for-tickets

  • 给一个出差天数的数组(值为[1, 365])，假设出差过程中可以购买1日票、7日票和30日票，对应价格存在一个数组中给出。求覆盖所有出差天数所需要的最少开销。

  • 方法一：DP + binarySearch. 数组中存放该位置对应日期的最小开销，每次往前查找可能的天数，dp[i] = dp[prev] + cost[x]更新。时间复杂度为O(NlogN).

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    class Solution {
        private final int[] VALID_PERIODS = new int[] {1, 7, 30};
        public int mincostTickets(int[] days, int[] costs) {
            if (days == null || days.length == 0 ||
               costs == null || costs.length == 0) {
                return 0;
            }
            int[] dp = new int[days.length];
            for (int i = 0; i < days.length; i++) {
                for (int j = 0; j < 3; j++) {
                    int startDay = days[i] - VALID_PERIODS[j] + 1;
                    int index = startDay < 1 ? 0 : Arrays.binarySearch(days, startDay);
                    if (index < 0) {
                        index = -index - 1;
                    }
                    if (dp[i] == 0) {
                        dp[i] = index > 0 ? dp[index - 1] + costs[j] : costs[j];
                    } else {
                        dp[i] = Math.min(dp[i], index > 0 ? dp[index - 1] + costs[j] : costs[j]);
                    }      
                }
            }
            return dp[days.length - 1];
        }
    }

  • 方法二：既然天数是固定的，我们完全可以固定一个[1, 365]数组来查找。这样就可以将时间变为O(N),空间也为O(N)、或者说O(366). 当然还可以对空间进行优化，利用modulo重复利用空间，这样可以缩小空间为O(30).

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    class Solution {
        private final int[] VALID_PERIODS = new int[] {1, 7, 30};
        private final int DAYS_IN_A_YEAR = 365;
        public int mincostTickets(int[] days, int[] costs) {
            if (days == null || days.length == 0 ||
               costs == null || costs.length == 0) {
                return 0;
            }
            
            int index = 0, lastDay = days[days.length - 1], maxValidPeriod = VALID_PERIODS[VALID_PERIODS.length - 1];
            int[] dp = new int[DAYS_IN_A_YEAR + 1];
            for (int day = days[0]; day <= lastDay; day++) {
                if (days[index] != day) {
                    dp[day] = dp[day - 1];
                } else {
                    dp[day] = Integer.MAX_VALUE;
                    for (int j = 0; j < 3; j++) {
                        dp[day] = Math.min(dp[day], dp[(Math.max(day - VALID_PERIODS[j], 0))] + costs[j]);
                    }
                    index++;
                }
            }
            return dp[lastDay];
        }
    }

986. interval-list-intersections

  • 给两个排好序的、自身互不重叠的interval数组，返回他们互相重叠的部分。用暴力if分类讨论搞定，具体情况比较复杂，但还是可以想清楚的。skip.

987. vertical-order-traversal-of-a-binary-tree

  • 给一个二叉树，要求返回垂直方向上节点value的遍历List of lists，在统一垂直线上浅的节点需要排在深的节点前面，若垂直方向相同、深浅相同，则按value从小到大排。
  • 一开始没有注意顺序问题，直接递归方法做了，利用一个index变量记录当前节点与root的相对偏移。而如果要考虑顺序，则首先考虑如何保证深浅——，利用一个变量level作为key，即可保证插入是level由浅到深的，而value则需要保证节点值从小到大，可直接用PriorityQueue.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    class Solution {
        private int leftMostIndex = 0;
        public List<List<Integer>> verticalTraversal(TreeNode root) {
            List<List<Integer>> ans = new ArrayList<>();
            if (root == null) {
                return ans;
            }
            Map<Integer, TreeMap<Integer, PriorityQueue<Integer>>> map = new HashMap<>();
            helper(root, 0, 0, map);
            for (int index = 0; index < map.size(); index++) {
                ans.add(new ArrayList<>());
                TreeMap<Integer, PriorityQueue<Integer>> treeMap = map.get(index + leftMostIndex); // 全局偏移
                for (int level : treeMap.keySet()) {
                    PriorityQueue<Integer> pq = treeMap.get(level);
                    while (!pq.isEmpty()) {
                        ans.get(index).add(pq.poll());
                    }
                }
            }
            return ans;
        }
        private void helper(TreeNode root, int index, int level, Map<Integer, TreeMap<Integer, PriorityQueue<Integer>>> map) {
            if (root == null) {
                return;
            }
            leftMostIndex = Math.min(index, leftMostIndex);     // 更新最左节点的index作为全局偏移
            map.putIfAbsent(index, new TreeMap<>());            // 在当前index插入新的TreeMap
            map.get(index).putIfAbsent(level, new PriorityQueue<>());   // 插入新的pq
            map.get(index).get(level).offer(root.val);
            helper(root.left, index - 1, level + 1, map);
            helper(root.right, index + 1, level + 1, map);
        }
    }

988. smallest-string-starting-from-leaf

  • 给一个二叉树，其中的数字只含有[0, 26]，表示小写字母。求从叶子到根的最小字典序的字符串。
  • 一开始理解错了字典序。字典序与长度无关，直接是按字母排的，因此用BFS没有任何优势。DFS写出来的代码还更简洁。

992. subarrays-with-k-different-integers

  • 给一个int数组，求含有k个不同数字的子数组的个数。
  • 和340类似，可以利用滑动窗口求至多K个不同数字的子数组个数和至多K - 1个不同数字的子数组个数，相减就是恰好K个不同数字的子数组个数。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    class Solution {
        public int subarraysWithKDistinct(int[] A, int K) {
            if (A == null || A.length == 0) {
                return 0;
            }
            return atMostKDistinct(A, K) - atMostKDistinct(A, K - 1);
        }
        private int atMostKDistinct(int[] nums, int k) {
            Map<Integer, Integer> map = new HashMap<>();
            int i = 0, count = 0;
            for (int j = 0; j < nums.length; j++) {
                map.put(nums[j], map.getOrDefault(nums[j], 0) + 1);
                while (map.size() > k) {
                    if (map.get(nums[i]) == 1) {
                        map.remove(nums[i]);
                    } else {
                        map.put(nums[i], map.get(nums[i]) - 1);
                    }
                    i++;
                }
                count += (j - i + 1);
            }
            return count;
        }
    }

993. cousins-in-binary-tree

  • 给一个各节点值各不相同的二叉树，给两个值，判断他们是否是cousin（depth相同而parent不同）。
  • 可以用map来track每个节点的depth和parent。也可以进行level traversal，放入null来进行分隔。如果找到的两个节点之间没有null说明是紧挨着的亲兄弟。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    class Solution {
        public boolean isCousins(TreeNode root, int x, int y) {
            if (root == null) {
                return false;
            }
            Queue<TreeNode> q = new LinkedList<>();
            q.offer(root);
            boolean found = false, sibling = false;
            while (!q.isEmpty()) {
                Queue<TreeNode> next = new LinkedList<>();
                while (!q.isEmpty()) {
                    TreeNode curr = q.poll();
                    if (curr == null) {
                        sibling = false;
                        continue;
                    }
                    if (curr.val == x || curr.val == y) {
                        if (found) {
                            return !sibling;
                        } else {
                            found = true;
                            sibling = true;
                        }
                    }
                    if (curr.left != null || curr.right != null) {
                        next.offer(curr.left);
                        next.offer(curr.right);
                        next.offer(null);       // 强行分隔
                    }
                }
                if (found) {
                    return false;
                }
                q = next;
            }
            return false;
        }
    }

994. rotting-oranges

  • 给一个二维数组，0表示空、1表示好的橘子、2表示烂的橘子，每分钟烂橘子会感染上下左右相邻的好橘子，问经过多久所有橘子都会烂掉，若不可能全烂掉则返回-1.
  • BFS即可，需要注意的是一开始要统计所有橘子数量，然后在BFS的过程中不断减去烂掉的橘子，最后如果还剩有橘子说明无法全部感染。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    class Solution {
        private int[][] directions = new int[][] {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        public int orangesRotting(int[][] grid) {
            if (grid == null || grid.length == 0) {
                return 0;
            }
            int rowCount = grid.length, colCount = grid[0].length, count = 0, orange = 0;
            Queue<int[]> q = new LinkedList<>();
            for (int i = 0; i < rowCount; i++) {
                for (int j = 0; j < colCount; j++) {
                    if (grid[i][j] != 0) {
                        orange++;
                    }
                    if (grid[i][j] == 2) {
                        q.add(new int[] {i, j});
                    }
                }
            }
            while (!q.isEmpty()) {
                int size = q.size();
                orange -= size;
                while (size-- > 0) {
                    int[] curr = q.poll();
                    for (int i = 0; i < directions.length; i++) {
                        int[] position = new int[] {curr[0] + directions[i][0], curr[1] + directions[i][1]};
                        if (isValid(position, rowCount, colCount) && grid[position[0]][position[1]] == 1) {
                            grid[position[0]][position[1]] = 2;
                            q.offer(position);
                        }
                    }
                }
                if (!q.isEmpty()) {
                    count++;
                }
            }
            return orange == 0 ? count : -1;
        }
        private boolean isValid(int[] position, int rowCount, int colCount) {
            return position[0] >= 0 && position[0] < rowCount
                && position[1] >= 0 && position[1] < colCount;
        }
    }

997. find-the-town-judge

  • 给一个二维数组，每一项为一个pair表示a trusts b，求所有人都trust且他不trust任何人的的那个数字。
  • 一开始使用map和set完成。但题目说了数组中各项不会重复，因此可以放心的利用图的入度来判断。没有一次过是因为有个测试没有想到，留个玄机。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
        public int findJudge(int N, int[][] trust) {
            if (trust == null || trust.length == 0) {
                return N == 1 ? 1 : -1;
            }
            int[] inDegrees = new int[N + 1];
            for (int[] pair : trust) {
                inDegrees[pair[0]]--;
                inDegrees[pair[1]]++;
            }
            for (int i = 1; i <= N; i++) {
                if (inDegrees[i] == N - 1) {
                    return i;
                }
            }
            return -1;
        }
    }

998. maximum-binary-tree-ii

  • 给一个二叉树，每个节点比它下方的所有节点都大。给一个val，插入这个max-tree，如果比root大就直接是新的root，如果小就到右子树继续插入。
  • 递归写法很直接，时间空间都是O(N)。为了优化递归所需的stack space，需要想iterative实现，尽可能潜入右子树，直到右节点值小于插入值。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    class Solution {
        public TreeNode insertIntoMaxTree(TreeNode root, int val) {
            TreeNode node = new TreeNode(val), curr = root;
            if (root == null || root.val < val) {
                node.left = root;
                return node;
            }
            while (curr.right != null && curr.right.val > val) {
                curr = curr.right;
            }
            node.left = curr.right;
            curr.right = node;
            return root;
        }
    }

1003. check-if-word-is-valid-after-substitutions

  • stack搞定。注意java中建议用arraydeque: Please consider using ArrayDeque instead of Stack for your Java solutions. Stack is an extension of Vector which is depricated List. It's methods are also synchronized which slows down the execution time.. 或者最暴力的直接循环替换S.replace("abc").
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution {
        public boolean isValid(String S) {
            if (S == null || S.length() == 0) {
                return true;
            }
            ArrayDeque<Character> stack = new ArrayDeque<>();
            char[] chars = S.toCharArray();
            for (char c : chars) {
                if (c == 'c') {
                    if (stack.size() >= 2 && stack.pop() == 'b' && stack.pop() == 'a') {
                        continue;
                    } else {
                        return false;
                    }
                } else {
                    stack.push(c);
                }
            }
            return stack.isEmpty();
        }
    }

1004. max-consecutive-ones-iii

  • 给一个只含有0或1的数组，假设可以将其中K个0换成1，问最长可以有多少连续的1.
  • 双指针，之间的范围就是至多替换K次后的序列。right持续往后走，若当前没有剩余的credit了，就挪动left知道恢复credit。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution {
        public int longestOnes(int[] A, int K) {
            if (A == null || A.length == 0) {
                return 0;
            }
            int left = 0, right = 0, maxLen = 0;
            while (right < A.length) {
                if (A[right] == 0) {
                    while (K == 0) {
                        if (A[left++] == 0) {
                            K++;
                        }
                    }
                    K--;
                }
                right++;
                maxLen = Math.max(maxLen, right - left);
            }
            return maxLen;
        }
    }

1007. minimum-domino-rotations-for-equal-row

  • 给两个数组，表示两排的骰子值。求最小的swap次数使得任意一排的骰子值完全一样。若不存在则返回-1.

  • 方法一：暴力尝试，要么是第一排骰子的值、要么是取第二排的，就分两次尝试。在每次尝试中要么使得第一排一致、要么使得第二排一致。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class Solution {
        public int minDominoRotations(int[] A, int[] B) {
            if (A == null || B == null || A.length != B.length) {
                return -1;
            }
            int retVal = getSwapWithTarget(A, B, A[0]);
            return retVal >= 0 ? retVal : getSwapWithTarget(A, B, B[0]);
        }
        private int getSwapWithTarget(int[] A, int[] B, int target) {
            for (int i = 0, equalTop = 0, equalBottom = 0; i < A.length && (A[i] == target || B[i] == target); i++) {
                if (A[i] != target) {
                    equalTop++; // 使得上面一排一致，因此需要swap一次
                }
                if (B[i] != target) {
                    equalBottom++;  // 使得下面一排一致
                }
                if (i == A.length - 1) {
                    return Math.min(equalTop, equalBottom);
                }
            }
            return -1;
        }
    }

  • 方法二：取并集的思路，对两排分别统计6个点数的出现次数，同时需要统计两排的值一样的次数。要想有答案，则必须存在一个点数使得上下两排的长度和除去重复部分后，足够覆盖整一排，最后最小的交换次数就是min(A, B) - (A & B)了。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class Solution {
        public int minDominoRotations(int[] A, int[] B) {
            if (A == null || B == null || A.length != B.length) {
                return -1;
            }
            int[] countA = new int[7];
            int[] countB = new int[7];
            int[] union = new int[7];
            for (int i = 0; i < A.length; i++) {
                countA[A[i]]++;
                countB[B[i]]++;
                if (A[i] == B[i]) {
                    union[A[i]]++;
                }
            }
            for (int i = 1; i <= 6; i++) {
                if (countA[i] + countB[i] - union[i] >= A.length) {
                    return Math.min(countA[i], countB[i]) - union[i]; // 上下相同就不用交换了
                }
            }
            return -1;
        }
    }

1008. construct-binary-search-tree-from-preorder-traversal

  • 给一个BST前序遍历得到的int数组，求还原成的BST。
  • 方法一：从当前节点往后找左子树和右子树，然后分别build，但是这样效率很低，因为需要重复比较大小。
  • 方法二：设置一个max值表示当前这个节点的上界，如果超过就可以直接返回null，然后也是递归找。关键是用一个全局的索引表示当前处理到数组的第几位了，就不需要重复比较大小了。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
        private int start = 0;
        public TreeNode bstFromPreorder(int[] preorder) {
            if (preorder == null || preorder.length == 0) {
                return null;
            }
            return build(preorder, Integer.MAX_VALUE);
        }
        private TreeNode build(int[] preorder, int max) {
            if (start == preorder.length || preorder[start] > max) {
                return null;
            }
            TreeNode root = new TreeNode(preorder[start++]);
            root.left = build(preorder, root.val);
            root.right = build(preorder, max);
            return root;
        }
    }

1010. pairs-of-songs-with-total-durations-divisible-by-60

  • 给一个int数组，求其中有多少对儿之和可以是60的倍数。
  • 本质上就是类似求two-sum，只是不求具体的索引。给一个时长t，在数组中找是否有其他时长x满足(x + t) % 60 == 0 -> x % 60 + t % 60 == 60 -> x % 60 == 60 - t % 60。但是edge case是t恰好是60的整数倍的时候，这时60 - t % 60 == 60，而我们希望它是0.直接的办法就是再摸一个。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution {
        public int numPairsDivisibleBy60(int[] time) {
            if (time == null || time.length == 0) {
                return 0;
            }
            int MOD = 60, count = 0;
            int[] bucket = new int[MOD];
            for (int t : time) {
                count += bucket[(MOD - t % MOD) % MOD];
                bucket[t % MOD]++;
            }
            return count;
        }
    }

1011. capacity-to-ship-packages-within-d-days

  • 给一个物品重量的int数组，再给一个天数D，要求将这些物品按顺序在D天之内用同一艘船运出，该船每天只能运一趟。求这艘船最少需要承受多少重量。
  • 经典的背包问题。可以利用二分查找找到最小重量，搜索下界是最终的一个物品、上届是所有物品的和。若mid符合条件，则尝试将上界挪到mid；若无法实现，则将下界挪到mid + 1.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    class Solution {
        public int shipWithinDays(int[] weights, int D) {
            if (weights == null || weights.length == 0) {
                return 0;
            }
            int sum = 0, max = 0;
            for (int weight : weights) {
                sum += weight;
                max = Math.max(weight, max);
            }
            int left = max, right = sum;
            while (left != right) {
                int mid = left + (right - left) / 2;
                if (isPossible(weights, mid, D)) {
                    right = mid;    // mid仍是可能的答案，需要保留在有效范围内
                } else {
                    left = mid + 1; // 不用再包含mid了
                }
            }
            return left;
        }
        private boolean isPossible(int[] weights, int capacity, int days) {
            int sum = 0;
            for (int weight : weights) {
                if (sum + weight > capacity) {
                    days--;
                    sum = weight;
                } else {
                    sum += weight;
                }
            }
            return days >= 1;
        }
    }

1014. best-sightseeing-pair

  • 给一个int数组，求其中最大的sum = A[left] + A[right] - (right - left)，即值之和减索引之差。
  • one pass的做法真的妙哉，将上式转换称sum = A[left] + left + A[right] - right，在从左往右循环时只需要保留left索引即可比较。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution {
        public int maxScoreSightseeingPair(int[] A) {
            if (A == null || A.length == 0) {
                return 0;
            }
            int retVal = 0, left = 0;
            for (int i = 1; i < A.length; i++) {
                int temp = A[i] - i + A[left] + left;
                retVal = Math.max(retVal, temp);
                if (A[i] + i > A[left] + left) {
                    left = i;
                }
            }
            return retVal;
        }
    }

1019. next-greater-node-in-linked-list

  • 给一个链表头节点，返回一个数组存放其中每一个元素的后续第一个比它大的元素。
  • 经典monotone问题，用stack解决。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    class Solution {
        public int[] nextLargerNodes(ListNode head) {
            if (head == null) {
                return new int[0];
            }
            List<Integer> list = new ArrayList<>();
            Stack<int[]> stack = new Stack<>();
            int index = 0;
            while (head != null) {
                while (!stack.isEmpty() && head.val > stack.peek()[1]) {
                    int[] top = stack.pop();
                    list.set(top[0], head.val);
                }
                stack.push(new int[] { index++, head.val });
                list.add(0);
                head = head.next;
            }
            int[] retVal = new int[index];
            for (int i = 0; i < index; i++) {
                retVal[i] = list.get(i);
            }
            return retVal;
        }
    }

1021. remove-outermost-parentheses

  • 给一个valid的括号字符串，求将最外层括号移除后的新字符串。例如(()())(())(()(()))可以拆分成(()()), (()), (()(()))，将每个部分的最外层移除后得到的就是()()()()(())。直接用一个计数来存左括号数目即可。pass。

1022. sum-of-root-to-leaf-binary-numbers

  • 给一个只含有0和1的二叉树，从根到叶子表示二进制的数，求所有表示出来的数的和。直接在每一节点处累加，如果后续还有节点就左移1后继续累加。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Solution {
        public int sumRootToLeaf(TreeNode root) {
            return dfs(root, 0);
        }
        private int dfs(TreeNode root, int val) {
            if (root == null) {
                return 0;
            }
            val += root.val;
            return root.left == root.right ? val : dfs(root.left, val << 1) + dfs(root.right, val << 1);
        }
    }

1024. video-stitching

  • 给一个视频的clip起始终止时间戳interval的数组，给目标终止时间T，求能拼接成[0, T]完整视频所需要的最少的clip数量。

  • 方法一：greedy。首先根据起始时间戳对所有clips从小到大排序。从clips中不断取比当前start小的所有clips，取它们中最大的end作为下一步循环的start。如果start和end都没有任何变化，说明中间断掉了，不可能拼成完整视频。时间复杂度O(N*logN)。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
        public int videoStitching(int[][] clips, int T) {
            if (clips == null || clips.length == 0) {
                return 0;
            }
            Arrays.sort(clips, (a, b) -> a[0] - b[0]);
            int count = 0;
            for (int i = 0, start = 0, end = 0; start < T; start = end, count++) {
                for (; i < clips.length && clips[i][0] <= start; i++) {
                    end = Math.max(end, clips[i][1]);
                }
                if (start == end) {
                    return -1;
                }
            }
            return count;
        }
    }

  • 方法二：DP。利用一个dp数组记录以i结束的视频所需的最小clips数，每次只取恰好能覆盖当前i的clip进行更新，转换方程是dp[i] = dp[起始时间戳] + 1。时间复杂度O(T*N).

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
        public int videoStitching(int[][] clips, int T) {
            if (clips == null || clips.length == 0) {
                return 0;
            }
            int[] dp = new int[T + 1];
            Arrays.fill(dp, T + 1);
            dp[0] = 0;
            for (int i = 1; i <= T; i++) {
                for (int[] clip : clips) {
                    if (clip[0] <= i && clip[1] >= i) {
                        dp[i] = Math.min(dp[i], dp[clip[0]] + 1);
                    }
                }
            }
            return dp[T] == T + 1 ? -1 : dp[T];
        }
    }

1026. maximum-difference-between-node-and-ancestor

  • 给一个二叉树，求祖先和孩子节点的最大差的绝对值，求差的两个节点必须是同一个flow下来的，而不能是siblings。

  • 方法一：bottom-up, 全局变量+最大最小值搞定。需要注意的是一开始想当然地只取了最小值，但实际上需要同时求孩子节点中的最小和最大，和当前节点的作差求绝对值才完整。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    class Solution {
        private int maxDiff = 0;
        public int maxAncestorDiff(TreeNode root) {
            if (root == null) {
                return 0;
            }
            getMinMax(root);
            return maxDiff;
        }
        private int[] getMinMax(TreeNode node) {
            int minNew = node.val;
            int maxNew = node.val;
            if (node.left != null) {
                int[] leftMinMax = getMinMax(node.left);
                minNew = Math.min(minNew, leftMinMax[0]);
                maxNew = Math.max(maxNew, leftMinMax[1]);
                maxDiff = Math.max(maxDiff, Math.max(Math.abs(node.val - leftMinMax[0]), Math.abs(node.val - leftMinMax[1])));
            }
            if (node.right != null) {
                int[] rightMinMax = getMinMax(node.right);
                minNew = Math.min(minNew, rightMinMax[0]);
                maxNew = Math.max(maxNew, rightMinMax[1]);
                maxDiff = Math.max(maxDiff, Math.max(Math.abs(node.val - rightMinMax[0]), Math.abs(node.val - rightMinMax[1])));
            }
            return new int[] { minNew, maxNew };
        }
    }

  • 方法二：top-down，反正都是求差的绝对值，完全可以将祖先的最大最小值传入孩子节点再作差，不需要返回成数组形式到上层。最终是在null节点结束递归返回maxDiff，直接用max - min即可.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
        private int maxDiff = 0;
        public int maxAncestorDiff(TreeNode root) {
            if (root == null) {
                return 0;
            }
            return dfs(root, root.val, root.val);
        }
        private int dfs(TreeNode node, int min, int max) {
            if (node == null) {
                return max - min;
            }
            max = Math.max(node.val, max);
            min = Math.min(node.val, min);
            return Math.max(dfs(node.left, min, max), dfs(node.right, min, max));
        }
    }

1027. longest-arithmetic-sequence

  • 给一个int数组，求其中最长子等差序列的长度。例如[20,1,15,3,10,5,8]最长的就是[20,15,10,5].
  • DP。在每一个节点处存放之前所有的信息diff+长度，这样从后面往前减的时候就直接能知道以这个差值往前还有多长。时间复杂度O(N^2)。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution {
        public int longestArithSeqLength(int[] A) {
            if (A == null || A.length == 0) {
                return 0;
            }
            HashMap<Integer, Integer>[] dp = new HashMap[A.length];
            int max = 2;
            for (int i = 0; i < A.length; i++) {
                dp[i] = new HashMap<Integer, Integer>();
                for (int j = i - 1; j >= 0; j--) {
                    int diff = A[i] - A[j];
                    if (dp[i].containsKey(diff)) {
                        continue;
                    }
                    dp[i].put(diff, dp[j].getOrDefault(diff, 1) + 1);   
                    max = Math.max(dp[i].get(diff), max);
                }
            }
            return max;
        }
    }

1029. two-city-scheduling

  • 公司需要面试2N个人，安排到2个城市onsite，给一个二维int数组表示每个人前往两个城市的开销，求每个城市分别去N个人的最小总开销。

  • 方法一：DP，每个人只有两种选择，去A或者去B，dp[i][j]表示安排i个人到A、j个人到B的总开销，dp[i][j]等于A处少一人加去A的开销或B处少一人加去B的开销的最小值，最后求dp[N][N]即可。时间复杂度O(N^2)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution {
        public int twoCitySchedCost(int[][] costs) {
            if (costs == null || costs.length == 0) {
                return 0;
            }
            int N = costs.length / 2;
            int[][] dp = new int[N + 1][N + 1];
            
            for (int i = 1; i <= N; i++) {
                dp[i][0] = dp[i - 1][0] + costs[i - 1][0];
                dp[0][i] = dp[0][i - 1] + costs[i - 1][1];
            }
            
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    dp[i][j] = Math.min(dp[i - 1][j] + costs[i + j - 1][0], dp[i][j - 1] + costs[i + j - 1][1]);
                }
            }
            return dp[N][N];
        }
    }

  • 方法二：假设先把所有人一股脑丢到A，然后考虑把一半的人丢到B会产生多少diff，这个refund实际上就是costB - costA，负值说明选择B就能拿到refund，因此直接对所有diff从小到大排序即可，取前N个最小的refund就是了。O(NlogN).

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution {
        public int twoCitySchedCost(int[][] costs) {
            if (costs == null || costs.length == 0) {
                return 0;
            }
            int N = costs.length / 2;
            int[] diff = new int [costs.length];
            int sum = 0;
            for (int i = 0; i < costs.length; i++) {
                sum += costs[i][0];
                diff[i] = costs[i][1] - costs[i][0];
            }
            
            Arrays.sort(diff);
            
            for (int i = 0; i < N; i++) {
                sum += diff[i];
            }
            return sum;
        }
    }

1031. maximum-sum-of-two-non-overlapping-subarrays

  • prefixSum之后固定L，分别求左右两侧以M为长度的最大subarray。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    class Solution {
        public int maxSumTwoNoOverlap(int[] A, int L, int M) {
            if (A == null || A.length == 0) {
                return 0;
            }
            int len = A.length;
            int[] sum = new int[len + 1];
            for (int i = 1; i <= len; i++) {
                sum[i] = sum[i - 1] + A[i - 1];
            }
            
            // SUM(A[i]...A[j]) = sum[j + 1] - sum[i];
            int retVal = 0;
            for (int i = L; i < sum.length; i++) {
                int sumL = sum[i] - sum[i - L];
                int sumLeft = getMaxSum(sum, 0, i - L, M);
                int sumRight = getMaxSum(sum, i, len, M);
                retVal = Math.max(sumL + Math.max(sumLeft, sumRight), retVal);
            }
            return retVal;
        }
        private int getMaxSum(int[] sum, int from, int to, int M) {
            int retVal = 0;
            for (int i = from + M; i <= to; i++) {
                retVal = Math.max(sum[i] - sum[i - M], retVal);
            }
            return retVal;
        } 
    }

  • 真·O(N)解法。最终结果只有两种情况，[L]子数组在左，[M]子数组在右；或者[M]子数组在左，[L]子数组在右. 因此最开始假设最大和retVal为[L,M]，maxL表示当前索引-M之前的长度为L的子数组最大值，maxM表示当前索引-L之前的长度为M的子数组最大值。遍历时同时更新maxL和maxM，再用retVal与maxL + (当前索引 - M这段)和maxM + (当前索引 - L这段).

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution {
        public int maxSumTwoNoOverlap(int[] A, int L, int M) {
            if (A == null || A.length == 0) {
                return 0;
            }
            int len = A.length;
            int[] sum = new int[len + 1];
            for (int i = 1; i <= len; i++) {
                sum[i] = sum[i - 1] + A[i - 1];
            }
            
            // SUM(A[i]...A[j]) = sum[j + 1] - sum[i];
            int retVal = sum[L + M], maxL = sum[L], maxM = sum[M];
            for (int i = L + M + 1; i < sum.length; i++) {
                maxL = Math.max(maxL, sum[i - M] - sum[i - L - M]); // i-M之前的长度为L的最大值
                maxM = Math.max(maxM, sum[i - L] - sum[i - L - M]); // i-L之前的长度为M的最大值
                retVal = Math.max(retVal, Math.max(maxL + sum[i] - sum[i - M], maxM + sum[i] - sum[i - L]));
            }
            return retVal;
        }
    }

1039. minimum-score-triangulation-of-polygon

  • 给一个数组表示一个N边形各个顶点的权重。在N边形内部连上N-2条边构成多个三角形，每个三角形顶点求乘积，最后将乘积求和作为score。问最小score是多少。
  • bottom-up DP。dp[i][j]表示从i顶点到j顶点的最小score，那么假设从k处拆分成前后两部分并将i, j, k顶点相连作为一个三角形，那么dp[i][j] = dp[i][k] + dp[k][j] + 三个顶点乘积。需要注意为了形成三角形，必须满足i < k < j。首先固定i和j之间距离为2，然后再慢慢增加为3, ..., A.length-1.时间复杂度O(N^3).
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
        public int minScoreTriangulation(int[] A) {
            if (A == null || A.length == 0) {
                return 0;
            }
            int[][] dp = new int[A.length][A.length];
            for (int len = 2; len < A.length; len++) {
                for (int left = 0; left + len < A.length; left++) {
                    int right = left + len;
                    dp[left][right] = Integer.MAX_VALUE;
                    for (int mid = left + 1; mid < right; mid++) {
                        dp[left][right] = Math.min(dp[left][right], dp[left][mid] + dp[mid][right] + A[left] * A[right] * A[mid]);
                    }
                }
            }
            return dp[0][A.length - 1];
        }
    }

1041. robot-bounded-in-circle

  • 假设一个机器人在一个平面直角坐标系中的原点，面向北方，给它一个字符串作为指令，L左转、R右转、G前进，判断无限次执行这个命令后它是否会回到原点。
  • 规律：如果指令执行一次结束时机器人已经回到原点，那之后肯定也会回到原点。如果没到原点，看它面向那个方向，如果是北方意味着它会越走越远，否则经过1次或3次命令后它还是会回到原点。关键就在于举出它“无法回到原点”的反例并总结规律。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
        final private int[][] dirs = new int[][] {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        public boolean isRobotBounded(String instructions) {
            int x = 0, y = 0, dirIndex = 0;
            for (char c : instructions.toCharArray()) {
                if (c == 'R') {
                    dirIndex = (dirIndex + 1) % 4;
                } else if (c == 'L') {
                    dirIndex = (dirIndex + 3) % 4;
                } else {
                    x += dirs[dirIndex][0];
                    y += dirs[dirIndex][1];
                }
            }
            return (x == 0 && y == 0) || dirIndex != 0;
        }
    }

1047. remove-all-adjacent-duplicates-in-string

  • 给一个字符串，返回删除相邻相同字符后的字符串。StringBuilder不断删即可。pass。

1048. longest-string-chain

  • 给一个字符串数组，组成chain的条件是前后两个字符串满足prev加上一个字符可以得到next。求这些字符串最多可以组成多长的chain。
  • 注意没有要求按顺序从原数组中取，因此可以任意组成chain，只要前后满足条件。那么利用类似DP的思路，维护一个string->int的map，对于每一个字符串尝试去掉一个字符看看map是否有对应的前序字符串。注意的是必须对原数组从短到长排序，这样从前往后取字符串的时候才能保证短的字符串在map中已经得到最终的count.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    class Solution {
        public int longestStrChain(String[] words) {
            if (words == null || words.length == 0) {
                return 0;
            }
            // 必须从短到长排序
            Arrays.sort(words, (a, b) -> a.length() - b.length());
            Map<String, Integer> map = new HashMap<>();
            int ans = 0;
            for (String word : words) {
                int max = 0;
                for (int i = 0; i < word.length(); i++) {
                    String prev = word.substring(0, i) + word.substring(i + 1);
                    max = Math.max(max, map.getOrDefault(prev, 0) + 1);
                }
                map.put(word, max);
                ans = Math.max(max, ans);
            }
            
            return ans;
        }
    }

1049. last-stone-weight-ii

  • 给一个int数组表示一堆石头，石头两两之间如果重量相同则合成为0，若不同则合成之后剩余为重量差。求将所有石头合成之后剩下最后的最小重量。
  • 以三个石头为例，他们之间取差后求和实际上只有8-2 = 6种情况，都是在一部分石头取正、另一部分取负求和的最小值，即positiveSum - negativeSum = positiveSum - (sum - positiveSum) = 2 * positiveSum - sum的最小值，因此取最小的那个能凑成的positiveSum就是所求了。dp[i]表示以i为sum的部分是否可以凑成，从dp[sum]开始往前看dp[i] - stone是否存在。最后从sum/2开始找positiveSum即为所求。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    class Solution {
        public int lastStoneWeightII(int[] stones) {
            if (stones == null || stones.length == 0) {
                return 0;
            }
            if (stones.length == 1) {
                return stones[0];
            }
            int sum = IntStream.of(stones).sum();
            boolean[] dp = new boolean[sum + 1];
            dp[0] = true;
            
            for (int stone : stones) {
                for (int tempSum = sum; tempSum >= 0; tempSum--) {
                    if (tempSum - stone < 0) {
                        break;
                    }
                    if (dp[tempSum - stone]) {
                        dp[tempSum] = true;
                    }
                }
            }
            
            for (int positiveSum = (sum + 1) / 2; positiveSum <= sum; positiveSum++) {
                if (dp[positiveSum]) {
                    return 2 * positiveSum - sum;
                }
            }
            return 0;
        }
    }

1051. height-checker

  • 给一个数组，求其中位置不对的整数个数。
  • 木桶排序后直接逐位比较即可。pass.

1052. grumpy-bookstore-owner

  • 给两个数组，一个表示该分钟时进入商店的人数，一个表示店主的心情，0表示可以、1表示爆炸。假设店主有能力控制K分钟内不爆炸，求最多能让顾客满意的人数。customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3时，控制最后三分钟不爆炸就可以让人数达到16个。
  • 双指针O(N)搞定。pass。

1053. previous-permutation-with-one-swap

  • 给一个int数组，求任意swap一对儿数字之后得到的恰好比当前permutation小的前一个排列。若已经最小了则直接放回本身。
  • 和next permutation很类似。这个就从后往前找第一个破坏了递减特性的数字，再从后往前找第一个比该数小的，注意如果有多个相同的则需要找到最前面的那个，将他们swap即得。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    class Solution {
        public int[] prevPermOpt1(int[] A) {
            if (A == null || A.length == 0) {
                return new int[0];
            }
            int index = -1;
            for (int i = A.length - 1; i > 0; i--) {
                if (A[i - 1] > A[i]) {
                    index = i - 1;
                    break;
                }
            }
            if (index == -1) {
                return A;
            }
            for (int i = A.length - 1; i > index; i--) {
                if (A[i] < A[index] && A[i] != A[i - 1]) {
                    int temp = A[index];
                    A[index] = A[i];
                    A[i] = temp;
                    break;
                }
            }
            return A;
        }
    }

1055. shortest-way-to-form-string

  • 给一个source字符串和一个target字符串(只含有小写字母)，求最少需要多少个source的子序列能够拼接出target，若不可能则返回-1。例如target = abbbbc, source = abc，就需要ab + b + b + bc总共4个子序列。

  • 方法一：近乎暴力的双指针，从target开始遍历，每次扫一遍source进行尽可能多的匹配，如果没有挪动说明完全没有match的字符串，直接返回-1. 时间复杂度O(M*N).

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    class Solution {
        public int shortestWay(String source, String target) {
            if (source == null || target == null) {
                return -1;
            }
            char[] sourceChar = source.toCharArray(), targetChar = target.toCharArray();
            int targetIndex = 0, count = 0;
            while (targetIndex < targetChar.length) {
                int targetIndexPrev = targetIndex;
                for (int sourceIndex = 0; sourceIndex < sourceChar.length && targetIndex < targetChar.length; sourceIndex++) {
                    if (targetChar[targetIndex] == sourceChar[sourceIndex]) {
                        targetIndex++;
                    }
                }
                if (targetIndex == targetIndexPrev) {
                    return -1;
                }
                count++;
            }
            return count;
        }
    }

  • 方法二：缩短在source中搜索的时间，对于source中每个字符维护一个List<Integer>，这样就可以用二分查找快速找到字符的理论位置（必须大于等于某个索引）。遍历target，取得当前字符在source中的所有index，用二分查找找出下一个可用索引。如果已经到头了说明用掉了一个source，否则source后续部分还可以继续用，只是要在下次二分搜索时搜当前source索引的下一位。时间复杂度O(N * logM)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    class Solution {
        public int shortestWay(String source, String target) {
            if (source == null || target == null) {
                return -1;
            }
            List<Integer>[] indexes = new List[26];
            char[] sourceChar = source.toCharArray(), targetChar = target.toCharArray();
            for (int i = 0; i < sourceChar.length; i++) {
                if (indexes[sourceChar[i] - 'a'] == null) {
                    indexes[sourceChar[i] - 'a'] = new ArrayList<>();
                }
                indexes[sourceChar[i] - 'a'].add(i);
            }
            int targetIndex = 0, sourceIndex = 0, count = 1;
            while (targetIndex < targetChar.length) {
                List<Integer> index = indexes[targetChar[targetIndex] - 'a'];
                if (index == null) {
                    return -1;
                }
                int i = Collections.binarySearch(index, sourceIndex);
                if (i < 0) {
                    i = -i - 1;
                }
                if (i == index.size()) {
                    count++;
                    sourceIndex = 0;
                } else {
                    sourceIndex = index.get(i) + 1;  // source后续部分可能可以继续用
                    targetIndex++;
                }
            }
            return count;
        }
    }

1057. campus-bikes

  • 给一组workers坐标和bikes坐标，要求每一个worker取车时取的时距离自己最近的bike，其中距离是用manhatten算的，即横纵坐标各自的差的绝对值之和。其中每一个坐标都在0~999，每一个坐标都是不同的。要求按照worker的索引顺序返回bike的索引。
  • 方法一：本质上就是要对所有可能<worker, bike>pair的排序。首先根据距离排序，其次根据worker索引排序，再其次根据bike索引排序。这样就能保证每次从里面取出来的是距离最短的。
  • 方法二：排序还可以更快。既然规定了坐标范围，那么最远的坐标就在(0,0)-(999,999)这一组产生，即1998。根据距离进行木桶排序，每个木桶的索引表示距离，里面存放的是一个List，表示所有这个距离的<w, b>pair。首先来一波O(N*M)的双重循环把两两之间的距离都存进去，然后就从小到大取距离中的list of pairs，每个pair中如果worker没有分配且bike没有被取走，就是一个合法的pair了。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    class Solution {
        public int[] assignBikes(int[][] workers, int[][] bikes) {
            if (workers == null || workers.length == 0 ||
               bikes == null || bikes.length == 0) {
                return new int[0];
            }
            List<int[]>[] bucket = new ArrayList[2001]; // 每个distance的所有w,b组合
            for (int i = 0; i < workers.length; i++) {
                for (int j = 0; j < bikes.length; j++) {
                    int dis = getDistance(workers[i], bikes[j]);
                    if (bucket[dis] == null) {
                        bucket[dis] = new ArrayList<int[]>();
                    }
                    bucket[dis].add(new int[] {i, j});
                }
            }
            
            boolean[] bikeVisited = new boolean[bikes.length];
            int[] ans = new int[workers.length];
            Arrays.fill(ans, -1);
            for (int dis = 0; dis < bucket.length; dis++) {
                List<int[]> pairs = bucket[dis];
                if (pairs != null) {
                    for (int[] pair : pairs) {
                        // 若这个w没有被分配且b没有被取
                        if (ans[pair[0]] == -1 && !bikeVisited[pair[1]]) {
                            ans[pair[0]] = pair[1];
                            bikeVisited[pair[1]] = true;
                        }
                    }
                }
            }
            return ans;
        }
        private int getDistance(int[] a, int[] b) {
            return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]);
        }
    }

1060. missing-element-in-sorted-array

  • 给一个排好序的数据和一个k，求从最小数开始第k个missing的数字。例如[1,5,8], 2就是3。
  • 方法一：最朴素的O(N)，从左往右遍历找。
  • 方法二：一看到排好序的就需要敏感点，想到O(logN)的二分查找。根据missing数字的个数来决定往左半部分还是右半部分进行搜索。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution {
        public int missingElement(int[] nums, int k) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
            int n = nums.length, left = 0, right = n - 1;
            while (left + 1 < right) {
                int mid = left + (right - left) / 2;
                int missingCountLeft = nums[mid] - nums[left] - mid + left;
                if (k <= missingCountLeft) {  // 说明在左半部分
                    right = mid;
                } else {
                    left = mid;
                    k -= missingCountLeft;
                }
            }
            return nums[left] + k >= nums[right] ?
                nums[left] + k + 1 :
                nums[left] + k;
        }
    }

1062. longest-repeating-substring

  • 给一个字符串，求其自身中最长的重复子字符串，可以重叠。

  • DP。dp[i][j]表示以i结尾和以j结尾的子字符串相等部分长度，在更新过程中求最大的即可。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
        public int longestRepeatingSubstring(String S) {
            if (S == null || S.length() == 0) {
                return 0;
            }
            int len = S.length(), maxLen = 0;
            int[][] dp = new int[len + 1][len + 1];
            for (int i = 1; i <= len; i++) {
                for (int j = i + 1; j <= len; j++) {
                    if (S.charAt(i - 1) == S.charAt(j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    }
                    maxLen = Math.max(maxLen, dp[i][j]);
                }
            }
            return maxLen;
        }
    }

  • 二分查找+set。猜一个长度，然后用sliding window逐个取子字符串存入set，看之前是否出现过。最坏情况时间复杂度是O(N^2)，平均是O(NlogN). 空间复杂度为O(N^2)，可以直接存成int的str.hashCode来降到O(N).

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    class Solution {
        private int binarySearch(String S, int n, int len) {
            HashSet<String> set = new HashSet<>();
            String curr;
            for (int from = 0; from < n - len + 1; from++) {
                curr = S.substring(from, from + len);
                if (set.contains(curr)) {
                    return from;
                }
                set.add(curr);
            }
            return -1;
        }
        public int longestRepeatingSubstring(String S) {
            if (S == null || S.length() == 0) {
                return 0;
            }
            int n = S.length(), maxLen = 0;
            int left = 1, right = n;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (binarySearch(S, n, mid) != -1) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return left - 1;
        }
    }

1066. campus-bikes-ii

  • 延续上一个给worker分配bike的任务，这次的要求是每个pair的mahattan distance之和最小。
  • 暴力解法，直接DFS，固定一个pair并进行相应的标记之后就dfs到下一层。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    class Solution {
        private int totalDistMin = Integer.MAX_VALUE;
        public int assignBikes(int[][] workers, int[][] bikes) {
            dfs(workers, bikes, new boolean[bikes.length], 0, 0);
            return totalDistMin;
        }
        private void dfs(int[][] workers, int[][] bikes, boolean[] bikeVisited, int workerId, int totalDist) {
            if (workerId == workers.length) {
                totalDistMin = Math.min(totalDistMin, totalDist);
                return;
            }
            if (totalDist >= totalDistMin) {    // 已经不可能更小了
                return;
            }
            for (int bikeId = 0; bikeId < bikes.length; bikeId++) {
                if (!bikeVisited[bikeId]) {
                    bikeVisited[bikeId] = true;
                    dfs(workers, bikes, bikeVisited, workerId + 1, totalDist + getDist(workers[workerId], bikes[bikeId]));
                    bikeVisited[bikeId] = false;
                }
            }
        }
        private int getDist(int[] a, int[] b) {
            return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]);
        }
    }

1076. number-of-submatrices-that-sum-to-target

  • 给一个int matrix，求其中有多少个submatrix的sum等于给定的target。
  • 对每一行求好prefixSum后，暴力求每个可能的submatrix sum。固定左列索引，右列索引不断向后，每到一列就开始从上到下遍历行，将0 ~ row和left ~ right这部分所夹的sum作为key存入map，value则是这个sum出现的次数。这样在从上到下遍历的过程中，如果能出现target，则必须满足currSum - prefixSum == target，因此直接在map中查找currSum - target出现的次数即可。时间复杂度O(col * col * row)，空间如果不算输入部分则为map的O(row). 如果将方向调转一下也可以将时间变成O(row * row * col)，因此实际上看row和col谁更小了。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    class Solution {
        public int numSubmatrixSumTarget(int[][] matrix, int target) {
            if (matrix == null || matrix.length == 0) {
                return 0;
            }
            int rows = matrix.length, cols = matrix[0].length;
            for (int r = 0; r < rows; r++) {
                for (int c = 1; c < cols; c++) {
                    matrix[r][c] += matrix[r][c - 1];
                }
            }
            int count = 0;
            Map<Integer, Integer> sumCount = new HashMap<>();
            for (int colLeft = 0; colLeft < cols; colLeft++) {
                for (int colRight = colLeft; colRight < cols; colRight++) {
                    sumCount.clear();
                    sumCount.put(0, 1);
                    int currSum = 0;
                    for (int row = 0; row < rows; row++) {
                        currSum += matrix[row][colRight] - (colLeft == 0 ? 0 : matrix[row][colLeft - 1]);
                        count += sumCount.getOrDefault(currSum - target, 0);
                        sumCount.put(currSum, sumCount.getOrDefault(currSum, 0) + 1);
                    }
                }
            }
            return count;
        }
    }

1091. shortest-path-in-binary-matrix

  • 给一个只含有0和1的矩阵，1是障碍物，0是通道，八个方向都可以走，求从左上到右下的最小步数。
  • 经典BFS，但是需要注意处理edge case，例如起点终点本身是障碍物、起点就是终点等。需要将return放在size那层循环外面才能在没有邻居（起点就是终点）的情况下返回。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    class Solution {
        final private int[][] directions = new int[][] {{0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}};
        public int shortestPathBinaryMatrix(int[][] grid) {
            if (grid == null || grid.length == 0 || grid[0].length == 0) {
                return -1;
            }
            int rows = grid.length, cols = grid[0].length;
            if (grid[0][0] != 0 || grid[rows - 1][cols - 1] != 0) {
                return -1;
            }
            boolean[][] visited = new boolean[rows][cols];
            Queue<int[]> q = new LinkedList<>();
            q.offer(new int[] { 0, 0 });
            visited[0][0] = true;
            int steps = 0;
            while (!q.isEmpty()) {
                int size = q.size();
                steps++;
                while (size-- > 0) {
                    int[] curr = q.poll();
                    if (curr[0] == rows - 1 && curr[1] == cols - 1) {
                        return steps;
                    }
                    for (int[] direction : directions) {
                        int rowNew = curr[0] + direction[0];
                        int colNew = curr[1] + direction[1];
                        if (rowNew < 0 || rowNew >= rows ||
                            colNew < 0 || colNew >= cols ||
                            visited[rowNew][colNew] ||
                            grid[rowNew][colNew] != 0) {
                            continue;
                        }
                        visited[rowNew][colNew] = true;
                        q.offer(new int[] {rowNew, colNew});
                    }
                }
            }
            return -1;
        }
    }

1093. statistics-from-a-large-sample

  • 给一个int数组，count[num]表示num出现了那么多次。返回这些数的minimum, maximum, mean, median, and mode，统统用double.
  • 可以two-pass先求总共有多少个数字，然后再直接挪到中间求median. 也可以双指针一个从前往后、一个从后往前，只要找到中间交汇处即可。没啥意思。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    class Solution {
        public double[] sampleStats(int[] count) {
            if (count == null || count.length == 0) {
                return new double[0];
            }
            int left = 0, right = count.length - 1, total = 0;
            double sum = 0.0;
            Integer min = null, max = null, modeNum = null;
            int leftPart = 0, rightPart = 0, leftMax = 0, rightMin = 0;
            while (left <= right) {
                while (left <= right && count[left] == 0) {
                    left++;
                }
                while (right >= left && count[right] == 0) {
                    right--;
                }
                if (left > right) {
                    break;
                }
                if (min == null) {
                    min = left;
                }
                if (max == null) {
                    max = right;
                }
                if (leftPart <= rightPart) {
                    if (modeNum == null || count[modeNum] < count[left]) {
                        modeNum = left;
                    }
                    sum += (count[left] * left);
                    total += count[left];
                    leftPart += count[left];
                    leftMax = left++;
                } else {
                    if (modeNum == null || count[modeNum] < count[right]) {
                        modeNum = right;
                    }
                    sum += (count[right] * right);
                    total += count[right];
                    rightPart += count[right];
                    rightMin = right--;
                }
            }
            double mean = sum / total;
            double median = 0;
            if (leftPart > rightPart) {
                median = leftMax;
            } else if (leftPart == rightPart) {
                median = (leftMax + rightMin) / 2.0;
            } else {
                median = rightMin;
            }
            return new double[] {(double) min, (double) max, mean, median, (double) modeNum};
        }
    }

1094. car-pooling

  • 给一个carpool信息数组，每个信息组成为[乘客数，上车坐标，下车坐标]，再给一个车子最大容量，判断是否可能从左到右将乘客一次性carpool完成。

  • 方法一：和interval类似，首先按照上车顺序排序，之后需要知道接下来下车的是谁，因此需要一个优先队列按照下车顺序从小到大排好。每次上车就扣除剩余容量，下车就增加容量。时间复杂度O(NlogN)，空间O(N).

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Solution {
        public boolean carPooling(int[][] trips, int capacity) {
            if (trips == null || trips.length == 0 || trips[0].length == 0) {
                return true;
            }
            Arrays.sort(trips, (a, b) -> a[1] - b[1]);
            PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
            for (int[] trip : trips) {
                while (!pq.isEmpty() && pq.peek()[2] <= trip[1]) {
                    capacity += pq.poll()[0];
                }
                capacity -= trip[0];
                if (capacity < 0) {
                    return false;
                }
                pq.offer(trip);
            }
            return true;
        }
    }

  • 方法二：和253题非常像，按照时间顺序（上下车坐标）来track可用的容量。将上下车的坐标作为key、乘客加减数量变化为value存入TreeMap，然后取出所有的value看看是否有任何时候使得capacity负了。时间、空间复杂度和方法一一样。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution {
        public boolean carPooling(int[][] trips, int capacity) {
            if (trips == null || trips.length == 0 || trips[0].length == 0) {
                return true;
            }
            TreeMap<Integer, Integer> treeMap = new TreeMap<>();
            for (int[] trip : trips) {
                treeMap.put(trip[1], treeMap.getOrDefault(trip[1], 0) + trip[0]);
                treeMap.put(trip[2], treeMap.getOrDefault(trip[2], 0) - trip[0]);
            }
            for (int change : treeMap.values()) {
                capacity -= change;
                if (capacity < 0) {
                    return false;
                }
            }
            return true;
        }
    }

1099. two-sum-less-than-k

  • 给一个数组，求其中小于等于给定值K的最大的两个数之和。
  • 对数组拍个序，然后双指针一前一后往中间夹逼，小于K就移动下界并取这个值与现有最大值比较，否则移动上界。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution {
        public int twoSumLessThanK(int[] A, int K) {
            if (A == null || A.length == 0) {
                return -1;
            }
            Arrays.sort(A);
            int left = 0, right = A.length - 1, max = -1;
            while (left < right) {
                int sum = A[left] + A[right];
                if (sum < K) {
                    max = Math.max(sum, max);
                    left++;
                } else {
                    right--;
                }
            }
            return max;
        }
    }

1102. path-with-maximum-minimum-value

  • 给一个grid，从左上角到右下角的路径cost为所经过元素的最小值。求所有路径中的最大cost。
  • 贪心，与一般BFS的区别就是需要用到PriorityQueue并且存入坐标对应的值，每次都从pq中取相邻未访问过元素的最大值。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    class Solution {
        private int[] dir = new int[] { 0, 1, 0, -1, 0 };
        public int maximumMinimumPath(int[][] A) {
            if (A == null || A.length == 0) {
                return 0;
            }
            int rows = A.length, cols = A[0].length;
            PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);   // 从大到小
            boolean[][] visited = new boolean[rows][cols];
            pq.offer(new int[] {A[0][0], 0, 0});
            visited[0][0] = true;
            int max = A[0][0];
            while (!pq.isEmpty()) {
                int[] curr = pq.poll();
                max = Math.min(max, curr[0]);
                if (curr[1] == rows - 1 && curr[2] == cols - 1) {
                    break;
                }
                for (int i = 0; i < 4; i++) {
                    int rowNew = curr[1] + dir[i];
                    int colNew = curr[2] + dir[i + 1];
                    if (rowNew >= 0 && rowNew < rows &&
                       colNew >= 0 && colNew < cols &&
                       !visited[rowNew][colNew]) {
                        visited[rowNew][colNew] = true;
                        pq.offer(new int[] { A[rowNew][colNew], rowNew, colNew });
                    }
                }
            }
            return max;
        }
    }

1104. path-in-zigzag-labelled-binary-tree

  • 给一个「无限」的满二叉树，标号从根1开始，蛇形走位，上一层从小到大、下一层从大到小。给定一个节点，求从根到它的路径。
  • 观察规律，二叉树的标号和二次幂/对数有很大关系，给定一个节点，它所处的层数就是log2(N)，它到该层最大值的offset就对应到上一层到最小值的offset，一层层向上找直到1就行了。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution {
        public List<Integer> pathInZigZagTree(int label) {
            LinkedList<Integer> list = new LinkedList<>();
            if (label <= 0) {
                return list;
            }
            list.addFirst(label);
            while (label != 1) {
                int level = (int)(Math.log(label) / Math.log(2));
                int offset = (int)Math.pow(2, level + 1) - 1 - label;
                label = (int)(Math.pow(2, level) + offset) / 2;
                list.addFirst(label);
            }
            return list;
        }
    }

1105. filling-bookcase-shelves

  • 给一个书本厚度和高度的数组，给定书架的宽度，求将这些书按照给定顺序放上书架所需要的最小高度。
  • DP。对于每一本书只有两种情况，要么另开一行新的书架，要么沿用当前的书架。首先假设另开新的一行书架，新的这一行高度就是这本书的高度；然后在逐本书往前，尝试将他们放下来，只要宽度够就放进来，然后比较这样得到的全部最小高度和最开始假设直接单独新开一行的总高度。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution {
        public int minHeightShelves(int[][] books, int shelfWidth) {
            if (books == null || books.length == 0 || books[0].length == 0) {
                return 0;
            }
            int[] dp = new int[books.length + 1];   // dp[i]表示[0, i)部分的最小高度
            for (int i = 1; i <= books.length; i++) {
                int width = books[i - 1][0];
                int height = books[i - 1][1];
                dp[i] = dp[i - 1] + height;          // 假设新开一行，[0, i - 1)最小高度加上当前高度
                for (int j = i - 1; j > 0 && books[j - 1][0] + width <= shelfWidth; j--) {
                    height = Math.max(height, books[j - 1][1]);   // 取和前一本书的较高者
                    width += books[j - 1][0];
                    dp[i] = Math.min(dp[j - 1] + height, dp[i]);  // [0, j - 1)的最小高度加当前高度
                }
            }
            return dp[books.length];
        }
    }

1109. corporate-flight-bookings

  • 给一个int数组表示[start, end, ticketNum]，总共有n个航班，求每个航班定了多少票。
  • 直觉是嵌套循环，其实更好办的是从头遍历，只在start处加上ticketnum，在结尾的后一个slot事先减去ticketnum。最后一波流从头到尾累加即可。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution {
        public int[] corpFlightBookings(int[][] bookings, int n) {
            if (bookings == null || bookings.length == 0 || n <= 0) {
                return new int[0];
            }
            int[] ans = new int[n];
            for (int[] booking : bookings) {
                ans[booking[0] - 1] += booking[2];
                if (booking[1] < n) ans[booking[1]] -= booking[2];
            }
            for (int i = 1; i < n; i++) {
                ans[i] += ans[i - 1];
            }
            return ans;
        }
    }

1110. delete-nodes-and-return-forest

  • 给一个二叉树，其中每个节点的val都不同，在[1, 1000]之间。再给一个数组表示需要删除的节点val，返回删除这些节点之后的forest，以List<TreeNode>的形式返回。
  • 递归方法。首先将toDelete数组存入一个set方便查询。对于每一个节点，首先判断它是否需要删除，不用删除的根节点就需要加到结果列表中了。然后继续对左右孩子递归，如果当前节点需要删除，那么对应的左右孩子就可能可以作为根节点了。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    class Solution {
        public List<TreeNode> delNodes(TreeNode root, int[] toDelete) {
            List<TreeNode> ans = new ArrayList<>();
            if (toDelete == null || toDelete.length == 0) {
                ans.add(root);
                return ans;
            }
            Set<Integer> toDeleteSet = new HashSet<>();
            for (int deleteVal : toDelete) {
                toDeleteSet.add(deleteVal);
            }
            helper(root, toDeleteSet, ans, true);
            return ans;
        }
        private TreeNode helper(TreeNode root, Set<Integer> toDeleteSet, List<TreeNode> ans, boolean isRoot) {
            if (root == null) {
                return null;
            }
            boolean shouldDelete = toDeleteSet.contains(root.val);  // 不需要删除、且是根节点，则需要返回
            if (isRoot && !shouldDelete) {
                ans.add(root);
            }
            root.left = helper(root.left, toDeleteSet, ans, shouldDelete);  // 当前节点需要删除->子节点可以作为根节点
            root.right = helper(root.right, toDeleteSet, ans, shouldDelete);
            return shouldDelete ? null : root;  // 父节点需要知道子节点是否被删，如果被删就需要设成null
        }
    }

1120. maximum-average-subtree

  • 给一个二叉树，求它所有子树的最大平均值。
  • 全局变量+dfs。pass。

1122. relative-sort-array

  • 给两个数组，arr2作为排序规则，arr1按照arr2中元素出现顺序排序。pass.

1123. lowest-common-ancestor-of-deepest-leaves

  • 给一个二叉树，求最深的叶子节点的LCA(最下层公共祖先). 例如[1,2,3,4,5]最深的节点就是2。
  • 没想出来怎么做。拆分成两部分，求深度和更新公共祖先。在递归时传入当前节点和该节点深度，对该节点左右子节点继续求深度，若左右节点返回的深度都是最深深度，说明当前节点就是LCA了。但如果是当前节点自己就是最深叶子，它左右仍会返回一个不存在的下一层的深度，但是当前节点确实就是最深叶子节点的LCA了。都只用遍历一遍，因此O(N).
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Solution {
        int deepest = 0;
        TreeNode lca = null;
        public TreeNode lcaDeepestLeaves(TreeNode root) {
            getDepth(root, 0);
            return lca;
        }
        private int getDepth(TreeNode node, int currDepth) {
            deepest = Math.max(deepest, currDepth);
            if (node == null) {
                return currDepth;
            }
            int leftDepth = getDepth(node.left, currDepth + 1);
            int rightDepth = getDepth(node.right, currDepth + 1);
            if (leftDepth == deepest && rightDepth == deepest) {
                lca = node;
            }
            return Math.max(leftDepth, rightDepth);
        }
    }

1130. minimum-cost-tree-from-leaf-values

  • 给一个int数组表示一棵二叉树的叶子节点，树中每个节点只能有0或者2个孩子。从叶子结点向上，parent是两个孩子之积。求这个数组能组成的所有树中，非叶子结点之和最小值。
  • 翻一下：给一个int数组，将相邻的两个元素merge，保留较大的元素，cost是二者之积。持续将这个数组merge到只剩下一个元素吗，求最小cost。

  • 方法一：DP。dp[i][j]表示[i, j]范围内的最小cost，如果给定最终的split点，那么[start, end]区间的cost为dp[start][mid] + dp[mid + 1][end] + start~mid部分的最大元素 * mid+1~end部分的最大元素. 时间复杂度为O(N^3)，空间O(N^2).

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    class Solution {
        public int mctFromLeafValues(int[] arr) {
            if (arr == null || arr.length == 0) {
                return 0;
            }
            int[][] maxBetween = new int[arr.length][arr.length];
            for (int i = 0; i < arr.length; i++) {
                maxBetween[i][i] = arr[i];
                for (int j = i + 1; j < arr.length; j++) {
                    maxBetween[i][j] = Math.max(arr[j], maxBetween[i][j - 1]);
                }
            }
            
            int[][] dp = new int[arr.length][arr.length];
            for (int len = 1; len < arr.length; len++) {
                for (int left = 0; left < arr.length - len; left++) {
                    int right = left + len;
                    if (len == 1) {
                        dp[left][right] = arr[left] * arr[right];
                    } else {
                        dp[left][right] = Integer.MAX_VALUE;
                        for (int mid = left; mid < right; mid++) {
                            dp[left][right] = Math.min(dp[left][right], dp[left][mid] + dp[mid + 1][right] + maxBetween[left][mid] * maxBetween[mid + 1][right]);
                        }
                    }
                }
            }
            return dp[0][arr.length - 1];
        }
    }

  • 方法二：贪心。对于相邻的两个元素(a, b)，假设a <= b，merge后a就被删了，cost为a * b，因此我们要尽可能minimize b。贪心地选择尽可能选与前、后相比是最小的元素进行移除，cost就是num * min(prev, after). 利用栈维护一个单调下降的序列，一旦比栈顶大，说明栈顶应该先被消掉才能保证cost最小，在pop时需要比较次栈顶元素和待入栈元素，选择较小的乘积。需要注意最开始要在栈顶存入MAX。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution {
        public int mctFromLeafValues(int[] arr) {
            if (arr == null || arr.length == 0) {
                return 0;
            }
            ArrayDeque<Integer> stack = new ArrayDeque<>();
            stack.push(Integer.MAX_VALUE);
            int retVal = 0;
            for (int num : arr) {
                while (stack.peek() <= num) {
                    int mid = stack.pop();
                    retVal += mid * Math.min(stack.peek(), num);
                }
                stack.push(num);
            }
            while (stack.size() > 2) {
                retVal += stack.pop() * stack.peek();
            }
            return retVal;
        }
    }

1140. stone-game-ii

  • 给一个int数组表示piles of stones，两个人轮流取前0 ~ X堆，其中X = [1, 2M]，M初始化为1并随着过程更新为max(X, M)。假设A先操作，求A能取得的最大数目。
  • 递归 + memo模拟操作过程。memo[i][m]记录的是从i开始、M = m的情况。若当前i到末尾的堆恰好在[1, 2M]之间了，那就无脑全部取掉。否则就遍历1 ～ 2M的所有情况，递归交给对方取，将对方所能取的所有情况都搞出来之后，目的就是选择一个最好的X让对方能取的最少。时间复杂度方面，DP的关键是看看每个状态被访问了多少次，对于dp[i][j]，i = [0, n - 1]，j = [0, n - 1]，内层对于X的取值还需要走一波[1, 2 * M]，因此总的时间复杂度为O(N^3)（把M也当作一个变量N）。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    class Solution {
        
        public int stoneGameII(int[] piles) {
            if (piles == null || piles.length == 0) {
                return 0;
            }
            int len = piles.length;
            int[] sums = new int[len];  // 从当前取到末尾的石头数
            sums[len - 1] = piles[len - 1];
            for (int i = len - 2; i >= 0; i--) {
                sums[i] = sums[i + 1] + piles[i];
            }
            int[][] memo = new int[len][len];
            return getMaxCount(sums, memo, 0, 1);
        }
        private int getMaxCount(int[] sums, int[][] memo, int from, int M) {
            int len = sums.length;
            if (from == len) {
                return 0;
            }
            if (2 * M >= len - from) {  // 如果能够取完剩余全部堆，就直接取完
                return sums[from];
            }
            if (memo[from][M] != 0) {
                return memo[from][M];
            }
            int min = Integer.MAX_VALUE;
            for (int i = 1; i <= 2 * M; i++) {  // 逐个尝试，当前选手取1～2M堆，看对手取多少
                min = Math.min(min, getMaxCount(sums, memo, from + i, Math.max(i, M)));
            }
            memo[from][M] = sums[from] - min;   // 要想我取得最多，就等同于让对手取的在所有性中最小
            return memo[from][M];
        }
    }

1143. longest-common-subsequence

  • 给两个字符串，求二者最长的公共子序列。

  • DP。dp[i][j]表示s1取i、s2取j个字符时的最大子序列长度。若i和j处字符相等，则最长长度就是dp[i - 1][j - 1] + 1，否则就需要看s1少取一位或者s2少取一位的最长长度。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution {
        public int longestCommonSubsequence(String text1, String text2) {
            if (text1 == null || text1.length() == 0 ||
               text2 == null || text2.length() == 0) {
                return 0;
            }
            char[] chars1 = text1.toCharArray(), chars2 = text2.toCharArray();
            int len1 = chars1.length, len2 = chars2.length;
            int[][] dp = new int[len1 + 1][len2 + 1];
            for (int i = 1; i <= len1; i++) {
                for (int j = 1; j <= len2; j++) {
                    if (chars1[i - 1] == chars2[j - 1]) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    } else {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                    }
                }
            }
            return dp[len1][len2];
        }
    }

  • 优化：dp每次只用到了相邻的两行，因此可以压缩成两行的dp数组。

1145. binary-tree-coloring-game

  • 给一个各个节点都不同的二叉树，共有n个节点且n是奇数。两个玩家取节点上色，A先选节点x，B选节点后，A先对所有能到达的节点上色，然后再轮到B上色，最终比较谁上色数更多，判断B能否赢。
  • 当A确定了他的节点后，B其实只有三个选择：该节点的parent/左/右child.而且需要注意的是总共的节点数n也给出了，因此其实只需要统计A所选节点的两个孩子，一减就知道上面那条总共有多少节点了。判断B能不能赢就是看这三个选择包含的节点数是否超过n / 2.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution {
        int leftCount, rightCount, target;
        public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
            target = x;
            countNodes(root);
            return Math.max(Math.max(leftCount, rightCount), n - leftCount - rightCount - 1) > n / 2;
        }
        private int countNodes(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int left = countNodes(root.left), right = countNodes(root.right);
            if (root.val == target) {
                leftCount = left;
                rightCount = right;
            }
            return left + right + 1;
        }
    }

1146. snapshot-array

  • 实现一个带有snapshot功能的array类，在get index的时候可以提供snapId，可能根据snapId来取array中的元素。
  • 对于每一个index可以维护一个TreeMap，这样可以在log(N)的时间内取得小于等于snapId的元素。创建SnapshotArray的复杂度为O(N)，snap是O(1), set是O(logsnap调用次数), get是O(logsnap调用次数).
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    class SnapshotArray {
        private TreeMap[] array;
        private int snapId;
        public SnapshotArray(int length) {
            this.snapId = 0;
            this.array = new TreeMap[length];
            for (int i = 0; i < length; i++) {
                this.array[i] = new TreeMap<Integer, Integer>();
                this.array[i].put(this.snapId, 0);
            }
        }
        
        public void set(int index, int val) {
            if (index > this.array.length) {
                return;
            }
            this.array[index].put(this.snapId, val);
        }
        
        public int snap() {
            return this.snapId++;
        }
        
        public int get(int index, int snapId) {
            if (snapId < 0 || index < 0 || index >= this.array.length) {
                return -1;
            }
            return (int) this.array[index].floorEntry(snapId).getValue();
        }
    }

1152. analyze-user-website-visit-pattern

  • 给三个数组，分别存放用户名、时间戳和访问网址。求被不同用户访问最多的三个subsequence。
  • 首先按照timestamp排序，然后统计每个用户访问的网址，然后取每个网址尝试拆分subsequence统计数目。pass.

1153. string-transforms-into-another-string

  • 给两个只含有小写字母的字符串，判断是否能够从str1转换成str2，转换指的是将所有出现的字母替换成任意其他小写字母。
  • 需要留意的是字母的替换顺序是matter的，例如先把aabcc中的a换成c，那么之后再把ccbcc中的c换成别的需要把四个c都换掉。实际上考点就在于这个cycle必须有一个中转字母，也就是不可以出现26个字母全部出现再替换的cycle里。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    class Solution {
        public boolean canConvert(String str1, String str2) {
            if (str1 == null || str2 == null || str2.length() != str1.length()) {
                return false;
            }
            if (str1.equals(str2)) {
                return true;
            }
            Map<Character, Character> map = new HashMap<>();
            char[] chars1 = str1.toCharArray(), chars2 = str2.toCharArray();
            for (int i = 0; i < chars1.length; i++) {
                if (map.containsKey(chars1[i])) {
                    if (map.get(chars1[i]) != chars2[i]) {
                        return false;
                    }
                } else {
                    map.put(chars1[i], chars2[i]);
                }
            }
            return new HashSet<Character>(map.values()).size() < 26;
        }
    }

1154.ordinal-number-of-date

  • 给一个日期字符串，求它是该年的第几天。pass。

1155. number-of-dice-rolls-with-target-sum

  • 给一个整数d表示骰子个数、f表示最大的点数、target表示目标值，求总共有多少种投骰子的组合。例如3,3,5总共就有6种。
  • 一开始使用dfs，但是超时。既然是当前状态依赖于之前的状态，自然想到了dp。也就是每一次丢骰子的时候需要知道target减去当前骰子数值的情况下，有多少种组合，这是一种bottom-up的思路。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
        private final int MOD_VALUE = (int) 1e9 + 7;
        public int numRollsToTarget(int d, int f, int target) {
            if (d * f < target) {
                return 0;
            }
            int[][] memo = new int[d + 1][target + 1];
            memo[0][0] = 1;
            for (int i = 1; i <= d; i++) {
                for (int j = 1; j <= target; j++) {
                    for (int k = 1; k <= f && k <= j; k++) {
                        memo[i][j] = ((memo[i][j] % MOD_VALUE) + (memo[i - 1][j - k] % MOD_VALUE)) % MOD_VALUE;
                    }
                }
            }
            return memo[d][target];
        }
    }

1167. minimum-cost-to-connect-sticks

  • 给一个int数组，将两个数组融合的开销就是他们的和，求将所有元素融合成一个的最小总开销。
  • 贪心，需要尽可能晚融合较大的数。直接priorityqueue每次取头两个累加即可。pass。

1171. remove-zero-sum-consecutive-nodes-from-linked-list

  • 给一个单向链表，要求删除连续的、相加为0的子序列，返回形式仍是链表。例如[1,2,3,-1,-2,-3,-4]返回[-4]。
  • 利用累加，同时维护一个sum -> node的map。如果当前累加的结果在之前出现过，则之前出现过的位置对应节点之后的所有节点直到当前节点都要删除，同时将他们这一段累计的sum从map中删除。时间复杂度O(N)，空间O(N). 注意节点可能value=0
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    class Solution {
        public ListNode removeZeroSumSublists(ListNode head) {
            ListNode dummyHead = new ListNode(0);
            dummyHead.next = head;
            Map<Integer, ListNode> map = new HashMap<>();
            map.put(0, dummyHead);
            int sum = 0;
            while (head != null) {
                sum += head.val;
                if (map.containsKey(sum)) {
                    removeFromMap(map, map.get(sum).next, head, sum);
                    map.get(sum).next = head.next;
                } else {
                    map.put(sum, head);
                }
                head = head.next;
            }
            return dummyHead.next;
        }
        private void removeFromMap(Map<Integer, ListNode> map, ListNode start, ListNode end, int sum) {
            while (start != end) {
                sum += start.val;
                map.remove(sum);
                start = start.next;
            }
        }
    }

1177. can-make-palindrome-from-substring

  • 给一个只含有a-z的字符串，每个query给[start, end]表示节选字符串的某一段中通过重组、和最多k次任意替换能否形成一个自对称的字符串。例如dbcdb, k=1为true。

  • 方法一：利用prefixSum求在字符串某索引之前的各个字母的出现频数，这样就可以在给定[start, end]时快速求出每个字母的出现频数。这时再统计其中有多少个出现次数是奇数，就需要进行替换，再和给定的k比较即可。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
     class Solution {
        public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
            List<Boolean> retVal = new ArrayList<>();
            if (s == null || s.length() == 0 || queries == null || queries.length == 0) {
                return retVal;
            }
            int[][] prefix = new int[s.length() + 1][26];
            for (int i = 0; i < s.length(); i++) {
                prefix[i + 1] = prefix[i].clone();
                prefix[i + 1][s.charAt(i) - 'a']++;
            }
            for (int[] query : queries) {
                int sum = 0;
                for (int i = 0; i < 26; i++) {
                    sum += (prefix[query[1] + 1][i] - prefix[query[0]][i]) % 2;
                }
                retVal.add(sum / 2 <= query[2]);
            }
            return retVal;
        }
    }

  • 方法二：其实我们并不关心每个字母出现的频数，只需要知道在给定范围内每个字母的频数是奇数还是偶数，完全可以用一个bit数组作异或来判断该字母是否需要进行替换。时间&空间复杂度O(s.length + query.length).

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution {
        public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
            List<Boolean> retVal = new ArrayList<>();
            if (s == null || s.length() == 0 || queries == null || queries.length == 0) {
                return retVal;
            }
            int[] bits = new int[s.length() + 1];
            for (int i = 0; i < s.length(); i++) {
                bits[i + 1] = bits[i] ^ (1 << (s.charAt(i) - 'a'));
            }
            for (int[] query : queries) {
                retVal.add(Integer.bitCount(bits[query[1] + 1] ^ bits[query[0]]) / 2 <= query[2]);
            }
            return retVal;
        }
    }

1181. before-and-after-puzzle

  • 给一个只含有小写字母和空格的字符串数组，如果两个string的首word和最后一个word相同，则可以拼接成新的字符串。求所有可能的拼接，按字典序返回。
  • 不难，直接维护一个首word -> string和lastWord -> string的map即可。事实上并不需要head和tail，只需要head。而且map中可以存放list of indexes而不是字符串本身。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    class Solution {
        public List<String> beforeAndAfterPuzzles(String[] phrases) {
            if (phrases == null || phrases.length == 0) {
                return new ArrayList<>();
            }
            Map<String, Set<String>> head = new HashMap<>(), tail = new HashMap<>();
            Map<String, Integer> count = new HashMap<>();
            for (String phrase : phrases) {
                String[] splitted = phrase.split(" ");
                head.computeIfAbsent(splitted[0], s -> new HashSet<>()).add(phrase);
                tail.computeIfAbsent(splitted[splitted.length - 1], s -> new HashSet<>()).add(phrase);
                count.put(phrase, count.getOrDefault(phrase, 0) + 1);
            }
            
            TreeSet<String> treeSet = new TreeSet<>();
            for (String lastWord : tail.keySet()) {
                if (!head.containsKey(lastWord)) {
                    continue;
                }
                for (String phraseHead : head.get(lastWord)) {
                    for (String phraseTail : tail.get(lastWord)) {
                        if (!phraseHead.equals(phraseTail) || count.get(phraseHead) > 1) {
                            treeSet.add(phraseTail + phraseHead.substring(lastWord.length()));
                        }
                    }
                }
            }
            return new ArrayList<>(treeSet);
        }
    }

1185. day-of-the-week

  • 给年月日，求该日期是星期几。所给日期在[1971, 2100]，且一定是valid的。
  • 暴力做法，利用01/01/1971是星期五，算相差多少天即可。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    class Solution {
        private final String[] WEEK_DAY = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
        private final int DAYS_IN_YEAR = 365;
        private final int[] DAYS_IN_MONTH = new int[] {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        private final int START_YEAR = 1971;
        public String dayOfTheWeek(int day, int month, int year) {
            int count = 0;
            for (int i = START_YEAR; i < year; i++) {
                count += DAYS_IN_YEAR;
                if (isLeapYear(i)) {
                    count++;
                }
            }
            
            for (int i = 0; i < month - 1; i++) {
                count += DAYS_IN_MONTH[i];
                if (i == 1 && isLeapYear(year)) {
                    count++;
                }
            }
            
            count += (day - 1);
            return WEEK_DAY[(count + 5) % 7];
        }
        private boolean isLeapYear(int year) {
            if (year % 100 == 0) {
                return year % 400 == 0;
            } else {
                return year % 4 == 0;
            }
        }
    }

1186.maximum-subarray-sum-with-one-deletion/

  • 给一个int数组，长度在[1, 10^5]，每个值在[-10^4, 10^4]。任意取其中非空的连续子数组，然后至多在上面删除一个元素，使得得到的和最大。求最大和。
  • 类似于DP。对于每一个元素，只有两种可能，要么删、要么保留。但是走到当前元素的时候并不知道之前是否已经执行过一次删除了，因此就需要维护两个dp变量，一个dpExclude表示之前已经执行过删除的连续子数组最大和，一个是尚未执行删除的连续子数组最大和，这时在当前元素就可以选择删除（直接取dpInclude）或者保留当前元素。保留当前元素又有多种可能，一种是继续前面删除过的dpExclude往里加，一种是继续往dpInclude里加，最后一种是直接以当前元素为起始。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution {
        public int maximumSum(int[] arr) {
            if (arr == null || arr.length == 0) {
                return 0;
            }
            int dpInclude = arr[0], dpExclude = 0, maxSum = arr[0];
            for (int i = 1; i < arr.length; i++) {  // 从第2个元素开始取，此时dpExclude表示不取第1个元素
                dpExclude = Math.max(dpInclude, dpExclude + arr[i]);   // 不取当前元素或者不取之前的某个元素
                dpInclude = Math.max(dpInclude + arr[i], arr[i]);      // 继续连续取元素或者作为新的起始 
                maxSum = Math.max(maxSum, Math.max(dpExclude, dpInclude));
            }
            return maxSum;
        }
    }

1187. make-array-strictly-increasing

  • 给两个int数组arr1和arr2，尝试从arr2中取元素替换到arr1中使得arr1严格递增。最少的替换数，可能是0.
  • DP。arr1中每一个位置可能有多种值，greedy的想法一方面是要让这个值尽可能小（这样后续的元素要保证递增就容易些）、另一方面又要兼顾总共的替换次数最少。因此考虑将arr2中元素全部存入TreeSet，这样就可以用higher来取恰好更大的最小可替换值。dp[i][j]表示经过至多i次替换后arr1[j]的最小值。时间复杂度O(logN * N * N)。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    class Solution { 
        public int makeArrayIncreasing(int[] arr1, int[] arr2) {
            if (arr1 == null || arr2 == null) {
                return 0;
            }
            TreeSet<Integer> treeSet = new TreeSet<>();
            for (int num : arr2) {
                treeSet.add(num);
            }
            int[][] dp = new int[arr1.length + 1][arr1.length + 1];
            for (int[] row : dp) {
                Arrays.fill(row, Integer.MAX_VALUE);
            }
            dp[0][0] = Integer.MIN_VALUE;
            
            for (int j = 1; j <= arr1.length; j++) {    // 总共j个元素
                for (int i = 0; i <= j; i++) {          // dp[i][j]表示index=j处、至多替换i次后的最小可能值
                    if (arr1[j - 1] > dp[i][j - 1]) {   // 当前元素已经比之前的元素大了，暂时取之
                        dp[i][j] = arr1[j - 1];
                    }
                    if (i > 0 && treeSet.higher(dp[i - 1][j - 1]) != null) {    // 尝试替换成treeSet中比前一个位置、少一次替换的值大的最小值
                        dp[i][j] = Math.min(dp[i][j], treeSet.higher(dp[i - 1][j - 1]));
                    }
                    if (j == dp.length - 1 && dp[i][j] != Integer.MAX_VALUE) {
                        return i;
                    }
                }
            }
            return -1;
        }
    }

1190. reverse-substrings-between-each-pair-of-parentheses

  • 给一个只含有小写字母和小括号的字符串，返回将小括号包围的部分反转之后并舍弃小括号的字符串。如(ed(et(oc))el)返回leetcode。

  • 方法一：Stack + StringBuilder.栈中存放当前的结果，若碰到左括号，则新建一个空的字符串存入栈，持续拼接到栈顶字符串；若碰到右括号，则将栈顶弹出并reverse，再拼入栈顶。由于需要再循环内部调用reverse，时间复杂度为O(N^2)，空间复杂度为O(N).

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    class Solution {
        public String reverseParentheses(String s) {
            if (s == null || s.length() == 0) {
                return s;
            }
            StringBuilder sb = new StringBuilder();
            Stack<StringBuilder> stack = new Stack<>();
            stack.push(new StringBuilder());
            char[] chars = s.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                if (chars[i] == '(') {
                    stack.push(new StringBuilder());
                } else if (chars[i] == ')') {
                    StringBuilder last = stack.pop();
                    stack.peek().append(last.reverse());
                } else {
                    stack.peek().append(chars[i]);
                }
            }
            return stack.pop().toString();
        }
    }

  • 方法二：逆天的O(N)做法。从前往后遍历，遇见(就从对应的)出来向左继续遍历，碰到)则到对应的(出来向右继续遍历。不过需要先构建pair数组方便找到对应的左右括号。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    class Solution {
        public String reverseParentheses(String s) {
            if (s == null || s.length() == 0) {
                return s;
            }
            int len = s.length();
            Stack<Integer> stack = new Stack<>();
            int[] pair = new int[len];
            char[] chars = s.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                if (chars[i] == '(') {
                    stack.push(i);
                } else if (chars[i] == ')') {
                    int leftIndex = stack.pop();
                    pair[leftIndex] = i;
                    pair[i] = leftIndex;
                }
            }
            
            StringBuilder sb = new StringBuilder();
            for (int i = 0, d = 1; i < len; i += d) {
                if (chars[i] == '(' || chars[i] == ')') {
                    i = pair[i];
                    d *= -1;
                } else {
                    sb.append(chars[i]);
                }
            }
            return sb.toString();
        }
    }

1192. critical-connections-in-a-network

  • 给一个数字n表示有多少服务器，给一个服务器之间edge的list。求所有critical edges，即去掉该edge就会使得至少一个服务器不可达。
  • 特别有意思的题。关键是观察到critical edge和环的关系：连接两个环之间的edge就是不可删除的edge，每个节点本身都可以看作一个环。从0号节点开始对邻居节点进行DFS，遍历到时就赋予一个不断++的时间timestamp，从A点到B点如果只有一个路径，也就是先到的A才能到B，那么他们的timestamp关系一定是增加的。对于除了parent的所有邻接节点依次标记timestamp，最后当前节点取所有邻接节点（除了parent）的timestamp最小值。如果对邻接节点进行DFS后，最开始赋予当前节点的timestamp比邻接点依然小，说明通过当前节点才能到达该邻接点，说明当前节点是环的出口，因此当前节点到邻接节点就是一个critcal edge了。时间复杂度我觉得是O(edge)，因为每个边都只会被dfs一次。
  • 下面这个解法还有一丝优化就是直接用timestamps的值来取代visited，如果timestamp是0（假设初始值为1）则说明该节点没有被访问过。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    class Solution {
        private int timestamp = 0;
        public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
            List<List<Integer>> ans = new ArrayList<>();
            if (connections == null || connections.size() == 0) {
                return ans;
            }
            
            List<Integer>[] graph = new ArrayList[n];
            for (int i = 0; i < n; i++) {
                graph[i] = new ArrayList<>();
            }
            
            for (List<Integer> connection : connections) {
                graph[connection.get(0)].add(connection.get(1));
                graph[connection.get(1)].add(connection.get(0));
            }
            
            dfs(graph, -1, 0, new boolean[n], new int[n], ans);
            return ans;
        }
        private void dfs(List<Integer>[] graph, int fromNode, int currNode, boolean[] visited, int[] timestamps, List<List<Integer>> ans) {
            visited[currNode] = true;
            timestamps[currNode] = timestamp++;
            int currTime = timestamps[currNode];
            
            for (int neighborNode : graph[currNode]) {
                if (neighborNode == fromNode) {
                    continue;
                }
                if (!visited[neighborNode]) {
                    dfs(graph, currNode, neighborNode, visited, timestamps, ans);
                }
                timestamps[currNode] = Math.min(timestamps[currNode], timestamps[neighborNode]);
                if (currTime < timestamps[neighborNode]) {
                    ans.add(Arrays.asList(currNode, neighborNode));
                }
            }
        }
    }

1197. minimum-knight-moves

  • 在一个无限大的棋盘上，马从(0, 0)开始走，给终点(x, y)，求最少需要多少步能走到，假设一定存在。

  • 经典BFS。需要将坐标encode成方便比较的形式。需要注意的是BFS需要在第一次见到该坐标的时候就要放入visited集合，因为可能存在重复的情况。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    class Solution {
        private static final int[] dir = {2, 1, 2, -1, 2, -1, -2, 1, 2}; // 8 possible moves.
        public int minKnightMoves(int x, int y) {
            x = Math.abs(x);
            y = Math.abs(y);    // 利用对称性
            String target = buildString(x, y);
            Queue<String> q = new LinkedList<>();
            String start = buildString(0, 0);
            q.offer(start);
            int steps = 0;
            Set<String> visited = new HashSet<>();
            visited.add(start);
            while (!q.isEmpty()) {
                int size = q.size();
                while (size-- > 0) {
                    String curr = q.poll();
                    if (curr.equals(target)) {
                        return steps;
                    }
                    int index = curr.indexOf(",");
                    for (int i = 0; i < 8; i++) {
                        int nextX = Integer.valueOf(curr.substring(0, index)) + dir[i];
                        int nextY = Integer.valueOf(curr.substring(index + 1)) + dir[i + 1];
                        String next = buildString(nextX, nextY);
                        if (nextX >= -2 && nextY >= -2 && visited.add(next)) {
                            q.offer(next);
                        }
                    }
                }
                steps++;
            }
            return -1;
        }
        private String buildString(int x, int y) {
            return new StringBuilder().append(x).append(",").append(y).toString();
        }
    }

  • 方法二：数学的方法-formula.)，虽然效率爆炸，但是暂时不想管这个。。。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    class Solution {
        public int minKnightMoves(int x, int y) {
            // Symmetry for axes
            x = Math.abs(x);
            y = Math.abs(y);
            // Symmetry for diagonal
            if (x < y) {
                int temp = x;
                x = y;
                y = temp;
            }
            if (x == 1 && y == 0) {
                return 3;
            }
            if (x == 2 && y == 2) {
                return 4;
            }
            int delta = x - y;
            if (y > delta) {
                return (int) (delta - 2 * Math.floor((float) (delta - y) / 3));
            } else {
                return (int) (delta - 2 * Math.floor((delta - y) / 4));
            }
        }
    }