Note for LeetCode in Java (1200 ~ 1600)

Posted on Edited on In Disqus:

刷题。祝我好运。

1202. smallest-string-with-swaps

  • 给一个字符串和一个list of pairs，每个pair表示这两个index的字符可以互换。求经过无限次互换后可以得到的最小的字符串。
  • 并查集+priorityqueue.首先遍历pairs构造并查集，然后对于每一个索引构建index -> 字符pq的map，最后走一波index取pq中的字符拼接即可。理论上并查集是O(N)，pq是O(NlogN)，因此总体时间复杂度是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
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[] parent;
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        if (s == null || s.length() == 0) {
            return null;
        }
        parent = new int[s.length()];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }
        
        for (List<Integer> pair : pairs) {
            union(pair.get(0), pair.get(1));
        }
        
        Map<Integer, PriorityQueue<Character>> map = new HashMap<>();
        char[] sChar = s.toCharArray();
        for (int i = 0; i < sChar.length; i++) {
            int root = find(i);
            map.putIfAbsent(root, new PriorityQueue<>());
            map.get(root).offer(sChar[i]);
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < sChar.length; i++) {
            sb.append(map.get(find(i)).poll());
        }
        return sb.toString();
    }
    private int find(int index) {
        while (parent[index] != index) {
            parent[index] = parent[parent[index]];
            index = parent[index];
        }
        return index;
    }
    private void union(int a, int b) {
        int aParent = find(a);
        int bParent = find(b);
        if (aParent < bParent) {
            parent[bParent] = aParent;
        } else {
            parent[aParent] = bParent;
        }
    }
}

1209. remove-all-adjacent-duplicates-in-string-ii

  • 给一个字符串数组，和一个整数k，将字符串中相邻的连续k个相同字母删除，返回完成所有删除后的剩余字符串。
  • 方法一：用stack存放字符和对应的计数，如果新加入的字符和栈顶字符相同，则累计计数。当达到k值时就将stringbuilder往回删即可。时间复杂度O(N)，因为每个字符只需要遍历一次，空间复杂度为O(N)，最坏情况输入字符串每个字符都要入栈。当然其实不强求one-pass的话，可以将sb赋值等到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
class Solution {
    class CharCount {
        char c;
        int count;
        public CharCount(char c, int count) {
            this.c = c;
            this.count = count;
        }
    }
    public String removeDuplicates(String s, int k) {
        if (s == null || s.length() == 0) {
            return s;
        }
        Stack<CharCount> stack = new Stack<>();
        char[] chars = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < chars.length; i++) {
            if (!stack.isEmpty() && chars[i] == stack.peek().c) {
                stack.peek().count++;
            } else {
                stack.push(new CharCount(chars[i], 1));
            }
            sb.append(chars[i]);
            if (stack.peek().count == k) {
                sb.setLength(sb.length() - k);
                stack.pop();
            }
        }
        return sb.toString();
    }
}
  • 方法二：双指针+计数数组。右指针不断往前遍历字符串，左指针用右指针的字符覆盖后，根据前一位字符来确定当前位置的计数，若字符相同则是前一位计数+1，否则重新从1开始计。当计数为k时，左指针就需要往回缩k位，相当于把这几个字符都省略掉了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public String removeDuplicates(String s, int k) {
        if (s == null || s.length() == 0) {
            return s;
        }
        char[] chars = s.toCharArray();
        int len = chars.length, left = 0, right = 0;
        int[] count = new int[len];
        while (right < len) {
            chars[left] = chars[right];
            count[left] = (left > 0 && chars[left - 1] == chars[left]) ? count[left - 1] + 1 : 1;
            if (count[left] == k) {
                left -= k;
            }
            left++;
            right++;
        }
        return new String(chars, 0, left);
    }
}

1213. intersection-of-three-sorted-arrays

  • 给三个严格升序的int数组，求三者的共同元素。
  • 直接循环搞定。pass.

1214. two-sum-bsts

  • 给两个BST和一个target值，判断两个BST中是否分别存在两个节点之和为给定target。
  • 事实上就是遍历二叉树和two sum两个题的结合。遍历BST通常用in-order，这样可以保证元素大小顺序。可以用stack方式做iterative in-order traverse，将遍历的元素用target减了之后存入set. 之后再对另一个BST遍历，遇见set中存在的元素就知道一定存在了。时间O(N1 + N2)，空间O(N1 + max(N1, N2)).
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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        Set<Integer> set = new HashSet<>();

        while (!stack.isEmpty() || root1 != null) {
            while (root1 != null) {
                stack.push(root1);
                root1 = root1.left;
            }
            root1 = stack.pop();
            set.add(target - root1.val);
            root1 = root1.right;
        }

        while (!stack.isEmpty() || root2 != null) {
            while (root2 != null) {
                stack.push(root2);
                root2 = root2.left;
            }
            root2 = stack.pop();
            if (set.contains(root2.val)) {
                return true;
            }
            root2 = root2.right;
        }

        return false;
    }
}

1216. valid-palindrome-iii

  • 给一个字符串和一个整数k，判断能否通过删除至多k个字符使得字符串自对称。
  • 和516几乎一样，本质上就是求最长的自对称的子序列，然后看看加上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 boolean isValidPalindrome(String s, int k) {
        if (s == null || s.length() == 0) {
            return true;
        }
        char[] chars = s.toCharArray();
        int len = chars.length;
        int[][] dp = new int[len][len];
        for (int from = len - 1; from >= 0; from--) {
            dp[from][from] = 1;
            for (int to = from + 1; to < len; to++) {
                if (chars[from] == chars[to]) {
                    dp[from][to] = dp[from + 1][to - 1] + 2;
                } else {
                    dp[from][to] = Math.max(dp[from + 1][to], dp[from][to - 1]);
                }
            }
        }
        return dp[0][len - 1] + k >= len;
    }
}

1218. longest-arithmetic-subsequence-of-given-difference

  • 给一个整数数组，再给一个diff作为子序列前后项的差值，求最长等差数列的长度。
  • 对于当前元素需要知道前面的以diff为差值的元素的最长长度。因此考虑维护一个Map，key为数组元素，value为以该元素结尾的最长长度。每次更新时就向前找差值为diff的元素的长度，如果不存在则以自己为新的开始。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        Map<Integer, Integer> value2Len = new HashMap<>();
        for (int num : arr) {
            value2Len.put(num, Math.max(value2Len.getOrDefault(num, 0), value2Len.getOrDefault(num - difference, 0) + 1));
        }
        int maxLen = 1;
        for (int len : value2Len.values()) {
            maxLen = Math.max(len, maxLen);
        }
        return maxLen;
    }
}

