public int maximalRectangle2(char[][] matrix) {
        // 思路： 和84题一样
        if (matrix.length == 0) return 0;
        int m = matrix.length;
        int n = matrix[0].length;
        int[] left = new int[n];
        int[] right = new int[n];
        int[] height = new int[n];
        Arrays.fill(left, 0);
        Arrays.fill(right, 0);
        Arrays.fill(height, 0);
        int maxA = 0;
        for (int i = 0; i < m; i++) {
            int cur_left = 0, cur_right = n;
            for (int j = 0; j < n; j++) { // compute height (can do this from either side)
                if (matrix[i][j] == '1') height[j]++;
                else height[j] = 0;
            }
            for (int j = 0; j < n; j++) { // compute left (from left to right)
                if (matrix[i][j] == '1') left[j] = Math.max(left[j], cur_left);
                else {
                    left[j] = 0;
                    cur_left = j + 1;
                }
            }
            // compute right (from right to left)
            for (int j = n - 1; j >= 0; j--) {
                if (matrix[i][j] == '1') right[j] = Math.min(right[j], cur_right);
                else {
                    right[j] = n;
                    cur_right = j;
                }
            }
            // compute the area of rectangle (can do this from either side)
            for (int j = 0; j < n; j++)
                maxA = Math.max(maxA, (right[j] - left[j]) * height[j]);
        }
        return maxA;
    }
}

package com.leetcode;

import java.util.Arrays;

public class MergeSortedArray88 {
    public static void main(String[] args) {
        int[] a = new int[]{1, 2, 4, 5, 6, 0};
        int[] b = new int[]{3};
        new Solution().merge(a, 5, b, 1);
        System.out.println(Arrays.toString(a));
    }

    /**
     * 思路：把前m个数放到nums1后面m个上，前面m个当作空的用来存放结果
     */
    private static class Solution {
        public void merge(int[] nums1, int m, int[] nums2, int n) {
            if (n == 0) return;
            if (m == 0) {
                for (int i = 0; i < nums1.length; i++) {
                    nums1[i] = nums2[i];
                }
                nums1[0] = nums2[0];
                return;
            }
            // 不开辟多余空间的写法且速度为 o(m+n)
            for (int i = m - 1; i >= 0; i--) {
                nums1[i + nums1.length - m] = nums1[i];
            }
            int p1 = nums1.length - m;
            int p2 = 0;
            int pres = 0;
            while (pres < nums1.length) {
                if (p1 == nums1.length) {
                    for (; p2 < n; p2++) {
                        nums1[pres++] = nums2[p2];
                    }
                } else if (p2 == n) {
                    return;
                } else {
                    if (nums1[p1] < nums2[p2]) nums1[pres++] = nums1[p1++];
                    else nums1[pres++] = nums2[p2++];
                }
            }
        }

        public void merge2(int[] nums1, int m, int[] nums2, int n) {
            int p1 = 0;
            int p2 = 0;
            int pres = 0;
            int[] res = new int[nums1.length];
            while (p1 < m || p2 < n) {
                if (p1 == m) {
                    for (; p2 < n; p2++) {
                        res[pres++] = nums2[p2];
                    }
                } else if (p2 == n) {
                    for (; p1 < m; p1++) {
                        res[pres++] = nums1[p1];
                    }
                } else {
                    if (nums1[p1] < nums2[p2]) res[pres++] = nums1[p1++];
                    else res[pres++] = nums2[p2++];
                }
            }
            nums1 = res;
        }
    }
}

package com.leetcode;

import java.util.Arrays;

public class ConstructBinaryTreefromPreorderandInorderTraversal105 {
    public static void main(String[] args) {
        TreeNode root = new Solution().buildTree(
                new int[]{3,9,20,15,7}, new int[]{9,3,15,20,7}
        );
//        System.out.println(Arrays.toString());

    }

    private static class Solution {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            return constructTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
        }

