LeetCode 401-500

1
class Solution {
2
    public List<String> readBinaryWatch(int turnedOn) {
3
        List<String> result = new ArrayList<>();
4

5
        for (int hour = 0; hour < 12; hour++) {
6
            for (int minute = 0; minute < 60; minute++) {
7
                if (Integer.bitCount(hour) + Integer.bitCount(minute) == turnedOn) {
8
                    result.add(hour + (minute < 10 ? ":0" : ":") + minute);
9
                }
10
            }
11
        }
12

13
        return result;
14
    }
15
}

1
class Solution {
2
    public String removeKdigits(String num, int k) {
3
        int end = 0;
4
        char[] array = num.toCharArray();
5

6
        for (int i = 0; i < num.length(); i++) {
7
            // encounter a decreasing sequence, locate the digit to be overwritten
8
            while (end > 0 && k > 0 && array[end - 1] > array[i]) {
9
                k--;
10
                end--;
11
            }
12

13
            // skip leading '0' and overwrite one digit with a digit after
14
            if (end > 0 || array[i] != '0') {
15
                array[end] = array[i];
16
                end++;
17
            }
18
        }
19

20
        // if there are still k left, return 0 or truncate the last k digits
21
        return end <= k ? "0" : String.valueOf(array, 0, end - k);
22
    }
23
}

1
class Solution {
2
    // <index, set of all possible k>
3
    Map<Integer, Set<Integer>> checked = new HashMap<>();
4

5
    public boolean canCross(int[] stones) {
6
        for (int i = 0; i < stones.length; i++) {
7
            checked.put(stones[i], new HashSet<>());
8
        }
9
        return helper(0, 1, stones[stones.length - 1]);
10
    }
11

12
    private boolean helper(int current, int k, int last) {
13
        if (current == last) {
14
            return true;
15
        }
16

17
        // skip if we have checked this k at the current stone
18
        if (k <= 0 || checked.get(current).contains(k)) {
19
            return false;
20
        }
21

22
        int next = current + k;
23
        if (checked.containsKey(next)) {
24
            if (helper(next, k - 1, last) || helper(next, k, last) || helper(next, k + 1, last)) {
25
                return true;
26
            }
27
        }
28
        checked.get(current).add(k);
29

30
        return false;
31
    }
32
}

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 int sumOfLeftLeaves(TreeNode root) {
18
        int result = 0;
19

20
        if (root == null) {
21
            return result;
22
        }
23

24
        if (root.left != null) {
25
            if (root.left.left == null && root.left.right == null) {
26
                result += root.left.val;
27
            } else {
28
                result += sumOfLeftLeaves(root.left);
29
            }
30
        }
31

32
        if (root.right != null) {
33
            result += sumOfLeftLeaves(root.right);
34
        }
35

36
        return result;
37
    }
38
}

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

7
        char[] map = new char[] {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
8
        StringBuilder sb = new StringBuilder();
9
        while (num != 0) {
10
            // transform last 4 bits to hex
11
            sb.append(map[num & 15]);
12

13
            // get rid of the last 4 bits
14
            num >>>= 4;
15
        }
16

17
        return sb.reverse().toString();
18
    }
19
}

