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(),
             [](vector<int>& a, vector<int>& b) {
                 return a[0] == b[0] ? a[1] < b[1] : a[0] < b[0];
             });
        vector<vector<int>> res;
        for (auto& interval : intervals) {
            if (res.empty() || res.back()[1] < interval[0]) {
                res.push_back(interval);
            } else {
                res.back()[1] = max(interval[1], res.back()[1]);
            }
        }
        return res;
    }
};

Learned:
1: Collections framework 的用法。 Tuitoral

2: Comparator in C++

https://www.geeksforgeeks.org/comparator-in-cpp/

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 an m x n matrix, return all elements of the matrix in spiral order.

Example 1:

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

Example 2:

Input: matrix = [[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]

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100

A:

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

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        int m = matrix.size(), n = matrix[0].size();
        int layer = 0; // layer starting from 0,
        while (layer <= m - 1 - layer && layer <= n - 1 - layer) {
            int r0 = layer, c0 = layer;
            int r1 = layer, c1 = n - 1 - layer;
            int r2 = m - 1 - layer, c2 = n - 1 - layer;
            int r3 = m - 1 - layer, c3 = layer;
            // top row, (gready first)
            for (int j = c0; j <= c1; j++) {
                res.push_back(matrix[r0][j]);
            }
            // right column
            for (int i = r1+1; i <= r2; i++) {
                res.push_back(matrix[i][c1]);
            }
            // bottom row
            if (r2 > r0) {
                for (int j = c2 - 1; j >= c3; j--) {
                    res.push_back(matrix[r2][j]);
                }
            }
            // left column
            if (c3 < c2) {
                for (int i = r3 - 1; i > r0; i--) {
                    res.push_back(matrix[i][c3]);
                }
            }
            layer++;
        }
        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 can trap after raining.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) 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.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

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;
    }
};

*******************第三遍**********为了面试的时候不出错，还是扫3遍，然后可以说再继续优化，可以扫2遍就行********

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> L(n, 0), R(n, 0);
        for (int i = 1; i < n; i++)
            L[i] = max(L[i - 1], height[i - 1]);

        for (int j = n - 2; j >= 0; j--)
            R[j] = max(R[j + 1], height[j + 1]);

        int total = 0;
        for (int i = 0; i < n; i++)
            total += max(0, min(R[i], L[i]) - height[i]);

        return total;
    }
};

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

Tiger's leetcode solution

Thursday, October 24, 2013

警示！！！！！！！！！

56. Merge Intervals ------- M !!!!!

A:

Wednesday, October 23, 2013

59. Spiral Matrix II ----M

54. Spiral Matrix --- M

A:

55. Jump Game -M

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

A:

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

N-Queens

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

Tuesday, October 22, 2013

50. Pow(x, n) -M

Monday, October 21, 2013

Anagrams

Multiply Strings

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

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

About Me

Blog Archive

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

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

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