Tiger's leetcode solution: October 2013

Thursday, October 24, 2013

警示！！！！！！！！！

“我年轻时总是想图个安逸。”我点了支烟答道，“所以面对机会我往往缩手缩脚犹豫不决，最终忍痛放弃。人习惯了安逸会产生惰性，更不愿去冒险，为此我丧失了很多机会。可人无远虑，必有近忧；我追求安逸平淡，最终却连这些都不得。我的生活变成一潭死水，几乎令我窒息。可我真实的内心，确实渴望挑战的。所以我不得不来个壮士断腕，把一切推倒重来。当时我发誓，我再不违背内心意志选择安逸生活了。因此每当遇到选择时，我都会遵循内心呼唤选择最富挑战性的那个—— 我玩的就是心跳。一路选择下来，生活轨迹自然就改变了。”

NOTE:

title里加了！！！！！！！！的是Tiger没有自己搞定的题目。要多多注意

wordLadderII 虽然自己的思路是对的。但是，由于特别容易犯错，也加了警示。

56. Merge Intervals -M

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

A:

自己写了Comparator里的compare函数。

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), 
            [](const vector<int>& a, const vector<int>& b ){
                return a[0] == b[0]? a[1]<b[1]:a[0]<b[0];}
            );
        vector<vector<int>> res;
        for(int i =0;i<intervals.size(); ++i)
        {
            auto tmp = intervals[i];
            if(res.empty() || res.back()[1]<tmp[0])
            {
                res.push_back(tmp);
            }else{
                res.back()[1] = max(res.back()[1], tmp[1]);
            }
        }
        return res;
    }
};

Learned:
1: Collections framework 的用法。 Tuitoral

Wednesday, October 23, 2013

59. Spiral Matrix II ----M

Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
Example:
Input: 3
Output:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

A:
同问题一。仍然是一层层地剥开设置。复杂度为n²

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> V(n, vector<int>(n,0));
        int c = 0;
        for(int layer = 0; layer < (n+1)/2;layer++){
            int x0 = layer, y0 = x0, x1 = n-layer-1, y1 = x1;
            for(int col = y0;col<=y1; col++){ // NEED <=  in case x0 == x1
                V[x0][col] = ++c;
            }
            for(int row = x0+1; row<=x1;row++){
                V[row][y1] = ++c;
            }
            if(x1>x0){
                for(int col = y1-1;col>= y0;col--){
                    V[x1][col] = ++c;
                }
            }
            if(y0<y1){
                for(int row = x1-1; row > x0;row--){
                    V[row][y0] = ++c;
                }
            }
        }
        return V;
    }
};
上面的是对于 m * n 矩阵的。  而对于 n * n 矩阵， 左右判断的可以省略掉 （当x0==x1时，只会增加第一个for loop)

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> V(n, vector<int>(n,0));
        int c = 0;
        for(int layer = 0; layer < (n+1)/2;layer++){
            int x0 = layer, y0 = x0, x1 = n-layer-1, y1 = x1;
            for(int col = y0;col<=y1; col++){ // NEED <=  in case x0 == x1
                V[x0][col] = ++c;
            }
            for(int row = x0+1; row<=x1;row++){
                V[row][y1] = ++c;
            }
            for(int col = y1-1;col>= y0;col--){
                V[x1][col] = ++c;
            }
            for(int row = x1-1; row > x0;row--){
                V[row][y0] = ++c;
            }
    }
        return V;
    }
};

Mistakes:

-------------------------------------3 rd Pass -----------------------------------
当n 是奇数，判断中心点的时候，一开始写成了 if(n%2 == 1 && layer +1 = n/2) 这样当n ==1的时候是不对的。

public class Solution {
    public int[][] generateMatrix(int n) {
        int[][] A = new int[n][n];
        helper(A,0,n-1,1);
        return A;
    }
    private void helper(int[][] A , int l, int r, int k){// l is the top left, r is down right corner
        if(l>r)
            return;
        if(l==r){
            A[l][l] = k++;
            return;
        }
        for(int j=l;j<r;j++)
            A[l][j]=k++;
        for(int i = l;i<r;i++)
            A[i][r] = k++;
        for(int j = r;j> l; j--)
            A[r][j] = k++;
        for(int i = r;i>l;i--)
            A[i][l] = k++;
        helper(A,l+1,r-1, k);
    }
}

Learned:

54. Spiral Matrix -M

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Example 1:

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]

Example 2:

Input:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

A:

一层层地剥开罢，按照上->右->下->左的顺序加入即可。
注意，当只有一行，一列的情况。（某一行，或某一列尽量取多的值。同时，在检查下面行，左边列的时候，要检查是否本行/列已经加过。

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        int m = matrix.size();
        if(m==0)
            return res;
        int n=matrix[0].size();
        
        for(int lay =0; lay<(min(n,m)+1)/2;++lay) // lay is layer
        {
            for(int col = lay; col< n-lay; ++col) // first row, get all value
                res.push_back(matrix[lay][col]);
            
            for(int row=lay+1; row <m-lay;++row) //right column, Not first one, but last one
                res.push_back(matrix[row][n-1-lay]);
            
            if(lay<m-1-lay)
                for(int col = n-2-lay; col>lay; --col)
                    res.push_back(matrix[m-1-lay][col]);
            
            if(lay<n-1-lay)
                for(int row = m-1-lay;row>lay;--row)
                    res.push_back(matrix[row][lay]);
        }
        return res;
    }
};

Mistakes:
1：由于我们每个边都是取了开头，没有取最后一个。导致，当只有一个点的时候，我们没能取出来。
解决方法：把upper row，全部取出来。

2; 当只有一行的时候，我们取了两遍，而这里，我们应该是先比较行数和列数，是否相同的。

3: 当只有一列的时候，类似于第一个错误，我们应该在某一列，尽量取多的值。
i. e. right col 第一个不取，但是取最后一个。

这里的关键点是 layer的时候，（因为一开始写成了i，因此导致错误， layer是需要min(col,row)

55. Jump Game -M

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.

A:

----------跟第二遍的思路一样---------------
思想：每次jump到最远的位置，然后，每一个可以jump的位置，都得visit看其是否更新reached 的值

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int far = 0;
        for(int i =0;i<=far && far < n;++i)
        {
            far = max(far, i + nums[i]);
        }
        return far>=n-1;
    }
};