1
class Solution {
2
    private int water = 0;
3
    private boolean[][] visited;
4
    private int visitedCnt = 0;
5

6
    private static class Block implements Comparable<Block> {
7
        int row;
8
        int col;
9
        int value;
10

11
        Block(int row, int col, int value) {
12
            this.row = row;
13
            this.col = col;
14
            this.value = value;
15
        }
16

17
        @Override
18
        public int compareTo(Block block) {
19
            return value - block.value;
20
        }
21
    }
22

23
    public int trapRainWater(int[][] heightMap) {
24
        if (heightMap == null || heightMap.length < 3 || heightMap[0].length < 3) {
25
            return 0;
26
        }
27

28
        int rows = heightMap.length;
29
        int cols = heightMap[0].length;
30
        PriorityQueue<Block> pq = new PriorityQueue<Block>();
31
        visited = new boolean[rows][cols];
32

33
        // add row edge blocks to priority queue
34
        for (int i = 0; i < cols; i++) {
35
            Block block1 = new Block(0, i, heightMap[0][i]);
36
            Block block2 = new Block(rows - 1, i, heightMap[rows - 1][i]);
37
            pq.offer(block1);
38
            pq.offer(block2);
39
            visited[0][i] = true;
40
            visited[rows - 1][i] = true;
41
            visitedCnt += 2;
42
        }
43

44
        // add column edge blocks to priority queue
45
        for (int i = 1; i < rows - 1; i++) {
46
            Block block1 = new Block(i, 0, heightMap[i][0]);
47
            Block block2 = new Block(i, cols - 1, heightMap[i][cols - 1]);
48
            pq.offer(block1);
49
            pq.offer(block2);
50
            visited[i][0] = true;
51
            visited[i][cols - 1] = true;
52
            visitedCnt += 2;
53
        }
54

55
        // BFS
56
        while (visitedCnt < rows * cols) {
57
            Block block = pq.poll();
58
            fill(block.row - 1, block.col, block.value, pq, heightMap);
59
            fill(block.row, block.col - 1, block.value, pq, heightMap);
60
            fill(block.row + 1, block.col, block.value, pq, heightMap);
61
            fill(block.row, block.col + 1, block.value, pq, heightMap);
62
        }
63

64
        return water;
65
    }
66

67

68
    public void fill(int row, int col, int min, PriorityQueue<Block> pq, int[][] heightMap) {
69
        if (row < 0 || col < 0 || row >= heightMap.length || col >= heightMap[0].length || visited[row][col]) {
70
            // out of bound, or visited block
71
            return;
72
        } else if (heightMap[row][col] >= min) {
73
            // visit a higher block, add to queue and mark it as visited
74
            Block newBlock = new Block(row, col, heightMap[row][col]);
75
            pq.offer(newBlock);
76
            visited[row][col] = true;
77
            visitedCnt++;
78
        } else {
79
            // visit a lower block, add water to be trapped
80
            water += min - heightMap[row][col];
81
            visited[row][col] = true;
82
            visitedCnt++;
83
            fill(row - 1, col, min, pq, heightMap);
84
            fill(row, col - 1, min, pq, heightMap);
85
            fill(row + 1, col, min, pq, heightMap);
86
            fill(row, col + 1, min, pq, heightMap);
87
        }
88
    }
89
}

1
class Solution {
2
    public boolean validWordAbbreviation(String word, String abbr) {
3
        int number = 0;
4
        int i = 0, j = 0;
5

6
        while (i < word.length() && j < abbr.length()) {
7
            if (abbr.charAt(j) >= '0' && abbr.charAt(j) <= '9') {
8
                number = number * 10 + abbr.charAt(j) - '0';
9
                if (number == 0) {
10
                    return false;
11
                }
12
                j++;
13
            } else {
14
                i += number;
15
                if (i >= word.length() || word.charAt(i) != abbr.charAt(j)) {
16
                    return false;
17
                }
18
                number = 0;
19
                i++;
20
                j++;
21
            }
22
        }
23

24
        // abbr ends with number
25
        i += number;
26
        return i == word.length() && j == abbr.length();
27
    }
28
}

1
class Solution {
2
    public int longestPalindrome(String s) {
3
        int[] freq = new int[128];
4
        for (int i = 0; i < s.length(); i++) {
5
            freq[s.charAt(i)]++;
6
        }
7

8
        int odd = 0;
9
        for (int i = 0; i < freq.length; i++) {
10
            if (freq[i] % 2 != 0) {
11
                odd++;
12
            }
13
        }
14

15
        return odd < 2 ? s.length() : s.length() - odd + 1;
16
    }
17
}

