LeetCode 501-600

1
/**
2
 * Definition for a binary tree node.
3
 * public class TreeNode {
4
 *     int val;
5
 *     TreeNode left;
6
 *     TreeNode right;
7
 *     TreeNode() {}
8
 *     TreeNode(int val) { this.val = val; }
9
 *     TreeNode(int val, TreeNode left, TreeNode right) {
10
 *         this.val = val;
11
 *         this.left = left;
12
 *         this.right = right;
13
 *     }
14
 * }
15
 */
16
class Solution {
17
    private int currVal;
18
    private int currCount = 0;
19
    private int maxCount = 0;
20
    private int modeCount = 0;
21
    private int[] modes;
22

23
    public int[] findMode(TreeNode root) {
24
        inorder(root);
25
        modes = new int[modeCount];
26
        modeCount = 0;
27
        currCount = 0;
28
        inorder(root);
29
        return modes;
30
    }
31

32
    private void inorder(TreeNode root) {
33
        if (root == null) {
34
            return;
35
        }
36
        inorder(root.left);
37

38
        // update current number's count
39
        if (root.val != currVal) {
40
            currVal = root.val;
41
            currCount = 0;
42
        }
43
        currCount++;
44

45
        if (currCount > maxCount) {
46
            // if current number is new mode, update
47
            maxCount = currCount;
48
            modeCount = 1;
49
        } else if (currCount == maxCount) {
50
            // current number one of the modes
51
            if (modes != null) {
52
                modes[modeCount] = currVal;
53
            }
54
            modeCount++;
55
        }
56

57
        inorder(root.right);
58
    }
59
}

1
class Solution {
2
    public int findMaximizedCapital(int k, int w, int[] Profits, int[] Capital) {
3
        // true if all capitals <= initial capital
4
        boolean speedUp = true;
5

6
        for (int c: Capital) {
7
            if (w < c) {
8
                speedUp = false;
9
            }
10
        }
11

12
        // add k largest profits
13
        if (speedUp) {
14
            PriorityQueue<Integer> heap = new PriorityQueue<>();
15
            for (int p: Profits) {
16
                heap.add(p);
17
                if (heap.size() > k) {
18
                    heap.poll();
19
                }
20
            }
21
            for (int h: heap) {
22
                w += h;
23
            }
24
            return w;
25
        }
26

27
        int n = Profits.length;
28
        PriorityQueue<Integer> minCapitalHeap = new PriorityQueue<>((a, b) -> Capital[a] - Capital[b]);
29
        PriorityQueue<Integer> maxProfitHeap = new PriorityQueue<>((a, b) -> Profits[b] - Profits[a]);
30

31
        // sort all projects by capital in ascending order
32
        for (int i = 0; i < n; i++) {
33
            minCapitalHeap.offer(i);
34
        }
35

36
        // we can finish at most k projects
37
        for (int i = 0; i < k; i++) {
38
            // find projects that can be selected with the available capital
39
            while (!minCapitalHeap.isEmpty() && Capital[minCapitalHeap.peek()] <= w) {
40
                maxProfitHeap.add(minCapitalHeap.poll());
41
            }
42

43
            // terminate if we are not able to find any available capital
44
            if (maxProfitHeap.isEmpty()) {
45
                break;
46
            }
47

48
            // add first project's profit
49
            w += Profits[maxProfitHeap.poll()];
50
        }
51

52
        return w;
53
    }
54
}

1
class Solution {
2
    public int[] nextGreaterElements(int[] nums) {
3
        int[] result = new int[nums.length];
4
        Stack<Integer> stack = new Stack<>();
5

6
        // first loop, get the index of next greater element in normal array
7
        for (int i = 0; i < nums.length; i++) {
8
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
9
                int index = stack.pop();
10
                result[index] = nums[i];
11
            }
12

13
            stack.push(i);
14
        }
15

16
        // second loop, get the index of next greater element in circular array
17
        for (int i = 0; i < nums.length; i++) {
18
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
19
                int index = stack.pop();
20
                result[index] = nums[i];
21
            }
22
        }
23

24
        // cannot find greater element
25
        while (!stack.isEmpty()) {
26
            result[stack.pop()] = -1;
27
        }
28

29
        return result;
30
    }
31
}