-------------1 st pass-----------------------------
从0开始，每一个位置都做标记，查看是否可以达到最后的点。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        // mark as negative if can arrive
        if(n<=1)
            return true;
        nums[0] *= -1;
        for(int i =0;i<n;++i)
        {
            int v = nums[i];
            if(v>0)
                break;
            for(int j = i+1;j<=i-v && j<n ; ++j)
            {
                if(j==n-1) // hit now,  since nums[n-1] can be 0, we need check here
                    return true;
                
                if(nums[j]>0)
                    nums[j] *= -1;
            }
        }
        return false;
    }
};

Mistakes:
1；第二遍的时候，忘记了判断curFarest是否很大。如果超过边境的话，会导致A[i] 出现 out of boundary exception.
2:

Learned:

---------------------------第三遍-------------
Error：
1： for loop 中，应该是 <= rightMost的，就是说，要计算新的最远端的距离的时候，要包括原本最远可以到达的点。

public class Solution {
    public boolean canJump(int[] A) {
        if(A.length <= 1)
            return true;
        int lastRightMost = 0;
        int rightMost = A[0];
        while(rightMost>lastRightMost && rightMost<A.length-1){
            int newRightMost = rightMost;
            for(int i = lastRightMost+1;i<=rightMost;i++){
                int newRightEnd = i+A[i];
                newRightMost = Math.max(newRightMost,newRightEnd);
            }
            lastRightMost  = rightMost;
            if(newRightMost > rightMost){
                rightMost = newRightMost;
            }
        }
        return rightMost>=A.length-1;
    }
}

N-Queens II !!!!!!!!!!!!!!!!!!!!!!!!!!

Q:
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.

A:
仅仅地把问题一，改改，拿过来，（用DFS ）来做，会太慢。
下面的代码，不是自己写的，是网上copy别人的。
第一次，让爷们儿，放弃了自己的方式。
好好学着下面的代码！！！！！！！！！！！！！！！！！！

public class Solution {
    public int totalNQueens(int n) {
        assert(n>0);
        return countSolution(1,new int[n]);
    }
    
    public int countSolution(int k, int[] pattern){
        int n= pattern.length;
        assert(k<=n);
        int res = 0;
        main:
        for(int i=0;i<n;i++){
            for(int j=0;j<k-1;j++){
                if(pattern[j]==i||Math.abs(j-k+1)==Math.abs(pattern[j]-i))
                continue main;
            }
            pattern[k-1]=i;
            if(k==n) return 1;
            else res+=countSolution(k+1,pattern);
        }
        return res;
    }
}

上面这个例子，包括下面的例子，都默认要求 n < 32

-------------------------方法2------------

public class Solution {

static int result = 0;
static int upperLimit = 0;

public int totalNQueens(int n) {
    upperLimit = (1 << n)-1;
    result = 0;
    int row = 0;
    int ld = 0;
    int rd = 0;
    dfs(row,ld,rd);
    return result;
}
private static void dfs(int row, int ld, int rd) {
    if(row >= upperLimit){
        result++;
        return;
    }
    int pos = upperLimit &(~(row|ld|rd));
    int p = 0;
    while(pos > 0){
        p = pos & (~pos+1);
        pos = pos-p;
        dfs(row+p,(ld+p)<<1,(rd+p)>>1);
    }
}
}

Mistakes:
背诵上面的代码吧。人家还用了个main:

Learned:
首先是label的运用。可以直接跳出2层循环。
当然，不建议这样用，可以设置个标识，如果内层跳出了，再跳第二层。

----------------------------3 rd Pass --------------------------
由于2D array 的值只有2个，因此，我们可以用1D array 来表示它。
比如： int[ ] {3,1,4,2} 代表放置的地点分别为[1,3], [2,1], [3,4], [2,4] （第一个是index)
这么一来，我们用很简单的用数组表示了整个Board，而且在isValid函数里判断的时候会非常简洁，而且把输出Board单独隔离了出来

注意，我们刚开始的时候，在isValid中，依然去判断行，列，对角线。其实是不必要的。只需要判断当前行之前的行，列即可。
因此，刚开始的时候，我们写成：


    private boolean isValid(int cur) {
        // no need to check col, check row
        for (int i = 0; i < cur; i++)
            if ( loc[i] == loc[cur])
                return false;
        // check diagonal \
        for (int i = 0; i < cur; i++) {
            int j = i + loc[cur] - cur; // new colum that is on diagonal
            if ( j >= 0 && j < N && loc[j] != loc[cur])
                return false;
        }
        // check diagonal /
        for (int i = 0; i < cur; i++) {
            int j = loc[cur] + cur - i;// new colum that is on diagonal /
            if ( j >= 0 && j < N && loc[j] != loc[cur])
                return false;
        }
        return true;
    }

这样其实是不必要的，只需要判断 x上的距离差和y轴上的距离差，绝对值相等即可。

public class Solution {
    int total = 0;

    public int totalNQueens(int n) {
        int[] loc = new int[n];
        dfs(loc,0);
        return total;
    }

    private void dfs(int[] loc,int row) {
        if (row >= loc.length) {
            total++;
            return;
        }
        for (int i = 0; i < loc.length; i++) {
            loc[row] = i+1;// loc[i]==j, means that on board[i][j] =='Q'
            if (isValid( loc,row))
                dfs(loc,row + 1);
        }
    }

    private boolean isValid(int[] loc,int cur) {
        for (int i = 0; i < cur; i++) 
            if (loc[i] == loc[cur] || Math.abs(loc[i] - loc[cur]) == (cur - i))
                return false;
        return true;
    }
}

Learned:
1：
用1D 来代替2D array-------- 其实，退化来讲，如果是一维的棋盘，上面只能有一个位置放Q的话。
我们也可以直接用一个变量来记录其位置即可。
2：
对2D 的数组来讲，要判断是其diagonal的值相等。只需要判断其 x 轴的差距，是否和 y轴的差距相等即可。（由于是2条对角线，因此，要去 Abs)

N-Queens

Q:
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

NOTE: The queen (♕,♛) is the most powerful piece in the game of chess,

able to move any number of squares vertically, horizontally, or diagonally.

A:
--------------------2 nd pass----------------------
DFS ---------- Use 2D array
出现的问题，还是在于，测试diagonal的时候，两条diagonal的表达有问题。比较坐标系不同。而这个问题其实很好解决。就是看(row,col) 所在的对角线有什么特征即可。不用考虑坐标系转换。

