LeetCode 201-300

1
class Solution {
2
    public int rangeBitwiseAnd(int left, int right) {
3
        if (left == 0) {
4
            return 0;
5
        }
6

7
        int count = 0;
8
        while (left != right) {
9
            left >>>= 1;
10
            right >>>= 1;
11
            count++;
12
        }
13

14
        return left <<= count;
15
    }
16
}

1
class Solution {
2
    public boolean isHappy(int n) {
3
        int result = 0, current = 0;
4
        while (result != 1) {
5

6
            // calculate current result
7
            while (n != 0) {
8
                current = n % 10;
9
                n /= 10;
10
                result += current * current;
11
            }
12

13
            // result cannot be 1 or 4, otherwise fall into loop
14
            if (result > 1 && result != 4) {
15
                n = result;
16
                result = 0;
17
            } else {
18
                break;
19
            }
20
        }
21

22
        return result == 1;
23
    }
24
}

1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode removeElements(ListNode head, int val) {
13
        if (head == null) {
14
            return head;
15
        }
16

17
        ListNode dummyHead = new ListNode(0);
18
        dummyHead.next = head;
19

20
        ListNode prev = dummyHead, cur = head;
21
        while (cur != null) {
22
            // when current element's value is val, skip
23
            if (cur.val == val) {
24
                prev.next = cur.next;
25
            } else {
26
                prev = prev.next;
27
            }
28

29
            // always move forward cur
30
            cur = cur.next;
31
        }
32

33
        return dummyHead.next;
34
    }
35
}

1
class Solution {
2
    public int countPrimes(int n) {
3
        if (n < 3) {
4
            return 0;
5
        }
6

7
        boolean[] prime = new boolean[n];
8
        Arrays.fill(prime, true);
9

10
        // assume all odd numbers are prime number
11
        int result = n / 2;
12

13
        for (int i = 3; i * i < n; i += 2) {
14
            // skip a composite number
15
            if (!prime[i]) {
16
                continue;
17
            }
18

19
            // multiples of composite numbers are skipped
20
            for (int j = i * i; j < n; j += 2 * i) {
21
                // this multiple of i has not been excluded
22
                if (prime[j]) {
23
                    result--;
24
                    prime[j] = false;
25
                }
26
            }
27
        }
28

29
        return result;
30
    }
31
}

1
class Solution {
2
    public boolean isIsomorphic(String s, String t) {
3
        if (s.length() != t.length()) {
4
            return false;
5
        }
6

7
        char[] sChars = s.toCharArray();
8
        char[] tChars = t.toCharArray();
9

10
        char[] sMap = new char[256];
11
        char[] tMap = new char[256];
12

13
        for (int i = 0; i < sChars.length; i++) {
14
            char a = sChars[i], b = tChars[i];
15

16
            // not yet mapped
17
            if (sMap[a] == 0 && tMap[b] == 0) {
18
                sMap[a] = b;
19
                tMap[b] = a;
20
            } else if (sMap[a] != b || tMap[b] != a) {
21
                return false;
22
            }
23
        }
24

25
        return true;
26
    }
27
}

1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode reverseList(ListNode head) {
13
        if (head == null) {
14
            return null;
15
        }
16

17
        ListNode prev = null;
18
        while (head != null) {
19
            ListNode next = head.next;
20
            head.next = prev;
21

22
            prev = head;
23
            head = next;
24
        }
25

26
        return prev;
27
    }
28
}

1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode() {}
7
 *     ListNode(int val) { this.val = val; }
8
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9
 * }
10
 */
11
class Solution {
12
    public ListNode reverseList(ListNode head) {
13
        return reverse(head, null);
14
    }
15

16
    private ListNode reverse(ListNode head, ListNode prev) {
17
        if (head == null) {
18
            return prev;
19
        }
20

21
        ListNode next = head.next;
22
        head.next = prev;
23
        return reverse(next, head);
24
    }
25
}

1
class Solution {
2
    boolean isCycle = false;
3

4
    public boolean canFinish(int numCourses, int[][] prerequisites) {
5

6
        List<List<Integer>> graph = new ArrayList<>();
7
        for (int i = 0; i < numCourses; i++) {
8
            graph.add(new ArrayList<Integer>());
9
        }
10

11
        // add all subsequent courses for each course
12
        for (int[] prerequisite : prerequisites)
13
            graph.get( prerequisite[1] ).add( prerequisite[0] );
14

15
        int[] courseStatus = new int[numCourses];
16
        for (int i = 0; i < numCourses; i++) {
17
            if (courseStatus[i] == 0) {
18
                dfs(courseStatus, i, graph);
19
            }
20
        }
21

22
        return !isCycle;
23
    }
24

25
    // 0 unvisited, 1 visiting, 2 visited
26
    private void dfs(int[] courseStatus, int node, List<List<Integer>> graph) {
27
        courseStatus[node] = 1;
28

29
        for (int next : graph.get(node)) {
30
            if (courseStatus[next] == 0) {
31
                dfs(courseStatus, next, graph);
32
            }
33

34
            if (courseStatus[next] == 1) {
35
                isCycle = true;
36
            }
37
        }
38

39
        courseStatus[node] = 2;
40
    }
41
}

