Question

link

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Stats

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

Analysis

This is a very classic problem.

The solution is standard, and we must be able to write it without even using our brain (only use hands).

Solution

Solution 1, recursive DFS calls.

Solution 2, nested loop. Code is shown below.

Code

First, my DFS solution

public ArrayList<ArrayList<Integer>> combine(int n, int k) {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
    if (k == 0) return ans;
    helper(ans, new ArrayList<Integer>(), n, k, 0, 0);
    return ans;
}

private void helper(ArrayList<ArrayList<Integer>> ans,ArrayList<Integer> list,
                    int n, int k, int curPt, int preNum) {
    if (curPt == k) {
        ans.add(new ArrayList<Integer>(list));
        return;
    }
    for (int i = preNum + 1; i <= n - k + 1 + curPt; i ++) {
        list.add(i);
        helper(ans, list, n, k, curPt + 1, i);
        list.remove(list.size() - 1);
    }
}

Second, my nested for-loop solution

public ArrayList<ArrayList<Integer>> combine(int n, int k) {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
    ans.add(new ArrayList<Integer>());
    if (n == 0 || k == 0 || k > n) return ans;
    ArrayList<ArrayList<Integer>> temp = null;
    for (int i = 0; i < k; i ++) {
        temp = new ArrayList<ArrayList<Integer>>();
        for (ArrayList<Integer> a: ans) {
            for (int j = 1; j <= n; j ++) {
                if (a.size() > 0 && a.get(a.size() - 1) >= j) 
                    continue;
                a.add(j);
                temp.add(new ArrayList<Integer>(a));
                a.remove(a.size() - 1);
            }
        }
        ans = temp;
    }
    return ans;
}

Updated June 14th, rewrote the code using template

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> ans = new LinkedList<List<Integer>>();
    if (n == 0 || k == 0 || n < k) {
        return ans;
    }
    helper(ans, new LinkedList<Integer>(), n, k, 1);
    return ans;
}

private void helper(List<List<Integer>> ans, List<Integer> path, int n, int k, int pos) {
    if (path.size() == k) {
        ans.add(new LinkedList<Integer>(path));
        return;
    }
    for (int i = pos; i <= n; i++) {
        path.add(i);
        helper(ans, path, n, k, i + 1);
        path.remove(path.size() - 1);
    }
}

Question

link

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

Stats

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

Solution

This is a very classical DFS question. Writing this solution fast and precise is very importnt.

The solution is recursive DFS search.

The second code posted below comes from this blog. The code is slightly shorter because it checks visited_array at the beginning of search() method, instead of for each directions. Other than that, it’s basically same solution.

Code

First, my code

public boolean exist(char[][] board, String word) {
    if (word.length() == 0) return true;
    int m = board.length, n = board[0].length;
    for (int i = 0; i < m; i ++) {
        for (int j = 0; j < n; j ++) {
            if (board[i][j] == word.charAt(0)) {
                int[][] visited = new int[m][n];
                visited[i][j] = 1;
                boolean ans = find(i, j, board, visited, word.substring(1));
                if (ans) return true;
            }
        }
    }
    return false;
}

private boolean find(int a, int b, char[][] board, int[][] visited, 
                    String word) {
    if (word.length() == 0) return true;
    int m = board.length, n = board[0].length;
    char target = word.charAt(0);
    if (a > 0 && visited[a-1][b] == 0 && board[a-1][b] == target) {
        visited[a - 1][b] = 1;
        boolean ans = find(a - 1, b, board, visited, word.substring(1));
        if (ans) return true;
        visited[a - 1][b] = 0;
    } // top
    if (a < m - 1 && visited[a+1][b] == 0 && board[a+1][b] == target) {
        visited[a + 1][b] = 1;
        boolean ans = find(a + 1, b, board, visited, word.substring(1));
        if (ans) return true;
        visited[a + 1][b] = 0;
    } // bottom
    if (b > 0 && visited[a][b-1] == 0 && board[a][b-1] == target) {
        visited[a][b - 1] = 1;
        boolean ans = find(a, b - 1, board, visited, word.substring(1));
        if (ans) return true;
        visited[a][b - 1] = 0;
    } // left
    if (b < n - 1 && visited[a][b+1] == 0 && board[a][b+1] == target) {
        visited[a][b + 1] = 1;
        boolean ans = find(a, b + 1, board, visited, word.substring(1));
        if (ans) return true;
        visited[a][b + 1] = 0;
    } // right
    return false;
}