        /**
         * @param preOrder 前序遍历结果
         * @param preS     结果开始下标
         * @param preE     结果结束下标
         * @param inOrder
         * @param inS
         * @param inE
         * @return
         */
        public TreeNode constructTree(int[] preOrder, int preS, int preE, int[] inOrder, int inS, int inE) {
            // 无遍历结果
            if (preS > preE || inS > inE) return null;
            else if (preS == preE) return new TreeNode(preOrder[preS]);
            // 找到根节点
            TreeNode root = new TreeNode(preOrder[preS]);
            // 找到中序遍历的左边和右边两个集合
            int rootPosi;
            for (rootPosi = inS; rootPosi <= inE; rootPosi++) {
                if (root.val == inOrder[rootPosi]) break;
            }
            // 找到前序遍历的左右两个集合
//            int preEnd;
//            for (preEnd = preS + 1; preEnd <= preE; preEnd++) {
//                // 判断是否在左集合内
//                boolean ifContains = false;
//                for (int i = inS; i <= rootPosi - 1; i++) {
//                    if (inOrder[i] == preOrder[preEnd]) ifContains = true;
//                }
//                if (!ifContains) {
//                    break;
//                }
//            }
//            preEnd--;
            int leftTreeLen = rootPosi-inS;
            root.left = constructTree(preOrder, preS + 1, preS+leftTreeLen, inOrder, inS, rootPosi - 1);
            root.right = constructTree(preOrder, preS+leftTreeLen + 1, preE, inOrder, rootPosi + 1, inE);
            return root;
        }
    }

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}

private void doSort(int[] nums, int start, int end) {
           if (start >= end) return;
           int tmp = nums[start];
           int startPoint = start;
           int endPoint = end;
           while (startPoint < endPoint) {
               while (startPoint < endPoint && nums[endPoint] > tmp) endPoint--;
               if (startPoint < endPoint) nums[startPoint++] = nums[endPoint];
               while (startPoint < endPoint && nums[startPoint] < tmp) startPoint++;
               if (startPoint < endPoint) nums[endPoint--] = nums[startPoint];
           }
           nums[startPoint] = tmp;
           doSort(nums, start, startPoint - 1);
           doSort(nums, startPoint + 1, end);
       }

package com.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

public class Subsets {
    public static void main(String[] args) {
        List<List<Integer>> subsets = new Solution().subsets(new int[]{0});
        subsets.forEach(x -> {
            x.forEach(System.out::print);
            System.out.println();
        });
    }

    /**
     * Given an integer array nums of unique elements, return all possible subsets (the power set).
     * <p>
     * The solution set must not contain duplicate subsets. Return the solution in any order.
     */
      /**
     * 回溯法
     */
    private static class Solution2 {
        public List<List<Integer>> subsets(int[] nums) {
            List<List<Integer>> ans = new ArrayList<>();
            getAns(nums, 0, new ArrayList<>(), ans);
            return ans;
        }

        private void getAns(int[] nums, int start, ArrayList<Integer> temp, List<List<Integer>> ans) {
            ans.add(new ArrayList<>(temp));
            for (int i = start; i < nums.length; i++) {
                temp.add(nums[i]);
                getAns(nums, i + 1, temp, ans);
                temp.remove(temp.size() - 1);
            }
        }
    }
    private static class Solution {
        public List<List<Integer>> subsets(int[] nums) {

            List<Integer> list = Arrays.stream(nums).boxed().collect(Collectors.toList());
            List<List<Integer>> lists = null;
            if (nums.length < 2) {
                lists = new ArrayList<>();
            } else {
                lists = doSplit(list);
            }
            for (int num : nums) {
                lists.add(Arrays.asList(num));
            }
            lists.add(new ArrayList<>());
            return lists;
        }

        List<List<Integer>> doSplit(List<Integer> nums) {
            List<List<Integer>> res = new LinkedList<>();
            if (nums.size() == 2) {
                res.add(Arrays.asList(nums.get(0), nums.get(1)));
                return res;
            }
            int startNum = nums.get(0);
            nums.remove(0);
            nums.forEach(x -> {
                res.add(Arrays.asList(startNum, x));
            });
            List<List<Integer>> subs = doSplit(nums);
            res.addAll(subs);
            subs.forEach(x -> {
                ArrayList<Integer> tmp = new ArrayList<>(x);
                tmp.add(0, startNum);
                res.add(tmp);
            });

            return res;
        }

    }
}

package com.leetcode;

import java.util.Arrays;

public class WordSearch79 {
    public static void main(String[] args) {
        System.out.println(new Solution().exist(new char[][]{
                {'a', 'a', 'a', 'a'}, {'a', 'a', 'a', 'a'}, {'a', 'a', 'a', 'a'}
        }, "aaaaaaaaaaaaa"));
    }