1
class Solution {
2
    public int splitArray(int[] nums, int m) {
3
        int minVal = Integer.MIN_VALUE, maxVal = 0;
4
        for (int num : nums) {
5
            minVal = Math.max(minVal, num);
6
            maxVal += num;
7
        }
8

9
        while (minVal < maxVal) {
10
            int mid = minVal + (maxVal - minVal) / 2;
11

12
            if (canSplit(mid, nums, m)) {
13
                maxVal = mid;
14
            } else {
15
                minVal = mid + 1;
16
            }
17
        }
18

19
        return minVal;
20
    }
21

22
    private boolean canSplit(int upperBoundSubarraySum, int[] nums, int m) {
23
        int curSubarraySum = 0, subarrayCount = 1;
24

25
        for (int num : nums) {
26
            curSubarraySum += num;
27

28
            if (curSubarraySum > upperBoundSubarraySum) {
29
                subarrayCount++;
30
                curSubarraySum = num;
31
                if (subarrayCount > m) {
32
                    return false;
33
                }
34
            }
35
        }
36

37
        return true;
38
    }
39
}

1
class Solution {
2
    public String minAbbreviation(String target, String[] dic) {
3
        Set<Integer> diffs = new HashSet<>();
4
        int targetLen = target.length();
5

6
        for (String word : dic) {
7
            if (word.length() == targetLen) {
8
                // mark each bit's difference between target and word
9
                int diff = 0;
10
                for (int i = 0; i < targetLen; i++) {
11
                    if (target.charAt(i) != word.charAt(i))  {
12
                        diff += 1 << i;
13
                    }
14
                }
15

16
                diffs.add(diff);
17
            }
18
        }
19

20
        // all words have different length, then return the shortest abbr
21
        if (diffs.isEmpty()) {
22
            return Integer.toString(targetLen);
23
        }
24

25
        int bits = Integer.MIN_VALUE;
26
        int max = Integer.MIN_VALUE;
27
        for (int i = 0; i < (1 << targetLen); i++) {
28
            boolean flag = true;
29

30
            // skip cases that are totally different from dic
31
            for (int diff : diffs) {
32
                if ((i & diff) == 0) {
33
                    flag = false;
34
                    break;
35
                }
36
            }
37

38
            // get maximum conflicting bits
39
            if (flag) {
40
                int sum = 0;
41
                for (int j = 0; j < targetLen - 1; j++) {
42
                    if (((i >> j) & 3) == 0) {
43
                        sum++;
44
                    }
45
                }
46

47
                if (sum > max) {
48
                    max = sum;
49
                    bits = i;
50
                }
51
            }
52
        }
53

54
        StringBuilder result = new StringBuilder();
55
        int count = 0;
56
        for (int i = 0; i < targetLen; i++) {
57

58
            // current pos cannot be replaced with an abbr digit, must use alphabet instead
59
            if ((bits & (1 << i)) != 0) {
60
                if (count != 0) {
61
                    result.append(count);
62
                    count = 0;
63
                }
64
                result.append(target.charAt(i));
65
            } else {
66
                count++;
67
            }
68
        }
69

70
        if (count != 0) {
71
            result.append(count);
72
        }
73
        return result.toString();
74
    }
75
}

1
class Solution {
2
    public List<String> fizzBuzz(int n) {
3
        List<String> result = new ArrayList<>();
4
        for (int i = 1; i <= n; i++) {
5
            if (i % 3 == 0 && i % 5 == 0) {
6
                result.add("FizzBuzz");
7
            } else if (i % 3 == 0) {
8
                result.add("Fizz");
9
            } else if (i % 5 == 0) {
10
                result.add("Buzz");
11
            } else {
12
                result.add(String.valueOf(i));
13
            }
14
        }
15

16
        return result;
17
    }
18
}

