Word Break II leetcode

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

用DFS来解, 但是要像word break里那样判定s是否能被切分然后再进行dfs切分, 否则会超时

public class Solution {
    public List<String> wordBreak(String s, Set<String> wordDict) {
        List<String> res = new ArrayList<String>();
        if (s == null || s.length() == 0) {
            return res;
        }
        boolean[] table = new boolean[s.length() + 1];
        table[0] = true;
        for (int i = 0; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if(table[j] && wordDict.contains(s.substring(j,i))) {//j+1到i字符
                    table[i] = true;
                    break;
                }
            }
        }
        if (table[s.length()] == false) {
            return res;
        }
        StringBuilder sb = new StringBuilder();
        helper(res, s, wordDict, 0, sb);
        return res;
    }
    public void helper(List<String> res, String s, Set<String> wordDict, int pos, StringBuilder sb) {
        if (pos == s.length()) {
            res.add(sb.toString());
            return;
        }
        for (int i = pos; i <= s.length(); i++) {
            String tem = s.substring(pos, i);
            if (wordDict.contains(tem)) {
                int len = sb.length();
                if (len > 0) {
                    sb.append(" ");
                }
                sb.append(tem);
                helper(res, s, wordDict, i, sb);
                sb.delete(len, sb.length());
            }
        }
    }
}

Text Justification leetcode

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactlyL characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left justified and no extra space is inserted between words.

For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.

Return the formatted lines as:

[
   "This    is    an",
   "example  of text",
   "justification.  "
]

下面讲解引用自http://codeganker.blogspot.com/2014/04/text-justification-leetcode.html

“这 道题属于纯粹的字符串操作，要把一串单词安排成多行限定长度的字符串。主要难点在于空格的安排，首先每个单词之间必须有空格隔开，而当当前行放不下更多的 单词并且字符又不能填满长度L时，我们要把空格均匀的填充在单词之间。如果剩余的空格量刚好是间隔倍数那么就均匀分配即可，否则还必须把多的一个空格放到 前面的间隔里面。实现中我们维护一个count计数记录当前长度，超过之后我们计算共同的空格量以及多出一个的空格量，然后将当行字符串构造出来。最后一 个细节就是最后一行不需要均匀分配空格，句尾留空就可以，所以要单独处理一下。时间上我们需要扫描单词一遍，然后在找到行尾的时候在扫描一遍当前行的单 词，不过总体每个单词不会被访问超过两遍，所以总体时间复杂度是O(n)。而空间复杂度则是结果的大小（跟单词数量和长度有关，不能准确定义，如果知道最 后行数r，则是O(r*L)）。代码如下：” 

public class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> res = new ArrayList<String>();
        if (words == null || words.length == 0) {
            return res;
        }
        int count = 0;//记录当前字符长度
        int last = 0;// 记录这一行起始字符的位置
        for (int i = 0; i < words.length; i++) {
            if (count + words[i].length() + i - last > maxWidth) {//i - last 是表示这一行单词之间空格总数
                i--;
                int spacenum = 0;
                int extrnum = 0;
                if (i - last > 0) {
                    spacenum = (maxWidth - count) / (i - last);//每个字符之间平均要有几个空格
                    extrnum = (maxWidth - count) % (i - last);//多余出来的空格
                }
                StringBuilder tem = new StringBuilder();
                for (int j = last; j <= i; j++) {
                    tem.append(words[j]);
                    if (j < i) {//第i个字符(每行最后一个)后面没有空格
                        for (int k = 0; k < spacenum; k++) {
                            tem.append(" ");
                        }
                        if (extrnum > 0) {//添加多余的空格
                            tem.append(" ");
                        }
                        extrnum--;
                    }
                }
                for (int j = tem.length(); j < maxWidth; j++) {//这个for循环作用于一行只有一个单词还maxWidth没填满一行的情况
                    tem.append(" ");
                }
                res.add(tem.toString());
                count = 0;
                last = i + 1;//下一个开始位置
            } else {
                count += words[i].length();
            }
        }
        StringBuilder tem = new StringBuilder();
        for (int i = last; i < words.length; i++) {//处理最后一行
            tem.append(words[i]);
            if (tem.length() < maxWidth) {
                tem.append(" ");
            }
        }
        for (int j = tem.length(); j < maxWidth; j++) {
            tem.append(" ");
        }
        res.add(tem.toString());
        return res;
    }
}

Surrounded Regions leetcode

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

这道题的题意是把那些四周被'X'包围的'O'都变成'X'

那么可以发现最外面的四周如果有O, 那么与之相连的O才能不被包围

所以就对最外层的'O'进行特殊处理, 对外层的'O'进行BFS, 把与之相连的O和它本身都变成'#'

