Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This problem is derived from the “Combination Sum” problem.

The solution is the “Combination Sum” solution plus some duplication avoidance technique.

Solution

Main part of this solution is same as “Combination Sum”. There is only 2 lines of code that needs to be added/modified.

First change, When go into the next recursive call, instead of:

helper(ans, cand, path, i, len, target - cand[i]);

Change it to

helper(ans, cand, path, i + 1, len, target - cand[i]);

Second change, inside the for-loop, instead of getting next element right away, we get the element with different value. The additional code is:

if (i > pos && candidates[i] == candidates[i - 1]) {
    continue;
}

My code

public class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        if (candidates == null || candidates.length == 0) {
            return ans;
        }
        Arrays.sort(candidates);
        int len = candidates.length;
        helper(ans, candidates, new ArrayList<Integer>(), 0, len, target);
        return ans;
    }

    private void helper(List<List<Integer>> ans, int[] cand, List<Integer> path, int pos, int len, int target) {
        if (target == 0) {
            ans.add(new ArrayList<Integer>(path));
            return;
        } else if (target < 0) {
            return;
        }
        for (int i = pos; i < len; i++) {
            // if 'i' points to a repeated number, skip.
            if (i > pos && cand[i] == cand[i - 1]) {
                continue;
            }
            // insert cand[i] into path list, and continue search dfs
            path.add(cand[i]);
            helper(ans, cand, path, i + 1, len, target - cand[i]);
            path.remove(path.size() - 1);
        }
    }
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is an NP problem.

It can be solved with basic recursion methods. I refered to this blog for the idea.

Solution

Recursively fetch the next element and subtract the value from the target. In the end, if target happen to be 0, then one solution is found. If target result to be less than 0, return. If larger than 0, continue.

My code

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        if (candidates == null || candidates.length == 0) {
            return ans;
        }
        Arrays.sort(candidates);
        int len = candidates.length;
        helper(ans, candidates, new ArrayList<Integer>(), 0, len, target);
        return ans;
    }

    private void helper(List<List<Integer>> ans, int[] cand, List<Integer> path, int pos, int len, int target) {
        if (target == 0) {
            ans.add(new ArrayList<Integer>(path));
            return;
        } else if (target < 0) {
            return;
        }
        for (int i = pos; i < len; i++) {
            // insert cand[i] into path list, and continue search dfs
            path.add(cand[i]);
            helper(ans, cand, path, i, len, target - cand[i]);
            path.remove(path.size() - 1);
        }
    }
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Solution

This is not a difficult problem.

Make use of three for-loops and nine arrays of length 9 (for each loop) to mark the status, then do DFS search.

However, I also found a very concise solution. Read below.

My code

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        if (board == null || board.length == 0) {
            return false;
        }
        int N = board.length;
        for (int i = 0; i < N; i++) {
            boolean[] foo = new boolean[N];
            // validate each row
            for (int j = 0; j < N; j++) {
                if (board[i][j] != '.') {
                    if (foo[board[i][j] - '1']) {
                        return false;
                    }
                    foo[board[i][j] - '1'] = true;
                }
            }
            foo = new boolean[N];
            // validate each column
            for (int j = 0; j < N; j++) {
                if (board[j][i] != '.') {
                    if (foo[board[j][i] - '1']) {
                        return false;
                    }
                    foo[board[j][i] - '1'] = true;
                }
            }
        }
        for (int a = 0; a < 3; a++) {
            for (int b = 0; b < 3; b++) {
                boolean[] foo = new boolean[N];
                for (int c = 0; c < 3; c++) {
                    for (int d = 0; d < 3; d++) {
                        if (board[a * 3 + c][b * 3 + d] != '.') {
                            if (foo[board[a * 3 + c][b * 3 + d] - '1']) {
                                return false;
                            }
                            foo[board[a * 3 + c][b * 3 + d] - '1'] = true;
                        }
                    }
                }
            }
        }
        return true;
    }
}

The following solution is from this blog. It’s a very clever and surprisingly concise code.

public boolean isValidSudoku(char[][] board) {
    boolean[][] rows = new boolean[9][9];
    boolean[][] cols = new boolean[9][9];
    boolean[][] blocks = new boolean[9][9];
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            int c = board[i][j] - '1';
            if (board[i][j] == '.') continue;
            if (rows[i][c] || cols[j][c] || blocks[i - i % 3 + j / 3][c])
                return false;
            rows[i][c] = cols[j][c] = blocks[i - i % 3 + j / 3][c] = true;
        }
    }
    return true;
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This question is not very difficult, yet commonly seen in interviews.

Without having any knowledge of pivot, we can check the mid-point value against left value and right value. Read this blog for more.

Solution

The code is easy to understand.

My code

Pay special attention to different larger/smaller conditions. It’s very easy to miss a equal sign or something.