1219. path-with-maximum-gold

  • 给一个grid表示金矿，求从其中任何一个点出发、不经过0且不重复走cell的情况下能拿到的最多的金矿。
  • DFS暴力解法，到达一个cell后收集金子，然后将当前cell标记为已访问，再尝试上下左右四个方向。时间复杂度感觉是O(4 ^ (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
class Solution {
    public int getMaximumGold(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int max = 0;
        for (int row = 0; row < grid.length; row++) {
            for (int col = 0; col < grid[0].length; col++) {
                max = Math.max(max, dfs(grid, row, col, 0));
            }
        }
        return max;
    }
    private final int[] dir = {0, 1, 0, -1, 0};
    private int dfs(int[][] grid, int row, int col, int sum) {
        if (isNotValid(grid, row, col) || grid[row][col] <= 0) {
            return sum;
        }
        sum += grid[row][col];
        grid[row][col] = -grid[row][col];
        int max = 0;
        for (int i = 0; i < 4; i++) {
            max = Math.max(max, dfs(grid, row + dir[i], col + dir[i + 1], sum));
        }
        grid[row][col] = -grid[row][col];
        return Math.max(max, sum);
    }
    private boolean isNotValid(int[][] grid, int row, int col) {
        return row < 0 || row >= grid.length || col < 0 || col >= grid[0].length;
    }
}

1220. count-vowels-permutation

  • 给一个整数n表示string的长度，求最多有多少种元音字母的排列，将结果膜1e9。元音字母排列需要满足：
    • Each character is a lower case vowel (‘a’, ‘e’, ‘i’, ‘o’, ‘u’)
    • Each vowel ‘a’ may only be followed by an ‘e’.
    • Each vowel ‘e’ may only be followed by an ‘a’ or an ‘i’.
    • Each vowel ‘i’ may not be followed by another ‘i’.
    • Each vowel ‘o’ may only be followed by an ‘i’ or a ‘u’.
    • Each vowel ‘u’ may only be followed by an ‘a’.
  • 给定了当前字符串的最后一个字母，这个字符串就确定了。因此只需要在每次循环中统计后续的字母出现次数即可，有点像木桶排序.
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 {
    private int MOD = (int)1e9 + 7;
    public int countVowelPermutation(int n) {
        if (n <= 0) {
            return 0;
        }
        List<List<Integer>> nextIndexLists = getNext();
        int[] count = new int[5];
        Arrays.fill(count, 1);
        while (n-- > 1) {
            int[] temp = new int[5];
            for (int i = 0; i < 5; i++) {
                List<Integer> nextIndexList = nextIndexLists.get(i);
                for (int nextIndex : nextIndexList) {
                    temp[nextIndex] = (count[i] + temp[nextIndex]) % MOD;
                }
            }
            count = temp;
        }
        return getSum(count);
    }
    private int getSum(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum = (sum + num) % MOD;
        }
        return sum;
    }
    private List<List<Integer>> getNext() {
        List<List<Integer>> retVal = new ArrayList<>();
        for (int i = 0; i < 5; i++) {
            retVal.add(new ArrayList<>());
        }
        // 0 a -> e
        retVal.get(0).add(1);
        
        // 1 e -> a, i
        retVal.get(1).add(0);
        retVal.get(1).add(2);
        
        // 2 i -> a, e, o, u
        retVal.get(2).add(0);
        retVal.get(2).add(1);
        retVal.get(2).add(3);
        retVal.get(2).add(4);
        
        // 3 o -> i, u
        retVal.get(3).add(2);
        retVal.get(3).add(4);
        
        // 4 u -> a
        retVal.get(4).add(0);
        
        return retVal;
    }
}

1229. meeting-scheduler

  • 给两个人的available slots数组，求最早的满足duration长度的meeting时间。
  • 方法一：排序后贪心找最早的overlap满足duration要求的部分，时间复杂度O(MlogM + NlogN)（双指针遍历是O(M + N)），空间复杂度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
class Solution {
    public List<Integer> minAvailableDuration(int[][] slots1, int[][] slots2, int duration) {
        if (slots1 == null || slots2 == null) {
            return new ArrayList<>();
        }
        Arrays.sort(slots1, (a, b) -> a[0] - b[0]);
        Arrays.sort(slots2, (a, b) -> a[0] - b[0]);
        
        int index1 = 0, index2 = 0, overlap = 0;
        while (index1 < slots1.length && index2 < slots2.length) {
            int left = Math.max(slots1[index1][0], slots2[index2][0]);
            int right = Math.min(slots1[index1][1], slots2[index2][1]);
            overlap = right - left;
            if (overlap >= duration) {
                return new ArrayList<Integer>(Arrays.asList(left, left + duration));
            }
            
            // 挪动结束更早的interval
            if (slots1[index1][1] <= slots2[index2][1]) {
                index1++;
            } else {
                index2++;
            }
        }
        return new ArrayList<>();
    }
}
  • 方法二：使用PriorityQueue，将两个人所有长度多于duration的时间段都入堆，然后每次取相邻的两个时间段求overlap。构建Heap的时间复杂度为O((M+N)log(M+N))，取每一个元素时间复杂度为O(log(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
class Solution {
    public List<Integer> minAvailableDuration(int[][] slots1, int[][] slots2, int duration) {
        if (slots1 == null || slots2 == null) {
            return new ArrayList<>();
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (int[] slot : slots1) {
            if (slot[1] - slot[0] >= duration) {
                pq.offer(slot);
            }
        }
        
        for (int[] slot : slots2) {
            if (slot[1] - slot[0] >= duration) {
                pq.offer(slot);
            }
        }
        
        while (pq.size() >= 2) {
            int[] left = pq.poll();
            int[] right = pq.peek();
            if (left[1] - right[0] >= duration) {
                return new ArrayList<>(Arrays.asList(right[0], right[0] + duration));
            }
        }
        
        return new ArrayList<>();
    }
}

1230. toss-strange-coins

  • 给一个数组，表示这堆硬币正面朝上的概率。给一个target，求每个硬币丢一次，总共恰好有target个硬币正面朝上的概率。
  • DP. dp[i][j]表示有i个正面朝上、囊括第j个硬币时的总概率。状态转移方程是dp[i][j] = dp[i][j - 1] * 第j个硬币的反面概率 + dp[i - 1][j - 1] * 第j个的正面概率。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public double probabilityOfHeads(double[] prob, int target) {
        if (prob == null || prob.length == 0) {
            return 0.0;
        }
        double[][] dp = new double[target + 1][prob.length];
        dp[0][0] = 1.0 - prob[0];
        if (dp.length > 1) {
            dp[1][0] = prob[0];
        }
        for (int i = 0; i <= target; i++) {
            for (int j = 1; j < prob.length; j++) {
                dp[i][j] = dp[i][j - 1] * (1 - prob[j]) + (i > 0 ? dp[i - 1][j - 1] * prob[j] : 0);
            }
        }
        return dp[target][prob.length - 1];
    }
}

1232. check-if-it-is-a-straight-line

  • 给一堆点，判断是否在一条直线上。直接用斜率搞.

1233. remove-sub-folders-from-the-filesystem

  • 给一堆文件目录的string数组，筛掉子文件夹，只保留所有根目录。例如/a, /a/b, /b/e就只保留/a, /b/e.
  • 先对数组按照长度排个序，然后用内置的startsWith就能知道后续的目录是否在之前出现过。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<String> removeSubfolders(String[] folder) {
    Arrays.sort(folder);
    int base = 0;
    int curr = 1;
    List<String> result = new ArrayList<>(folder.length);
    result.add(folder[0]);
    while (curr < folder.length) {
        if (!folder[curr].startsWith(folder[base])) {
            result.add(folder[curr]);
            base = curr;
        }
        curr++;
    }
    return result;
}

1234. replace-the-substring-for-balanced-string

  • 给一个只包含QWER的、长度是4的倍数的字符串，求需要替换的最短长度的子字符串使得替换后可以让QWER四个字母出现的频次相同。
  • 双指针/滑动窗口的思想，先统计每个字符出现的频数存入count数组。需要被替换的字符一定是频数超过len / 4的。右指针挪动时从当前字符的频数减1，然后循环判断当前是否符合所有字符频数都小于等于len / 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
41
42
class Solution {
    public int balancedString(String s) {
        if (s == null || s.length() == 0 || s.length() % 4 != 0) {
            return 0;
        }
        char[] sChar = s.toCharArray();
        int[] QWERCount = new int[] {0, 0, 0, 0};
        for (int i = 0; i < sChar.length; i++) {
            doCount(sChar[i], QWERCount, 1);
        }
        int target = sChar.length / 4;
        if (QWERCount[0] == target && QWERCount[1] == target && QWERCount[2] == target && QWERCount[3] == target) {
            return 0;
        }

        int left = 0, right = 0, minLen = sChar.length;
        while (right < sChar.length) {
            doCount(sChar[right++], QWERCount, -1);
            while (left < right && QWERCount[0] <= target && QWERCount[1] <= target && QWERCount[2] <= target && QWERCount[3] <= target) {
                minLen = Math.min(minLen, right - left);
                doCount(sChar[left++], QWERCount, 1);
            }
        }
        return minLen;
    }
    private void doCount(char c, int[] QWERCount, int inc) {
        switch(c) {
            case 'Q':
                QWERCount[0] += inc;
                break;
            case 'W':
                QWERCount[1] += inc;
                break;
            case 'E':
                QWERCount[2] += inc;
                break;
            case 'R':
                QWERCount[3] += inc;
                break;
        }
    }
}

1239. maximum-length-of-a-concatenated-string-with-unique-characters

  • 给一个string数组，其中不包含重复字符的可以无限拼接，求所能拼接的最长长度。其中字符串只包含小写字母。
  • 想到了bitMask，但是没有想到如何高效地计算长度。事实上用了bitmask之后，1的个数就是不同字母的个数，也就是长度了。对于每个字符串，需要和之前所有的有效bit进行拼接尝试，如果可以拼接，就相应地更新最长长度。时间复杂度为O(2^arr.size)，因为需要在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
27
28
29
30
class Solution {
    public int maxLength(List<String> arr) {
        if (arr == null || arr.size() == 0) {
            return 0;
        }
        List<Integer> dp = new ArrayList<>();
        dp.add(0);
        int retVal = 0;
        for (String s : arr) {
            int bit = 0, duplicate = 0;
            for (char c : s.toCharArray()) {
                int curr = (1 << (c - 'a'));
                duplicate |= (bit & curr);  // 如果自身都有重复了，不可用于后续拼接
                bit |= curr;
            }
            if (duplicate != 0) {
                continue;
            }
            for (int i = dp.size() - 1; i >= 0; i--) {  // 注意不能用foreach，因为循环中要add
                if ((dp.get(i) & bit) != 0) {
                    continue;
                }
                int newBit = (bit | dp.get(i));
                dp.add(newBit);
                retVal = Math.max(retVal, Integer.bitCount(newBit));
            }
        }
        return retVal;
    }
}

1244. design-a-leaderboard

  • 实现leaderboard的addScore, topK, reset函数，按照playerId更新/重置分数，随时取topK分数总和（不关心具体是谁topK）。
  • 方法一：维护一个Map存放ID->score的映射，然后用TreeMap结构倒序存放每个score出现的次数方便取topK的和。时间复杂度，对于addScore是O(logN)（更新TreeMap里的score），对于reset也是O(logN)，对于topK是O(K)（只需要遍历TreeMap的前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
class Leaderboard {
    Map<Integer, Integer> idScoreMap;
    TreeMap<Integer, Integer> scoreCountMap;
    public Leaderboard() {
        idScoreMap = new HashMap<>();
        scoreCountMap = new TreeMap<>(Collections.reverseOrder());
    }
    
    public void addScore(int playerId, int score) {
        if (idScoreMap.containsKey(playerId)) {
            int currScore = idScoreMap.get(playerId);
            if (scoreCountMap.containsKey(currScore)) {
                scoreCountMap.put(currScore, scoreCountMap.get(currScore) - 1);
                if (scoreCountMap.get(currScore) == 0) {
                    scoreCountMap.remove(currScore);
                }
            }
            
            int newScore = currScore + score;
            idScoreMap.put(playerId, newScore);
            scoreCountMap.put(newScore, scoreCountMap.getOrDefault(newScore, 0) + 1);
        } else {
            idScoreMap.put(playerId, score);
            scoreCountMap.put(score, scoreCountMap.getOrDefault(score, 0) + 1);
        }
    }

    public int top(int K) {
        int sum = 0, count = 0;
        for (Map.Entry<Integer, Integer> entry : scoreCountMap.entrySet()) {
            if (K > entry.getValue() + count) {
                sum += entry.getKey() * entry.getValue();
                count += entry.getValue();
            } else {
                sum += entry.getKey() * (K - count);
                break;
            }
        }
        return sum;
    }
    
    public void reset(int playerId) {
        int score = idScoreMap.get(playerId);
        if (scoreCountMap.get(score) == 1) {
            scoreCountMap.remove(score);
        } else {
            scoreCountMap.put(score, scoreCountMap.get(score) - 1);
        }
        idScoreMap.remove(playerId);
    }
}
  • 方法二：只维护一个id->score的map，在topK的时候用PriorityQueue做topK操作，时间复杂度为O(K) + O(NlogK)（O(K)为最初K个元素放入堆，对于剩下的N-K个元素，每次入堆都需要加入新元素和弹出最小元素，每个操作都是O(logK)）。
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 Leaderboard {
    Map<Integer, Integer> idScoreMap;
    public Leaderboard() {
        idScoreMap = new HashMap<>();
    }
    
    public void addScore(int playerId, int score) {
        idScoreMap.put(playerId, idScoreMap.getOrDefault(playerId, 0) + score);
    }

    public int top(int K) {
        PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());
        
        for (Map.Entry<Integer, Integer> entry : idScoreMap.entrySet()) {
            pq.offer(entry);
            if (pq.size() > K) {        // 注意必须加入新元素之后再尝试poll
                pq.poll();
            }
        }
        
        int sum = 0;
        Iterator it = pq.iterator();
        while (it.hasNext()) {
            sum += ((Map.Entry<Integer, Integer>)it.next()).getValue();
        }
        return sum;
    }
    
    public void reset(int playerId) {
        idScoreMap.remove(playerId);
    }
}

1245. tree-diameter

  • 给一个无向树的所有edges，其中节点标号为[0, edges.length + 1]，diameter指的是从一个节点到另一个节点的最长的经过的edge数量。求这个树的diameter。
  • 首先对edges构建图，用List存储即可。然后从0出发，对于当前节点的所有临接点求depth（除了previous节点防止无限递归），维护所有邻接点中最大的两个depth，这个sum的最大值就是diameter了。返回的是临界点中最大depth + 1，因为preivous节点到当前节点也需要一个edge。时间、空间复杂度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
31
32
33
34
35
36
37
38
39
40
class Solution {
    private int diameter = 0;
    public int treeDiameter(int[][] edges) {
        if (edges == null || edges.length == 0) {
            return 0;
        }
        List<Integer>[] graph = getGraph(edges);
        getDepth(-1, 0, graph);
        return diameter;
    }
    private List<Integer>[] getGraph(int[][] edges) {
        int n = edges.length;
        List<Integer>[] graph = new List[n + 1];
        for (int i = 0; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }
        return graph;
    }
    private int getDepth(int prev, int curr, List<Integer>[] graph) {
        int max1 = 0, max2 = 0;
        for (int neighbor : graph[curr]) {
            if (neighbor == prev) {
                continue;
            }
            int depth = getDepth(curr, neighbor, graph);
            if (depth >= max1) {
                max2 = max1;
                max1 = depth;
            } else if (depth > max2) {
                max2 = depth;
            }
        }
        diameter = Math.max(diameter, max1 + max2);
        return max1 + 1;
    }
}

1247. minimum-swaps-to-make-strings-equal

  • 给两个只含有x和y的字符串，允许两个字符串之间任何两个字符交换，求至少多少次交换可以让两个字符串相同。
  • 类似于贪心的思路，x-x和y-y不动，只针对x-y和y-x进行交换。x-y和y-x内部首先进行“交叉”交换后，剩下的就是内部两两交换了。
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 minimumSwap(String s1, String s2) {
        if (s1 == null || s2 == null || s1.length() != s2.length() || s1.equals(s2)) {
            return 0;
        }
        char[] s1Char = s1.toCharArray(), s2Char = s2.toCharArray();
        int xyCount = 0, yxCount = 0;
        for (int i = 0; i < s1Char.length; i++) {
            if (s1Char[i] == 'x' && s2Char[i] == 'y') {
                xyCount++;
            } else if (s1Char[i] == 'y' && s2Char[i] == 'x') {
                yxCount++;
            }
        }
        
        if ((xyCount + yxCount) % 2 != 0) {
            return -1;
        }
        int ans = 0;
        ans += (xyCount / 2);
        ans += (yxCount / 2);
        ans += (xyCount % 2 + yxCount % 2);
        return ans;
    }
}

1248. count-number-of-nice-subarrays

  • 给一个int数组，求恰好有k个奇数的sub-array个数。
  • 第一想法就是滑动窗口，但是正向解并不容易，因此考虑如何exclude，转换为「至多k个奇数的sub-array个数」减去「至多k - 1个奇数的sub-array个数」。左指针固定不动，右指针若碰到奇数就计数减1，此时右指针往回直到左指针之间的sub-array都是「至多k个奇数」。当计数为负时，就需要挪动左指针，直到计数非负。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k == 0 || k > nums.length) {
            return 0;
        }
        return atMost(nums, k) - atMost(nums, k - 1);
    }

    private int atMost(int[] nums, int k) {
        int i = 0, count = 0;
        for (int j = 0; j < nums.length; j++) {
            k -= nums[j] % 2;
            while (k < 0) {
                k += nums[i++] % 2;
            }
            count += j - i + 1;
        }
        return count;
    }
}