public class Solution { 
    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for(int i=0;i<n;i++)
            Arrays.fill(board[i],'.');
        List<List<String>> all = new LinkedList<List<String>>();
        dfs(board,0,all);
        return all;
    }
    private void dfs(char[][] board, int col, List<List<String>> all){
        for(int i =0;i<board.length;i++){
            board[i][col] = 'Q';
            if(isValid(board,i,col)){
                if(col==board.length-1){// done
                    List list = new LinkedList<String>();
                    for(int j =0;j<board.length;j++)
                        list.add(new String(board[j]));
                    all.add(list);
                }else{
                    dfs(board,col+1,all);
                }
            }
            board[i][col] = '.';
        }
    }
    private boolean isValid(char[][] board, int row ,int col){ // board[i][j] is just been set
        for(int j=0; j<col; j++)
            if(board[row][j]=='Q')
                return false;
        for(int i=0;i<board.length;i++){ 
            int j = row + col -i;// check diagal /
            if(i!= row && j>=0 && j< col && board[i][j]=='Q')
                return false;
            j = i + col - row; // check diagonal \
            if(i!= row && j>=0 && j< col && board[i][j]=='Q')
                return false;
        }
        return true;
    }
}

--------------3rd pass---------------------

这里用了2D array，  如果用一维数组表示的话（类似于N-Queen II) ，

方法是：一维数组的下标表示横坐标（哪一行），而数组的值表示纵坐标（哪一列）。

Mistakes:
1： System.out.print(str[i].charAt(j) + '\t'); 打印出的结果是数字。哎，不是char 类型
应该写成System.out.print(""+str[i].charAt(j) + '\t'); 加个"" 就好了。
2：

Tuesday, October 22, 2013

50. Pow(x, n) -M

Q:
Implement pow(x, n).

A:
----------4th pass---------Iterative way ------------

public class Solution {
    public double pow(double x, int n) {
        if(n<0)
            return 1/(x*pow(x,-(n+1)));
        double result = 1;        
        while(n!=0){
            if(n%2 ==1)
                result *= x;                
            x = x*x;
            n = n>>1;       
        }
        return result;   
    }
}