1
class Trie {
2

3
    class TrieNode {
4
        public TrieNode() {}
5
        boolean isEnd = false;
6
        TrieNode[] children = new TrieNode[26];
7
    }
8

9
    private TrieNode root = new TrieNode();
10

11
    /** Initialize your data structure here. */
12
    public Trie() {}
13

14
    /** Inserts a word into the trie. */
15
    public void insert(String word) {
16
        TrieNode cur = root;
17
        for (char c : word.toCharArray()) {
18
            if (cur.children[c - 'a'] == null) {
19
                cur.children[c - 'a'] = new TrieNode();
20
            }
21
            cur = cur.children[c - 'a'];
22
        }
23

24
        cur.isEnd = true;
25
    }
26

27
    /** Returns if the word is in the trie. */
28
    public boolean search(String word) {
29
        TrieNode cur = root;
30
        for (char c : word.toCharArray()) {
31
            if (cur.children[c - 'a'] == null) {
32
                return false;
33
            }
34
            cur = cur.children[c - 'a'];
35
        }
36

37
        // must exactly match, so the word in trie should also end
38
        return cur.isEnd;
39
    }
40

41
    /** Returns if there is any word in the trie that starts with the given prefix. */
42
    public boolean startsWith(String prefix) {
43
        TrieNode cur = root;
44
        for (char c : prefix.toCharArray()) {
45
            if (cur.children[c - 'a'] == null) {
46
                return false;
47
            }
48
            cur = cur.children[c - 'a'];
49
        }
50

51
        return true;
52
    }
53
}

1
class Solution {
2
    public int minSubArrayLen(int s, int[] nums) {
3
        if (nums == null || nums.length == 0) {
4
            return 0;
5
        }
6

7
        int sum = 0, left = 0, right = 0;
8

9
        // By default, the minimum length is Max integer
10
        int result = Integer.MAX_VALUE;
11

12
        while (right < nums.length) {
13
            sum += nums[right];
14
            right++;
15

16
            // delete as many nums[left] as possible
17
            while (sum >= s) {
18
                result = Math.min(result, right - left);
19
                sum -= nums[left];
20
                left++;
21
            }
22
        }
23

24
        return result == Integer.MAX_VALUE ? 0 : result;
25
    }
26
}

1
class Solution {
2
    boolean isCycle = false;
3
    int[] result;
4
    int resultIndex;
5

6
    public int[] findOrder(int numCourses, int[][] prerequisites) {
7
        result = new int[numCourses];
8
        resultIndex = numCourses - 1; // start from the last course
9

10
        List<List<Integer>> graph = new ArrayList<>();
11
        for (int i = 0; i < numCourses; i++) {
12
            graph.add(new ArrayList<Integer>());
13
        }
14

15
        // add all subsequent courses for each course
16
        for (int[] prerequisite : prerequisites) {
17
            graph.get( prerequisite[1] ).add( prerequisite[0] );
18
        }
19

20
        int[] courseStatus = new int[numCourses];
21
        for (int i = 0; i < numCourses; i++) {
22
            if (courseStatus[i] == 0) {
23
                dfs(courseStatus, i, graph);
24
            }
25
        }
26

27
        return isCycle ? new int[]{} : result;
28
    }
29

30
    // 0 unvisited, 1 visiting, 2 visited
31
    private void dfs(int[] courseStatus, int node, List<List<Integer>> graph) {
32
        courseStatus[node] = 1;
33

34
        for (int next : graph.get(node)) {
35
            if (courseStatus[next] == 0) {
36
                dfs(courseStatus, next, graph);
37
            }
38

39
            if (courseStatus[next] == 1) {
40
                isCycle = true;
41
            }
42
        }
43

44
        courseStatus[node] = 2;
45

46
        result[resultIndex] = node;
47
        resultIndex--;
48
    }
49
}