1249. minimum-remove-to-make-valid-parentheses

  • 给一个只含有(, )和字母的字符串，返回经过validate的字符串，需要在validate过程中尽可能少地删除括号。
  • 用Set记录需要删除的括号的索引，利用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
class Solution {
    public String minRemoveToMakeValid(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        Stack<Integer> leftIndex = new Stack<>();
        Set<Integer> invalidIndexSet = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                leftIndex.push(i);
            } else if (s.charAt(i) == ')') {
                if (leftIndex.isEmpty()) {
                    invalidIndexSet.add(i);
                } else {
                    leftIndex.pop();
                }
            }
        }
        invalidIndexSet.addAll(leftIndex);
        
        if (invalidIndexSet.size() == 0) {
            return s;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (!invalidIndexSet.contains(i)) {
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }
}

1253. reconstruct-a-2-row-binary-matrix

  • 假设一个矩形只有上下两行且元素为0或者1，给一个upper表示上一行的和、lower表示下一行的和，再给一个colsum表示每一列的和。要求复原这个矩阵，若无法复原则返回空数组。
  • 贪心做法，先把colsum为2和0的都搞一遍，然后再填充1的，因为col的顺序无所谓。这题挺没意思的。

1254. number-of-closed-islands

  • 给一个grid，其中0表示陆地、1表示海水，求有多少个岛（完全被水包围），注意grid边缘的陆地是为大陆。
  • 先走一波把边缘的大陆填充为1，然后再走一波，碰到0就是岛屿了，并填充为1。时间复杂度为O(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
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    private int[] dirs = new int[] {1, 0, -1, 0, 1};
    public int closedIsland(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (i == 0 || j == 0 || i == grid.length - 1 || j == grid[0].length - 1) {
                    fill(grid, i, j);
                }
            }
        }
        
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 0) {
                    count++;
                    fill(grid, i, j);
                } 
            }
        }
        return count;
    }
    private void fill(int[][] grid, int i, int j) {
        if (i < 0 || j < 0 || i == grid.length || j == grid[0].length
           || grid[i][j] != 0) {
            return;
        }
        grid[i][j] = 1;
        for (int d = 0; d < 4; d++) {
            fill(grid, i + dirs[d], j + dirs[d + 1]);
        }
    }
}