1
class Solution {
2
    public List<String> fizzBuzz(int n) {
3
        // define the order of how you want to concat the words here using lambda comparator
4
        TreeMap<Integer, String> map = new TreeMap<>((a, b) -> a - b);
5
        map.put(3, "Fizz");
6
        map.put(5, "Buzz");
7
        // map.put(7, "Yuzz");
8
        // map.put(9, "Mozz");
9
        // add more encoding options here ...
10

11
        List<String> result = new LinkedList();
12
        for (int i = 1; i <= n; i++) {
13
            StringBuilder encoded = new StringBuilder();
14
            for (int num : map.keySet()) {
15
                if (i % num == 0) {
16
                    encoded.append(map.get(num));
17
                }
18
            }
19

20
            result.add((encoded.length() == 0) ? String.valueOf(i) : encoded.toString());
21
        }
22

23
        return result;
24
    }
25
}

1
class Solution {
2
    public int numberOfArithmeticSlices(int[] A) {
3
        int newSlice = 0, result = 0;
4

5
        for (int i = 2; i < A.length; i++) {
6
            if (A[i-1] - A[i-2] == A[i] - A[i-1]) {
7
                newSlice++;
8
                result += newSlice;
9
            } else {
10
                newSlice = 0;
11
            }
12
        }
13

14
        return result;
15
    }
16
}

1
class Solution {
2
    public int thirdMax(int[] nums) {
3
        Integer max1 = null;
4
        Integer max2 = null;
5
        Integer max3 = null;
6

7
        for (Integer n : nums) {
8
            if (n.equals(max1) || n.equals(max2) || n.equals(max3)) {
9
                continue;
10
            }
11

12
            if (max1 == null || n > max1) {
13
                max3 = max2;
14
                max2 = max1;
15
                max1 = n;
16
            } else if (max2 == null || n > max2) {
17
                max3 = max2;
18
                max2 = n;
19
            } else if (max3 == null || n > max3) {
20
                max3 = n;
21
            }
22
        }
23

24
        return max3 == null ? max1 : max3;
25
    }
26
}

1
class Solution {
2
    public int thirdMax(int[] nums) {
3
        PriorityQueue<Integer> pq = new PriorityQueue<>();
4
        Set<Integer> set = new HashSet<>();
5

6
        for (int n : nums) {
7
            if (set.add(n)) {
8
                pq.offer(n);
9

10
                if (pq.size() > 3) {
11
                    pq.poll();
12
                }
13
            }
14
        }
15

16
        if (pq.size() == 2) {
17
            pq.poll();
18
        }
19
        return pq.peek();
20
    }
21
}

1
class Solution {
2
    public String addStrings(String num1, String num2) {
3
        StringBuilder result = new StringBuilder();
4
        int carry = 0;
5
        int len1 = num1.length() - 1;
6
        int len2 = num2.length() - 1;
7

8
        while (len1 >= 0 || len2 >= 0) {
9
            int x = len1 >= 0 ? num1.charAt(len1) - '0' : 0;
10
            int y = len2 >= 0 ? num2.charAt(len2) - '0' : 0;
11
            int sum = (x + y + carry) % 10;
12
            carry = (x + y + carry) / 10;
13
            result.append(sum);
14
            len1--;
15
            len2--;
16
        }
17

18
        if (carry != 0) {
19
            result.append(carry);
20
        }
21
        return result.reverse().toString();
22
    }
23
}

1
class Solution {
2
    public boolean canPartition(int[] nums) {
3
        int sum = 0;
4
        for (int val: nums) sum += val;
5
        if (sum % 2 == 1) {
6
            return false;
7
        }
8
        sum /= 2;
9

10
        Boolean[] dp = new Boolean[sum + 1];
11
        dp[0] = true;
12
        boolean result = canPartition(sum, 0, nums, dp);
13
        return result;
14
    }
15

16
    private boolean canPartition(int sum, int pos, int[] nums, Boolean[] dp) {
17
        if (sum == 0) {
18
            return true;
19
        }
20
        if (sum < 0 || pos == nums.length) {
21
            return false;
22
        }
23
        if (dp[sum] != null) {
24
            return dp[sum];
25
        }
26

27
        dp[sum] = canPartition(sum - nums[pos], pos + 1, nums, dp) || canPartition(sum, pos + 1, nums, dp);
28
        return dp[sum];
29
    }
30
}