这样一来对于整个矩阵 如果还是'O'的说明他被X包围, 应该变成X, 把所有的# 再变成O

//bfs
public class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length <= 1 || board[0].length <= 1) {
            return;
        }
        for (int i = 0; i <board[0].length; i++) {//fill第一行和最后一行
            fill(board, 0, i);
            fill(board, board.length - 1, i);
        }
        for (int i = 0; i < board.length; i++) {//对第一列和最后一列fill
            fill(board, i, 0);
            fill(board, i, board[0].length - 1);
        }
        for (int i = 0; i< board.length; i++) {
            //最后一次遍历, 把内部的'O'变成'X', '#'变成'O'
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    public void fill (char[][] board, int i, int j) {
        if (board[i][j] != 'O') {
            return;
        }
        board[i][j] = '#';
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(i * board[0].length + j);//把矩阵的横纵坐标编码存储
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            //解码
            int row = cur / board[0].length;
            int column = cur % board[0].length;
            if (row > 0 && board[row - 1][column] == 'O') {//向上找
                queue.offer((row - 1) * board[0].length + column);
                board[row - 1][column] = '#';
            }
            if (row < board.length - 1 && board[row + 1][column] == 'O') {//向下找
                queue.offer((row + 1) * board[0].length + column);
                board[row + 1][column] = '#';
            }
            if (column > 0 && board[row][column - 1] == 'O') {//向左找
                queue.offer(row * board[0].length + column - 1);
                board[row][column - 1] = '#';
            }
            if (column < board[0].length - 1 && board[row][column + 1] == 'O') {//向右找
                queue.offer(row * board[0].length + column + 1);
                board[row][column + 1] = '#';
            }
        }
    }
}
//dfs cause stack over flow
public class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length <= 1 || board[0].length <= 1) {
            return;
        }
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                bfs(board, i, 0);
            }
            if (board[i][n - 1] == 'O') {
                bfs(board, i, n - 1);
            }
        }
        for (int i = 1; i <= n - 2; i++) {
            if (board[0][i] == 'O') {
                bfs(board, 0, i);
            }
            if (board[m-1][0] == 'O') {
                bfs(board, m - 1, i);
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    public void bfs(char[][] board, int column, int row) {
        if (column < 0 || column >= board.length || row < 0 || row >= board[0].length || board[column][row] != 'O') {
            return;
        }
        board[column][row] = '#';
        bfs(board, column - 1, row);
        bfs(board, column + 1, row);
        bfs(board, column, row - 1);
        bfs(board, column, row + 1);
    }
}

Word Search leetcode

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

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

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.
这道题的原理就是利用深度优先搜索, 从一个点出发, 上下左右搜索看是否能找到相等于word的字符串. 因为每一次的dfs访问的点不能被二次访问, 所以要维护一个m * n 的boolean矩阵 记录访问过的点.
对于每一个点的dfs时间是O(m*n)。我们对每个顶点都要做一次搜索，所以总的时间复杂度最坏是O(m^2*n^2)，空间上就是要用一个数组来记录访问情况，所以是O(m*n)。

public class Solution {
    public boolean exist(char[][] board, String word) {
        if (word == null || word.length() == 0) {
            return true;
        }
        if (board == null || board.length == 0 || board[0].length == 0) {
            return false;
        }
        boolean[][] used = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (helper(board, word, 0, i, j, used)) {
                    return true;
                }
            }
        }
        return false;
    }
    private boolean helper(char[][] board, String word, int index, int i, int j, boolean[][] used) {
        if (index == word.length()) {
            return true;
        }
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || used[i][j] || board[i][j] != word.charAt(index)) {
            return false;
        }
        used[i][j] = true;
        boolean res = helper(board, word, index + 1, i + 1, j, used) ||helper(board, word, index + 1, i - 1, j, used) || helper(board, word, index + 1, i, j + 1, used) || helper(board, word, index + 1, i, j - 1, used);
        used[i][j] = false;
        return res;
    }
}

Set Matrix Zeroes leetcode

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