1267. count-servers-that-communicate

  • 给一个只含有0或1的grid，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
class Solution {
    public int countServers(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int rows = grid.length, cols = grid[0].length, count = 0;
        int[] rowOneCount = new int[rows], colOneCount = new int[cols];
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1) {
                    rowOneCount[r]++;
                    colOneCount[c]++;
                    count++;
                }
            }
        }

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1 && rowOneCount[r] == 1 && colOneCount[c] == 1) {
                    count--;
                }
            }
        }
        return count;
    }
}

1268. search-suggestions-system

  • 给一个字符串数字，然后给一个字符串模拟用户输入搜索关键字，返回0～3个以用户当前输入的字符串为前缀的备选项，按字典序选最多三个。例如[aba, abb, abc, abbb]，用户输入abbbc，返回[[aba, abb, abbb], [aba, abb, abbb], [abb, abbb], [abbb], []].
  • 也是很有意思的题。观察规律看出，假如str是排序后的所有备选字符串，str[i]是str[j]的prefix，那么str[i]一定是str[i + 1], str[i + 2], ... , str[j]的prefix。因此考虑用二分查找/Tree结构来加速搜索，对于检索字符串的每个字符进行逐个拼接+查找。利用TreeMap的ceilingKey和floorKey可以分别找到「大于等于给定值」和「小于等于给定值」，如果两个都有就在ceiling对应的index往后取3个或者floor对应的index往后1个。每次搜索都是O(logN)，但是有排序，所以还是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
26
27
28
29
30
31
class Solution {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        List<List<String>> ans = new ArrayList<>();
        if (products == null || products.length == 0) {
            return ans;
        }
        TreeMap<String, Integer> map = new TreeMap<>();
        Arrays.sort(products);
        List<String> productsList = Arrays.asList(products);
        
        for (int i = 0; i < products.length; i++) {
            map.put(products[i], i);    // str -> i，方便之后取subList
        }
        
        String key = "";
        for (char c : searchWord.toCharArray()) {    // [ab, abc, abd, abdc, ac]
            key += c;                                // ab
            String ceiling = map.ceilingKey(key);    // 最小的>=, 搜ab返回ab
            String floor = map.floorKey(key + "~");  // 最大的<=, 搜ab~返回ac
            if (ceiling == null || floor == null) {
                break;
            }
            ans.add(productsList.subList(map.get(ceiling), Math.min(map.get(ceiling) + 3, map.get(floor) + 1)));
        }
        
        while (ans.size() < searchWord.length()) {
            ans.add(new ArrayList<>());
        }
        return ans;
    }
}