    /**
     * Given an m x n grid of characters board and a string word, return true if word exists in the grid.
     * <p>
     * The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
     */
    private static class Solution {
        public boolean exist(char[][] board, String word) {
            // 1. 定位到字母开头
            int colLen = board[0].length;
            char character = word.charAt(0);
            boolean[][] usage = new boolean[board.length][colLen];
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < colLen; j++) {
                    if (board[i][j] == character) {
                        // 2. 判断是否能找完
                        usage[i][j] = true;
                        if (doFind(board, i, j, -1, 1, word, usage)) return true;
                        else usage[i][j] = false;
                    }
                }
            }
            return false;
        }

        /**
         * @param board          矩阵
         * @param i              当前位置
         * @param j
         * @param previousDirect 从哪来
         * @param chPosi         要查找的字符位置
         * @return
         */
        private boolean doFind(char[][] board, int i, int j, int previousDirect, int chPosi, String word, boolean[][] usage) {
            if (chPosi == word.length()) return true;
            // 0 1 2 3  上 下 左 右
            if (previousDirect != 0 && i > 0 && !usage[i - 1][j] && board[i - 1][j] == word.charAt(chPosi)) {
                usage[i - 1][j] = true;
                if (doFind(board, i - 1, j, 1, chPosi + 1, word, usage)) return true;
                else usage[i - 1][j] = false;
            }
            if (previousDirect != 1 && i < board.length - 1 && !usage[i + 1][j] && board[i + 1][j] == word.charAt(chPosi)) {
                usage[i + 1][j] = true;
                if (doFind(board, i + 1, j, 0, chPosi + 1, word, usage)) return true;
                else usage[i + 1][j] = false;
            }
            if (previousDirect != 2 && j > 0 && !usage[i][j - 1] && board[i][j - 1] == word.charAt(chPosi)) {
                usage[i][j - 1] = true;
                if (doFind(board, i, j - 1, 3, chPosi + 1, word, usage)) return true;
                else usage[i][j - 1] = false;
            }
            if (previousDirect != 3 && j < board[0].length - 1 && !usage[i][j + 1] && board[i][j + 1] == word.charAt(chPosi)) {
                usage[i][j + 1] = true;
                if (doFind(board, i, j + 1, 2, chPosi + 1, word, usage)) return true;
                else usage[i][j + 1] = false;
            }
            return false;
        }
    }
}

package com.leetcode;

import java.util.Arrays;

public class RemoveDuplicates80 {
    public static void main(String[] args) {
        int[] tmp = new int[]{1, 2, 2, 2, 3, 3};
        System.out.println(new Solution().removeDuplicatesEasy(tmp));
        System.out.println(Arrays.toString(tmp));
    }

    private static class Solution {
        public int removeDuplicates(int[] nums) {

            int point = 1;
            int same = nums[0];
            int sameTimes = 0;
            int len = nums.length;
            while (point < len) {
                if (nums[point] == same) sameTimes++;
                else {
                    same = nums[point];
                    sameTimes = 0;
                }
                if (sameTimes >= 2) {
                    for (int i = point + 1; i < len; i++) {
                        nums[i - 1] = nums[i];
                    }
                    len--;
                    point--;
                }
                point++;
            }
            return len;
        }

        /**
         * Success
         * Details
         * Runtime: 1 ms, faster than 16.69% of Java online submissions for Remove Duplicates from Sorted Array II.
         * Memory Usage: 38.6 MB, less than 99.46% of Java online submissions for Remove Duplicates from Sorted Array II.
         * Next challenges:
         *
         * @param nums
         * @return
         */
        public int removeDuplicatesFaster(int[] nums) {
            // 差距 默认为-1，如果这一次和上一次相等 差值为0 如果这一次和上一次再相等差值++ 如果这一次和上一次不等，判断差距，移动，然后重设为-1；
            int range = -1;
            int point = nums.length - 2;
            int len = nums.length;
            while (point >= 0) {
                if (nums[point] == nums[point + 1]) range++;
                if (nums[point] != nums[point + 1] || point == 0) {
                    if (range >= 1) {
                        len -= range;
                        if (point == 0 && nums[0] == nums[1]) point--;
                        for (int i = point + 1; i < len; i++) {
                            nums[i] = nums[i + range];
                        }
                    }
                    range = -1;
                }
                point--;
            }
            return len;
        }