1
class Solution {
2
    public String convertToBase7(int num) {
3
        if (num == 0) {
4
            return "0";
5
        }
6

7
        StringBuilder sb = new StringBuilder();
8
        int n = Math.abs(num);
9

10
        while (n != 0) {
11
            sb.append(n % 7);
12
            n /= 7;
13
        }
14

15
        if (num < 0) {
16
            sb.append("-");
17
        }
18
        return sb.reverse().toString();
19
    }
20
}

1
class Solution {
2
    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
3
        // directions to top, bottom, left and right
4
        int[][] dirs = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
5

6
        // store shotest distance
7
        int[][] distance = new int[maze.length][maze[0].length];
8

9
        // Set all cell as -1 initially
10
        for (int[] d : distance) {
11
            Arrays.fill(d, -1);
12
        }
13

14
        distance[start[0]][start[1]] = 0; // start distance
15
        Queue<int[]> q = new ArrayDeque<>();
16
        q.add(start);
17

18
        while (!q.isEmpty()) {
19
            int[] c = q.poll();
20
            for (int[] dir : dirs) {
21
                int count = distance[c[0]][c[1]];
22
                int x = c[0];
23
                int y = c[1];
24
                while (x + dir[0] >= 0 && x + dir[0] < maze.length && y + dir[1] >= 0 && y + dir[1] < maze[0].length && maze[x + dir[0]][y + dir[1]] != 1) {
25
                    x += dir[0];
26
                    y += dir[1];
27
                    count++;
28
                }
29

30
                // unvisited cell, or a shorter path, add it to queue and update distance
31
                if (distance[x][y] == -1 || distance[x][y] > count) {
32
                    q.add(new int[]{x, y});
33
                    distance[x][y] = count;
34
                }
35
            }
36
        }
37

38
        return distance[destination[0]][destination[1]];
39
    }
40
}

1
class Solution {
2
    public String[] findRelativeRanks(int[] score) {
3
        if (score == null || score.length == 0) {
4
            return null;
5
        }
6
        int n = score.length;
7
        String[] result = new String[n];
8

9
        // find min and max values to set buckets
10
        int max = 0, min = Integer.MAX_VALUE;
11
        for (int num : score) {
12
            max = Math.max(max, num);
13
            min = Math.min(min, num);
14
        }
15

16
        // each value is mapped to a unique index
17
        int[] valToIndex = new int[max - min + 1];
18
        Arrays.fill(valToIndex, -1);
19
        for (int i = 0; i < n; i++) {
20
            valToIndex[score[i] - min] = i;
21
        }
22

23
        // start from highest scores to assign rank
24
        int rank = 1;
25
        for (int val = max - min; val >= 0; val--) {
26
            if (valToIndex[val] == -1) {
27
                continue;
28
            }
29

30
            if (rank == 1) {
31
                result[valToIndex[val]] = "Gold Medal";
32
            } else if (rank == 2) {
33
                result[valToIndex[val]] = "Silver Medal";
34
            } else if (rank == 3) {
35
                result[valToIndex[val]] = "Bronze Medal";
36
            } else {
37
                result[valToIndex[val]] = String.valueOf(rank);
38
            }
39
            rank++;
40
        }
41

42
        return result;
43
    }
44
}

1
class Solution {
2
    public boolean checkPerfectNumber(int num) {
3
        if (num <= 1) {
4
            return false;
5
        }
6

7
        int sumOfDivisors = 0;
8

9
        for (int i = 2; i <= (int)Math.sqrt(num); i++) {
10
            if (num % i == 0) {
11
                sumOfDivisors += (i + num / i);
12
            }
13
        }
14

15
        return sumOfDivisors + 1 == num;
16
    }
17
}

1
/**
2
 * Definition for a binary tree node.
3
 * public class TreeNode {
4
 *     int val;
5
 *     TreeNode left;
6
 *     TreeNode right;
7
 *     TreeNode() {}
8
 *     TreeNode(int val) { this.val = val; }
9
 *     TreeNode(int val, TreeNode left, TreeNode right) {
10
 *         this.val = val;
11
 *         this.left = left;
12
 *         this.right = right;
13
 *     }
14
 * }
15
 */