1
class Solution {
2
    public List<List<Integer>> pacificAtlantic(int[][] matrix) {
3
        List<List<Integer>> result = new ArrayList<>();
4
        if (matrix.length == 0 || matrix[0].length == 0) {
5
            return result;
6
        }
7

8
        int m = matrix.length;
9
        int n = matrix[0].length;
10
        boolean[][] pacific = new boolean[m][n];
11
        boolean[][] atlantic = new boolean[m][n];
12

13
        // top and bottom
14
        for (int col = 0; col < n; col++) {
15
            dfs(matrix, 0, col, matrix[0][col], pacific);
16
            dfs(matrix, m-1, col, matrix[m-1][col], atlantic);
17
        }
18

19
        // left and right
20
        for (int row = 0; row < m; row++) {
21
            dfs(matrix, row, 0, matrix[row][0], pacific);
22
            dfs(matrix, row, n-1, matrix[row][n-1], atlantic);
23
        }
24

25
        // find all grids that meet requirements
26
        for (int i = 0; i < m; i++) {
27
            for (int j = 0; j < n; j++) {
28
                if (pacific[i][j] && atlantic[i][j]) {
29
                    List<Integer> temp = new ArrayList();
30
                    temp.add(i);
31
                    temp.add(j);
32
                    result.add(temp);
33
                }
34
            }
35
        }
36

37
        return result;
38
    }
39

40
    private void dfs(int[][] matrix, int r, int c, int preHeight, boolean[][] ocean) {
41
        // skip out-of-bound & higher flow & visited cases
42
        if (r < 0 || c < 0 || r > matrix.length-1 || c > matrix[0].length-1 || matrix[r][c] < preHeight || ocean[r][c]) {
43
            return;
44
        }
45

46
        ocean[r][c] = true;
47
        dfs(matrix, r - 1, c, matrix[r][c], ocean); // up
48
        dfs(matrix, r + 1, c, matrix[r][c], ocean); // down
49
        dfs(matrix, r, c - 1, matrix[r][c], ocean); // left
50
        dfs(matrix, r, c + 1, matrix[r][c], ocean); // right
51
    }
52
}

1
class Solution {
2
    public int wordsTyping(String[] sentence, int rows, int cols) {
3
        // a new line which is starting with certain index in sentence, what is the starting index of next line
4
        int[] nextIndex = new int[sentence.length];
5

6
        // how many times the pointer in current line passes over the last index
7
        int[] times = new int[sentence.length];
8

9
        for (int i = 0; i < sentence.length; i++) {
10
            int curLen = 0;
11
            int cur = i;
12
            int time = 0;
13

14
            while (curLen + sentence[cur].length() <= cols) {
15
                // word + space
16
                curLen += sentence[cur].length() + 1;
17
                cur++;
18

19
                // the whole sentence is added for a time
20
                if (cur == sentence.length) {
21
                    cur = 0;
22
                    time++;
23
                }
24
            }
25

26
            // stop at the first word of next line and times of the previous line
27
            nextIndex[i] = cur;
28
            times[i] = time;
29
        }
30

31
        int result = 0;
32
        int cur = 0; // start from the first word in the sentence
33
        for (int i = 0; i < rows; i++) {
34
            result += times[cur];
35
            cur = nextIndex[cur]; // update start of next row
36
        }
37

38
        return result;
39
    }
40
}

1
class Solution {
2
    public int countBattleships(char[][] board) {
3
        if (board.length == 0 || board[0].length == 0) {
4
            return 0;
5
        }
6

7
        int result = 0;
8
        for (int i = 0; i < board.length; i++) {
9
            for (int j = 0; j < board[0].length; j++) {
10
                if (board[i][j] == '.') {
11
                    continue;
12
                }
13

14
                // 1 x N or N x 1, thus we can always check left or up grid to determine the same battleship
15
                if ((i > 0 && board[i-1][j] == 'X') || (j > 0 && board[i][j-1] == 'X')) {
16
                    continue;
17
                }
18
                result++;
19
            }
20
        }
21

22
        return result;
23
    }
24
}