        public int removeDuplicatesEasy(int[] nums) {
                int i = 0;
                for (int n : nums)
                    if (i < 2 || n > nums[i-2])
                        nums[i++] = n;
                return i;
        }
    }
}

package com.leetcode;

public class SearchinRotatedSortedArrayII81 {
    public static void main(String[] args) {
        System.out.println(new Solution().search2(new int[]{2, 5, 6, 0, 0, 1, 2}, 3));
    }

    /**
     * There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).
     * <p>
     * Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].
     * <p>
     * Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.
     */
    private static class Solution {
        public boolean search(int[] nums, int target) {
            int posi = findSplitPosi(nums, 0, nums.length - 1);
            System.out.println(posi);
            return false;
        }

        int findSplitPosi(int[] nums, int start, int end) {
            if (start > end - 1) return 0;
            int mid = (start + end) / 2;
            if (nums[mid] > nums[mid + 1]) return mid + 1;
            else {
                if (nums[mid] > nums[nums.length - 1]) return findSplitPosi(nums, mid + 1, end);
                else return findSplitPosi(nums, start, mid);
            }
        }

        /**
         * 一次性找出 就不再像上一个一样先找出两个顺序数组了
         *
         * @param nums
         * @param target
         * @return
         */
        public boolean search2(int[] nums, int target) {
            return doSearch(nums, target, 0, nums.length - 1);
        }

        private boolean doSearch(int[] nums, int target, int start, int end) {
            if (start > end) return false;
            boolean isSorted = nums[start] < nums[end];
            if (isSorted && target > nums[start] && target > nums[end]) return false;
            int mid = (start + end) / 2;
            if (nums[mid] == target) return true;
                // 在左区间？ 如果区间非顺序，那么也可能在右区间
            else if (nums[mid] > target) {
                if (isSorted) return doSearch(nums, target, start, mid - 1);
                else return doSearch(nums, target, start, mid - 1) || doSearch(nums, target, mid + 1, end);
            }
            // 右区间？
            else {
                if (isSorted) return doSearch(nums, target, mid + 1, end);
                else return doSearch(nums, target, start, mid - 1) || doSearch(nums, target, mid + 1, end);
            }
        }
    }
}

package com.leetcode;

import java.util.Arrays;
import java.util.Map;

public class LargestRectangleArea {
    public static void main(String[] args) {
        System.out.println(new Solution().largestRectangleArea(new int[]{
               3,6,5,7,4,8,1,0
        }));
    }

    /**
     * Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.
     * <p>
     * 思路：很简单，先准备一个数组用来存放每个数的最大面积，然后从第一个开始，先看数组有没有没有再动，如果右边的小于左边，那么第一个的最大面积为右边的数的最大面积，
     * 去算右边的最大面积且存储在数组中，
     */
    private static class Solution {
        public int largestRectangleArea(int[] heights) {
            int[] areas = new int[heights.length];
            Arrays.fill(areas, 0);
            int max = 0;
            for (int i = 0; i < heights.length; i++) {
                max = Math.max(max, doFindArea(heights, i, areas));
            }
            return max;
        }

        /**
         * 找到这个位置的最大面积
         *
         * @param heights
         * @param posi
         * @param areas
         * @return
         */
        private int doFindArea(int[] heights, int posi, int[] areas) {
            // 当前最大面积不存在，开始查
            if (areas[posi] == 0) {
                areas[posi] = heights[posi];
                int i = posi, j = posi;
                int leftMax = 0;
                int rightMax = 0;
                // 往左走，找到左边比自己小的最大值，本身区域也增加
                while (i > 0) {
                    i--;
                    // 左边的比当前的高
                    if (heights[i] > heights[posi]) areas[posi] += heights[posi];
                    // 往左走的时候如果左边和自己一样 那么值也一样
                    else if (heights[i] == heights[posi]) {
                        areas[posi] = areas[i];
                        return areas[posi];
                    }
                    else {
                        // 左边的比当前低
                        // 先看左边是否有最大面积，没有就算
                        if (areas[i] == 0) doFindArea(heights, i, areas);
                        leftMax = areas[i];
                        break;
                    }
                }
                // 往右走，找到右边比自己小的最大值，本身区域也增加
                while (j < heights.length - 1) {
                    j++;
                    if (heights[j] >= heights[posi]) areas[posi] += heights[posi];
                    else {
                        if (areas[j] == 0) doFindArea(heights, j, areas);
                        rightMax = areas[j];
                        break;
                    }
                }
                // 现在有了本身的大小，有了遇到的两个比自身小的数的区域最大值
                areas[posi] = Math.max(Math.max(areas[posi], leftMax), rightMax);
            }
            return areas[posi];
        }
    }
}