1273. delete-tree-nodes

  • 给一个以0为root的多叉树，以两个数组的形式，一个表示该索引出节点的parent索引，一个表示该索引处的值。将所有sum为0的子树删除后，剩下的节点数。
  • 构图后DFS，每层返回以该节点为root的子树的sum和节点数，如果为0则节点数直接以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
28
29
30
31
32
33
34
class Solution {
    public int deleteTreeNodes(int nodes, int[] parent, int[] value) {
        if (nodes <= 0 || parent == null || parent.length == 0 || value == null || value.length == 0) {
            return 0;
        }
        List<List<Integer>> graph = buildGraph(nodes, parent);
        return dfs(graph, value, 0)[1];
    }
    private List<List<Integer>> buildGraph(int nodes, int[] parent) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < nodes; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < nodes; i++) {
            if (parent[i] == -1) {
                continue;
            }
            graph.get(parent[i]).add(i);
        }
        return graph;
    }
    private int[] dfs(List<List<Integer>> graph, int[] value, int root) {
        int sum = value[root], countRemainNodes = 1;
        for (int child : graph.get(root)) {
            int[] temp = dfs(graph, value, child);
            sum += temp[0];
            countRemainNodes += temp[1];
        }
        if (sum == 0) {
            countRemainNodes = 0;
        }
        return new int[] {sum, countRemainNodes};
    }
}

1277. count-square-submatrices-with-all-ones

  • 给一个只含有0和1的matrix，求其中有多少个1填充而成的正方形。
  • DP。画个图就能理解了，若当前位置为1，则在dp矩阵中当前位置的正方形个数等于上、左上、左三个位置中最小值加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 countSquares(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int rows = matrix.length, cols = matrix[0].length, count = 0;
        int[][] dp = new int [rows][cols];
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (matrix[r][c] == 1) {
                    if (r > 0 && r < rows && c > 0 && c < cols) {
                        dp[r][c] = Math.min(dp[r - 1][c], Math.min(dp[r - 1][c - 1], dp[r][c - 1])) + 1;
                    } else {
                        dp[r][c] = 1;
                    }
                }
                count += dp[r][c];
            }
        }
        return count;
    }
}

1283. find-the-smallest-divisor-given-a-threshold

  • 给一个正整数数组，给一个threshold，求最小的divisor使得数组中所有数除以这个divisor之商小于等于所给的threshold。注意这里的除法是向上取整的。
  • 二分法找出最左边符合条件的divisor即可。其实不必纠结最大最小值，直接按照题目所给的boundary就好了。
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 smallestDivisor(int[] nums, int threshold) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int left = 1, right = (int)1e6;
        while (left < right) {
            int mid = left + (right - left) / 2, sum = getSum(nums, mid);
            if (sum == threshold) {
                right = mid;
            } else if (sum < threshold) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    private int getSum(int[] nums, int divisor) {
        int sum = 0;
        for (int num : nums) {
            sum += (num - 1) / divisor + 1;
        }
        return sum;
    }
}

1289. minimum-falling-path-sum-ii

  • 和931类似。给一个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
27
28
29
30
31
32
33
34
35
36
37
38
39
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, min = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        int[] dp = new int[cols];
        for (int c = 0; c < cols; c++) {
            dp[c] = A[0][c];
            if (dp[c] < min) {
                min2 = min;
                min = dp[c];
            } else {
                min2 = Math.min(min2, dp[c]);
            }
        }
        for (int r = 1; r < rows; r++) {
            int[] dpTemp = new int[cols];
            int minTemp = Integer.MAX_VALUE, min2Temp = Integer.MAX_VALUE;
            for (int c = 0; c < cols; c++) {
                dpTemp[c] = A[r][c] + (dp[c] == min ? min2 : min);
                if (dpTemp[c] < minTemp) {
                    min2Temp = minTemp;
                    minTemp = dpTemp[c];
                } else {
                    min2Temp = Math.min(min2Temp, dpTemp[c]);
                }
            }
            dp = dpTemp;
            min = minTemp;
            min2 = min2Temp;
        }
        for (int num : dp) {
            retVal = Math.min(retVal, num);
        }
        return retVal;

    }
}

1292. maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold

  • 给一个非负的int矩阵和一个threshold，求其中sum <= threshold的最大边长。
  • 首先需要思考的是如何快速取得某个位置的正方形之和：用另一个矩阵存放从左上方第一个元素到当前位置的矩阵所有元素和，要求正方形的和就直接减左侧和上方的多余矩形，再补加回重复减的左上方正方形即可。在求sum的过程中，可以直接求出以某个长度为边长的正方形内部和，与threshold比较即可。时间空间都是O(M*N).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maxSideLength(int[][] mat, int threshold) {
        if (mat == null || mat.length == 0 || mat[0].length == 0) {
            return 0;
        }
        int rows = mat.length, cols = mat[0].length, len = 1;
        int[][] sum = new int[rows + 1][cols + 1];
        for (int r = 1; r <= rows; r++) {
            for (int c = 1; c <= cols; c++) {
                sum[r][c] = sum[r - 1][c] + sum[r][c - 1] - sum[r - 1][c - 1] + mat[r - 1][c - 1];
                if (r >= len && c >= len &&
                   sum[r][c] - sum[r - len][c] - sum[r][c - len] + sum[r - len][c - len] <= threshold) {
                    len++;
                }
            }
        }
        return len - 1;
    }
}

1315. sum-of-nodes-with-even-valued-grandparent

  • 给一个二叉树，求grandparent是偶数的所有节点值之和。
  • 递归DFS，需要不断传入parent和grandparent到下一层才能让后序节点知道是否需要加上自己的值。
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int sumEvenGrandparent(TreeNode root) {
        return getSum(root, 1, 1);
    }
    private int getSum(TreeNode node, int parent, int grandparent) {
        if (node == null) {
            return 0;
        }
        return getSum(node.left, node.val, parent) + getSum(node.right, node.val, parent) + (grandparent % 2 == 0 ? node.val : 0);
    }
}

1328. break-a-palindrome

  • 给一个只含有小写字母的自对称字符串，求恰好替换一个字母后的非对称字符串、且所得的字典序最小。
  • 破坏自对称非常好办，就找到第一个非a的字母换成a即可，注意这一步可以利用自对称的性质只遍历一半的字符串；若全都是a则将最后一个字符替换成b即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public String breakPalindrome(String palindrome) {
        if (palindrome == null || palindrome.length() <= 1) {
            return "";
        }
        char[] sChar = palindrome.toCharArray();
        for (int i = 0; i < sChar.length / 2; i++) {
            if (sChar[i] != 'a') {
                sChar[i] = 'a';
                return String.valueOf(sChar);
            }
        }
        
        sChar[sChar.length - 1] = 'b';
        return String.valueOf(sChar);
    }
}

1339. maximum-product-of-splitted-binary-tree

  • 给一个二叉树，将其中一个边去掉后拆分成两棵树，分别求和后取product，求最大的product.
  • 直接递归方法做。可以看出，如果有全局的sum，那么在以当前节点为独立子树的话，product = (total - curr) * curr. 为了避免重复对节点求该节点的sum，可以一边求当前节点这颗树的sum，一边更新全局product。
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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private long retVal = 0;
    private int totalSum = 0;
    public int maxProduct(TreeNode root) {
        totalSum = getSum(root);
        getMax(root);
        return (int) (retVal % 1_000_000_007);
    }
    private int getSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int sumLeft = getSum(root.left);
        int sumRight = getSum(root.right);
        int sum = root.val + sumLeft + sumRight;
        return sum;
    }
    private int getMax(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftSum = getMax(root.left);
        int rightSum = getMax(root.right);
        int currSum = leftSum + rightSum + root.val;
        retVal = Math.max((long) currSum * (totalSum - currSum), retVal);
        return currSum;
    }
}
  • 还可以直接将所有子树的和存入数组，逐个用totalSum去减、求积。