16
class Solution {
17
    private List<Integer> list;
18
    private int maxFreq = 0;
19

20
    // <sum, freq>
21
    private Map<Integer, Integer> map;
22

23
    public int[] findFrequentTreeSum(TreeNode root) {
24
        if (root == null) {
25
            return new int[]{};
26
        }
27

28
        map = new HashMap<>();
29
        list = new ArrayList<>();
30

31
        DFS(root);
32

33
        int[] result = new int[list.size()];
34
        int i = 0;
35
        for (int ele: list) {
36
            result[i] = ele;
37
            i++;
38
        }
39
        return result;
40
    }
41

42
    private int DFS(TreeNode cur) {
43
        // current subtree's sum
44
        if (cur == null) {
45
            return 0;
46
        }
47
        int leftSum = DFS(cur.left);
48
        int rightSum = DFS(cur.right);
49
        int sum = leftSum + rightSum + cur.val;
50

51
        int curFreq = map.getOrDefault(sum, 0) + 1;
52
        map.put(sum, curFreq);
53

54
        // empty list and add the new largest sum
55
        if (curFreq > maxFreq) {
56
            maxFreq = curFreq;
57
            list.clear();
58
            list.add(sum);
59
        } else if (curFreq == maxFreq) {
60
            list.add(sum);
61
        }
62

63
        return sum;
64
    }
65
}

1
class Solution {
2
    public int fib(int n) {
3
        if (n == 0) {
4
            return 0;
5
        }
6
        if (n == 1) {
7
            return 1;
8
        }
9

10
        // current index of Fibonacci sequence
11
        int current = 2;
12

13
        // current Fibonacci number
14
        int num = 0;
15

16
        // preceding two numbers
17
        int preceding2 = 0;
18
        int preceding1 = 1;
19

20
        while (current <= n) {
21
            num = preceding2 + preceding1;
22

23
            // update preceding numbers
24
            preceding2 = preceding1;
25
            preceding1 = num;
26
            current++;
27
        }
28

29
        return num;
30
    }
31
}

1
/*
2
// Definition for a Node.
3
class Node {
4
    public int val;
5
    public Node left;
6
    public Node right;
7
    public Node parent;
8
};
9
*/
10

11
class Solution {
12
    public Node inorderSuccessor(Node x) {
13
        // no right child, find the smallest ancestor which is larger than x
14
        if (x.right == null) {
15
            Node cur = x;
16

17
            // search upwards in the right subtree
18
            while (cur.parent != null && cur.parent.right == cur) {
19
                cur = cur.parent;
20
            }
21
            return cur.parent;
22
        }
23

24
        // have right child, find the leftmost element in the right subtree
25
        Node cur = x.right;
26
        while (cur.left != null) {
27
            cur = cur.left;
28
        }
29
        return cur;
30
    }
31
}

1
/**
2
 * Definition for a binary tree node.
3
 * public class TreeNode {
4
 *     int val;
5
 *     TreeNode left;
6
 *     TreeNode right;
7
 *     TreeNode() {}
8
 *     TreeNode(int val) { this.val = val; }
9
 *     TreeNode(int val, TreeNode left, TreeNode right) {
10
 *         this.val = val;
11
 *         this.left = left;
12
 *         this.right = right;
13
 *     }
14
 * }
15
 */
16
class Solution {
17
    private int result = 0;
18
    private int maxLevel = -1;
19

20
    public int findBottomLeftValue(TreeNode root) {
21
        findLevel(root, 0);
22
        return result;
23
    }
24

25
    // in-order will always visit the leftmost value first
26
    public void findLevel(TreeNode root, int level) {
27
        if (root == null) {
28
            return;
29
        }
30

31
        findLevel(root.left, level + 1);
32

33
        // update current max level
34
        if (level > maxLevel) {
35
            maxLevel = level;
36
            result = root.val;
37
        }
38

39
        findLevel(root.right, level + 1);
40
    }
41
}