Mistakes:
1:   第一次实现的时候，，没有考虑效率。   就直接n 个x连乘了。
2: 当建立ArrayList 的时候，    while (al.get(al.size() - 1) * 2 <n) {   但是这里，应该是 <= n 的
3：

Learned:
1:计算以2为底的log函数

-----------------3rd pass -------------------直接来计算----------
Error:
1: 刚开始，分开考虑 n 的正负号。但真因为这样，负数转正数会有溢出的情况。
    public double pow(double x, int n) {
        if(n==0)
            return 1;
        if(n<0)
            return 1/powPos(x,-n);
        // now n>0
        return powPos(x,n);
    }
因此，上面是不对的。
2：    double powPos（）的base case应该是 n == 0;
教训阿，还是分情况简单好记。否则的话，会容易惹出不必要的错误。而且既然自己不太熟悉 bit 操作。那就在面试的时候尽量避免。

class Solution {
public:
    double myPow(double x, int n) {
        if(n<0)
            return 1 /(x* myPow(x, -(n+1)));   // n -> -n  can have overflow if n<0
        if(n==0)
            return 1;
        double res = n&1 ? x : 1;
        double half = myPow(x, n/2);
        return res * half * half;
    }
};

最终改成了： ----------- 教训：当int 负数变正数的时候，一定要检查是否有溢出。（或者我们就一直用负数来搞。

public class Solution {
    public double pow(double x, int n) {
        return pow2(x,n);
    }
    private double pow2(double x, long n){
        if(n==0)
            return 1;
        if(n<0)
            return 1/pow2(x,-n);

        double b = pow2(x,n/2);
        if(n%2==0)
            return b*b;
        else
            return b*b*x;
    }
}

--------------------都当作负数来搞------------------------------------

public class Solution {
    public double pow(double x, int n) {
        if(n==0)
            return 1;
        if(n==-1)
            return 1/x;
        if(n>0)
            return 1/pow(x,-n);
            
        double b = pow(x,n/2);
        if(n%2==0)
            return b*b;
        else
            return b*b*1/x;
    }
}

Monday, October 21, 2013

Anagrams

Q:
Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
For example:

Input:	["tea","and","ate","eat","dan"]
Output:	["tea","ate","eat"]
Expected:	["and","dan","tea","ate","eat"]

A:
--------------------利用HashMap来保持，做到了O(n)的效率------------------------

public class Solution {
  public ArrayList<String> anagrams(String[] strs) {
    // using method to siulate O(n) method ,assume string length is constant
    ArrayList<String> al = new ArrayList<String>();
    if(strs == null)
        return al;
    HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
    for(String str : strs){
        char [] chars = str.toCharArray();
        Arrays.sort(chars);
        String newStrKey = new String(chars);
        
        if(map.containsKey(newStrKey)){
            map.get(newStrKey).add(str);
        }else{
            ArrayList<String> tmp = new ArrayList<String>();
            tmp.add(str);
            map.put(newStrKey,tmp);
        }
    }
    // iterator the Map to find the list, that is longger than 1
    Iterator<String> iter = map.keySet().iterator();
    while (iter.hasNext()) {
        String key = iter.next();
        ArrayList<String> tmp = map.get(key);
        if(tmp.size()>1)
            al.addAll(tmp);
    }
    return al;
    }
}

Mistakes:
1: 要注意， anagram的个数必须要大于1的。
2：这种问题，首先就应该问明白，对于边界情况，怎么定义。
例如，这道题，对于两个空字符串，也是定义为了anagram.

Input:	["",""]
Output:	[]
Expected:	["",""]

解决方法就是：先判断是否为空字符串？？？？？

哎，手欠啊，刚开始，习惯性的，加了句：|| strs[0].length() == 0 --------return al1;

3: 题意理解错误，刚开始，以为是只能有一个anagram了。

Learned:
1：when converting a char array back to String， it seems that we can use the build-in method toString(); ------- but it seems not right.

char[] charArray = {'a', 'b', 'c'};
Solution 1:
String b = new String(a);
Solution 2:
String str = String.valueOf(charArray);

其实，所有的toArray（）方法，返回的都是一个Object. 要谨慎使用。
2：另一种 HashMap的遍历方式：

1）： Iterator<String> iter = map.keySet().iterator();
2）： Iterator<Entry<String, String>> iter = map.entrySet().iterator();
3): for(T t : map.KeySet()){ // do something }

Multiply Strings

Q:
Given two numbers represented as strings, return multiplication of the numbers as a string.
Note: The numbers can be arbitrarily large and are non-negative.

A: 就是用两个数组来存储（倒序存储），并相乘

Mistakes:
1:   连乘的时候，应该是从最低位开始。也就是说，array1 和array 2的最后一位。(length -1 ) 开始
2：结果的末位，总是一个0，很奇怪！！！----------原因就是长度分别为 n1 和 n2    ---> 乘积的长度为 n1+ n2的。   那么，如果我们都是从最后一个index 算起，那么会导致，A[n1-1] *A[ n2-1] 这无法表达结果的index，（按理说，应该 i+ j -1）
--------------------解决方法：   把数字从低到高排列，然后相乘完毕，再反过来即可。

public class Solution {

    public String multiply(String num1, String num2) {
        // use two arrays to store the numbers, and multiply them
        // assume none of the input is null
        int n1 = num1.length();
        int n2 = num2.length();
        // ue two array to store them
        int[] int1 = new int[n1];
        int[] int2 = new int[n2];
        int[] result = new int[n1 + n2];

        for (int i = n1 - 1; i >= 0; i--)
            int1[i] = num1.charAt(i) - '0';

        for (int i = n2 - 1; i >= 0; i--)
            int2[i] = num2.charAt(i)- '0';

        for (int i = n2 - 1; i >= 0; i--) { // for each digits of int2,
            int[] tmp = new int[n1 + n2];
            int digit2 = int2[i];
            int carry = 0;
            for (int j = n1 - 1; j >= 0; j--) {
                int digit1 = int1[j];
                tmp[i + j + 1] = (digit1 * digit2 + carry)%10;
                carry = (digit1 * digit2 + carry) /10;
            }
            if (carry > 0) {
                tmp[i ] = carry;
            }
            addSum(result, tmp);
        }
        // change sum array to String
        // find first that is not zero
        int index = 0;
        while (index< result.length && result[index] == 0)
            index++;
        if (index  == result.length) // if result is 0
            return "0";
        else {//
            StringBuffer buf = new StringBuffer("");
            for (int i = index; i < result.length; i++)
                buf.append(result[i]);
            return buf.toString();
        }

    }

    private void addSum(int[] A, int B[]) {
        // size of A and B are the same
        int n = A.length;
        int carry = 0;
        for (int i = n - 1; i >= 0; i--) {
            int sum = A[i] + B[i] + carry;
            carry = sum / 10;
            A[i] = sum % 10;
        }
    }

}

------Mistakes:
1: when testing whether result is 0, , in the while loop, we forget to check whether the index is still in bound

------------------------------- 3rd-----------------------------

思路同上，但没有先把 string 转换成 int array

public class Solution {
    public String multiply(String num1, String num2) {
        if(num1.length() ==0 || num2.length() ==0)
            return "";
        int n1 = num1.length(), n2 = num2.length();
        int[] C  = new int[n1+n2];
        for(int i =n1-1;i >=0;i--){
            int a = num1.charAt(i)-'0';
            int carry = 0;
            int j =n2-1;
            for( ;j>=0;j--){
                int b = num2.charAt(j)-'0';
                int sum = (a*b+carry+C[i+j+1])%10;
                carry = (a*b+carry+C[i+j+1])/10;
                C[i+j+1]  = sum;
            }
            while(carry !=0){
                int sum = ( C[i+j+1]+carry) %10;
                carry = ( C[i+j+1]+carry) / 10;
                C[i+j+1] = sum;
            }
        }
        // make C to string
        int index = 0;
        while (index< C.length && C[index] == 0)
            index++;
        if (index  == C.length) // if C is 0
            return "0";
            
        StringBuffer buf = new StringBuffer();
        for(int i =index;i<C.length;i++)
            buf.append(""+C[i]);
        return buf.toString().trim();
    }
}

42. Trapping Rain Water --H ！！！！！老毛病，第一个方法不太对

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

A:

[解题思路]
对于任何一个坐标，检查其左右的最大坐标，然后相减就是容积。所以，
1. 从左往右扫描一遍，对于每一个坐标，求取左边最大值。
2. 从右往左扫描一遍，对于每一个坐标，求最大右值。
3. 再扫描一遍，求取容积并加和。

Mistakes:

扫两遍***********

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if(n<=2)
            return 0;
        vector<int> maxLeft(n,0);
        for(int i = 1;i<n;i++){
            maxLeft[i] = max(maxLeft[i-1], height[i-1]);
        }
        int res = 0;
        int maxRight = height[n-1];
        for(int i = n-2;i>0;i--){
            res += max(0, (min(maxLeft[i], maxRight) - height[i]));
            maxRight = max(maxRight, height[i]);
        }
        return res;
    }
};

Learned:
1：尽量让自己的helper function 为private 。阿三可能用这个来据你。

Sunday, October 20, 2013

First Missing Positive

Q:
Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
A:
就是求和，然后-------哎，可是有重复啊！！！！！！！！
考虑到负值的存在，因此我们需要设一个值，来记录positive number 的个数。
另外，记录till now max

Remember, we are required to find the first, i.e. there might exist multiple missing positive integer.

例如： int [] A = {3,3,4,1,1,1};
基本的思路来源于：当设置都封死了我们利用现有算法，也不让用额外的空间，因此，我们只能更改已给的空间。
哎，这样不行，那样也不行。就只能考虑，在A数组上更改了。

基本思路是：用地址代表数字内容。亦即，A[i] 的内容，更改为 i+1.
首先，对于负数。我们统统 set to be zero. 对于正数，改成其相反数。

因此，当遇到一个数字为负值。首先该位置设0，表明我们经历过了。
紧接着，就找value 对应的position , 如果该position 已经为正，则我们现在遇到的这个数字，已经是重复的了。直接跳过。如果 A[val -1] < 0。则继续调整。
经过分析，我们可以看到。虽然for loop 里有while 循环，但是，每个while都至少set 一个A的位置为非负。因此，总的次数，不超过2*A.length()的。
也就保证了O（n）的效率。

public class Solution { 
    public int firstMissingPositive(int[] nums) {
        // find a value, called val, put it on position nums[val -1]
        int n = nums.length;
        for(int i =0;i< n;i++){
            int val = nums[i];
            if(val<=0 || val == i+1 || val >= n || nums[val-1] == val)
                continue;
            // swap these two position
            int tmp = nums[i];
            nums[i] = nums[val-1];
            nums[val-1] = tmp;
            i--;
        }
        for(int i =0;i< n;i++){
            if(nums[i] != i+1)
                return i+1;
        }
        return nums.length+1;
    }
}