package com.leetcode;

import java.util.Arrays;

public class PlusOne66 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution().plusOne(new int[]{0})));
    }

    private static class Solution {
        public int[] plusOne(int[] digits) {
            int carry = 0;
            for (int i = digits.length - 1; i >= 0; i--) {
                if (i == digits.length - 1) {
                    digits[i] += 1;
                    if (digits[i] == 10) {
                        digits[i] = 0;
                        carry++;
                    }
                } else {
                    digits[i] += carry;
                    if (digits[i] == 10) digits[i] = 0;
                    else carry = 0;
                }
            }
            if (carry == 1) {
                int[] newArr = new int[digits.length + 1];
                newArr[0] = 1;
                for (int i = 0; i < digits.length; i++) {
                    newArr[i + 1] = digits[i];
                }
                return newArr;
            }
            return digits;
        }
    }
}

package com.leetcode;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class SetZeroes73 {
    public static void main(String[] args) {
        int[][] matrix = new int[][]{
                {0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}
        };
        new Solution().setZeroes2(matrix);
        for (int[] ints : matrix) {
            System.out.println(Arrays.toString(ints));
        }
    }

    private static class Solution {
        public void setZeroes(int[][] matrix) {
            Set<Integer> cols = new HashSet();
            Set<Integer> rows = new HashSet();
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[i].length; j++) {
                    if (matrix[i][j] == 0) {
                        cols.add(j);
                        rows.add(i);
                    }
                }
            }
            for (Integer col : cols) {
                for (int i = 0; i < matrix.length; i++) {
                    matrix[i][col] = 0;
                }
            }
            for (Integer row : rows) {
                for (int i = 0; i < matrix[row].length; i++) {
                    matrix[row][i] = 0;
                }
            }
        }

        // O(1) space的算法 遍历 如果一个数为0 将对应第一行和第一列的值置为0a
        public void setZeroes2(int[][] matrix) {
            int m = matrix.length;
            int n = matrix[0].length;
            for (int i = 1; i < m; i++)
                for (int j = 1; j < n; j++)
                    if (matrix[i][j] == 0) {
                        matrix[i][0] = 0;
                        matrix[0][j] = 0;
                    }
            // set to zero
            for (int i = 1; i < m; i++)
                for (int j = 1; j < n; j++)
                    if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
            // 看第一行 和 第一列是否需要置空
            boolean isRow = false;
            boolean isCol = false;
            for (int i = 0; i < m; i++) {
                if (matrix[i][0] == 0) isRow = true;
            }
            for (int i = 0; i < n; i++) {
                if (matrix[0][i] == 0) isCol = true;
            }
            if (isRow)
                for (int i = 0; i < m; i++) {
                    matrix[i][0] = 0;
                }
            if (isCol)
                for (int i = 0; i < n; i++) {
                    matrix[0][i] = 0;
                }
        }

    }
}

package com.leetcode;

public class SearchMatrix74 {
    public static void main(String[] args) {
        System.out.println(new Solution().searchMatrix(new int[][]{
                {1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}
        }, 11));

    }

    /**
     * Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
     * <p>
     * Integers in each row are sorted from left to right.
     * The first integer of each row is greater than the last integer of the previous row.
     */
    private static class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            int startRow = 0;
            int endRow = matrix.length - 1;
            int startCol = 0;
            int endCol = matrix[0].length - 1;

            // 二分法查行
            while (startRow < endRow) {
                int middleRow = (startRow + endRow) / 2;
                if (matrix[middleRow][0] > target) {
                    endRow = middleRow - 1;
                } else if (matrix[middleRow][0] < target) {
                    if (matrix[middleRow][endCol] < target) startRow = middleRow + 1;
                    else startRow = endRow = middleRow;
                } else if (matrix[middleRow][0] == target) {
                    return true;
                }
            }
            // 二分查找列
            while (startCol <= endCol) {
                int middleCol = (startCol + endCol) / 2;
                if (matrix[startRow][middleCol] == target) {
                    return true;
                } else if (matrix[startRow][middleCol] > target) {
                    endCol = middleCol - 1;
                } else if (matrix[startRow][middleCol] < target) {
                    startCol = middleCol + 1;
                }
            }
            return false;
        }
    }
}

package com.leetcode;

public class UniquePaths62 {
    public static void main(String[] args) {
        System.out.println(new Solution().uniquePaths(7, 3));
    }

    /**
     * A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
     * <p>
     * The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
     * <p>
     * How many possible unique paths are there?
     * <p>
     * Input: m = 3, n = 2
     * Output: 3
     * Explanation:
     * From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
     * 1. Right -> Down -> Down
     * 2. Down -> Down -> Right
     * 3. Down -> Right -> Down
     */
    private static class Solution {
        public int uniquePaths(int m, int n) {
            int[][] matrix = new int[m][n];
            for (int i = 0; i < n; i++) {
                matrix[m - 1][i] = 1;
            }
            for (int i = 0; i < m; i++) {
                matrix[i][n - 1] = 1;
            }
            for (int i = m - 2; i >= 0; i--) {
                for (int j = n - 2; j >= 0; j--) {
                    matrix[i][j] = matrix[i + 1][j] + matrix[i][j + 1];
                }
            }
            return matrix[0][0];
        }
    }
}

package com.leetcode;

public class UniquePathsII63 {
    public static void main(String[] args) {
        System.out.println(new Solution().uniquePathsWithObstacles(new int[][]{
                {0}
        }));
    }


    /**
     * A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
     * <p>
     * The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
     * <p>
     * Now consider if some obstacles are added to the grids. How many unique paths would there be?
     * <p>
     * An obstacle and space is marked as 1 and 0 respectively in the grid.
     */
    private static class Solution {
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
            int m = obstacleGrid.length;
            int n = obstacleGrid[0].length;
            if (m == 1 && n == 1) {
                if (obstacleGrid[0][0] == 0) return 1;
                else return 0;
            }
            if (obstacleGrid[m - 1][n - 1] == 1) return 0;
            for (int i = n - 2; i >= 0; i--) {
                if (obstacleGrid[m - 1][i] == 1) obstacleGrid[m - 1][i] = 0;
                else {
                    if (i == n - 2) obstacleGrid[m - 1][i] = 1;
                    else obstacleGrid[m - 1][i] = obstacleGrid[m - 1][i + 1];
                }
            }
            for (int i = m - 2; i >= 0; i--) {
                if (obstacleGrid[i][n - 1] == 1) obstacleGrid[i][n - 1] = 0;
                else {
                    if (i == m - 2) obstacleGrid[i][n - 1] = 1;
                    else obstacleGrid[i][n - 1] = obstacleGrid[i + 1][n - 1];
                }
            }
            for (int i = m - 2; i >= 0; i--) {
                for (int j = n - 2; j >= 0; j--) {
                    if (obstacleGrid[i][j] == 1) obstacleGrid[i][j] = 0;
                    else {
                        obstacleGrid[i][j] = obstacleGrid[i + 1][j] + obstacleGrid[i][j + 1];
                    }
                }
            }
            return obstacleGrid[0][0];
        }
    }
}

package com.leetcode;

public class TrappingRainWater42 {
    public static void main(String[] args) {
        System.out.println(new Solution3().trap(new int[]{9, 8, 9, 5, 8, 8, 8, 0, 4}));
    }

    /**
     * Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
     * <p>
     * 涉及数组 动规 双指针
     * <p>
     * 思路：首先找到最高点，分别向左右两边找第二高的点，找到第二高的点，将第二高的值减去包裹的所有高度，
     * <p>
     * Runtime: 2 ms, faster than 21.28% of Java online submissions for Trapping Rain Water.
     * Memory Usage: 38.3 MB, less than 86.97% of Java online submissions for Trapping Rain Water.
     */
    private static class Solution {
        public int trap(int[] height) {
            return doTrap(height, 0, height.length - 1);
        }

        private int doTrap(int[] height, int start, int end) {
            if (start >= end - 1) return 0;
            int heighestIndex = findMaxIndex(height, start, end, 0);
            int totalWater = 0;
            int leftSecondHeightIndex = findMaxIndex(height, start, heighestIndex - 1, 0);
            int rightSecondHeightIndex = findMaxIndex(height, heighestIndex + 1, end, 1);
            // 找到左边包含水源
            if (leftSecondHeightIndex != -1) {
                for (int i = leftSecondHeightIndex + 1; i <= heighestIndex - 1; i++) {
                    totalWater += height[leftSecondHeightIndex] - height[i];
                }
                totalWater += doTrap(height, start, leftSecondHeightIndex);
            }
            // 找到右边包含水源
            if (rightSecondHeightIndex != -1) {
                for (int i = heighestIndex + 1; i <= rightSecondHeightIndex - 1; i++) {
                    totalWater += height[rightSecondHeightIndex] - height[i];
                }
                totalWater += doTrap(height, rightSecondHeightIndex, end);
            }
            return totalWater;
        }