"这是一个矩阵操作的题目，目标很明确，就是如果矩阵如果有元素为0，就把对应的行和列上面的元素都置为0。这里最大的问题就是我们遇到0的时候不能直接把矩阵的行列在当前矩阵直接置0，否则后面还没访问到的会被当成原来是0，最后会把很多不该置0的行列都置0了。
一个直接的想法是备份一个矩阵，然后在备份矩阵上判断，在原矩阵上置0，这样当然是可以的，不过空间复杂度是O(m*n)，不是很理想。
上面的方法如何优化呢？我们看到其实判断某一项是不是0只要看它对应的行或者列应不应该置0就可以，所以我们可以维护一个行和列的布尔数组，然后扫描一遍矩阵记录那一行或者列是不是应该置0即可，后面赋值是一个常量时间的判断。这种方法的空间复杂度是O(m+n)。
其实还可以再优化，我们考虑使用第一行和第一列来记录上面所说的行和列的置0情况，这里问题是那么第一行和第一列自己怎么办？想要记录它们自己是否要置0，只需要两个变量（一个是第一行，一个是第一列）就可以了。然后就是第一行和第一列，如果要置0，就把它的值赋成0（反正它最终也该是0，无论第一行或者第一列有没有0），否则保留原值。然后根据第一行和第一列的记录对其他元素进行置0。最后再根据前面的两个标记来确定是不是要把第一行和第一列置0就可以了。这样的做法只需要两个额外变量，所以空间复杂度是O(1)。
时间上来说上面三种方法都是一样的，需要进行两次扫描，一次确定行列置0情况，一次对矩阵进行实际的置0操作，所以总的时间复杂度是O(m*n)。代码如下："

讲解转自:http://codeganker.blogspot.com/2014/04/set-matrix-zeroes-leetcode.html

//空间O(m + n 做法)
public class Solution {
    public void setZeroes(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        int row = matrix.length;
        int column = matrix[0].length;
        boolean[] rowflag = new boolean[row];
        boolean[] colflag = new boolean[column];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (matrix[i][j] == 0) {
                    rowflag[i] = true;
                    colflag[j] = true;
                }
            }
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (rowflag[i] == true) {
                    matrix[i][j] = 0;
                }
            }
        }
        for (int j = 0; j < column; j++) {
            for (int i = 0; i < row ; i++) {
                if (colflag[j] == true) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}
//空间O(1)做法
public class Solution {
    public void setZeroes(int[][] matrix) {
        if (matrix == null || matrix.length == 0|| matrix[0].length == 0) {
            return;
        }
        boolean colflag = false;//记录第一列是否会变成0
        boolean rowflag = false;//记录第一行是否会变成0
        for (int i = 0; i < matrix[0].length; i++) {//判断第一列
            if(matrix[0][i] == 0) {
                rowflag = true;
                break;
            }
        }
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][0] == 0) {
                colflag = true;
                break;
            }
        }
        for (int i = 1; i < matrix.length; i++) {//用第一行和第一列存储0
            for (int j = 1; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for (int i = 1; i < matrix.length; i++) {// 把有0的对应行列都变为0
            for (int j = 1; j < matrix[0].length; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (rowflag) {//判断第一行是否全变成0
            for (int i = 0; i < matrix[0].length; i++) {
                matrix[0][i] = 0;
            }
        }
        if (colflag) {
            for (int i = 0; i < matrix.length; i++) {
                matrix[i][0] = 0;
            }
        }
        return;
    }
}

Spiral Matrix II leetcode

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = 3,

You should return the following matrix:

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

和Spiral Matrix类似, 但是这里是n*n的矩阵, 最后要判断n是否是奇数 如果是奇数那么还要添加中间的matrix[n/2][n/2]位置的数字 时间复杂度O(n^2)

public class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        if (n == 0) {
            return res;
        }
        int num = 1;
        int mid = n / 2;
        for (int i = 0; i < mid; i++) {
            for (int j = i; j < n - i - 1; j++) {
                res[i][j] = num++;
            }
            for (int j = i; j < n - i - 1; j++) {
                res[j][n - i - 1] = num++;
            }
            for (int j = n - i - 1; j > i; j--) {
                res[n - i - 1][j] = num++;
            }
            for (int j = n - i - 1; j > i; j--) {
                res[j][i] = num++;
            }
        }
        if ((n % 2) == 1) {
            res[mid][mid] = num++;
        }
        return res;
    }
}

Spiral Matrix leetcode

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

For example,
Given the following matrix:

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

You should return [1,2,3,6,9,8,7,4,5].

就是一层一层的处理矩阵, 实现中要注意两个细节，一个是因为题目中没有说明矩阵是不是方阵，因此要先判断一下行数和列数来确定螺旋的层数。另一个是走一次是走两行两列, 但是如果遇(行和列中间最小的是)单数的, 还要再判定一下然后继续走完. 

时间复杂度O(m*n)空间O(1)

public class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<Integer>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return res;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        int min = Math.min(row, col);
        int mid = min / 2;
        for (int i = 0; i < mid; i++) {
            for (int j = i; j < col - i - 1; j++) {
                res.add(matrix[i][j]);
            }
            for (int j = i; j < row - i - 1; j ++) {
                res.add(matrix[j][col - i - 1]);
            }
            for (int j = col - i - 1; j > i; j--) {
                res.add(matrix[row - i - 1][j]);
            }
            for (int j = row - i -1; j > i; j--) {
                res.add(matrix[j][i]);
            }
        }
        if (min % 2 == 1) {
            if (row < col) {
                for (int j = mid; j < col - mid; j++) {
                    res.add(matrix[mid][j]);
                }
            } else {
                for (int j = mid; j < row - mid; j++) {
                    res.add(matrix[j][mid]);
                }
            }
        }
        return res;
    }
}