1
class WordDictionary {
2

3
    public class TrieNode {
4
        public TrieNode() {}
5
        TrieNode[] children = new TrieNode[26];
6
        boolean isEnd = false;
7

8
        public boolean match(String word, int index) {
9
            if (index == word.length()) {
10
                return isEnd;
11
            }
12

13
            // check all not-null children
14
            if (word.charAt(index) == '.') {
15
                for (int i = 0 ; i < 26; i++) {
16
                    if (children[i] != null && children[i].match(word, index + 1)) {
17
                        return true;
18
                    }
19
                }
20

21
                return false;
22
            } else {
23
                return children[word.charAt(index) - 'a'] != null && children[word.charAt(index) - 'a'].match(word, index + 1);
24
            }
25
        }
26
    }
27

28
    private TrieNode root = new TrieNode();
29

30
    /** Initialize your data structure here. */
31
    public WordDictionary() {}
32

33
    /** Adds a word into the data structure. */
34
    public void addWord(String word) {
35
        TrieNode cur = root;
36
        for (char c : word.toCharArray()) {
37
            if (cur.children[c - 'a'] == null) {
38
                cur.children[c - 'a'] = new TrieNode();
39
            }
40

41
            cur = cur.children[c - 'a'];
42
        }
43

44
        cur.isEnd = true;
45
    }
46

47
    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
48
    public boolean search(String word) {
49
        return root.match(word, 0);
50
    }
51
}

1
class Solution {
2
    public class TrieNode {
3
        TrieNode[] children = new TrieNode[26];
4
        String word;
5
    }
6

7
    public TrieNode buildTrie(String[] words) {
8
        TrieNode root = new TrieNode();
9

10
        for (String word : words) {
11
            TrieNode cur = root;
12
            for (char c : word.toCharArray()) {
13
                if (cur.children[c - 'a'] == null) {
14
                    cur.children[c - 'a'] = new TrieNode();
15
                }
16
                cur = cur.children[c - 'a'];
17
            }
18

19
            // only set cur.word when finishing inserting a word
20
            cur.word = word;
21
        }
22

23
        return root;
24
    }
25

26
    public List<String> findWords(char[][] board, String[] words) {
27
        List<String> result = new ArrayList<>();
28
        TrieNode root = buildTrie(words);
29

30
        for (int i = 0; i < board.length; i++) {
31
            for (int j = 0; j < board[0].length; j++) {
32
                dfs(board, i, j, root, result);
33
            }
34
        }
35

36
        return result;
37
    }
38

39
    public void dfs(char[][] board, int i, int j, TrieNode cur, List<String> result) {
40
        char c = board[i][j];
41
        if (c == '#' || cur.children[c - 'a'] == null) {
42
            return;
43
        }
44
        cur = cur.children[c - 'a'];
45

46
        // end of current word
47
        if (cur.word != null) {
48
            result.add(cur.word);
49

50
            // avoid repeat searching
51
            cur.word = null;
52
        }
53

54
        // temporarily mark visited character
55
        board[i][j] = '#';
56

57
        // try four adjacent grids
58
        if (i > 0) {
59
            dfs(board, i - 1, j, cur, result);
60
        }
61
        if (j > 0) {
62
            dfs(board, i, j - 1, cur, result);
63
        }
64
        if (i < board.length - 1) {
65
            dfs(board, i + 1, j, cur, result);
66
        }
67
        if (j < board[0].length - 1) {
68
            dfs(board, i, j + 1, cur, result);
69
        }
70

71
        board[i][j] = c;
72
    }
73
}

1
class Solution {
2
    private int helper(int[] nums, int low, int high) {
3

4
        // prev2: max profit without current number's prior number
5
        // prev: max profit between (1. without current number 2. prev2 + current number)
6
        int prev2 = 0, prev = 0;
7

8
        for (int i = low; i <= high; i++) {
9
            int temp = prev;
10
            prev = Math.max(prev, prev2 + nums[i]);
11
            prev2 = temp;
12
        }
13

14
        return prev;
15
    }
16

17
    public int rob(int[] nums) {
18
        if (nums == null || nums.length == 0) {
19
            return 0;
20
        } else if (nums.length == 1) {
21
            return nums[0];
22
        }
23

24
        return Math.max(helper(nums, 0, nums.length - 2), helper(nums, 1, nums.length - 1));
25
    }
26
}

1
class Solution {
2
    public String shortestPalindrome(String s) {
3
        if (s.length() == 0 || s.length() == 1) {
4
            return s;
5
        }
6

7
        // try to divide the string into two parts, using head
8
        int head = 0;
9
        for (int tail = s.length() - 1; tail >= 0; tail--) {
10
            if (s.charAt(head) == s.charAt(tail)) {
11
                head++;
12
            }
13
        }
14

15
        // already a palindrome
16
        if (head == s.length()) {
17
            return s;
18
        }
19

20
        String suffix = s.substring(head);
21
        return new StringBuilder(suffix).reverse().toString() + shortestPalindrome(s.substring(0, head)) + suffix;
22
    }
23
}