Mistakes:
1：没有考虑重复的情况。例如A = [1, 1].
2: 找到解决方法后，没有考虑输入为空的情况。（其实考虑了，但是，直接用assert排除了)
3：题意理解不透彻， given input A=[1,2]， the output is expected to be : 3

Learned:

----------------------------------第二遍------------
思路和上面的不一样：
简单来讲，就是对每一个位置，如果错位排列的，把其位置调整过来。
记得调整的时候，要检查，是否是相同的数字，如果相同，则不必swap了（会有loop)

public class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for(int i =0;i<nums.length;i++){
            if(nums[i]<=0 || nums[i] >n){
                nums[i] = -1;
            }else if(nums[i] != i+1){
                int nextPos = nums[i] - 1;
                if(nums[i]== nums[nextPos]){
                    nums[i] = -1;
                }else{// swap this two position
                    int tmp = nums[i];
                    nums[i] = nums[nextPos];
                    nums[nextPos] = tmp;
                }
                i--;
            }
        }
        // find the first position that is not a match
        for(int i =0;i<nums.length;i++)
            if(nums[i] != i+1)
                return i+1;
        return n + 1;
    }
}

Combination Sum II

Q:
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:

All numbers (including target) will be positive integers.
Elements in a combination (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ ≤ a₂ ≤ … ≤ a_k).
The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

A:

-----------Java-----------recursive--------------------

思路同上------------但是，在不用某个value 的时候，要直接退到后面，直到值不一样。

public class Solution {
    public List<List<Integer>> combinationSum2(int[] A, int target) {
        Arrays.sort(A);
        return helper(A,0,target);
    }
    private List<List<Integer>> helper(int[] A, int start, int target){
        List<List<Integer>>  all = new LinkedList<List<Integer>>();
        if(start>=A.length || target < A[start])
            return all;
        if(target == A[start]){
            List<Integer> list = new LinkedList<Integer>();
            list.add(target);
            all.add(list);
            return all;
        }
        all = helper(A,start+1,target-A[start]);
        for(List<Integer> al : all )
            al.add(0,A[start]);
        
        while(start+1<A.length && A[start+1] == A[start])
            start++;
        all.addAll(helper(A,start+1,target));
        return all;
    }
}

-----------C++ -------iterative ------------

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& C, int target) {
        std::sort(C.begin(), C.end());
        vector<vector<int>> res, tmpRes={{}};
        vector<int> sumList = {0};
        
        for(int i =0;i<C.size(); i++)
        {
            int val = C[i], nVal = 1;
            while( i+1 < C.size() && C[i+1] == val ) // count of current val
            {
                i++;
                nVal++;
            }
            int curCount = tmpRes.size();
            for(int j = 0; j< curCount; ++j)
            {
                auto B = tmpRes[j];
                auto curSum = sumList[j];
                for(int k = 0; k<nVal; k++)
                {
                    B.push_back(val);
                    curSum += val;
                    if (curSum < target){ // add to next round
                        auto C = B; //must create a copy, as B can change next round
                        tmpRes.push_back(C);
                        sumList.push_back(curSum);
                    }else if(curSum == target){
                        res.push_back(B);
                    }
                }
            }            
        }        
        return res;        
    }
};

Learned:

Combination Sum

Q:
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:

All numbers (including target) will be positive integers.
Elements in a combination (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ ≤ a₂ ≤ … ≤ a_k).
The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]A:

public class CombinationSum {
    public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
        // first sort the array
        Arrays.sort(candidates);
        return combinationSum(candidates,0, target);    
    }

    private ArrayList<ArrayList<Integer>> combinationSum(int[] candidates,
            int startIndex, int target) {
        // use startIndex as the first starting index of candidates, to
        // calculate the sum
        ArrayList<ArrayList<Integer>> all = new ArrayList<ArrayList<Integer>>();
        if (target < 0 || startIndex>= candidates.length) {
            return all;
        }
        if(target == candidates[startIndex]){
            ArrayList<Integer> al = new ArrayList<Integer>();
            al.add(target);
            all.add(al);
        }
        // if we do NOT use the startIndex value
        all.addAll( combinationSum(candidates,startIndex+1, target));
        //  if we use one startIndex value
        ArrayList<ArrayList<Integer>> nextAll =  combinationSum(candidates,startIndex, target- candidates[startIndex]);
        combineResult(all,nextAll,candidates[startIndex]);
        return all;
    }

    private void combineResult(ArrayList<ArrayList<Integer>> all,
            ArrayList<ArrayList<Integer>> nextAll, int firstValue) {
        // combine the nextAll into all
        for(int i =0;i<nextAll.size();i++){
            ArrayList<Integer> al = nextAll.get(i );
            al.add(0 , firstValue);
            all.add(al);
        }
    }
}

Mistakes:
1: 利用递归调用，基础条件检验的时候，忘了检测 startIndex是否越界。
2：肏， 忘了最基本的，当条件符合的时候，就加上，并且返回啊。检查target 是否和第一个数字吻合。

Learned:

----------------------------------第二遍-----递归的时候， 把所有的index after beginIndex 都用for loop遍历了一遍，造成了，极大的重复-----------------

----------------------第三遍也是同样的错误，哎～～～～～～～～～～～～～～～

public class Solution {
    public ArrayList<ArrayList<Integer>> combinationSum(int[] A, int target) {
        Arrays.sort(A);
        return helper(A, 0, target);
    }

    private ArrayList<ArrayList<Integer>> helper(int[] A, int start, int target) {
        ArrayList<ArrayList<Integer>> all = new ArrayList<ArrayList<Integer>>();
        if (start >= A.length || target < A[start]) 
            return all;
        
        if (target == A[start]) {
            ArrayList<Integer> al = new ArrayList<Integer>();
            al.add(target);
            all.add(al);
            return all;
        }
        // target > A[start], we can continue to divide it
        // use A[i]
        ArrayList<ArrayList<Integer>> less1 = helper(A, start, target - A[start]);
        for (int j = 0; j < less1.size(); j++)
            less1.get(j).add(0, A[start]);
        all.addAll(less1);
        // do not use A[i];
        less1 = helper(A, start + 1, target);
        all.addAll(less1);
        return all;
    }
}

Substring with Concatenation of All Words