Sudoku Solver leetcode

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...

与n皇后问题类似, 对于每个空格逐步添加数字, 不对了就回溯

如果对一个格子尝试从0~9都不行，那么说明整个sudoku无解，返回false

对整个棋盘所有'.'都填完了，返回true

public class Solution {
    public void solveSudoku(char[][] board) {
        if (board == null || board.length < 9 || board[0].length < 9) {
            return;
        }
        helper(board);
    }
    public boolean helper(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (char c = '1'; c <= '9'; c++) {
                        if (isValid(board, i, j, c)) {
                            board[i][j] = c;
                            if (helper(board)) {
                                return true;
                            } else {
                                board[i][j] = '.';
                            }
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    public boolean isValid(char[][] board, int i, int j, char c) {
        //check column
        for (int row = 0; row < 9; row ++) {
            if (board[row][j] == c) {
                return false;
            }
        }
        // check row
        for (int column = 0; column < 9; column++) {
            if (board[i][column] == c) {
                return false;
            }
        }
        //check block
        for (int row = i / 3 * 3; row < i / 3 * 3 + 3; row++) {
            for(int column = j / 3 * 3; column < j / 3 * 3 + 3; column++) {
                if (board[row][column] == c) {
                    return false;
                }
            }
        }
        return true;
    }
}
//
public class Solution {
    public void solveSudoku(char[][] board) {
        helper(board, 0, 0);
    }
    public boolean helper(char[][] board, int m, int n) {
        if (n >= 9) {
            return helper(board, m + 1, 0);
        }
        if (m == 9) {
            return true;
        }
        if (board[m][n] == '.') {
            for (int i = 1; i <= 9; i++) {
                board[m][n] = (char)(i + '0');
                if (isvalid(board, m, n)) {
                    if (helper(board, m, n+ 1)) {
                        return true;
                    }
                }
                board[m][n] = '.';
            }
        } else {
            return helper(board, m, n+ 1);
        }
        return false;
    }
    public boolean isvalid(char[][] board, int m, int n) {
        for (int i = 0; i < 9; i++) {
            if (i != m && board[i][n] == board[m][n]) {
                return false;
            }
        }
        for (int i = 0; i < 9; i++) {
            if (i != n && board[m][i] == board[m][n]) {
                return false;
            }
        }
        for (int i = m / 3 * 3; i< m / 3 * 3 + 3; i++) {
            for (int j = n /3 * 3; j < n / 3 *3 + 3; j++) {
                if (i != m && j != n && board[i][j] == board[m][n]) {
                    return false;
                }
            }
        }
        return true;
    }
}

Valid Sudoku leetcode

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

A partially filled sudoku which is valid.

Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

首先按照每行chek 然后每列check 最后每个block 分别check

check的方法是维护一个hashset 如果是'.'就跳过 如果是char就看set中是否包含 如果包含就return false 不包含就把当前char放入set中

对于block的i j取法比较trick 

k/ 3 * 3  ~ k / 3 * 3 + 2 是代表行数 k % 3 * 3 ~ k % 3 *3 + 2 是列数 这样对于每个k都可以表示一个block
时间复杂度 O(3*n^2)

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        HashSet<Character> set = new HashSet<Character>();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    continue;
                }
                if (set.contains(board[i][j])) {
                    return false;
                }
                set.add(board[i][j]);
            }
            set.clear();
        }
        for (int j = 0; j < 9; j++) {
            for (int i = 0; i < 9; i++) {
               if (board[i][j] == '.') {
                    continue;
                }
                if (set.contains(board[i][j])) {
                    return false;
                }
                set.add(board[i][j]);
            }
            set.clear(); 
        }
        for (int k = 0; k < 9; k++) {
            for (int i = k / 3 * 3; i < k / 3 * 3 + 3; i ++) {
                for (int j = (k % 3) * 3; j < (k % 3) * 3 + 3; j++) {
                    if (board[i][j] == '.') {
                    continue;
                }
                if (set.contains(board[i][j])) {
                    return false;
                }
                set.add(board[i][j]);
                }
            }
            set.clear(); 
        }
        return true;
    }
}

First Missing Positive leetcode

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.

因为用O(n)时间和constant空间 所以不能用hashtable. 可以将数组本身变成一个hashmap 使得nums[0] = 1, num[1] = 2... nums[i] = i + 1 最后如果哪个i违反了num[i] = i +1 , i + 1 就是我们要找的值

扫描数组中每个数：