1
class Solution {
2
    public int findKthLargest(int[] nums, int k) {
3
        if (nums == null || nums.length == 0) {
4
            return -1;
5
        }
6

7
        // kth largest is equal to (nums.length - k)th smallest
8
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
9
    }
10

11
    // quick select: kth smallest
12
    public int quickSelect(int[] nums, int begin, int end, int k) {
13
        if (begin == end) {
14
            return nums[begin];
15
        }
16
        if (begin > end) {
17
            return Integer.MAX_VALUE;
18
        }
19

20
        int pivot = nums[begin + (end - begin) / 2];
21
        int left = begin;
22
        int right = end;
23

24
        while (left <= right) {
25
            while (left <= right && nums[left] < pivot) {
26
                left++;
27
            }
28
            while (left <= right && nums[right] > pivot) {
29
                right--;
30
            }
31

32
            if (left <= right) {
33
                swap(nums, left, right);
34
                left++;
35
                right--;
36
            }
37
        }
38

39
        if (right >= k && right >= begin) {
40
            return quickSelect(nums, begin, right, k);
41
        } else if (left <= k && left <= end) {
42
            return quickSelect(nums, left, end, k);
43
        } else {
44
            return nums[k];
45
        }
46
    }
47

48
    private void swap(int[] A, int i, int j) {
49
        int temp = A[i];
50
        A[i] = A[j];
51
        A[j] = temp;
52
    }
53
}

1
class Solution {
2
    public List<List<Integer>> combinationSum3(int k, int n) {
3
        List< List<Integer> > result = new ArrayList<>();
4
        backtrack(result, new ArrayList<>(), k, n, 1);
5
        return result;
6
    }
7

8
    private void backtrack(List< List<Integer> > result, List<Integer> temp, int k, int n, int start) {
9
        if (temp.size() == k && n == 0) {
10
            result.add(new ArrayList<>(temp));
11
            return;
12
        }
13

14
        for (int i = start; i <= 9; i++) {
15
            temp.add(i);
16

17
            // need k numbers; remain sum is n - i; starting index is i + 1
18
            backtrack(result, temp, k, n - i, i + 1);
19
            temp.remove(temp.size() - 1);
20
        }
21
    }
22
}

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

7
        Set<Integer> set = new HashSet<Integer>();
8
        for (Integer num : nums) {
9
            if (!set.add(num)) {
10
                return true;
11
            }
12
        }
13

14
        return false;
15
    }
16
}

1
class Solution {
2
    public List<List<Integer>> getSkyline(int[][] buildings) {
3
        List<List<Integer>> result = new ArrayList();
4

5
        List<int[]> height = new ArrayList();
6
        for (int[] b : buildings) {
7
            height.add(new int[]{b[0], -b[2]});
8
            height.add(new int[]{b[1], b[2]});
9
        }
10

11
        // first sort by x coordinate, then sort by height
12
        Collections.sort(height, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
13

14
        // <height, num>
15
        TreeMap<Integer, Integer> bst = new TreeMap();
16
        bst.put(0, 1);
17
        int prev = 0;
18

19
        for (int[] h : height) {
20

21
            if (h[1] < 0) {
22
                // a new building is incoming
23
                bst.put(-h[1], bst.getOrDefault(-h[1], 0) + 1);
24
            } else if (bst.get(h[1]) == 1) {
25
                // current highest building reaches end, should output second highest building later
26
                bst.remove(h[1]);
27
            } else {
28
                bst.put(h[1], bst.get(h[1]) - 1);
29
            }
30

31
            // output highest new building
32
            int cur = bst.lastKey();
33
            if (cur != prev) {
34
                result.add(new ArrayList(Arrays.asList(h[0], cur)));
35
                prev = cur;
36
            }
37
        }
38

39
        return result;
40
    }
41
}

1
class Solution {
2
    public boolean containsNearbyDuplicate(int[] nums, int k) {
3
        Map<Integer, Integer> map = new HashMap<>();
4

5
        for (int i = 0; i < nums.length; i++) {
6
            // if not present, new entry, else the old entry will be updated
7
            Integer idx = map.put(nums[i], i);
8

9
            if (idx != null && Math.abs(idx - i) <= k) {
10
                return true;
11
            }
12
        }
13

14
        return false;
15
    }
16
}

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

7
        TreeSet<Long> set = new TreeSet<>();
8
        for (int i = 0; i < nums.length; i++) {
9
            long num = (long)nums[i];
10

11
            // get upper bound and lower bound of current num
12
            // find if there is any element in this range
13
            Long floor = set.floor(num), ceiling = set.ceiling(num);
14
            if ((floor != null && num - floor <= t) || (ceiling != null && ceiling - num <= t)) {
15
                return true;
16
            }
17

18
            // add current num to set
19
            set.add(num);
20

21
            // delete k-th number backward
22
            if (i >= k) {
23
                set.remove((long)nums[i - k]);
24
            }
25
        }
26

27
        return false;
28
    }
29
}