Q:
You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.
For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]
You should return the indices: [0,9].
(order does not matter).
A:
哦，这道题，一开始是理解错了题目意思了。
仔细研读要求。是对每一个substring,例如从0 开始的，还有从9开始的substring（长度为L的总长度），里面包含了L里的所有的non-intervening 组合。就是把所有的L的string连起来。
例如，上面例子中从0 开始的: barfoo 就是L的一个组合。同样，从9开始的，foobar 也是一个组合。
假设L 里一共有n个string，每个string 长度为 m
分析：
1：我们不能穷尽L的组合形式。 2^n
2: 我们如果从每一个节点都开始计算L，有点儿太啰嗦的感觉。想想有没有什么好方法，来跳过部分预先监测的结果。
3： NOTE: strings in L， might exist replication.
4: 初步设想，用一个 list 记录所有match 的节点。然后看后面的substring是否match。这样，问题就归结于该list里面的值，是否能凑够0到n-1个match。--------但这里有个问题，就是L中可能有重复的情况。需要注意对待。
（问题就归结到，一个list，每个点包含了match的位置，如果全部的，都有0到n-1都能match的话，就加入result中，否则移动到下一个点。）

class Solution:
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        res = []
        import copy 
        if len(words) == 0:
            return res
        wLen = len(words[0])
        origD = {} # cannot use set(), since words might have duplicates
        for w in words:
            self.add2Dict(w,origD)
            
        for i in range(wLen):
            D = copy.deepcopy(origD)
            foundD = {}
            # check every possible starting position, to see whether it is a match
            startIndex = i # the index that not valid 
            for end in range(i, len(s) - wLen +1, wLen):
                # continue adding, till we find a match
                substr = s[end:end+wLen]
                if substr in D: # in original dict
                    self.add2Dict(substr,foundD)
                    self.removeD(substr,D)
                    if len(D) == 0:
                        res.append(startIndex)
                        topStr = s[startIndex: startIndex + wLen]
                        self.add2Dict(topStr, D)
                        self.removeD(topStr,foundD)
                        startIndex += wLen
                        
                elif substr in foundD: # found, but have been removed before
                    while s[startIndex: startIndex+ wLen] != substr:
                        ss = s[startIndex: startIndex+wLen]
                        self.add2Dict(ss,D)
                        self.removeD(ss,foundD)
                        startIndex += wLen
                    startIndex += wLen
                    
                else: # not in words at all,  reset the whole
                    startIndex = end + wLen # next position is a good (or loop till right)
                    self.addD1toD2(foundD,D)
        return res     
    
    def removeD(self, word, D):
        if D[word] == 1:
            del D[word]
        else:
            D[word] = D[word] -1
    
    def add2Dict(self, word, D):
        if word not in D:
            D[word] = 1
        else:
            D[word] = D[word] + 1
    
    def addD1toD2(self, D1, D2): # merge two dict, into D2
        for k in D1:
            self.add2Dict(k,D2)
        D1.clear()

------------------------------4th pass----------------------------
思路：因为允许重复，所以要记录下出现的次数，因此需要用HashMap.
而这次，为了加速，我们在最外边的循环中，用了基于各个起始点的位置。

public class Solution {
    public List<Integer> findSubstring(String S, String[] L) {
        List<Integer> list = new LinkedList<Integer>();
        if(S==null || L == null | S.length()==0 || L.length == 0)
            return list;
        // note that L might contains duplicates
        int n = S.length(), m = L[0].length(), k = L.length;
        HashMap<String, Integer> origMap = new HashMap<String,Integer>();
        for(int i= 0;i<L.length;i++){
            String str = L[i];
            int count = 1;
            if( origMap.containsKey(str)){
                count += origMap.get(str);
            }
            origMap.put(str,count);
        }
        for(int i =0;i<m;i++){ // for each possible starting position
            HashMap<String,Integer> tmpMap = new HashMap<String, Integer>();
            int j = i;
            while( j<= n-m ){
                // remove the oldest
                if( j-m*k>=0 ){
                    String oldStr = S.substring(j-m*k,j-m*k+m);
                    if(tmpMap.containsKey(oldStr)){
                        if(tmpMap.get(oldStr)>1){
                            tmpMap.put(oldStr,tmpMap.get(oldStr)-1);
                        }else{
                            tmpMap.remove(oldStr);
                        }
                    }
                }
                // add the newest
                String newStr = S.substring(j,j+m);
                int nFind = 1;
                if(tmpMap.containsKey(newStr)){
                    nFind += tmpMap.get(newStr);
                }
                tmpMap.put(newStr,nFind);
                // check if it is match
                boolean isAllFind = true;
                for(String str : origMap.keySet()){
                    if(tmpMap.containsKey(str)== false || tmpMap.get(str)!=origMap.get(str)){
                        isAllFind = false;
                        break;
                    }
                }
                if(isAllFind)
                    list.add(j-m*k+m);
                //update j
                j+=m;
            }
        }
        return list;
    }
}

--------------------第二遍----------- AC 了 --------
思路就是：既然允许有重复，而且，还要尽量快，用Set是不太行了。那就用HashMap，来记录下每个key的出现的次数。

public class Solution {
    public ArrayList<Integer> findSubstring(String S, String[] L) {
        ArrayList<Integer> al = new ArrayList<Integer>();
        if (S == null || L == null || S.length() == 0 || L.length == 0)
            return al;
        // make a set from L, so that we can
        int nL = L.length;
        int mL = L[0].length();
        for (int k = 0; k <= S.length() - nL * mL; k++) {
            Map<String, Integer> map = buildSet(L);
            String curS = S.substring(k, k + mL * nL);
            int i = 0;
            int matchedCount = 0;
            while (matchedCount < nL) {
                String tmp = curS.substring(i, i + mL);
                if (map.containsKey(tmp)) {
                    int count = map.get(tmp);
                    if(count <=0)
                        break;
                    map.put(tmp, count - 1);
                    i += mL;
                    matchedCount++;
                } else 
                    break;
            }
            // iterator all the list, to see whether it has been fully visited
            boolean isAllFind = true;
            for(String key : map.keySet())
                if(map.get(key)>0){
                    isAllFind = false;
                    break;
                }
            if(isAllFind)
                al.add(k);
        }
        return al;
    }

    private Map<String, Integer> buildSet(String[] L) {
        Map<String, Integer> map = new HashMap<String, Integer>();
        for (int i = 0; i < L.length; i++) {
            if (map.containsKey(L[i])) {
                int count = map.get(L[i]);
                map.put(L[i], count + 1);
            } else
                map.put(L[i], 1);
        }
        return map;
    }
}