public class Solution {
    public int search(int[] A, int target) {
        if (A == null || A.length == 0) {
            return -1;
        }
        int len = A.length;
        int left = 0; 
        int right = len - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (A[mid] == target) {
                return mid;
            } else if (A[left] < A[mid]) {
            // remember to pay attention to (A[left] == target) case
                if (A[left] <= target && target < A[mid]) {
                    right = mid;
                } else {
                    left = mid;
                }
            } else {
            // remember to pay attention to (A[right] == target) case
                if (A[mid] < target && target <= A[right]) {
                    left = mid;
                } else {
                    right = mid;
                }
            }
        }
        if (A[left] == target) {
            return left;
        } else if (A[right] == target) {
            return right;
        }
        return -1;
    }
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Solution

The key to solve this problem is binary search. Previously my solution is to find the element first, then check left bound and right bound respectively. In worst case, this will take O(n) time. This method, though, will pass OJ, but is not an optimized solution.

First solution is from this blog. Using binary search to search twice - once for left bound, and once for right bound. Code is below.

Second solution is from this blog. This idea is still using binary search, also search twice, but a more tricky manner. Instead of searching the number, it searches (number - 0.5) and (number + 0.5).

My code

Solution 1

public class Solution {
    public int[] searchRange(int[] A, int target) {
        int[] ans = new int[] {-1, -1};
        if (A == null || A.length == 0) {
            return ans;
        }
        int len = A.length;
        int left = 0, right = len - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (A[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        if (A[left] == target) {
            ans[0] = left;
        } else {
            return ans;
        }
        left = 0;
        right = len - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (A[mid] <= target) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        ans[1] = right;
        return ans;
    }
}

Solution 2

public int[] searchRange(int[] A, int target) {
    if (A == null) return null;
    int[] result = { -1, -1 };
    int low = binarySearch(A, target - 0.5);
    // Be care for there , low>=A.length must be checked
    if (low >= A.length || A[low] != target) return result;
    result[0] = low;
    result[1] = binarySearch(A, target + 0.5) - 1;
    return result;
}

public int binarySearch(int[] A, double t) {
    int low = 0, high = A.length - 1;
    while (low <= high) {
        int m = (low + high) / 2;
        if (A[m] < t) low = m + 1;
        if (A[m] > t) high = m - 1;
    }
    return low;
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a very basic, yet very difficult question. It is not easy to get it correct at first attempt.

Read this blog for more.

My code

public class Solution {
    public int searchInsert(int[] A, int target) {
        if (A == null || A.length == 0) {
            return 0;
        }
        int len = A.length;
        int left = 0;
        int right = len - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (A[mid] >= target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        // now are have a adjacent range [left, right]
        if (target <= A[left]) {
            return left;
        } else if (target <= A[right]) {
            // remember not to miss the == case
            return right;
        } else {
            return right + 1;
        }
    }
}

Question

link

Stats

Analysis

The image below explains the solution very well (for the input number “687432”).

Solution

Read this blog for a very nice piece of code.

The following code is written by me.

My code

public class Solution {
    public void nextPermutation(int[] num) {
        if (num == null || num.length <= 1) {
            return;
        }
        int len = num.length;
        int p = len - 2;
        // note that when values are equals, proceed the pointer! 
        // same for line 22
        while (p >= 0 && num[p] >= num[p + 1]) {
            // move p to left as long as its value is larger than next num
            // we want to find the end of increasing sequence (from end to start)
            p--;
        }
        if (p == -1) {
            // the input is a strictly decreasing sequence
            Arrays.sort(num);
            return;
        }
        // replace number at p with an larger value found in the right of p
        int w = len - 1;
        while (num[w] <= num[p]) {
            w--;
        }
        // ok, now swap number at p and w
        swop(num, p, w);
        // reverse all numbers to the right of p
        reverse(num, p + 1, len - 1);
    }

    private void swop(int[] num, int a, int b) {
        int temp = num[a];
        num[a] = num[b];
        num[b] = temp;
    }

    private void reverse(int[] num, int a, int b) {
        while (a < b) {
            swop(num, a++, b--);
        }
    }
}

Question

link

Stats

Solution

There are 2 ways to solve this problem, stack and DP.

Stack method 1 is more straight-forward (code shown below). The idea is to keep a stack of “(” indexes, and another variable called “last”. Note that only “)” can violates a pattern. So whenever I see a “(”, just push to stack. When the pattern is violated by a “)”, I update “last”. The code explains itself very well. If not, look here

Stack method 2 is more tricky. This time I will not only push the index of “(” to stack, but also the index of “)” when the pattern got violated. It’s hard to explain, and hard to think of at first.

The DP solution is not very difficult. Basically create an array of same length as string s. dp[i] denotes the length of valid parenthese ending with index i. The idea is similar to this blog, but he used reverse DP, and I use normal DP.

I will explain DP with an example of input “)()()”. For this string, we have dp[0] = 0, dp[1] = 0, dp[2] = 2, dp[3] = 0. For dp[4], I check the 3rd position first, and find that dp[4] = 2. Then I also have to add dp[2] into dp[4] to make it complete. The end result is dp[4] = 2 + 2 = 4.

My code

Stack method 1 (recommended)

public class Solution {
    public int longestValidParentheses(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int len = s.length();
        int longest = 0;
        Stack<Integer> stack = new Stack<Integer>();
        int start = 0;
        for (int i = 0; i < len; i++) {
            char ch = s.charAt(i);
            if (ch == '(') {
                // well, no matter what, '(' is alway a valid part
                // push the index to the stack
                stack.push(i);
            } else if (ch == ')') {
                if (stack.isEmpty()) {
                    // invalid ')', update 'start' variable
                    start = i + 1;
                } else {
                    int pos = stack.pop();
                    if (stack.isEmpty()) {
                        // this is why we need 'start' variable
                        longest = Math.max(longest, i - start + 1);
                    } else {
                        // important: must peek stack again.
                        // eg. (()()  if don't peek again 
                        longest = Math.max(longest, i - stack.peek());
                    }
                }
            }
        }
        return longest;
    }
}

Stack method 2

public int longestValidParentheses(String s) {
    int res = 0;
    Stack<Integer> stack = new Stack<Integer>();
    char[] arr = s.toCharArray();
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == ')' && !stack.isEmpty() && arr[stack.peek()] == '(') {
            stack.pop();
            if (stack.isEmpty()) res = i + 1;
            else res = Math.max(res, i - stack.peek());
        } else stack.push(i);
    }
    return res;
}

DP

public int longestValidParentheses(String s) {
    int len = s.length();
    if (len <= 1) return 0;
    int max = Integer.MIN_VALUE;
    int[] dp = new int[len];
    for (int i = 1; i < len; i ++) {
        if (s.charAt(i) == '(') dp[i] = 0;
        else {
            int j = i - 1 - dp[i - 1];
            if (j >= 0 && s.charAt(j) =='(') {
                dp[i] = dp[i - 1] + 2;
                if (j >= 1) dp[i] += dp[j - 1];
            }
            else dp[i] = 0;
        }
        max = Math.max(max, dp[i]);
    }
    return max;
}

Definition

A heap is a specialized tree-based data structure that satisfies the heap property:

If A is a parent node of B, then the key of node A is ordered with respect to the key of node B with the same ordering applying across the heap.

Heaps can then be classified further as either “max heap” and “min heap”.

Details

We take max heap for example. The keys of parent nodes are always greater than or equal to the children node.

The heap is an implementation of priority queue. In fact, priority queues are often referred to as “heaps”, regardless of how they may be implemented.

Note that despite the similarity of the name “heap” to “stack” and “queue”, the latter two are abstract data types, while a heap is a specific data structure, and “priority queue” is the proper term for the abstract data type.

Insert

1. Add the element to the bottom level of the heap.

2. Compare the added element with its parent; if they are in the correct order, stop.

3. If not, swap the element with its parent and return to the previous step.

The number of operations required is dependent on the number of levels the new element must rise to satisfy the heap property, thus the insertion operation has a time complexity of O(log n).

Delete

1. Replace the root of the heap with the last element on the last level.

2. Compare the new root with its children; if they are in the correct order, stop.

3. If not, swap the element with one of its children and return to the previous step. (Swap with its smaller child in a min-heap and its larger child in a max-heap.)

Time complexity

How about building a heap?

It’s O(n).

Why? You may ask - “why not O(nlgn) like we do successive insert for n time”?

Read answers from stackoverflow.

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

The problem is solved in 2 steps. First, get the next k-group. If remaining items is less than k, terminate the program. Otherwise, reserve this k-group and keep going.

To solve this question is very tricky. We need to be clear about this: 4 nodes need to be kept track of: 2 elements before and after the k-group, and 2 elements within the k-group.

The difficult point is while and after reverse the k-group, how to maintain the ‘pre’ node and future ‘pre’ node correctly.

Solution

Use Linkedlist Template from NineChap to solve.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (k <= 1 || head == null) {
            return head;
        }
        ListNode nextGroup = head;
        for (int i = 0; i < k; i++) {
            if (nextGroup == null) {
                // there isn't k nodes in this list
                return head;
            }
            nextGroup = nextGroup.next;
        }
        // now we're sure the list have at least k nodes
        // reverse this list (by re-connecting the next pointer k times)
        ListNode newHead = head;
        ListNode tail = null;
        for (int i = 0; i < k; i++) {
            ListNode temp = newHead.next;
            newHead.next = tail;
            tail = newHead;
            newHead = temp;
        }
        // now newHead is pointing to the actual new head
        // temp (which is not accessable here) is same as nextGroup
        // last step, reconnect everything and call recursion method
        head.next = reverseKGroup(nextGroup, k);
        return tail;
    }
}