让A[0]=1, A[1]=2, A[2]=3, ... , 这样一来，最后如果哪个数组元素违反了A[i]=i+1即说明i+1就是我们要求的第一个缺失的正数

1. 如果A[i]<1或者A[i]>n。跳过

2. 如果A[i] = i+1，说明A[i]已经在正确的位置，跳过

3. 如果A[i]!=i+1，且0<A[i]<=n，应当将A[i]放到A[A[i]-1]的位置，所以可以交换两数。

这里注意，当A[i] = A[A[i]-1]时会陷入死循环。这种情况下直接跳过。


避免2和死循环可以用 A[i] != A[A[i] - 1] 来描述

时间O(n)

public class Solution {
    public int firstMissingPositive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 1;
        }
        for (int i = 0; i < nums.length; i++) {
            if ( nums[i] > 0 && nums[i] <= nums.length && nums[nums[i] - 1] != nums[i]) {
                int tem = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i] ;
                nums[i] = tem;
                i--;
                //先改变nums[nums[i] - 1] 再改变nums[i] 否则nums[i]先变化nums[nums[i - 1]]就不是原来的位置了
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return nums.length + 1;
    }
}

Pascal's Triangle II leetcode

Given an index k, return the kth row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

与Pascal's Triangle 思路相同 难度是控制空间为O(k), 所以就只在一个arraylist上面更新修改.

与I不同的是我们对于每一行从后往前扫 每个i res[i]等于res[i-1]+ res[i]

 如果从前往后扫的话res[i]被覆盖但是对于下一个res[i + 1]还需要再用刀之前的res[i] 而不是新的res[i]

时间O(n^2) 空间O(k)

public class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> res = new ArrayList<Integer>();
        if (rowIndex < 0) {
            return res;
        }
        res.add(1);
        for (int i = 1; i <= rowIndex; i++) {
            for (int j = res.size() - 1; j > 0; j--) {
                res.set(j, res.get(j - 1) + res.get(j));
            }
            res.add(1);
        }
        return res;
    }
}

Pascal's Triangle leetcode

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,
Return

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

用一个指针保存前一行, 然后每个新行要根据前一行得出. 时间复杂度O(1 + 2 + 3...n) = O(n^2)

public class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (numRows <= 0) {
            return res;
        }
        List<Integer> tem = new ArrayList<Integer>();
        tem.add(1);
        res.add(tem);
        for (int i = 2; i <= numRows; i++) {
            List<Integer> cur = new ArrayList<Integer>();
            cur.add(1);
            for (int j = 0; j < tem.size() - 1; j++) {
                cur.add(tem.get(j) + tem.get(j + 1));
            }
            cur.add(1);
            res.add(cur);
            tem = cur;
        }
        return res;
    }
}
//只用一个list的做法
public class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (numRows <= 0) {
            return res;
        }
        List<Integer> tem = new ArrayList<Integer>();
        tem.add(1);
        res.add(new ArrayList<Integer>(tem));
        for (int i = 2; i <= numRows; i++) {
            int size = tem.size();
            for (int j = size - 1; j > 0; j--) {
                int cur = tem.get(j) + tem.get(j - 1);
                tem.set(j, cur);
            }
            tem.add(1);
            res.add(new ArrayList<Integer>(tem));
        }
        return res;
    }
}

Rotate Image leetcode

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

思路是先把matrix按照对角线翻转 再按照垂直翻转 时间 O(n * n)

1 2 3       1 4 7         7 4 1

4 5 6 --> 2 5 8 -- >  8 5 2

7 8 9       3 6 9         9 6 3 

public class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix[0].length;
        int temp;
        for(int i = 0; i < n; i++){
            for(int j = i+1; j < n; j++){
                temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
         
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n/2; j++){
                temp = matrix[i][j];
                matrix[i][j] = matrix[i][n-1-j];
                matrix[i][n-1-j] = temp;
            }
        }
    }
}
public class Solution {
    public void rotate(int[][] matrix) {
        if(matrix == null || matrix.length==0 || matrix[0].length==0) {
            return;
        }
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n - 1 - i; j++) {
                int tem = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - j][i];
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
                matrix[j][n - 1 - i] = tem;
            }
        }
    }
}

Next Permutation leetcode

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

讲解转自:http://codeganker.blogspot.com/2014/03/next-permutation-leetcode.html

"这道题是给定一个数组和一个排列，求下一个排列。算法上其实没有什么特别的地方，主要的问题是经常不是一见到这个题就能马上理清思路。下面我们用一个例子来说明，比如排列是(2,3,6,5,4,1)，求下一个排列的基本步骤是这样：1) 先从后往前找到第一个不是依次增长的数，记录下位置p。比如例子中的3，对应的位置是1;2) 接下来分两种情况：    (1) 如果上面的数字都是依次增长的，那么说明这是最后一个排列，下一个就是第一个，其实把所有数字反转过来即可(比如(6,5,4,3,2,1)下一个是(1,2,3,4,5,6));    (2) 否则，如果p存在，从p开始往后找，找到下一个数就比p对应的数小的数字(找到这样一个数，它的下一个数比p对应的数小。4的下一个数是1，比3小)，然后两个调换位置，比如例子中的4。调换位置后得到(2,4,6,5,3,1)。最后把p之后的所有数字倒序，比如例子中得到(2,4,1,3,5,6), 这个即是要求的下一个排列。

以上方法中，最坏情况需要扫描数组三次，所以时间复杂度是O(3*n)=O(n)，空间复杂度是O(1)。"

public class Solution {
    public void nextPermutation(int[] nums) {
        if (nums.length == 0 || nums == null) {
            return;
        }
        int i = nums.length - 2;
        while (i >= 0 && nums[i + 1] <= nums[i]) {
            i--;
        }
        if (i >= 0){//存在逆序的数字
            int j = i + 1;
            while (j < nums.length && nums[j] > nums[i]) {
                j++;
            }
            j--;
            int tem = nums[j];
            nums[j] = nums[i];
            nums[i] = tem;
        }
        reverse(nums, i + 1);
    }
    public void reverse(int[] nums, int index) {
        int left = index;
        int right = nums.length - 1;
        while (left < right) {
            int tem = nums[right];
            nums[right] = nums[left];
            nums[left] = tem;
            right--;
            left++;
        }
    }
}

Remove Element leetcode

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

维护一个指针从前往后扫, 如果碰到与给定的target相同的就把当前的和num[len]调换继续扫描, 并把len - 1 复杂度是O(n)

public class Solution {
    public int removeElement(int[] nums, int val) {
        if(nums == null || nums.length == 0) {
            return 0;
        }
        int len = nums.length - 1;
        for (int i = 0; i <= len; i++) {
            if (nums[i] == val) {
                nums[i] = nums[len];
                i--;
                len--;
            }
        }
        return len + 1;
    }
}

Container With Most Water leetcode

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

brute force方法是对每一对都求面积, 然后比较面积 要遍历两次  时间复杂度O(n^2)

另外一种方法是two points的方法, 从两头开始计算面积, 因为蓄水面积是由短板决定的, 每次比较左右point 哪个是短板就移动哪一个, 这样只扫面一次数组 时间O(n)

public class Solution {
    public int maxArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int left = 0;
        int right = height.length - 1;
        int area = 0;
        while (left < right) {
            area = Math.max(area, Math.min(height[left], height[right]) * (right - left));
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return area;
    }
}

Regular Expression Matching leetcode

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

(注意 ' * ' 匹配零个或者多个前面的元素 不能单独出现, 第二个string只要有一部分匹配第一个就可以)

这道题有两个case

1. 第二个char不是'*':

判定的第一个元素是否match 然后再递归match后面元素

2. 第二个char是' * '

p元素的第一个元素是. 或者p能匹配第i个元素 然后递归的match s的i+1后面 和p的* 后面元素

specail case p的长度是0 或者1 

public class Solution {
    public boolean isMatch(String s, String p) {
        if (p.length() == 0) {
            return s.length() == 0;
        }
        if (p.length() == 1) {//长度为1是special case
            return (s.length() == 1) && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.');
        }
        if (p.charAt(1) != '*') {// case 1 第二个元素不是*
            if (s.length() == 0) {
                return false;
            } else {
                return (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.') && isMatch(s.substring(1), p.substring(1));
            }
        } else {// case 2 第二个元素是*
            if (isMatch (s, p.substring(2))) {//case2.1 *不代表任何element
                return true;
            }
            int i = 0;
            //case2.2 * 代表一个或者多个element
            while (i < s.length() && (s.charAt(i) == p.charAt(0) || p.charAt(0) == '.')) {
                //因为*可以匹配多个跟前边相同的元素 只要i跟前边相同就可以继续往下找
                if (isMatch(s.substring(i + 1), p.substring(2))) {
                    return true;
                }
                i++;
            }
            return false;
        }
    }
}

Wildcard Matching leetcode

Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

如果s字符的i位和p字符的j位置如果想吻合则拿i+1 和j+1继续比较

用一个star来记录*出现的位置, 首先当前字符i先和*的下一位比较, 如果不符合的话, 那么用i+1和*下一位比较 以此类推
while循环以第一个字符的长度作为限定, 最后判定第一个字符循环完是否第二个字符也全部走完 走完true 否则false

public class Solution {
    public boolean isMatch(String s, String p) {
        int i = 0;
        int j = 0;
        int star = -1;
        int mark = -1;
        while (i < s.length()) {
            if (j < p.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '?')) {
                i++;
                j++;
            } else if (j < p.length() && p.charAt(j) == '*') {
                star = j;
                mark = i;
                j++;
            } else if (star != -1) {
                //匹配s中当前字符与p中*后面的字符，如果匹配，则在第一个if中处理，如果不匹配，则继续比较s中的下一个字符。
                j = star + 1;
                i = mark + 1;
                mark++;
            } else {
                return false;
            }
        }
        while (j < p.length() && p.charAt(j) == '*') {//如果字符串后面有多余的* 
            j++;
        }
        return j == p.length();
    }
}

Length of Last Word leetcode

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example,
Given s = "Hello World",
return 5.

第一种方法是把string按照" " 分成string[] 返回最后一个
第二种方法是维护一个count 从后面往前数遇到第一个空格为止,返回count值 如果count为0 说明最后一个字符是空格 继续往前数一个string 

public class Solution {
    public int lengthOfLastWord(String s) {
        String[] tem = s.split(" ");
        if (tem.length == 0 || tem == null) {
            return 0;
        }
        return tem[tem.length - 1].length();
    }
}
public class Solution {
    public int lengthOfLastWord(String s) {
        if (s.length() == 0 || s == null) {
            return 0;
        }
        int count = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) != ' ') {
                count++;
            }
            if (s.charAt(i) == ' ' && count != 0) {
                return count;
            }
        }
        return count;
    }
}

Group Anagrams leetcode

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

把给的string都变成charArray然后排序, 把sort好的再变成string 存入hashmap, map 的value值为一个list<> list内存放变形之前的string.

如果一个string在hashmap中出现过 这个string一定是个变形词 把各个string放入对应的list中,遍历一次时间复杂度O(nlogn) + O(n*klogk) = O(nlogn)

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<List<String>>();
        if (strs == null || strs.length == 0) {
            return res;
        }
        Arrays.sort(strs);
        HashMap<String, List<String>> map = new HashMap<String, List<String>>();
        for (String s : strs) {
            char[] chararray = s.toCharArray();
            Arrays.sort(chararray);
            String temstr = new String(chararray);
            if (map.containsKey(temstr)) {
                map.get(temstr).add(s);
            } else {
                List<String> tem = new ArrayList<String>();
                tem.add(s);
                map.put(temstr, tem);
            }
        }
        for (List<String> l : map.values()) {
            res.add(l);
        }
        return res;
    }
}

Implement strStr() leetcode

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

就是给一个target 看target里面是否包含另外给定的字符

假设target长度m 匹配长度n, 对target每个长度为n的substring都检查一次 时间O((m- n)* n)= O(m*n)

public class Solution {
    public int strStr(String haystack, String needle) {
        if (haystack == null || needle == null || needle.length() == 0) {
            return 0;
        }
        if (needle.length() > haystack.length()) {
            return -1;
        }
        for (int i = 0; i <= haystack.length() - needle.length(); i++) {
            boolean res = true;
            for (int j = 0; j < needle.length(); j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    res = false;
                    break;
                }
            }
            if (res == true) {
                return i;
            }
        }
        return -1;
    }
}

Max Points on a Line leetcode

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
给一个2d的平面, 所给的数据结构point代表一个点, 让找一条点最多的直线. 
对于一个点来说斜率相同的就在一条直线上, 所以遍历所有点i, 对于每个点再遍历一次, 得到所有的斜率存入hashmap key是斜率 value是此斜率上的点数, 如果key已经存在的话就value + 1 不存在就给value赋值2(一条线有两个点) 这里要注意因为遍历可能会出现跟i点相同的点(x, y 值都相同),对于这样的点他存在在i为起始的所有直线上 所以我们维护一个same来记录这样的点的个数.
最后value中的最大值加上same的个数就是每个i点的最多直线数目 比较每个i点得到最后的最多直线
注意: 第二次遍历不用从0开始遍历 直接从i开始遍历就可以 (后面的点就不用太回头看已经扫描过得点)因为如果此点和前边的点组成的线是最多的点 那么前边已经遍历过了
因为会出现slop = 0 或者slop = 无穷大 但是因为slop是double型数 所有的0 不相等 所以单独拿出来讨论

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    public int maxPoints(Point[] points) {
        if (points == null || points.length == 0) {
            return 0;
        }
        int max = 1;
        for (int i = 0; i < points.length; i++) {
            HashMap<Double, Integer> hash = new HashMap<Double, Integer>();
            int localmax = 1;//最少一个点
            int same = 0;
            double slop = 0.0;
            for (int j = i + 1; j < points.length; j++) {
                if (points[j].x == points[i].x && points[j].y == points[i].y) {
                    same++;
                    continue;
                } 
                if (points[j].y == points[i].y) {
                    slop = 0.0;
                } else if (points[j].x == points[i].x) {
                    slop = (double) Integer.MAX_VALUE;
                } else {
                    slop = (double) (points[j].y - points[i].y) / (double)(points[j].x - points[i].x);
                }
                if (hash.containsKey(slop)) {
                    hash.put(slop, hash.get(slop) + 1);
                } else {
                    hash.put(slop, 2);
                }
            }
            for (Integer value : hash.values()) {
                localmax = Math.max(localmax, value);
            }
            localmax += same;
            max = Math.max(localmax, max);
        }
        return max;
    }
}

Valid Number

Validate if a given string is numeric.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

要满足的情况:

对于一个小数点:

1.前边不能出现过小数点或者exp 2.不能单独存在(.) 3.如果他是0位 后边必须是数字 4. 如果是最后一位前边也必须是数字

对于 e 或者E

1. 不能前边存在exp 2. 不能是最后一位或者第一位 3.前一位必须是数字或者'.' 4. 后一位必须是数字或者加减号

对于加减号:

1.不能是最后一位 2. 如果不是第一位的话能把么前边必须是e 或者E 3.下一位必须是数字或者'.'

public class Solution {
    public boolean isNumber(String s) {
        if (s == null) {
            return false;
        }
        s = s.trim();
        if (s.length() == 0) {
            return false;
        }
        boolean dot = false;
        boolean exp = false;
        for (int i = 0; i < s.length(); i++) {
            switch(s.charAt(i)) {
                case '.':
                    if ( dot|| exp|| ((i==0||!(s.charAt(i-1)>='0'&&s.charAt(i-1)<='9')) 
                    && (i==s.length()-1||!(s.charAt(i+1)>='0'&&s.charAt(i+1)<='9')))){
                        return false;
                    }
                    dot = true;
                    break;
                case 'e':
                case 'E':
                    if (i == 0 || i == s. length() - 1|| exp|| !((s.charAt(i - 1) >= '0' && s.charAt(i - 1) <= '9')|| s.charAt(i - 1) == '.')|| !((s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9') || s.charAt(i + 1) == '+' || s.charAt(i + 1) == '-' )) {
                        return false;
                    }
                    exp = true;
                    break;
                case '+':
                case '-':
                    if ((i > 0 && s.charAt(i - 1) != 'e' && s.charAt(i - 1) != 'E') || i == s.length() - 1 || !((s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9') || s.charAt(i + 1) == '.')) {
                        return false;
                    }
                    break;
                case '0':
                case '1':
                case '2':
                case '3':
                case '4':
                case '5':
                case '6':
                case '7':
                case '8':
                case '9':
                    break;
                default://对于其他情况 如字母空格
                return false;
            }
        }
        return true;
    }
}

Sqrt(x) leetcode

Implement int sqrt(int x).
注意这道题是返回int 的平方根 所以:

sqrt(3) = 1

sqrt(4) = 2

sqrt(5) = 2

sqrt(10) = 3

用二分法来判定 逐步找到平方根, 但是要注意的是只要符合 mid^2 <= x < (mid + 1)^2 那么mid就是x的平方根.

另外要注意的是mid^2可能溢出 所以用x/mid >= mid的形式来表示

时间复杂度是O(log(x)) 空间是O(1)

public class Solution {
    public int mySqrt(int x) {
        if (x < 0) {
            return -1;
        } else if (x == 0) {
            return 0;
        }
        int left = 1;
        int right = x;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (x / mid >= mid  && x / (mid + 1) < mid + 1 ) {
                return mid;
            } else if (x / mid < mid) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return 0;
    }
}

Add Binary leetcode

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

从低位开始相加, 每得出一位的结果添加到result里 最后得到的result是低位在前边 所以要reverse一下.

只遍历了一次 时间复杂度是O(max(m,n)) 空间复杂度也是O(max(m,n))

public class Solution {
    public String addBinary(String a, String b) {
        if (a == null || a.length() == 0) {
            return b;
        }
        if (b == null || b.length() == 0) {
            return a;
        }
        int next = 0;
        int digit;
        StringBuilder res = new StringBuilder();
        int i = a.length() - 1;
        int j = b.length() - 1;
        while (i >= 0 && j>=0) {
            digit = a.charAt(i) - '0' + b.charAt(j) - '0' + next;
            next = digit / 2;
            digit = digit % 2;
            res.append(digit);
            i--;
            j--;
        }
        while (i >= 0) {
            digit = a.charAt(i) - '0' + next;
            next = digit / 2;
            digit = digit % 2;
            res.append(digit);
            i--;
        }
        while (j >= 0) {
            digit = b.charAt(j) - '0' + next;
            next = digit / 2;
            digit = digit % 2;
            res.append(digit);
            j--;
        }
        if (next > 0) {
            res.append(next);
        }
        return res.reverse().toString();
    }
}