1348. tweet-counts-per-frequency

  • 实现tweet统计类，实现record记录推特id和发送时间戳(second)，实现getTweetCountsPerFrequency查询从x秒到y秒之间以freq为间隔的推特数量统计list。
  • 统计推特按照时间顺序的发推数量，就想到treemap。同时发现新内置方法subMap可以根据给定key范围返回一个submap。在submap中按照frequency进行统计即可。
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
class TweetCounts {
    
    private final static String MINUTE = "minute";
    private final static String HOUR = "hour";
    private final static String DAY = "day";
    
    Map<String, TreeMap<Integer, Integer>> map;
    
    public TweetCounts() {
        map = new HashMap<>();
    }
    
    public void recordTweet(String tweetName, int time) {
        if (tweetName == null) {
            return;
        }
        map.putIfAbsent(tweetName, new TreeMap<Integer, Integer>());
        map.get(tweetName).put(time, map.get(tweetName).getOrDefault(time, 0) + 1);
    }
    
    public List<Integer> getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime) {
        List<Integer> retVal = new ArrayList<>();

        int interval = 1;
        switch (freq) {
            case MINUTE:
                interval = 60;
                break;
            case HOUR:
                interval = 3600;
                break;
            case DAY:
                interval = 86400;
        }
        
        TreeMap<Integer, Integer> timeCount = map.get(tweetName);
        if (timeCount == null) {
            return retVal;
        }
        
        int size = (endTime - startTime) / interval + 1;
        int[] bucket = new int[size];

        // 取query时间范围内的所有tweet的发送时间和计数
        Set<Map.Entry<Integer, Integer>> intervalTweetCountSet = timeCount.subMap(startTime, endTime + 1).entrySet();
        for (Map.Entry<Integer, Integer> entry : intervalTweetCountSet) {
            int index = (entry.getKey() - startTime) / interval;
            bucket[index] += entry.getValue();
        }
        
        for (int num : bucket) {
            retVal.add(num);
        }
        return retVal;
    }
}

/**
 * Your TweetCounts object will be instantiated and called as such:
 * TweetCounts obj = new TweetCounts();
 * obj.recordTweet(tweetName,time);
 * List<Integer> param_2 = obj.getTweetCountsPerFrequency(freq,tweetName,startTime,endTime);
 */

1367. linked-list-in-binary-tree

  • 给一个链表和一个二叉树，判断在二叉树中是否存在一个从上到下的path和链表的值一致。
  • 方法一：暴力递归判断，从当前root向下DFS判断，不行就分别尝试从左子树和右子树继续走。时间O(N * min(LenLL, HtBT))，空间O(HtBT).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean isSubPath(ListNode head, TreeNode root) {
        if (head == null) {
            return true;
        }
        if (root == null) {
            return false;
        }
        return dfs(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
    }
    private boolean dfs(ListNode head, TreeNode root) {
        if (head == null) {
            return true;
        }
        if (root == null) {
            return false;
        }
        return head.val == root.val && (dfs(head.next, root.left) || dfs(head.next, root.right));
    }
}
  • 方法二：DP，大名鼎鼎的KMP子字符串匹配算法。
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
class Solution {
    private int[] pattern, kmpTable;
    public boolean isSubPath(ListNode head, TreeNode root) {
        pattern = list2arr(head);
        kmpTable = getKmpTable(pattern);
        return kmpSearch(root, 0);
    }
    private boolean kmpSearch(TreeNode root, int j) {
        if (j == pattern.length) {
            return true;
        }
        if (root == null) {
            return false;
        }
        while (j > 0 && root.val != pattern[j]) {
            j = kmpTable[j - 1];
        }
        if (root.val == pattern[j]) {
            j++;
        }
        return kmpSearch(root.left, j) || kmpSearch(root.right, j);
    }
    private int[] getKmpTable(int[] pattern) {
        int[] kmpTable = new int[pattern.length];
        for (int i = 1, j = 0; i < kmpTable.length; i++) {
            while (j > 0 && pattern[i] != pattern[j]) {
                j = kmpTable[j - 1];
            }
            if (pattern[i] == pattern[j]) {
                kmpTable[i] = ++j;
            }
        }
        return kmpTable;
    }
    private int[] list2arr(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        int[] retVal = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            retVal[i] = list.get(i);         
        }
        return retVal;
    }
}

1353. maximum-number-of-events-that-can-be-attended

  • 给一个events的int二维数组，含有每个活动的开始时间和结束时间。同一时间只能参加一个活动，只要参加了一个单位时间就算参加过，求最多参加多少个活动。
  • 贪心做法，首先按照开始时间排序，挪动当前时间的时候就把所有已经开始的活动的结束时间加入优先队列，每次参加最早结束的活动。
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 {
    public int maxEvents(int[][] events) {
        if (events == null || events.length == 0) {
            return 0;
        }
        // 按照开始时间排序
        Arrays.sort(events, (a, b) -> Integer.compare(a[0], b[0]));

        int i = 0, count = 0, len = events.length, currTime = 0;
        PriorityQueue<Integer> endTimePQ = new PriorityQueue<>();

        while (!endTimePQ.isEmpty() || i < len) {
            if (endTimePQ.isEmpty()) {
                currTime = events[i][0];    // 设为当前最早活动开始时间
            }
            while (i < len && events[i][0] <= currTime) {
                endTimePQ.offer(events[i++][1]);    // 将所有已经开始的活动的结束时间塞入pq
            }
            
            // 在currTime参加一个最早结束的活动
            endTimePQ.poll();
            count++;        
            currTime++;
            
            // 将所有已经结束的活动删掉
            while (!endTimePQ.isEmpty() && endTimePQ.peek() < currTime) {
                endTimePQ.poll();
            }
        }
        return count;
    }
}

1371. validate-binary-tree-nodes

  • 总共有n个node，给两个array分别表示这些node的左、右孩子节点标号，判断这个cluster是否能构成合法的二叉树。
  • 判断每个节点是否只有一个parent节点、整个cluster中有且只有一个跟节点。这个跟节点的判断是两方面，一是并查集找的老大就是本身、二是它不能有parent。
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
class Solution {
    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        if (n <= 0 || leftChild == null || rightChild == null || leftChild.length != n || rightChild.length != n) {
            return false;
        }
        int[] root = new int[n];
        int[] parentCount = new int[n];
        for (int i = 0; i < n; i++) {
            root[i] = i;
        }
        for (int i = 0; i < n; i++) {
            if (!union(root, parentCount, i, leftChild[i]) ||
               !union(root, parentCount, i, rightChild[i])) {
                return false;
            }
        }
        int rootCount = 0, zeroParentCount = 0;
        for (int i = 0; i < n; i++) {
            if (find(root, i) == i) {
                rootCount++;
            }
            if (parentCount[i] == 0) {
                zeroParentCount++;
            }
        }
        if (rootCount != 1 || zeroParentCount != 1) {
            return false;
        }
        return true;
    }
    private int find(int[] root, int id) {
        while (root[id] != id) {
            root[id] = root[root[id]];
            id = root[id];
        }
        return id;
    }
    private boolean union(int[] root, int[] parentCount, int parent, int child) {
        if (child < 0) {
            return true;
        }
        int parentRoot = find(root, parent);
        int childRoot = find(root, child);
        if (childRoot != parentRoot) {
            root[childRoot] = parentRoot;
        }
        return (++parentCount[child]) < 2;
    }
}

