警示！！！！！！！！！

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










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/

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

52. N-Queens II ---H !!!!!!!!!!!!!!!!!!!!!!!!!!

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

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

 

Example 1:

Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

Example 2:

Input: n = 1
Output: 1

 

Constraints:

• 1 <= n <= 9

A:
仅仅地把问题一，改改，拿过来，（用DFS ）来做，会慢。(但是能过）

class Solution {

public:

int totalNQueens(int n) {

int res = 0;

vector<vector<int>> board(n, vector<int>(n, 0));

helper(board, 0, res);

return res;

}

private:

// set a value on row_th row(all n column), and then contiue to next row

void helper(vector<vector<int>>& board, int row, int& res) {

int n = board.size();

if (row >= n) {

res++;

return;

}

for (int j = 0; j < n; j++) {

board[row][j] = 1;

if (isValid(board, row, j))

helper(board, row + 1, res);

board[row][j] = 0;

}

}

bool isValid(vector<vector<int>>& board, int row, int col) {

int n = board.size();

// position board[row][col] is just set to 1, need check if it is valid

// check going up to see if there's 1

for (int i = 0; i < row; i++)

if (board[i][col])

return false;

// check the whole row are NOT needed

// check diagonal (slash)

for (int i = 0; i < n; i++) {

int j = i + col - row;

if (j >= 0 && j < n) {

if (i != row && board[i][j])

return false;

}

}

// check anti-diagonal (anti-slash)

for (int i = 0; i < n; i++) {

int j = col + row - i;

if (j >= 0 && j < n) {

if (i != row && board[i][j])

return false;

}

}

return true;

}

};

下面的代码，不是自己写的，是网上copy别人的。
第一次， 让爷们儿，放弃了自己的方式。
好好学着下面的代码！！！！！！！！！！！！(time beat 100%;  memory beat 96%)

class Solution {
public:
    int totalNQueens(int n) {
        vector<int> pattern(n); //pattern[i] store the column index of the queen in row i
        return countSolution(1, pattern);
    }
private:
    int countSolution(int k, vector<int>& pattern) { //k: the current row number 
        int n = pattern.size();
        int res = 0;
        for (int i = 0; i < n; i++) {
            bool valid = true;
            for (int j = 0; j < k - 1; j++) {
                if (pattern[j] == i || abs(j - k + 1) == abs(pattern[j] - i)) {
                    valid = false;
                    break;
                }
            }
            if (!valid)
                continue;
            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)

51. N-Queens --- H !!!!

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

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

 

Example 1:

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2:

Input: n = 1
Output: [["Q"]]

 

Constraints:

• 1 <= n <= 9

A:
 --------------------2 nd pass----------------------
DFS ----------  Use 2D array
出现的问题，还是在于，测试diagonal的时候， 两条diagonal的表达有问题。

并不是对角线上的2条才需要检查。 左右的diagonal方向都需要。

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<char>> board(n, vector<char>(n, '.'));
        vector<vector<string>> res;
        dfs(board, res, 0);
        return res;
    }
private:
    void dfs(vector<vector<char>>& board, vector<vector<string>>& res, int row) {
        int n = board.size();
        if (row == n) {
            vector<string> curRes;
            for (int i = 0; i < n; i++) {
                string tmp(board[i].begin(), board[i].end());
                curRes.push_back(tmp);
            }
            res.push_back(curRes);
        } else {
            for (int j = 0; j < n; j++) {
                board[row][j] = 'Q';
                if (isValid(board, row, j))
                    dfs(board, res, row + 1);
                board[row][j] = '.';
            }
        }
    }
    bool isValid(vector<vector<char>>& board, int row, int col) {
        int n = board.size();
        // check each row i
        for (int j = 0; j < n; j++) {
            if (j != col && board[row][j] == 'Q')
                return false;
        }
        // now check colum : col
        for (int i = 0; i < n; i++) {
            if (i != row && board[i][col] == 'Q')
                return false;
        }
        // check diagonal
        for (int i = 0; i < n; i++) {
            int j = i + (col - row);
            if (j >= 0 && j < n && i != row && board[i][j] == 'Q')
                return false;
        }
        // check reverse diagonal
        for (int i = 0; i < n; i++) {
            int j = (col + row) - i;
            if (j >= 0 && j < n && i != row && board[i][j] == 'Q')
                return false;
        }
        return true;
    }
};

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

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

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

Mistakes: