Missing Ranges leetcode

Given a sorted integer array where the range of elements are [lower, upper] inclusive, return its missing ranges.

For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99, return ["2", "4->49", "51->74", "76->99"].

public class Solution {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> res = new ArrayList<String>();
        if (nums.length == 0) {
            res.add(helper(lower, upper));
            return res;
        }
        if (nums[0] > lower) {
            res.add(helper(lower, nums[0] - 1));
        }
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] - nums[i - 1] > 1) {
                res.add(helper(nums[i - 1] + 1, nums[i] - 1));
            }
        }
        if (nums[nums.length - 1] < upper) {
            res.add(helper(nums[nums.length - 1] + 1, upper));
        }
        return res;
    }
    public String helper(int lower, int upper) {
        if (lower == upper) {
            return lower + "";
        } else {
            return lower + "->" + upper;
        }
    }
}

Two Sum II - Input array is sorted leetcode

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

时间 O(n) space O(1)

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;
        int[] res = new int[2];
        while (left < right) {
            if (numbers[left] + numbers[right] == target) {
                res[0] = left + 1;
                res[1] = right + 1;
                return res;
            } else if (numbers[left] + numbers[right] > target) {
                right--;
            } else {
                left++;
            }
        }
        return null;
    }
}

Rotate Array leetcode

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

采用三步翻转法

public class Solution {
    public void rotate(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return;
        }
        int n = nums.length;
        if (k > n) {
            k = k%n;
        }
        rotate(nums, 0, n - k - 1);
        rotate(nums, n - k, n - 1);
        rotate(nums, 0, n - 1);
    }
    public void rotate(int[] nums, int left, int right) {
        if (left > right) {
            return;
        }
        int start = left;
        int end = right;
        while (start < end) {
            int tem = nums[start];
            nums[start] = nums[end];
            nums[end] = tem;
            start++;
            end--;
        }
    }
}

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

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

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

candy leetcode

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

与trapping rain water相同, 初始化所有都为1

从左往右遍历找到相对于左边所需要的最小数量  这一次保证相邻儿童比左边的rating高的拿得多

再从右往左遍历找到相对于右边最小数量, 这一次遍历可以保证相邻的儿童比右边rating高的拿得多, 不会影响左边的 因为左边相邻的也可以确保比他的右边rating高的拿得多

最终数量为这两个数量中最大的
时间O(n) 空间 O(n)

public class Solution {
    public int candy(int[] ratings) {
       if (ratings.length == 0 || ratings == null) {
           return 0;
       }
       int len = ratings.length;
       int[] left = new int[len];
       int[] right = new int[len];
       left[0] = 1;
       for (int i = 1; i < len; i++) {
           if (ratings[i] > ratings[i-1]) {
               left[i] = left[i-1] +1;
           } else {
               left[i] = 1;
           }
       }
       right[len - 1] = left[len - 1];
       for (int j = len - 2; j >= 0; j--) {
           if (ratings[j] > ratings[j + 1]) {
               right[j] = right[j +1] +1;
           } else {
               right[j] = 1;
           }
       }
       int res = 0;
       for (int i = 0; i < len; i++) {
           res += Math.max(left[i], right[i]);
       }
       return res;
    }
}

Trapping Rain Water leetcode

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.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

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!

对于位置i可蓄水量取决于他的左右侧高度的较小值与height[i]的差值, 所以只要找到i的左侧的短板和右侧短板 

从左到右遍历一遍找到左侧的短板 再从右到左便利一次找到右边的短板
一共遍历三次 时间O(n) 空间 O(n)

public class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int len = height.length;
        int[] left = new int[len];
        int[] right = new int[len];
        int leftmax = height[0];
        int rightmax = height[len - 1];
        for (int i = 1; i < len; i ++) {
            left[i] = Math.max(leftmax, height[i]);
            leftmax = Math.max(leftmax, height[i]);
        }
        for (int j = len - 2; j >= 0; j--) {
            right[j] = Math.max(rightmax, height[j]);
            rightmax = Math.max(rightmax, height[j]);
        }
        int res = 0;
        for (int i = 0; i < len; i ++) {
            int tem = Math.min(left[i], right[i]) - height[i];
            if (tem > 0) {
                res += tem;
            }
        }
        return res;
    }
}

Median of Two Sorted Arrays leetcode

第一种方法 先把两个数组合并, 然后返回新数组的中间值 时间复杂度 O(m + n) 空间 O(m + n)

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[] tem = new int[m + n];
        int idx1 = m - 1;
        int idx2 = n - 1;
        int idx = idx1 + idx2 + 1;
        while (idx1 >= 0 && idx2 >= 0) {
            if (nums1[idx1] >= nums2[idx2]) {
                tem[idx--] = nums1[idx1--];
            } else {
                tem[idx--] =  nums2[idx2--];
            }
        }
        if (idx2 < 0) {
            for (int i = idx1; i >= 0; i--) {
                tem[idx--] = nums1[i];
            }
        }
        if (idx1 < 0) {
            for (int i = idx2; i>= 0; i--) {
                tem[idx--] = nums2[i];
            }
        }
        if ((m + n) % 2 == 1) {
            return tem[(m + n) / 2 ];
        } else {
            return (tem[(m + n) / 2] + tem[(m + n) / 2 - 1]) / 2.0;
        }
    }
}

可以依照：寻找一个unioned sorted array中的第k大（从1开始数）的数。因而等价于寻找并判断两个sorted array中第k/2（从1开始数）大的数。

特殊化到求median，那么对于奇数来说，就是求第(m+n)/2+1（从1开始数）大的数。

而对于偶数来说，就是求第(m+n)/2大（从1开始数）和第(m+n)/2+1大（从1开始数）的数的算术平均值。

那么如何判断两个有序数组A,B中第k大的数呢？

我们需要判断A[k/2-1]和B[k/2-1]的大小。

如果A[k/2-1]==B[k/2-1]，那么这个数就是两个数组中第k大的数。

如果A[k/2-1]<B[k/2-1], 那么说明A[0]到A[k/2-1]都不可能是第k大的数，所以需要舍弃这一半，继续从A[k/2]到A[A.length-1]继续找。当然，因为这里舍弃了A[0]到A[k/2-1]这k/2个数，那么第k大也就变成了，第k-k/2个大的数了。

如果 A[k/2-1]>B[k/2-1]，就做之前对称的操作就好。

 这样整个问题就迎刃而解了。

当然，边界条件页不能少，需要判断是否有一个数组长度为0，以及k==1时候的情况。

因为除法是向下取整，并且页为了方便起见，对每个数组的分半操作采取：

int partA = Math.min(k/2,m);
int partB = k - partA; 

 为了能保证上面的分半操作正确，需要保证A数组的长度小于B数组的长度。
总的时间复杂度为O(logk),空间复杂度也是O(logk)，即为递归栈大小。在这个题目中因为k=(m+n)/2,所以复杂度是O(log(m+n))。

同时，在返回结果时候，注意精度问题，返回double型的就好。 

public class Solution {
    public double findMedianSortedArrays(int A[], int B[]) {
        int m = A.length;
        int n = B.length;
        if ((m + n) % 2 ==1 ){
            return helper(A, 0, m - 1, B, 0, n - 1, (m + n) / 2 + 1);//k传得是第k个，index实则k-1
        } else {
            return (helper(A, 0, m - 1, B, 0, n - 1, (m + n) / 2 + 1) + helper(A, 0, m - 1, B, 0, n - 1, (m + n) / 2)) / 2.0;
        }
    }
    public int helper(int A[], int i, int i0, int B[], int j, int j0, int k){
        int a = i0 - i + 1;// x现有的A数组长度
        int b = j0 - j + 1;
        if (a > b){ // 如果A数组比B数组长 反过来比较
            return helper(B, j, j0, A, i, i0, k);
        }
        if (a == 0){ //当A数组的值全部比较完的时候
            return B[j + k -  1];//此时的k与原来的k相比已经删除了A的长度 
                                //-1是因为index要-1
        }
        if (k == 1){//此时必须要退出 因为k==1时候已经无法再往下分
            return Math.min(A[i], B[j]);
        }
        int posA = Math.min(k/2, a);//防止此时k/2溢出
        int posB = k - posA;
        if (A[posA + i -1] == B[posB + j - 1]){// 如果相等 则中心元素就为次相等值
            return A[posA + i - 1];
        } else if(A[posA + i -1] > B[posB + j - 1]){
            return helper(A, i, i0, B, posB + j, j0, k - posB);//删除前posB个元素
        } else{
            return helper(A, posA + i, i0, B, j, j0, k - posA);
        }
    }
}

Merge Sorted Array leetcode

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are mand n respectively.

用倒序的方法从大到小排列，i = m+n-1 注意for循环内都是if语句 时间O(m+n)

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int j = m - 1;
        int k = n - 1;
        for (int i = m + n - 1; i >= 0; i--){
            if (k >= 0 && j >= 0){
                if (A[j] > B[k]){
                    A[i] = A[j];
                    j--;
                } else {
                    A[i] = B[k];
                    k--;
                }
            } else if (k >= 0){
                A[i] = B[k];
                k--;
            } else {// 这个else判定可以没有 因为此时i==j
                A[i] = A[j];
                j--;
            }
        }
        
    }
}

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int index = m + n - 1;
        int i = m - 1;
        int j = n -1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[index] = nums1[i];
                i--;
                index--;
            } else {
                nums1[index] = nums2[j];
                j--;
                index--;
            }
        }
        while (j >= 0) {
            nums1[index] = nums2[j];
            j--;
            index--;
        }
    }
}

Remove Duplicates from Sorted Array II leetcode

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

依旧是两个指针，并且用一个count来记录重复次数。  遍历一次 时间O(n)空间 O(1)

public class Solution {
    public int removeDuplicates(int[] nums) {
        int index = 1;
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                count++;
                if (count >= 3) {
                    continue;
                }
            } else{
                count = 1;
            }
            nums[index++] = nums[i];
        }
        return index;
    }
}

Remove Duplicates from Sorted Array leetcode

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

这道题用两个指针， 一个保留当前有效的长度 一个往后扫 因为是排序过得数组，重复元素一定是相邻的。 复杂度O(n)空集复杂度O(1).

public class Solution {
    public int removeDuplicates(int[] A) {
        if (A == null || A.length == 0){
            return 0;
        }
        int index = 1;
        for (int i = 1; i < A.length; i++){
            if (A[i] != A[i - 1]){
                A[index] = A[i];
                index ++;
            }
        }
        A = Arrays.copyOf(A, index);
        return index;
    }
}

subsetsII leetcode

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

public class Solution {
    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if(num.length == 0|| num == null){
            return result;
        }
        ArrayList<Integer> tem = new ArrayList<Integer>();
        Arrays.sort(num);
        dfs(result, tem, num, 0);
        return result;
    }
    public void dfs(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> tem, int[] num, int pos){
        result.add(new ArrayList<Integer> (tem));
        for(int i=pos; i<num.length; i++){
            if ( i != pos && num[i] == num[i - 1]) {
                continue;
            }    
            tem.add(num[i]);
            dfs(result,tem,num,i+1);
            tem.remove(tem.size()-1);
            
        }
    }
}

1. 这道题之前一定要sort一下。
2.判重用了一个if语句
分析：
假设还用subset方法 对于[1,2,2,2]
结果是[]
[1]
[1, 2(1)]
[1, 2(1), 2(2)]
[1, 2(1), 2(2), 2(3)]
[1, 2(1), 2(3)]//把2（3）删去 再把2(2)删去,此时2(1)层没循环完, 还可以再加入2(3)
[1,2(2)]
[1,2(2),(2,3)]
.............
只关心取了几个2不在乎取哪几个

在if语句里 i!= pos, 说明pos位置的数上一次已经取过(已跳过),为了避免与已经跳过的数重复, 说以如果num[i]==num[i-1]就continue