1372. longest-zigzag-path-in-a-binary-tree

  • 给一个二叉树，求其中最长的zig-zag路径长度。
  • DFS，返回三个值：取左子树、取右子树、不取当前节点的最大长度。递归从孩子返回上来的就是三个值，就可以决定是往左拼、往右拼、不拼。时间空间都是O(N).
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int longestZigZag(TreeNode root) {
        return dfs(root)[2];
    }
    private int[] dfs(TreeNode root) {
        if (root == null) {
            return new int[] { -1, -1, -1 };
        }
        int[] left = dfs(root.left), right = dfs(root.right);
        int maxLen = Math.max(Math.max(left[1], right[0]) + 1, Math.max(left[2], right[2]));
        return new int[] { left[1] + 1, right[0] + 1, maxLen };
    }
}

1379. find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree

  • 给一个二叉树和它的clone，给一个target节点，求clone中对应的节点。
  • 直接在递归的时候比较reference。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        if (original == null) {
            return null;
        }
        if (original == target) {
            return cloned;
        }
        TreeNode leftRet = getTargetCopy(original.left, cloned.left, target);
        return leftRet == null ? getTargetCopy(original.right, cloned.right, target) : leftRet;
    }
}

1392. longest-happy-prefix

  • happy prefix的定义就是非空的prefix同时也是suffix。
  • 完美应用KMP。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public String longestPrefix(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        int len = s.length();
        int[] dp = new int[len];
        for (int i = 1; i < len; i++) {
            int j = dp[i - 1];
            while (j > 0 && s.charAt(i) != s.charAt(j)) {
                j = dp[j - 1];
            }
            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }
            dp[i] = j;
        }
        return dp[len - 1] == 0 ? "" : s.substring(0, dp[len - 1]);
    }
}

1396. design-underground-system

  • 计算地铁两站之间的平均直接通勤时间，map搞定。pass。

[1406.stone-game-iii] (https://leetcode.com/problems/stone-game-iii/)

  • 给一个石头array，每个石头有一定的分数，两个人轮流从左侧取1/2/3个石头，假设两个人都是“全局最优”地做决策，判断最后是先手赢、后手赢还是平局
  • DP。和1140类似的miniMax思路，先维护一个suffixSum得到从当前位置取完最后所有石头的分数和，每次取石头时分别尝试1/2/3个，最优的意思就是穷举对手能得到的分数，让它最少，那么我的分数就最优了。最后比较二者的分数即可。时间复杂度为O(N)，因为dp总共只有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 String stoneGameIII(int[] stoneValue) {
        if (stoneValue == null || stoneValue.length == 0) {
            return "";
        }
        int n = stoneValue.length;
        int[] sums = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            sums[i] = (i == n - 1 ? 0 : sums[i + 1]) + stoneValue[i];
        }
        int aliceScore = getMax(sums, new Integer[n], 0);
        int bobScore = sums[0] - aliceScore;
        return aliceScore > bobScore ? "Alice" : (aliceScore == bobScore ? "Tie" : "Bob");
    }
    private int getMax(int[] sums, Integer[] dp, int start) {
        if (start >= sums.length) {
            return 0;
        }
        if (dp[start] == null) {
            for (int len = 1; len <= 3 && start + len <= sums.length; len++) {
                int opponentMaxScore = getMax(sums, dp, start + len);
                if (dp[start] == null) {
                    dp[start] = sums[start] - opponentMaxScore;
                } else {
                    dp[start] = Math.max(dp[start], sums[start] - opponentMaxScore);
                }
            }
        }
        return dp[start];
    }
}
  • follow-up优化空间：事实上由于我们只需要suffixSum[]

1423. maximum-points-you-can-obtain-from-cards

  • 给一个int数组表示牌面分数，每次只能从头或尾取，求取k次能获得的最大分数。
  • 既然每次都是从头或尾巴取，从整体上看就是中间那部分必须是最小值，问题转化为求长度为len - k的subarray的最小值。或者直接从头取k个，然后滑动更新，取max即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int maxScore(int[] cardPoints, int k) {
        if (cardPoints == null || cardPoints.length == 0 || k > cardPoints.length) {
            return 0;
        }
        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += cardPoints[i];
        }
        int max = sum;
        for (int i = 1; i <= k; i++) {
            sum -= cardPoints[k - i];
            sum += cardPoints[cardPoints.length - i];
            max = Math.max(max, sum);
        }
        return max;
    }
}

1428. leftmost-column-with-at-least-a-one

  • 给一个只含有0/1、行与行之间有序的matrix，每次只能读一个位置的元素，求最左的含有1的列索引。
  • 从右上角出发，遇到0就向下、遇到1就向左，因为行之间有序，所以当前是0下面的行可能有1，当前是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
/**
 * // This is the BinaryMatrix's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface BinaryMatrix {
 *     public int get(int row, int col) {}
 *     public List<Integer> dimensions {}
 * };
 */

class Solution {
    public int leftMostColumnWithOne(BinaryMatrix binaryMatrix) {
        if (binaryMatrix == null) {
            return 0;
        }
        List<Integer> dims = binaryMatrix.dimensions();
        int rows = dims.get(0), cols = dims.get(1);
        int row = 0, col = cols - 1, minCol = Integer.MAX_VALUE;
        while (row < rows && col >= 0) {
            if (binaryMatrix.get(row, col) == 0) {
                row++;
            } else {
                minCol = col;
                col--;
            }
        }
        return minCol == Integer.MAX_VALUE ? -1 : minCol;
    }
}

1481. least-number-of-unique-integers-after-k-removals

  • 给一个int数组和k，求恰好删除k个数后剩余的unique数字最小值。例如[2,3,2]删除1个数字，最小剩余unique数就是1.
  • 方法一：统计所有数字出现的次数，按照出现次数从小到大排序，greedy每次删除出现次数最少的，剩余的unique数字就一定是最少的。
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 findLeastNumOfUniqueInts(int[] arr, int k) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : arr) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        List<Integer> list = new ArrayList<>(map.values());
        Collections.sort(list);
        int i = 0;
        for (int count : list) {
            k -= count;
            if (k < 0) {
                break;
            }
            i++;
        }
        return list.size() - i;
    }
}
  • 方法二：在排序这一步利用木桶排序，每个「出现次数」从小到大取，每次k可以直接尝试扣除所有occur * occurCount，不够cover的时候减去可以cover的部分即可。
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 int findLeastNumOfUniqueInts(int[] arr, int k) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : arr) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        int[] occurCount = new int[arr.length + 1];
        for (int count : map.values()) {
            occurCount[count]++;
        }
        
        int occur = 1, remaining = map.size();
        while (k > 0) {
            if (k - occur * occurCount[occur] > 0) {
                k -= occur * occurCount[occur];
                remaining -= occurCount[occur++];
            } else {
                return remaining - k / occur;   // k不够cover所有，看能够干掉几个数字
            }
        }
        return remaining;
    }
}