Mistakes:
----------------第二遍------开始理解错题意了。
1：所谓的withougt any interleaving characters,是指一个 concatenation里面不能interleaving. 但是，多个，是可以的。
2：输入的 L 可以是["a","b","a"] ，因此，不能用Set 来存储。

Learned:

---------------3 rd 想利用每个L 中的 string 映射到一个HashMap上去。------------
思想很简单，和楼上的那个通不过的方法如出一致。-------------其实就是第二遍的思想。-------
就是对每个string in L ,map 一个数值。作为标记。然后，看其是否在map中出现过，如果出现过，对比出现的次数。

但是，还是suffer了这样一个问题，就是L 中有重复的情况。
因此，我们还需要记录在L中出现的次数。作为参照物，还要记录用过的次数。
因此，我们自己定义了一个类。

public class Solution {
    public ArrayList<Integer> findSubstring(String S, String[] L) {
        ArrayList<Integer> al = new ArrayList<Integer>();
        int n = L.length;// assume n > 0
        int l = L[0].length();
        HashMap<String, SNode> map = new HashMap<String, SNode>();
        int nDifferent=0; // number of different Strings in L
        for(int i =0;i< n;i++){
            SNode node = map.get(L[i]);
            if(node == null){
                nDifferent++;
                node = new SNode(nDifferent);
                map.put(L[i],node);
            }else
                node.count++;
        }
        // for each position, calculate its total sum
        for(int i =0;i<= S.length() - l*n; i++){
            for(int j =0;j< n;j++) // reset all 
                map.get(L[j]).nUsed=0;
            // test sum of these String
            boolean isBreak = false;
            for(int k = 0;k<n;k++){
                String str= S.substring(i+k*l, i+(k+1)*l);
                SNode node = map.get(str);
                if(node == null || node.nUsed>=node.count){
                    isBreak = true;
                    break;
                }else{
                    node.nUsed++;
                }
            }
            if(!isBreak)
                al.add(i);
        } 
        return al;
    }
    
}
class SNode{
    public int val;
    public int count;
    public int nUsed=0; // number of used
    public SNode(int v){
        val = v;
        count = 1;
    }
}

Thursday, October 17, 2013

Count and Say

Q:
The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the n^th sequence.
Note: The sequence of integers will be represented as a string.

题意是
n=1时输出字符串1；
n=2时，数上次字符串中的数值个数，因为上次字符串有1个1，所以输出11；
n=3时，由于上次字符是11，有2个1，所以输出21；
n=4时，由于上次字符串是21，有1个2和1个1，所以输出1211。
依次类推，写个countAndSay(n)函数返回字符串。
A:

public class Solution {
   public String countAndSay(int n) {
        // recursively
        if (n == 1) {
            return "1";
        } else {
            String lastStr = countAndSay(n - 1);
            StringBuffer buf = new StringBuffer();
            // use two pointer to check
            int slowRunner = 0, fastRunner;
            while (slowRunner < lastStr.length()) {
                fastRunner = slowRunner;
                while (fastRunner < lastStr.length()) {
                    if (lastStr.charAt(fastRunner) == lastStr
                            .charAt(slowRunner)) {
                        fastRunner++;
                    }else{
                        break;
                    }
                }
                // now fastRunner point to the next value that 
             //either != slowRunner, or exceed array boundary
                buf.append( fastRunner-slowRunner);
                buf.append( lastStr.charAt(slowRunner));
                slowRunner = fastRunner;
            }
            return buf.toString();
        }
    }
}

Mistakes:
1: 当 update fastRunner的时候，当值与slowRunner 不相等的时候，我们要break 该while Loop。 ------------ 开始，就SB，没有加上。
2：

Learned:

----------------------第一遍是递归调用--------第二遍是-------------DP 建立--------------

public class Solution {
    public String countAndSay(int n) {
        // assume n >=1
        String lastStr = "1";
        StringBuffer buf;
        for (int i = 2; i <= n; i++) { // DP calculate each layer
            buf = new StringBuffer();
            for (int j = 0; j < lastStr.length(); j++) {
                char curCh = lastStr.charAt(j);
                int count = 1;
                while (j + 1 < lastStr.length() && lastStr.charAt(j + 1) == curCh) {
                    count++;
                    j++;
                }
                buf.append("" + count + curCh);
            }
            lastStr = buf.toString();
        }
        return lastStr;
    }
}

public class Solution {
    public String countAndSay(int n) {
        String res = "1";
        for(int i =0; i<n-1;i++)
            res = helper(res);
        return res;
    }
    private String helper(String str){
        StringBuffer buf = new StringBuffer();
        int  i = 0;
        while(i<str.length()){
            int len=1;
            while(i+1<str.length() && str.charAt(i)==str.charAt(i+1)){
                len++;
                i++;
            }
            buf.append(""+len+str.charAt(i));
            i++;
        }
        return buf.toString();
    }
}

Sudoku Solver

Q:
Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.

A sudoku puzzle...

...and its solution numbers marked in red.

A:就是简单的回溯啊~~~~~~~~~ 你那样用手做的方法，很可能做不出来的。

public class Solution {
   public void solveSudoku(char[][] board) {
        recursiveSolveSudoku(board);
    }

    private boolean recursiveSolveSudoku(char[][] board) {
        // recursive Solve Sudoku
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (int k = 0; k < 9; k++) {
                        board[i][j] = (char) ('1' + k);
                        if (isValid(board, i, j) && recursiveSolveSudoku(board))
                            return true;
                        board[i][j] = '.';// put the '.' back
                    }
                    return false;// !!!!!!!!!! cannot fill any char here
                }
            }
        }
        return true;
    }

    private boolean isValid(char[][] board, int row, int col) {
        // check if soduku is still valid after setting the value at (row,col)
        // position
        Set<Character> contained = new HashSet<Character>();
        char ch;
        // check the line of (row,col)
        for (int j = 0; j < 9; j++) {
            ch = board[row][j];
            if (contained.contains(ch))
                return false;
            if (ch > '0' && ch <= '9')
                contained.add(ch);
        }

        // check the column of {row,col}
        contained = new HashSet<Character>();
        for (int i = 0; i < 9; i++) {
            ch = board[i][col];
            if (contained.contains(ch))
                return false;
            if (ch > '0' && ch <= '9')
                contained.add(ch);
        }

        // check the small 3-by-3 square of {row,col}
        contained = new HashSet<Character>();
        int outerI = row / 3;
        int outerJ = col / 3;
        for (int i = outerI * 3; i < outerI * 3 + 3; i++) {
            for (int j = outerJ * 3; j < outerJ * 3+3; j++) {
                ch = board[i][j];
                if (contained.contains(ch))
                    return false;
                if (ch > '0' && ch <= '9')
                    contained.add(ch);
            }
        }
        return true;
    }
}