        /**
         * 找到最高点的下标
         *
         * @param direction 靠近哪边的最高点，因为可能有高度相同， 1：表示靠近右边的最大值，0表示靠近左边的最大值
         */
        private int findMaxIndex(int[] height, int start, int end, int direction) {
            // 相邻的两个墙壁找最高无意义
            if (start >= end) return -1;
            int tmp;
            if (direction == 0) {
                tmp = start;
                for (int i = start; i <= end; i++) {
                    if (height[tmp] < height[i]) tmp = i;
                }
            } else {
                tmp = end;
                for (int i = end; i >= start; i--) {
                    if (height[tmp] < height[i]) tmp = i;
                }
            }
            return tmp;
        }
    }

    /**
     * 上一种太慢，换种，两个指针，一个头，一个尾 都不为0，左指针又走到比自身大的，右指针左走到比自己大的，分别计算两个指针刚刚和现在的位置包含的水量。
     * 直到左右指针相遇结束
     * <p>
     * Runtime: 2 ms, faster than 21.28% of Java online submissions for Trapping Rain Water.
     * Memory Usage: 38.3 MB, less than 86.97% of Java online submissions for Trapping Rain Water.
     */

    private static class Solution2 {
        public int trap(int[] height) {
            int totalWater = 0;
            int startPoint = 0, endPoint = height.length - 1;
            int recordStart, recordEnd;
            while (startPoint < endPoint) {
                // 直到比自己大
                recordStart = startPoint;
                recordEnd = endPoint;
                // 指针走的时候会有递减的情况 如果指针一次走到底了 那么需要重置指针 让另一个指针走
                while (startPoint < endPoint - 1 && height[recordStart] >= height[startPoint + 1]) startPoint++;
                startPoint++;
                // reset
                if (startPoint >= endPoint && height[recordStart] > height[startPoint]) startPoint = recordStart;
                while (startPoint < endPoint - 1 && height[recordEnd] >= height[endPoint - 1]) endPoint--;
                endPoint--;
                if (startPoint >= endPoint && height[endPoint] < height[recordEnd]) endPoint = recordEnd;
                // 分别计算水量
                for (int i = recordStart + 1; i < startPoint; i++) {
                    totalWater += height[recordStart] - height[i];
                }
                for (int i = endPoint + 1; i < recordEnd; i++) {
                    totalWater += height[recordEnd] - height[i];
                }
            }
            return totalWater;
        }
    }

    /**
     * 上面那个思路稍微修改下即可 80%  不重置指针，而是先找到最大值，左指针和右指针最高只能找到最大值
     *
     * Runtime: 1 ms, faster than 81.80% of Java online submissions for Trapping Rain Water.
     * Memory Usage: 38 MB, less than 99.27% of Java online submissions for Trapping Rain Water.
     *
     */
    private static class Solution3 {
        public int trap(int[] height) {
            int totalWater = 0;
            int startPoint = 0, endPoint = height.length - 1;
            int recordStart, recordEnd;
            // 找到最大值 左右指针只能走到最大值
            int maxIndex = 0;
            for (int i = 1; i < height.length; i++) {
                if (height[maxIndex] < height[i]) maxIndex = i;
            }
            while (startPoint < endPoint) {
                // 直到比自己大
                recordStart = startPoint;
                recordEnd = endPoint;
                // 指针走的时候会有递减的情况 如果指针一次走到底了 那么需要重置指针 让另一个指针走
                while (startPoint < maxIndex && height[recordStart] >= height[startPoint + 1]) startPoint++;
                if (startPoint < maxIndex) startPoint++;
                while (endPoint > maxIndex && height[recordEnd] >= height[endPoint - 1]) endPoint--;
                if (endPoint > maxIndex) endPoint--;
                // 分别计算水量
                for (int i = recordStart + 1; i < startPoint; i++) {
                    totalWater += height[recordStart] - height[i];
                }
                for (int i = endPoint + 1; i < recordEnd; i++) {
                    totalWater += height[recordEnd] - height[i];
                }
            }
            return totalWater;
        }
    }

}