Second, code from blog

public boolean exist(char[][] board, String word) {
    int height = board.length;
    int width = board[0].length;
    boolean[][] visited = new boolean[height][width];
    for (int i = 0; i < height; i++) 
        for (int j = 0; j < width; j++) 
            if (search(board, visited, i, j, word, 0)) 
                return true;
    return false;
}

private boolean search(char[][] board, boolean[][] visited, 
        int row, int col, String word, int index) {
    if (word.charAt(index) != board[row][col]) 
        return false;
    if (index == word.length() - 1) 
        return true;

    int height = board.length;
    int width = board[0].length;
    visited[row][col] = true;
    //up
    if (row > 0 && !visited[row - 1][col] 
            && search(board, visited, row - 1, col, word, index + 1)) 
        return true;
    //down
    if (row < height - 1 && !visited[row + 1][col] 
            && search(board, visited, row + 1, col, word, index + 1)) 
        return true;
    //left
    if (col > 0 && !visited[row][col - 1] 
            && search(board, visited, row, col - 1, word, index + 1)) 
        return true;
    //right
    if (col < width - 1 && !visited[row][col + 1] 
            && search(board, visited, row, col + 1, word, index + 1)) 
        return true;
    // if we did not find the path we need set this position as unvisited
    visited[row][col] = false;

    return false;
}

Question

link

Stats

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

Analysis

This is a classic question of math and CS. It’s easy, but there are a few magical solutions for this problem.

Solution

The most standard solution is using binary search. I have the code for that.

Newton’s method is a great way to solve this problem. It uses derivative to keep finding the next better approximation to the root of the value. There is a great article on this topic talking about Newton’s method, and some even faster implementations.

That article is definitely worth reading. I will quote a small propertion of it.

求出根号a的近似值：首先随便猜一个近似值x，然后不断令x等于x和a/x的平均数，迭代个六七次后x的值就已经相当精确了。
例如，我想求根号2等于多少。假如我猜测的结果为4，虽然错的离谱，但你可以看到使用牛顿迭代法后这个值很快就趋近于根号2了：
(       4  + 2/4        ) / 2 = 2.25
(     2.25 + 2/2.25     ) / 2 = 1.56944..
( 1.56944..+ 2/1.56944..) / 2 = 1.42189..
( 1.42189..+ 2/1.42189..) / 2 = 1.41423..
....
这种算法的原理很简单，我们仅仅是不断用(x,f(x))的切线来逼近方程x^2-a=0的根。根号a实际上就是x^2-a=0的一个正实根，这个函数的导数是2x。也就是说，函数上任一点(x,f(x))处的切线斜率是2x。那么，x-f(x)/(2x)就是一个比x更接近的近似值。代入 f(x)=x^2-a得到x-(x^2-a)/(2x)，也就是(x+a/x)/2。

相关的代码如下：

float SqrtByNewton(float x)
{
 float val = x;//最终
 float last;//保存上一个计算的值
 do
 {
  last = val;
  val =(val + x/val) / 2;
 }while(abs(val-last) > eps);
 return val;
}然后我们再来看下性能测试：

 

哇塞，性能提高了很多

My code

Binary search.

public int sqrt(int x) {
    if (x <= 1)
        return x;
    long left = 1, right = x;
    long mid, square;
    while (right - left > 1) {
        mid = (left + right) / 2;
        square = mid * mid;
        if (square == x)
            return (int) mid;
        else if (square > x)
            right = mid;
        else if (square < x)
            left = mid;
    }
    return (int) left;
}

Newton’s method, code from this blog.

public int sqrt(int x) {
    if (x == 0) return 0;
    double last = 0, res = 1;
    while (res != last) {
        last = res;
        res = (res + x / res) / 2;
    }
    return (int) res;
}

Question

link

Stats

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

Analysis

This is a extremely interesting question, with very tricky solutions. But the 3rd piece of code is actually the standard solution (by making use of the idea from partition array).

Code

First solution came from this blog.

public void sortColors(int[] A) {
    int a = -1, b = -1, c = -1;
    for (int i = 0; i < A.length; i ++) {
        if (A[i] == 0) {
            A[++ c] = 2;
            A[++ b] = 1;
            A[++ a] = 0;
        } else if (A[i] == 1) {
            A[++ c] = 2;
            A[++ b] = 1;
        } else {
            A[++ c] = 2;
        }
    }
}