1
class Solution {
2
    public int findRotateSteps(String ring, String key) {
3
        // <character, character's index in ring>
4
        List<Integer>[] map = new List[26];
5

6
        for (int i = 0; i < ring.length(); i++) {
7
            char c = ring.charAt(i);
8
            if (map[c - 'a'] == null) {
9
                map[c - 'a'] = new ArrayList();
10
            }
11
            map[c - 'a'].add(i);
12
        }
13

14
        int[][] dp = new int[ring.length() + 1][key.length() + 1];
15
        return helper(ring, key, 0, 0, map, dp);
16
    }
17

18
    private int helper(String ring, String key, int rIdx, int kIdx, List<Integer>[] map, int[][] dp) {
19
        // already end of the key, no more characters to press
20
        if (key.length() == kIdx) {
21
            return 0;
22
        }
23

24
        // already calculated
25
        if (dp[rIdx][kIdx] > 0) {
26
            return dp[rIdx][kIdx];
27
        }
28

29
        int min = Integer.MAX_VALUE;
30
        for (int i : map[key.charAt(kIdx) - 'a']) {
31
            // clockwise vs anticlockwise offset
32
            int offset = Math.min(Math.abs(rIdx - i), ring.length() - Math.abs(rIdx - i));
33

34
            // current offset + all subsequent offsets
35
            min = Math.min(min, offset + helper(ring, key, i, kIdx + 1, map, dp));
36
        }
37

38
        // +1 for pressing the button
39
        dp[rIdx][kIdx] = min + 1;
40

41
        return dp[rIdx][kIdx];
42
    }
43
}

1
/**
2
 * Definition for a binary tree node.
3
 * public class TreeNode {
4
 *     int val;
5
 *     TreeNode left;
6
 *     TreeNode right;
7
 *     TreeNode() {}
8
 *     TreeNode(int val) { this.val = val; }
9
 *     TreeNode(int val, TreeNode left, TreeNode right) {
10
 *         this.val = val;
11
 *         this.left = left;
12
 *         this.right = right;
13
 *     }
14
 * }
15
 */
16
class Solution {
17
    public List<Integer> largestValues(TreeNode root) {
18
        List<Integer> result = new ArrayList<Integer>();
19
        largestValues(root, result, 0);
20
        return result;
21
    }
22

23
    public void largestValues(TreeNode root, List<Integer> result, int height) {
24
        if (root == null) {
25
            return;
26
        }
27

28
        if (height == result.size()) {
29
            // add value in the new height
30
            result.add(root.val);
31
        } else {
32
            // set max of current height
33
            result.set(height, Math.max(result.get(height), root.val));
34
        }
35

36
        largestValues(root.left, result, height + 1);
37
        largestValues(root.right, result, height + 1);
38
    }
39
}

1
class Solution {
2
    public int longestPalindromeSubseq(String s) {
3
        int[] dp = new int[s.length()];
4

5
        // dp[i][j]: the longest palindromic subsequence's length of substring(i, j)
6
        // dp[i][j] = dp[i+1][j-1] + 2 if s.charAt(i) == s.charAt(j)
7
        // otherwise, dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])
8
        // we can then reduce dp[m][n] to dp[n]
9
        for (int i = s.length() - 1; i >= 0; i--) {
10
            dp[i] = 1;
11
            int pre = 0;
12
            for (int j = i + 1; j < s.length(); j++) {
13
                int tmp = dp[j];
14
                if (s.charAt(i) == s.charAt(j)) {
15
                    dp[j] = pre + 2;
16
                } else {
17
                    dp[j] = Math.max(dp[j], dp[j - 1]);
18
                }
19

20
                pre = tmp;
21
            }
22
        }
23

24
        return dp[s.length() - 1];
25
    }
26
}

1
class Solution {
2
    public int findMinMoves(int[] machines) {
3
        int total = 0, n = machines.length;
4
        for (int m : machines) {
5
            total += m;
6
        }
7

8
        // skip impossible cases
9
        if (total % n > 0) {
10
            return -1;
11
        }
12

13
        int target = total / n, result = 0, toRight = 0;
14
        for (int m : machines) {
15
            // the clothes that we need to pass to the right number
16
            toRight = m + toRight - target;
17
            result = Math.max(result, Math.max(Math.abs(toRight), m - target));
18
        }
19

20
        return result;
21
    }
22
}