package com.leetcode;

import java.util.Arrays;

public class JumpGameII45 {
    public static void main(String[] args) {
        System.out.println(new Solution2().jump(new int[]{2, 3, 1, 1, 4}));
    }

    /**
     * 问题：
     * Given an array of non-negative integers nums, you are initially positioned at the first index of the array.
     * Each element in the array represents your maximum jump length at that position.
     * Your goal is to reach the last index in the minimum number of jumps.
     * You can assume that you can always reach the last index.
     * <p>
     * 当前位置值为最大跳跃步数，如何移动最小次数跳到最后
     * <p>
     * 思路：先用动态规划的思想，从低到高，从最后开始算最优跳跃次数 -1表示无法到达终点
     * <p>
     * Runtime: 0 ms, faster than 100.00% of Java online submissions for Jump Game II.
     * Memory Usage: 36.3 MB, less than 85.37% of Java online submissions for Jump Game II.
     */
    private static class Solution {
        public int jump(int[] nums) {
            int[] jumpTimes = new int[nums.length];
            Arrays.fill(jumpTimes, -1);
            for (int i = nums.length - 1; i >= 0; i--) {
                if (i == nums.length - 1) {
                    jumpTimes[i] = 0;
                    continue;
                }
                // 每位再遍历后面的次数 选最小的
                int min = jumpTimes[i + 1];
                for (int j = 1; j <= nums[i]; j++) {
                    if (i + j < nums.length && min > jumpTimes[i + j] && jumpTimes[i + j] != -1) min = jumpTimes[i + j];
                }
                jumpTimes[i] = min + 1;
            }
            return jumpTimes[0];
        }
    }

    /**
     * 改造成贪心算法
     * <p>
     * 思路：选择能跳到的范围内的，最远下一次跳跃距离
     * 当前的currentJumpEnd记录能跳到的最远位置，在当前位置和最远位置里面挑出跳的最远的方案：max，i==currentPosi表明已经找到最大跳远距离了
     */
    private static class Solution2 {
        public int jump(int[] nums) {
            int jumpTimes = 0;
            int max = 0;
            int currentJumpEnd = 0;
            // 记录能跳的最远位置
            for (int i = 0; i < nums.length - 1; i++) {
                max = Math.max(max, i + nums[i]);
                if (i == currentJumpEnd) {
                    jumpTimes++;
                    currentJumpEnd = max;
                }
            }
            return jumpTimes;
        }
    }
}

package com.leetcode;

import java.lang.reflect.Array;
import java.util.Arrays;

public class RotateImage48 {
    public static void main(String[] args) {
        new Solution().rotater2(new int[][]{
                {1, 2, 3}, {4, 5, 6}, {7, 8, 9}
        });
    }

    /**
     * Runtime: 3 ms, faster than 100.00% of Java online submissions for Rotate Image.
     * Memory Usage: 39 MB, less than 48.87% of Java online submissions for Rotate Image.
     */
    private static class Solution {
        public void rotate(int[][] matrix) {
            // 从第一列开始
            for (int i = 0; i < matrix.length; i++) {
                for (int j = i; j < matrix.length; j++) {
                    swap(matrix, i, j, j, i);
                }
                for (int j = 0; j < matrix.length / 2; j++) {
                    swap(matrix, i, j, i, matrix.length - 1 - j);
                }
            }
            Arrays.stream(matrix).forEach(x -> System.out.println(Arrays.toString(x)));
        }

        private void swap(int[][] matrix, int i, int j, int newI, int newJ) {
            int tmp = matrix[newI][newJ];
            matrix[newI][newJ] = matrix[i][j];
            matrix[i][j] = tmp;
        }

        public void rotater2(int[][] matrix) {
            // 从第一列开始
            StringBuffer out = new StringBuffer();
            out.append("[");
            // 列
            for (int i = 0; i < matrix.length; i++) {
                out.append("[");
                for (int j = matrix.length - 1; j >= 0; j--) {
                    out.append(matrix[j][i]);
                    if (j!=0) out.append(",");
                }
                out.append("]");
                if (i != matrix.length-1) out.append(",");
            }
            out.append("]");
            System.out.println(out.toString());
        }
    }
}