Second solution, 2 pointer & swap which is written here.

public void sortColors(int[] A) {
    int len = A.length;
    int i = 0, x = 0, y = len - 1;
    while (i <= y) {
        if (A[i] == 0) 
            swap(A, i ++, x ++);
        else if (A[i] == 2) 
            swap(A, i, y --);
        else i ++;
    }
}

private void swap(int[] A, int a, int b) {
    int temp = A[a];
    A[a] = A[b];
    A[b] = temp;
}

Updated on July 4th, 2014: Use of solution of Partition Array to partition colors twice:

1. first time move all 0 to left.
2. second time move all 1 to left, following the 0s.

Code :

public void sortColors(int[] A) {
    if (A == null || A.length == 0) {
        return;
    }
    int len = A.length;
    partition(A, 0, len - 1, 0);
    int p = 0;
    while (p < len && A[p] == 0) {
        p++;
    }
    partition(A, p, len - 1, 1);
}

private void partition(int[] A, int start, int end, int target) {
    // find the target and put it on the left side of the array
    while (start < end) {
        while (start < A.length && A[start] == target) {
            start++;
        }
        while (end >= 0 && A[end] != target) {
            end--;
        }
        if (start > end) {
            break;
        } else {
            int temp = A[start];
            A[start] = A[end];
            A[end] = temp;
        }
    }
}

Question

link

Stats

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

Analysis

This is a very difficult string question. I read this blog and then understands the question. The solution is just straight-forward without any fancy algo/thinkings.

[解题思路]
利用栈的特性，如果sub string element
1. 等于“/”，跳过，直接开始寻找下一个element
2. 等于“.”，什么都不需要干，直接开始寻找下一个element
3. 等于“..”，弹出栈顶元素，寻找下一个element
4. 等于其他，插入当前elemnt为新的栈顶，寻找下一个element

最后，再根据栈的内容，重新拼path。这样可以避免处理连续多个“/”的问题。

Solution

Simply make use of stack and read thru all substrings seperated by /.

Code

public String simplifyPath(String path) {
    Stack<String> stack = new Stack<String>();
    String[] list = path.split("/");
    for(String cur: list) {
        if (cur.equals("/") || cur.equals(".")
            || cur.equals("")) continue;
        if (cur.equals("..")) {
            if (! stack.isEmpty()) stack.pop();
        } else stack.push(cur);
    }
    String ans = "";
    if (stack.isEmpty()) return "/";
    while (! stack.isEmpty()) {
        ans = "/" + stack.pop() + ans;
    }
    return ans;
}

Question

link

Stats

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

Analysis

This is a very borning question. The O(m+n) space solution is trivial, I will not cover. The constant space solution is making use of 1st row and 1st columns of the input array.

Solution

The idea is clear enough, but writing the code is not as easy. This post is a good explanation and code for the solution.

Difficult point: when there’s 0, set 0; but when there is no 0, do not touch on the value (if original it’s 3, keep it 3).

Code

public void setZeroes(int[][] matrix) {
    int m = matrix.length;
    if (m == 0) return;
    int n = matrix[0].length;
    if (n == 0) return;

    int firstrow = 1, firstcol = 1;
    for (int i = 0; i < m; i ++) 
        if (matrix[i][0] == 0) 
            firstcol = 0;
    for (int i = 0; i < n; i ++) 
        if (matrix[0][i] == 0) 
            firstrow = 0;
    for (int i = 1; i < m; i ++) {
        for (int j = 1; j < n; j ++) {
            if (matrix[i][j] == 0) {
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }
    for (int i = 1; i < m; i ++) {
        if (matrix[i][0] == 0)
            for (int j = 1; j < n; j ++) 
                matrix[i][j] = 0;
        if (firstcol == 0) matrix[i][0] = 0;
    }
    for (int i = 1; i < n; i ++) {
        if (matrix[0][i] == 0)
            for (int j = 1; j < m; j ++) 
                matrix[j][i] = 0;
        if (firstrow == 0) matrix[0][i] = 0;
    }
    if(firstrow == 0 || firstcol == 0) 
        matrix[0][0] = 0;
}

Question

link

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Stats

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

Related questions

Search a 2D Matrix.

Searching a 2D Sorted Matrix.

Count negative in a 2D Sorted Matrix.

Analysis

This is a binary search question.

Solution

I did not use binary, but use the easier linear search. It still passed.

Code

my code revised (2D binary search)

public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return false;
    }
    int m = matrix.length;
    int n = matrix[0].length;
    // find target vertically from matrix[0] to matrix[m-1]
    int top = 0, bottom = m - 1;
    int mid;
    while (top + 1 < bottom) {
        mid = top + (bottom - top) / 2;
        if (matrix[mid][0] < target) {
            top = mid;
        }
        else {
            bottom = mid;
        }
    }
    // locate the row number
    int row = -1;
    if (matrix[top][0] <= target && target <= matrix[top][n-1]) {
        row = top;
    }
    else if (matrix[bottom][0] <= target && target <= matrix[bottom][n-1]) {
        row = bottom;
    }
    else {
        return false;
    }
    // now find target from matrix[row]
    int left = 0, right = n - 1;
    while (left + 1 < right) {
        mid = left + (right - left) / 2;
        if (matrix[row][mid] < target) {
            left = mid;
        }
        else {
            right = mid;
        }
    }
    return (matrix[row][left] == target || matrix[row][right] == target);
}