1472. design-browser-history

  • 实现一个浏览历史的类，记录用户访问的page，允许前进、后退操作。
  • 方法一：利用list，结合index挪动确定前进、后退的有效范围。
  • 方法二：双stack，一个记录future，一个回溯history.
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 BrowserHistory {

    Stack<String> future, history;
    public BrowserHistory(String homepage) {
        future = new Stack<>();
        history = new Stack<>();
        history.add(homepage);
    }
    
    public void visit(String url) {   // 访问了新页面，future就直接清空
        future.clear();
        history.add(url);
    }
    
    public String back(int steps) {
        while (steps > 0 && history.size() > 1) {   // history栈顶是当前page，至少需要一个
            future.add(history.pop());      // 只有经过回退，future中才会存放页面
            steps--;
        }
        return history.peek();
    }
    
    public String forward(int steps) {
        while (steps > 0 && !future.isEmpty()) {    
            history.add(future.pop());
            steps--;
        }
        return history.peek();
    }
}

1488. avoid-flood-in-the-city

  • 给一个int数组，其中0表示不降雨、正整数表示在city_id处下雨，在不降雨的时候可以任选一个city_id排空，若在排空前又出现降雨则会发洪水。返回能不发洪水的排空schedule。例如[1,2,0,0,2,1]其中一个可行的排空顺序为[-1,-1,2,1,-1,-1].
  • 抽象一下，本质上就是求前后两次city_id之间可用的0的索引，因此考虑用map记录每个降雨出现的索引（第几天），同时记录所有不降雨的天数存入heap，这样可以取给定索引之后的不降雨的索引。注意不能简单地用PQ取代。时间复杂度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
26
27
28
29
30
31
32
class Solution {
    Map<Integer, Integer> oneIndexMap;
    TreeSet<Integer> zeroIndexSet;
    public int[] avoidFlood(int[] rains) {
        if (rains == null || rains.length == 0) {
            return new int[0];
        }
        int[] ans = new int[rains.length];
        oneIndexMap = new HashMap<>();
        zeroIndexSet = new TreeSet<>();
        
        for (int i = 0; i < rains.length; i++) {
            if (rains[i] > 0) {
                ans[i] = -1;
                if (oneIndexMap.containsKey(rains[i])) {
                    Integer nextZeroIndex = zeroIndexSet.higher(oneIndexMap.get(rains[i]));
                    if (nextZeroIndex == null) {
                        return new int[0];
                    } else {
                        ans[nextZeroIndex] = rains[i];
                    }
                    zeroIndexSet.remove(nextZeroIndex);
                }
                oneIndexMap.put(rains[i], i);
            } else {
                ans[i] = 1;
                zeroIndexSet.add(i);
            }
        }
        return ans;
    }
}

1510. stone-game-iv

  • 给一个正整数表示有n个石头，A和B两个人轮流取正平方数个石头，最后取完所有石头的是赢家，双方都全局最优，判断先手能不能赢。
  • DP，dp[i]表示当前剩下i个石头时先取的人能不能赢，那么当前如果取了x个，dp[i - x]如果必输，那我只要取x就必赢了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean winnerSquareGame(int n) {
        boolean[] canWin = new boolean[n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                if (!canWin[i - j * j]) {
                    canWin[i] = true;
                    break;
                }
            }
        }
        return canWin[n];
    }
}

[1536. stone-game-v] (https://leetcode.com/problems/stone-game-v/)

  • 给一个石头堆，A每次将石头分成两份，B会将分数较多的舍弃，A的分数累加上分数较少的部分，然后继续由A进行split，最后只剩下一个石头的时候结束。求A的最大分数。
  • DP. dp[i][j]表示从i到j这部分的最大分数，利用prefixSum快速求区间的分数和，穷举当前区间的石头所有的split方式，保留最大的分数。
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 int stoneGameV(int[] stoneValue) {
        if (stoneValue == null || stoneValue.length == 0) {
            return 0;
        }
        int len = stoneValue.length;
        int[] prefixSum = new int[len];
        prefixSum[0] = stoneValue[0];
        for (int i = 1; i < len; i++) {
            prefixSum[i] = prefixSum[i - 1] + stoneValue[i];
        }
        return getScore(prefixSum, new int[len][len], 0, len - 1);
    }
    private int getScore(int[] prefixSum, int[][] dp, int start, int end) {
        if (start == end) {
            return 0;
        }
        if (dp[start][end] == 0) {
            for (int len = 1; start + len <= end; len++) {
                int leftSum = prefixSum[start + len - 1] - (start == 0 ? 0 : prefixSum[start - 1]);
                int rightSum = prefixSum[end] - prefixSum[start + len - 1];
                int score = 0;
                if (leftSum < rightSum) {
                    score = leftSum + getScore(prefixSum, dp, start, start + len - 1);
                } else if (leftSum > rightSum) {
                    score = rightSum + getScore(prefixSum, dp, start + len, end);
                } else {
                    score = Math.max(leftSum + getScore(prefixSum, dp, start, start + len - 1),
                                    rightSum + getScore(prefixSum, dp, start + len, end));
                }
                dp[start][end] = Math.max(dp[start][end], score);
            }
        }
        return dp[start][end];
    }
}

1578. minimum-deletion-cost-to-avoid-repeating-letters

  • 给一个字符串和一个cost数组表示删除对应位置的字符所需的cost，求最少需要多少cost才能将字符串删得没有相邻字符。
  • 直接双指针遍历搞定，最小cost也就是每一个团簇里面保留一个最大cost者。pass.

1793. maximum-score-of-a-good-subarray

  • 给一个int数组以及一个k，在i <= k <= j的范围中，score为min(num[i ~ j]) * (j - i + 1)，求最大的score。
  • 本质上就是要快速求出给定范围i ~ j的最小值，由于有i <= k <= j这个限制，可以以k为界维护一个minFromK数组记录从i到k以及从k到j的最小值。然后双指针从两侧夹逼，若i ~ k的min比k ~ j的小则把i往右挪（因为把j往做挪的score一定比当前小）。时间、空间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
class Solution {
    public int maximumScore(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        int[] minFromK = new int[len];
        minFromK[k] = nums[k];
        for (int i = k - 1; i >= 0; i--) {
            minFromK[i] = Math.min(minFromK[i + 1], nums[i]);
        }
        for (int j = k + 1; j < len; j++) {
            minFromK[j] = Math.min(minFromK[j - 1], nums[j]);
        }
        
        int maxScore = minFromK[k], i = 0, j = len - 1;
        while (i < j) {
            maxScore = Math.max(maxScore, Math.min(minFromK[i], minFromK[j]) * (j - i + 1));
            if (j == k || minFromK[i] < minFromK[j]) {
                i++;
            } else {
                j--;
            }
        }
        return maxScore;
    }
}
  • 优化：我们可以选择从k向两侧扩展，这样就不需要提前知道最小值存入数组了，直接每次在i和j处看看下一位谁更小，尽量拖延向更小者挪动的时机。
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 maximumScore(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k < 0 || k >= nums.length) {
            return 0;
        }
        int len = nums.length, maxScore = nums[k], min = nums[k], i = k, j = k;
        while (i > 0 || j < len - 1) {
            if (i == 0) {
                j++;
            } else if (j == len - 1) {
                i--;
            } else if (nums[i - 1] < nums[j + 1]) {
                j++;    // j的下一位更大，意味着长度增加的同时min会更大
            } else {
                i--;
            }
            min = Math.min(min, Math.min(nums[i], nums[j]));
            maxScore = Math.max(maxScore, min * (j - i + 1));
        }
        
        return maxScore;
    }
}