1
class Solution {
2
    // dp[i][j] : the number of combinations to make up amount j by using the first i types of coins
3
    public int change(int amount, int[] coins) {
4
        int[][] dp = new int[coins.length+1][amount+1];
5
        dp[0][0] = 1;
6

7
        for (int i = 1; i <= coins.length; i++) {
8
            dp[i][0] = 1;
9

10
            // dp[i - 1][j]: the number of combinations if we don't use the i-th coin
11
            // dp[i][j-coins[i-1]]：the number of combinations if we must use at least one of the i-th coin
12
            for (int j = 1; j <= amount; j++) {
13
                dp[i][j] = dp[i-1][j] + (j >= coins[i-1] ? dp[i][j - coins[i-1]] : 0);
14
            }
15
        }
16

17
        return dp[coins.length][amount];
18
    }
19

20
//     public int change(int amount, int[] coins) {
21
//         int[] dp = new int[amount + 1];
22
//         dp[0] = 1;
23

24
//         for (int coin : coins) {
25
//             for (int i = coin; i <= amount; i++) {
26
//                 dp[i] += dp[i-coin];
27
//             }
28
//         }
29

30
//         return dp[amount];
31
//     }
32
}

1
class Solution {
2
    private Map<Integer, Integer> map = new HashMap<>();
3
    private int row, col, total;
4
    private Random rand = new Random();
5

6
    public Solution(int m, int n) {
7
        row = m;
8
        col = n;
9
        total = row * col;
10
    }
11

12
    public int[] flip() {
13
        // generate index, decrease total number of values
14
        int r = rand.nextInt(total);
15
        total--;
16

17
        // check if we have already put something at this index
18
        int x = map.getOrDefault(r, r);
19

20
        // swap, put total at index that we generated
21
        map.put(r, map.getOrDefault(total, total));
22

23
        return new int[]{x / col, x % col};
24
    }
25

26
    public void reset() {
27
        map.clear();
28
        total = row * col;
29
    }
30
}
31

32
/**
33
 * Your Solution object will be instantiated and called as such:
34
 * Solution obj = new Solution(m, n);
35
 * int[] param_1 = obj.flip();
36
 * obj.reset();
37
 */

1
class Solution {
2
    public boolean detectCapitalUse(String word) {
3
        int count = 0;
4

5
        char[] wordArray = word.toCharArray();
6
        for (int i = 0; i < wordArray.length; i++) {
7
            if (wordArray[i] >= 'A' && wordArray[i] <= 'Z') {
8
                count++;
9
            }
10
        }
11

12
        return count == 0 ||
13
               count == wordArray.length ||
14
               (count == 1 && wordArray[0] >= 'A' && wordArray[0] <= 'Z');
15
    }
16
}

1
class Solution {
2
    public int findLUSlength(String[] strs) {
3
        int result = -1, n = strs.length;
4
        for (int i = 0; i < n; i++) {
5
            if (strs[i].length() < result) {
6
                continue;
7
            }
8

9
            int j = -1;
10
            while (++j < n) {
11
                if (i != j && isSubsequence(strs[i], strs[j])) {
12
                    break;
13
                }
14
            }
15

16
            // current string is not subsequence of any other string
17
            if (j == n) {
18
                result = Math.max(result, strs[i].length());
19
            }
20
        }
21

22
        return result;
23
    }
24

25
    public boolean isSubsequence(String a, String b) {
26
        int i = 0, j = 0;
27

28
        while (i < a.length() && j < b.length()) {
29
            if (a.charAt(i) == b.charAt(j++)) {
30
                i++;
31
            }
32
        }
33

34
        return i == a.length();
35
    }
36
}

1
class Solution {
2
    public boolean checkSubarraySum(int[] nums, int k) {
3
        if (nums.length < 2) {
4
            return false;
5
        }
6

7
        // <mod value, index>
8
        Map<Integer, Integer> map = new HashMap<>();
9

10
        // the first subarray with first two numbers in array could form the result
11
        map.put(0, -1);
12

13
        int curSum = 0;
14
        int curMod = 0;
15
        for (int i = 0; i < nums.length; i++) {
16
            curSum += nums[i];
17

18
            // corner case: k CANNOT be 0 when we use a number mod k
19
            curMod = k != 0 ? curSum % k : curSum;
20

21
            // the mode repeat again, so numbers between them should be a multiple of k
22
            if (map.containsKey(curMod)) {
23
                // subarray of size at least 2
24
                if (i - map.get(curMod) > 1) {
25
                    return true;
26
                }
27
            } else {
28
                map.put(curMod, i);
29
            }
30
        }
31

32
        return false;
33
    }
34
}