A good binary search code here (1D binary search)

public boolean searchMatrix(int[][] matrix, int target) {
    if(matrix==null || matrix.length==0 || matrix[0].length==0) 
        return false;

    int m = matrix.length;
    int n = matrix[0].length;
    int start = 0;
    int end = m*n-1;

    while(start<=end){
        int mid=(start+end)/2;
        int midX=mid/n;
        int midY=mid%n;

        if(matrix[midX][midY]==target) 
            return true;
        if(matrix[midX][midY]<target){
            start=mid+1;
        }else{
            end=mid-1;
        }
    }
    return false;
}

Question

link

Stats

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

Analysis

This is an easy question.

My code

public int[] plusOne(int[] digits) {
    int n = digits.length - 1;
    while (n != -1 && digits[n] == 9) {
        n--;
    }
    if (n != -1) {
        // a non-9 number is found. change it. 
        digits[n] ++;
        for (int i = n + 1; i < digits.length; i ++) {
            digits[i] = 0;
        }
        return digits;
    } else {
        int[] newD = new int[digits.length + 1];
        newD[0] = 1;
        for (int i = 1; i < newD.length; i ++) {
            newD[i] = 0;
        }
        return newD;
    }
}

Question

link

Stats

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

Analysis

This is a very difficult string matching question.

The sliding window solution is very well explained in this post (the best solution).

To help illustrate this approach, I use a different example: S = “acbbaca” and T = “aba“. The idea is mainly based on the help of two pointers (begin and end position of the window) and two tables (needToFind and hasFound) while traversing S. needToFind stores the total count of a character in T and hasFound stores the total count of a character met so far. We also use a count variable to store the total characters in T that’s met so far (not counting characters where hasFound[x] exceeds needToFind[x]). When count equals T‘s length, we know a valid window is found.

Each time we advance the end pointer (pointing to an element x), we increment hasFound[x] by one. We also increment count by one if hasFound[x] is less than or equal to needToFind[x]. Why? When the constraint is met (that is, count equals to T‘s size), we immediately advance begin pointer as far right as possible while maintaining the constraint.

How do we check if it is maintaining the constraint? Assume that begin points to an element x, we check if hasFound[x] is greater than needToFind[x]. If it is, we can decrement hasFound[x] by one and advancing begin pointer without breaking the constraint. On the other hand, if it is not, we stop immediately as advancing begin pointer breaks the window constraint.

Finally, we check if the minimum window length is less than the current minimum. Update the current minimum if a new minimum is found.

Essentially, the algorithm finds the first window that satisfies the constraint, then continue maintaining the constraint throughout.

i) S = “acbbaca” and T = “aba“.

ii) The first minimum window is found. Notice that we cannot advance begin pointer as hasFound['a'] == needToFind['a'] == 2. Advancing would mean breaking the constraint.

iii) The second window is found. begin pointer still points to the first element ‘a’. hasFound['a'] (3) is greater than needToFind['a'] (2). We decrement hasFound['a'] by one and advance begin pointer to the right.

iv) We skip ‘c’ since it is not found in T. Begin pointer now points to ‘b’. hasFound['b'] (2) is greater than needToFind['b'] (1). We decrement hasFound['b'] by one and advance begin pointer to the right.

v) Begin pointer now points to the next ‘b’. hasFound['b'] (1) is equal to needToFind['b'] (1). We stop immediately and this is our newly found minimum window.