Mistakes:
1：刚开始，就是用的手算的思路。但是，不用回溯，是不行的。哎~~~~~~~~~~
2：ArrayList 调用remove方法时，当我们想remove Object时，但是，我们的object是Integer。这时候，我们就不能直接remove Integer，需要先找到其的index，再remove

3：同样的回溯，你写的就是太慢，别人写的，就快啊
原本，我们这样写
boolean[] findFlag = new boolean[10];
        // check the line of (row,col)
        for (int j = 0; j < 9; j++) {
            char ch = board[row][j];
            if (ch == '.')
                continue;
            int value = Integer.valueOf("" + ch);
            if (findFlag[value]) {
                return false;
            } else {
                findFlag[value] = true;
            }
        }

对手是用了HashSet --------------应该，我们以前的也没问题的。代码里，少写了个+3

Learned:
1: Cannot create a generic array of ArrayList<Integer>　　所以说，下面这句是不对的
ArrayList<Integer>[][] candidites = new ArrayList<Integer>[9][9];
2 -------------------下面是别人的东东----------------

做了这道题，对backtracking的理解又加深了一点点。

1 每个backtracking的题目，最好都有独立判断isValid的程序，这样架构清楚。同时，valid判断函数在这里可以稍微研究一下。只要当前要判断的位置上的数值和本行没有重复，本列没有重复，九宫格没有重复就可以。一旦重复立即返回，减少判断次数。

2 backtracking的递归函数，怎么能没有返回值呢？！因为要判断递归的方案正确与否，所以这里的递归一定是有返回值的（除非是combination那种没有正确错误概念的backtracking）！
3 可以考虑“先放置，再判断”的方案。比如这里，首先判断当前位置是否为空，如果为空，那么放置一个元素，检查它是否正确。如果正确，就继续进行下面的递归（也就是第29行 isValid&&solveSudoku的作用）。当函数返回错误之后，将刚刚的数值变为空，再进行下一次尝试即可。
4 所有的方案（k从1到9）完毕之后，应该返回错误，这个是不应该被忽略的。
5 最后一点需要注意的是，当i,j循环完毕之后，第36行应该返回true。这里实际上是最终/最底层的一次循环，表明已经解出了sudoku，返回true！切记切记，最终情况！

--------------------------------第二遍---------思路完全一样，代码略有精简，没有用Set，仅仅就是比较 ch 的值。---------------

public class Solution {
   public void solveSudoku(char[][] board) {
        helper(board);
    }
    private boolean helper(char[][] board){
        for(int i =0;i< 9;i++){
            for(int j = 0;j<9; j++){
                if(board[i][j] == '.'){
                    for(char ch = '1';ch<='9';ch++){
                        board[i][j] = ch;
                        if(isValid(ch,i,j,board) && helper(board))
                            return true;
                        board[i][j] = '.';
                    }
                    return false; // cannot fill any char here
                }
            }
        }
        return true;
    }
    private boolean isValid(char ch, int row, int col, char[][] board){
        // check that after inserting ch at position i,j,  the board is still valid
        // check row 
        for(int j = 0;j<9;j++){
            if(j != col)
                if(board[row][j] == ch)
                    return false;
        }
        // check column
        for(int i = 0; i<9; i++)
            if(i != row)
                if(board[i][col] == ch)
                    return false;
        // check  small square
        int i = row/3, j = col /3;
        board[row][col] = '.';
        for(int ii = i*3;ii<i*3+3;ii++){
            for(int jj = j*3;jj<j*3+3;jj++){
                if(board[ii][jj] == ch){
                    return false;
                }
            }
        }
        board[row][col] = ch;
        return true;
    }
}

-------------------------------第三遍--------------------
为了节省时间，试着用List of Set to check the possible directly, but no much speed improvement.

public class Solution {
    List<Set<Character>> row = new LinkedList();
    List<Set<Character>> col = new LinkedList();
    List<Set<Character>> subBox = new LinkedList();
    public void solveSudoku(char[][] board) {// we know that board is 9-by-9 array
        // initialize the list of Sets
        for(int i =0;i<9;i++){
            HashSet tmpRow = new HashSet<Character>();
            for(int j =0;j<9;j++)
                tmpRow.add(board[i][j]);
            row.add(tmpRow);

            HashSet tmpCol = new HashSet<Character>();
            for(int j =0;j<9;j++)
                tmpCol.add(board[j][i]);
            col.add(tmpCol);

            HashSet tmpBox = new HashSet<Character>();
            subBox.add(tmpBox);
        }
        for(int i =0;i<9;i++)
            for(int j =0;j<9;j++)
                subBox.get(j / 3 + (i / 3) * 3).add(board[i][j]);

        helper(board);
    }
    private boolean helper(char[][] board){
        for(int i =0;i<9;i++){
            for(int j =0;j<9;j++){
                if(board[i][j] !='.')
                    continue;
                for(char ch = '1';ch<='9';ch++){
                    if(isValid(i,j,ch)){
                        board[i][j] = ch;
                        // update list of Set
                        row.get(i).add(ch);
                        col.get(j).add(ch);
                        subBox.get(j/3+(i/3)*3).add(ch);
                        // DFS
                        if(helper(board))
                            return true;

                        board[i][j] = '.';
                        // clear the newly added value
                        row.get(i).remove(ch);
                        col.get(j).remove(ch);
                        subBox.get(j/3+(i/3)*3).remove(ch);
                    }
                }
                return false;
            }
        }
        return true;
    }
    private boolean isValid(int i, int j, char ch){
        return !row.get(i).contains(ch) &&  !col.get(j).contains(ch) && !subBox.get(j/3+(i/3)*3).contains(ch);
    }
}

Mistakes:
2: 在试完了所有的9种可能填的选项之后，应该直接返回false了，而不是等待其最后返回true.

Thursday, October 24, 2013

A:

Wednesday, October 23, 2013

A:

Given an array of non-negative integers, you are initially positioned at the first index of the array.

A:

--------------3rd pass---------------------

Tuesday, October 22, 2013

Monday, October 21, 2013

****************扫两遍***************************

Sunday, October 20, 2013

-----------Java-----------recursive--------------------

Thursday, October 17, 2013

扫两遍***********