Both the begin and end pointers can advance at most N steps (where N is S‘s size) in the worst case, adding to a total of 2N times. Therefore, the run time complexity must be in O(N).

Solution

Best code is from this post.

First of all, keep a HashMap to store all letters and occurrance. Then declare a ‘count’ variable. This is an important varaible. It helps us to check whether we have successfully achieve at least 1 window. After we found the first window, the ‘count’ variable shall always equals to total number of letters in ’T'.

Now the looping part. Basically we assume that the window end at one point, and we find the correct starting position and calculate corresponding length.

The coding part is very difficult. Try to practise more.

Code

Updated on July 7th, code:

public String minWindow(String S, String T) {
    HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    HashMap<Character, Integer> map2 = new HashMap<Character, Integer>();
    for (Character ch: T.toCharArray()) {
        if (map.containsKey(ch)) {
            map.put(ch, map.get(ch) + 1);
        } else {
            map.put(ch, 1);
            map2.put(ch, 0);
        }
    }
    int count = 0;
    int start = 0;
    int end = 0;
    String result = "";
    while (end < S.length()) {
        char cur = S.charAt(end);
        if (!map.containsKey(cur)) {
            end++;
            continue;
        }
        map2.put(cur, map2.get(cur) + 1);
        if (map2.get(cur) <= map.get(cur)) {
            count++;
        }

        if (count == T.length()) {
            // locate start point
            while(true) {
                char ll = S.charAt(start);
                if (!map.containsKey(ll)) {
                    start++;
                    continue;
                }
                if (map2.get(ll) > map.get(ll)) {
                    map2.put(ll, map2.get(ll) - 1);
                    start++;
                    continue;
                } else {
                    break;
                }
            }
            if (result.equals("") || result.length() > end - start + 1) {
                result = S.substring(start, end + 1);
            }
        }
        end++;
    }
    return result;
}

Updated on July 19th, rewrite the code changing all while-loop to for-loop:

public String minWindow(String S, String T) {
    if (S.length() < T.length()) {
        return "";
    }
    HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    HashMap<Character, Integer> found = new HashMap<Character, Integer>();
    for (Character ch: T.toCharArray()) {
        if (map.containsKey(ch)) {
            map.put(ch, map.get(ch) + 1);
        } else {
            map.put(ch, 1);
            found.put(ch, 0);
        }
    }

    String window = S;
    int count = 0;
    int start  = 0;

    char[] letters = S.toCharArray();
    for (int i = 0; i < letters.length; i++) {
        char ch  = letters[i];
        if (!map.containsKey(ch)) {
            continue;
        }
        if (found.get(ch) < map.get(ch)) {
            count++;
        }
        found.put(ch, found.get(ch) + 1);
        if (count == T.length()) {
            // update the start pointer
            for (; start <= i; start++) {
                char sChar = letters[start];
                if (!map.containsKey(sChar)) {
                    continue;
                }
                if (found.get(sChar) <= map.get(sChar)) {
                    break;
                } else {
                    found.put(sChar, found.get(sChar) - 1);
                }
            }
            if (window.length() > i - start + 1) {
                window = S.substring(start, i + 1);
            }
        }
    }
    return count == T.length() ? window : "";
}

Question

link

Stats

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

Analysis

This is a difficult DP problem. A lot of people said in their blog that they spent tons of time on this question.

Solution

I posted below a very standard solution. The unconventional part of this solution is instead of declaring DP array of m*n size, I must declare it (m+1)*(n+1) size, where dp[i][j] denotes the distance of 2 strings that ends with (i)th and (j)th char respectively.

The rest of the code is easy to understand.

Code

my code

public int minDistance(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();

    int[][] dp = new int[m+1][n+1];
    for (int i = 0; i <= m; i++) {
        dp[i][0] = i;
    }
    for (int i = 0; i <= n; i++) {
        dp[0][i] = i;
    }
    for (int a = 1; a <= m; a++) {
        char aa = word1.charAt(a-1);
        for (int b = 1; b <= n; b++) {
            char bb = word2.charAt(b-1);
            if (aa == bb) 
                dp[a][b] = dp[a-1][b-1];
            else {
                int t1 = dp[a-1][b-1] + 1;
                int t2 = dp[a][b-1] + 1;
                int t3 = dp[a-1][b] + 1;
                dp[a][b] = Math.min(Math.min(t1, t2), t3);
            }
        }
    }
    return dp[m][n];
}