代码随想录题解

代码随想录刷题

1数组

1.1二分查找

1.1.1二分查找

关键词：有序（升序)，不重复

思路：有序，不重复，马上就可以想到是二分查找，不断的二分缩小范围就可以找到目标值

class Solution {
    public int search(int[] nums, int target) {
        if(target < nums[0] || target > nums[nums.length - 1]){
            return -1;
        }
        int left = 0;
        int right = nums.length -1;
        while(left <= right){
            int mid = left + ((right - left) >> 1);
            if (target > nums[mid]){
                left = mid + 1;
            }else if (target < nums[mid]){
                right = mid - 1;
            } else{
                return mid;
            }
        }
        return -1;
    }
}

1.1.2搜索插入位置

关键词：排序数组，升序，无重复元素

思路：二分查找找到该元素即可，需要注意的是数组中可能不会出现该元素，这时需要返回该元素该出现的位置，一共有以下4种情况

1. target比数组全部元素大，索引正好为数组大小
2. target比数组全部元素小，索引为0
3. 数组中存在target，直接返回target的索引
4. 数组中不存在target，当left=right，如果这个值比target大，那么right-1，应该返回left或right+1，如果这个值比target小，left++，应该返回left或right

class Solution {
    public int searchInsert(int[] nums, int target) {
        // 如果小于最小值
        if (target < nums[0]) {
            return 0;
        }
        // 如果大于最大值
        int right = nums.length - 1;
        if (target > nums[right]) {
            return nums.length;
        }
        // 二分查找
        int left = 0;
        int mid;
        while (left <= right) {
            mid = left + ((right - left) >> 1);
            if (target > nums[mid]) {
                left = mid + 1;
            } else if (target < nums[mid]) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return left;
    }
}

1.1.3在排序数组中查找元素的第一个和最后一个位置

思路：依然是二分查找，不过在找到元素后要不断的往左右二分逼近，找到全部元素

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = 0;
        int right = nums.length -1 ;
        int mid ;
        int l=-1, r=-1;
        while(left<=right){
            mid=left+((right-left)>>1);
            if(target>nums[mid]){
                left = mid+1;
            }else if(target<nums[mid]){
                right = mid-1;
            }else{
                l=mid;
                right = mid-1;
            }
        }
        left=0;
        right=nums.length-1;
        while(left<=right){
            mid=left+((right-left)>>1);
            if(target>nums[mid]){
                left = mid+1;
            }else if(target<nums[mid]){
                right = mid-1;
            }else{
                r=mid;
                left = mid+1;
            }
        }
        return new int[]{l,r};  
    }
}

1.1.4X的平方根

思路：给定的x的平方根只能存在于0到x之间，通过二分查找不断逼近找到平方小于X的最小值即可，但是要注意目标数的平方可能会超过int的范围，这时候要转换成long

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

1.1.5有效的完全平方数

思路：跟上题差不多，二分查找平方等于num的数，如果找到了要返回true，找不到直接返回false即可

class Solution {
    public boolean isPerfectSquare(int num) {
        int left = 0;
        int right = num;
        int mid=0;
        long sqa;
        while(left<=right){
            mid = left+((right-left)>>1);
            sqa=(long)mid*mid;
            if(sqa>num){
                right = mid-1;
            }else if (sqa<num){
                left = mid+1;
            }else{
                return true;
            }
        }
        return false;
    }
}

1.2移除元素

1.2.1移除元素

思路：看到这道题最先的思路是用一个指针遍历数组，遇到val后直接往后找到第一个不等于val的元素，然后进行交换，但是每次都要从val开始往后遍历会重复走很多步，时间复杂度也是O（n^2)，这时候用双指针就可以解决这个问题，快指针遍历元素找到全部非val元素，慢指针维护一段不含val的数组

class Solution {
    public int removeElement(int[] nums, int val) {
        if(nums.length == 0){
            return 0;
        }
        int fast = 0;
        int slow = 0;
        while(fast < nums.length){
            nums[slow] = nums[fast];
            if(nums[fast++] != val){
                slow++;
            }
        }
        return slow ;
    }
}

1.2.2删除排序数组中的重复项

思路：还是双指针遍历，快指针找到不是重复的元素，然后赋值交换给慢指针，最后返回根据慢指针的索引确定k的值

class Solution {
    public int removeDuplicates(int[] nums) {
        int slow = 0;
        int fast = 0;
        int n = nums.length - 1;
        while(fast < nums.length){
            nums[slow] = nums [fast];
            while(fast < n && nums[fast] == nums[fast+1]){
                fast++;
            }
            fast++;
            slow++;
        }
        return slow;
    }
}

1.2.3移动零

思路：还是快慢指针将0维护在快慢指针中间的位置

class Solution {
    public void moveZeroes(int[] nums) {
        int slow = 0;
        int fast = 0;
        while(fast < nums.length){
            if(nums[fast] != 0){
                int tem = nums[slow];
                nums[slow] = nums[fast];
                nums[fast] = tem;
                slow++;
            }
            fast++;
        }
    }
}

1.2.4比较含退格的字符串

思路：用双指针将字符串重构成有效字符串，然后比较两个字符串

class Solution {
    public boolean backspaceCompare(String s, String t) {
        if(getString(s.toCharArray()).equals(getString(t.toCharArray()))){
            return true;
        }
        return false;
    }
    
    public String getString(char[] a){
        int slow = 0;
        int fast = 0;
        while(fast < a.length){
            if(a[fast] != '#'){
                a[slow] = a[fast];
                slow++;
            }else{
                slow = Math.max(slow-1,0);
            }
            fast++;
        }
        return new String(a,0,slow);
    }
}

1.3有序数组的平方

思路：如果数组是从零开始，那么每个数平方后大小顺序也是不变的，但是数组可能存在负数的情况，那么很自然的想到找到平方最小的数然后向左右遍历选出平方较小值插入到新数组中，但是找到最小的元素比较麻烦，所以可以反过来寻找，从头尾开始往中间找，先找到最大的元素，慢慢找到中间小的

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] res= new int[nums.length];
        int left = 0;
        int right = nums.length - 1;
        int index = nums.length - 1;
        while(left <= right){
            if(nums[right] * nums[right] > nums[left] * nums[left]){
                res[index--] = nums[right] * nums[right--];
            }else {
                res[index--] = nums[left] * nums[left++];
            }
        }
        return res;
    }
}

1.4长度最小的子数组

1.4.1长度最小的子数组

思路：用两个指针维护一个滑动窗口，找到满足条件的子数组然后记录长度最小的子数组

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int len = nums.length;
        int sum = 0;
        for(int left = 0, right = 0; right<nums.length;right++){
            sum += nums[right];
            while(sum >= target){
                sum-=nums[left];
                len = Math.min(right - left, len);
                left++;
            }
        }
        return len == nums.length ? 0 : len+1; 
    }
}

1.4.2水果成篮

思路：还是用双指针维护一个滑动窗口找到最长的子数组，可以用map记录一个值出现的次数，并且维护滑动窗口的key小于等于2，找到最大的滑动窗口即可

class Solution {
    public int totalFruit(int[] fruits) {
        Map<Integer, Integer> maps = new HashMap<>();
        int left = 0;
        int length =0;
        for(int right = 0; right<fruits.length;right++){
            maps.put(fruits[right], maps.getOrDefault(fruits[right],0) + 1);
            while(maps.size() > 2){
                if(maps.get(fruits[left]) > 1){
                    maps.put(fruits[left], maps.get(fruits[left]) -1);
                }else{
                    maps.remove(fruits[left]);
                }
                left++;
            }
            length=Math.max(length, right - left + 1);
        }
        return length;
    }
}

1.4.3最小覆盖字串

思路：还是用滑动窗口和map解决这个问题，用map记录t中字符出现的次数，然后用滑动窗口寻找字串，快指针往后遍历先判断该字符是否存在于于map，如果存在则将次数减一，慢指针就遇见就加一，找到最小的字符串

class Solution {
    public String minWindow(String s, String t) {
        char[] charArray = t.toCharArray();
        Map<Character, Integer> target =  new HashMap<>();
        for (char c : charArray) {
            target.put(c, target.getOrDefault(c, 0) + 1);
        }
        int left = 0;
        int len = Integer.MAX_VALUE;
        int lres = 0;
        int rres = 0;
        for(int right = 0; right < s.length(); right++) {
            if (!target.containsKey(s.charAt(right))){
                continue;
            }
            target.put(s.charAt(right), target.get(s.charAt(right)) - 1);
            while (check(target)) {
                if (right - left + 1 < len){
                    len = right - left + 1;
                    lres = left;
                    rres = right;
                }
                if (target.containsKey(s.charAt(left))){
                    target.put(s.charAt(left), target.get(s.charAt(left)) + 1);
                }
                left++;
            }

        }
        return len == Integer.MAX_VALUE ? "" : s.substring(lres,rres +1);
    }
    Boolean check(Map<Character, Integer> target){
        for (Map.Entry<Character, Integer> entry : target.entrySet()) {
            if (entry.getValue() > 0){
                return false;
            }
        }
        return true;
    }
}

1.5螺旋矩阵

1.5.1螺旋矩阵Ⅱ

思路：这种题没什么算法思想考察，主要看对边界的判定和处理，这道题直接创建出二维数组然后照着四个方向循环遍历输出即可

// 方式yi
class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        int end = n*n;
        int cur = 1;
        int i=0;
        int j =0;
        while(cur < end){
            while(j+1<n && res[i][j+1]==0 && cur < end) res[i][j++] = cur++;
            while(i+1<n && res[i+1][j]==0 && cur < end) res[i++][j] = cur++;
            while(j>0   && res[i][j-1]==0 && cur < end) res[i][j--] = cur++;
            while(i>0   && res[i-1][j]==0 && cur < end) res[i--][j] = cur++;
        }
        res[i][j]= cur;
        return res;
    }
}

// 方式二
class Solution {
    public int[][] generateMatrix(int n) {
        int left = 0;
        int right = n - 1;
        int top = 0;
        int bottom = n - 1;
        int[][] matrix = new int[n][n];
        int cur = 1;
        int end = n * n;
        int i = top;
        int j = left -1;
        while(cur <= end) {
            while (j < right && cur <= end) matrix[i][++j] = cur++;
            ++top;
            while (i < bottom && cur <= end) matrix[++i][j] = cur++;
            --right;
            while (j > left && cur <= end) matrix[i][--j] = cur++;
            --bottom;
            while (i > top && cur <= end) matrix[--i][j] = cur++;
            ++left;
        }
        return matrix;
    }
}

1.5.2螺旋矩阵

思路：用四个值记录数组的上下左右边，然后按照四个方向遍历添加，当上到下边重合或左右边重合即为最后一段遍历

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int top = 0;
        int bottom = matrix.length-1;
        int left = 0;
        int right = matrix[0].length-1;
        int end = matrix.length * matrix[0].length;
        List<Integer> res = new ArrayList<>();
        while(top <= bottom || left <= right){
            for(int i=left;i<=right&&top<=bottom;i++) {res.add(matrix[top][i]);}
            top++;
            for(int i = top; i<=bottom&&left<=right; i++){ res.add(matrix[i][right]);}
            right--;
            for(int i=right;i>=left&&top<=bottom;i--) {res.add(matrix[bottom][i]);}
            bottom--;
            for(int i = bottom; i>= top&&left<=right; i--){ res.add(matrix[i][left]);}
            left++;
        }
        return res;
    }
}

1.5.3顺时针打印矩阵

思路：跟上题基本一致，四个值记录四条边界然后四个方向循环记录

class Solution {
    public int[] spiralArray(int[][] array) {
        if(array.length == 0){
            return new int[]{};
        }
        int top=0;
        int bottom=array.length-1;
        int left=0;
        int right=array[0].length-1;
        int[] res=new int[array.length*array[0].length];
        int cur=0;
        while(top<=bottom||left<=right){
            for(int i=left;i<=right&&top<=bottom;i++) res[cur++]=array[top][i];
            top++;
            for(int i=top;i<=bottom&&left<=right;i++) res[cur++]=array[i][right];
            right--;
            for(int i=right;i>=left&&top<=bottom;i--) res[cur++]=array[bottom][i];
            bottom--;
            for(int i=bottom;i>=top&&left<=right;i--) res[cur++]=array[i][left];
            left++;
        }
        return res;
    }
}

2.链表

2.1移除链表元素

思路：简单遍历，找到目标元素时指向他的next，为了防止处理头节点为null的情况，可以添加一个虚拟头节点

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // 雅指针
        ListNode p = new ListNode(0);
        p.next = head;
        head=p;
        ListNode cur = p.next;
        while(cur!=null){
            if(cur.val==val){
                p.next=cur.next;
                cur=p.next;
            }else{
                p=cur;
                cur=p.next;
            }
        }
        return head.next;
    }
}

2.2设计链表

思路：头尾指针都设置一个虚拟节点解决边界特判，然后记录一下数组大小就好了

class MyLinkedList {

    class ListNode {
        int val;
        ListNode pre;
        ListNode next;

    }

    ListNode head;
    ListNode tail;

    int size;

    public MyLinkedList() {
        this.head = new ListNode();
        this.tail = new ListNode();
        this.head.next = tail;
        this.tail.pre = head;
        this.size = 0;
    }

    public int get(int index) {
        if (index >= size ) {
            return -1;
        }
        ListNode p = head;
        for (int i = 0; i <= index; i++) {
            p = p.next;
        }
        return p.val;
    }

    public void addAtHead(int val) {
        ListNode p = new ListNode();
        p.val = val;

        p.next = head.next;
        head.next = p;

        p.pre = head;
        p.next.pre = p;

        this.size++;
    }

    public void addAtTail(int val) {
        ListNode p = new ListNode();
        p.val = val;

        p.pre = tail.pre;
        tail.pre = p;

        p.pre.next = p;
        p.next = tail;

        this.size++;
    }

    public void addAtIndex(int index, int val) {
        if(index > size){
            return;
        }
        ListNode node = new ListNode();
        node.val = val;
        
        ListNode p = head;
        for(int i = 0; i <= index; i++){
            p = p.next;
        }
        
        node.pre = p.pre;
        p.pre = node;
        
        node.pre.next = node;
        node.next = p;
        
        this.size++;
        
    }

    public void deleteAtIndex(int index) {
        if(index >= size){
            return;
        }

        ListNode p = head;
        for(int i = 0; i <= index; i++){
            p = p.next;
        }
        
        p.pre.next = p.next;
        p.next.pre = p.pre;
        
        this.size--;
    }
}

2.3翻转链表

思路1：直接翻转，遍历链表，保存好当前节点的下一个节点，然后将当前节点的next指向上一个节点，迭代即可

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode next ;
        while(cur!=null){
            next = cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
}

思路2：头插法，遍历链表，将遍历到的节点直接头插到新的链表，得到的新链表就是原链表翻转后的结果

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode p = new ListNode();
        ListNode q;
        while(head!=null){
            q=head.next;
            head.next=p.next;
            p.next=head;
            head=q;
        }
        return p.next;

    }
}

思路3：用栈先进后出的特性解决，将链表节点全部入栈，然后出栈组成新链表

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        Stack<ListNode> stack = new Stack<>();
        while(head!=null){
            stack.push(head);
            head=head.next;
        }
        ListNode h = stack.pop();
        ListNode p = stack.pop();
        h.next = p;
        while(stack.size()!=0){
            p.next=stack.pop();
            p=p.next;
        }
        p.next=null;
        return h;
    }
}

2.4两两交换链表中的节点

思路1：跟上题思路1类似，只是每次取出两个节点翻转

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode p = new ListNode();
        p.next=head;
        ListNode pre = p;
        ListNode left = head;
        ListNode right ;
        ListNode next;
        while(left!=null&&left.next!=null){
            right = left.next;
            next=right.next;
            pre.next = right;
            right.next=left;
            left.next=next;
            pre=left;
            left=next;
        }
        return p.next;
    }
}

思路2：跟上题思路2类似，每次取出两个节点头插

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode head2 = new ListNode();
        head2.next=head;
        ListNode tail=head2;
        ListNode left,right;
        while(head!=null&&head.next!=null){
            left = head;
            right = head.next;
            head=right.next;
            tail.next=right;
            left.next=right.next;
            right.next=left;
            tail=left;
        }
        return head2.next;
    }
}

思路3：跟上题思路3类似，但是是用队列每次取出两个节点，这里就不放代码了

2.5删除链表中倒数第N个节点

思路：快慢指针，先让快指针往后走N个元素，然后快慢指针以同样的速度往后遍历，当快指针到达最后一个节点的时候慢指针就是倒数前n+1个节点

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode p = new ListNode();
        p.next = head;
        ListNode fast = p;
        ListNode slow = p;
        for(int i =0;i<=n;i++){
            fast=fast.next;
        }
        while(fast!=null){
            fast=fast.next;
            slow=slow.next;
        }
        slow.next=slow.next.next;
        return p.next;
    }
}

2.6链表相交

思路：两个链表最后有公共部分，那么相等的时候他们距离链表尾的距离是一样的，那么可以先遍历两个链表，然后得到两个链表的长度，然后让长的先往后走数值等于链表长度只差个节点，然后一起往后遍历比较是否相等

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA;
        ListNode b = headB;
        int lena=0;
        int lenb=0;
        while(a!=null){
            lena++;
            a=a.next;
        }
        while(b!=null){
            lenb++;
            b=b.next;
        }
        a=headA;
        b=headB;
        if(lena>lenb){
            for(int i =lena-lenb;i>0;i--){
                a=a.next;
            }
        }else{
            for(int i=lenb-lena;i>0;i--){
                b=b.next;
            }
        }
        while(a!= null){
            if(a==b){
                return a;
            }
            a=a.next;
            b=b.next;
        }
        return null;
    }
}

但是看了官方的题解，虽然时间上都是O（n），但是代码量少了很多，处理方式也更优雅

两个链表直接同步往后遍历，到达链表尾部后从另一个链表头继续遍历，比较两个指针是否相等，相当于把一个链表拼接在了对方链表的最后，这样他们的总长度都是两个链表之和，就可以直接比较是否相等了，从代码量上看明显优雅了很多

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a=headA;
        ListNode b=headB;
        while(a!=b){
            a=a==null?headB:a.next;
            b=b==null?headA:b.next;
        }
        return a;
    }
}

2.7环形链表

思路：这道题可以分成两部分一部分是判断链表是否成环，判断成环后还要判断环形的起点，判断是否成环用快慢指针很快就可以判断出来，但是找到环形的节点就要用点数学推导

fast=a+m*(b+c)+b

slow=a+b

fast=2*slow

联立上面三式 : a+b=m*(b+c) ==>a=(m-1)*b + m*c

当m=1时，a=c，所以快慢指针相遇后只需要从头节点同步遍历，相遇的交点即为环的头节点

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null && fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                fast=head;
                while(fast!=slow){
                    fast=fast.next;
                    slow=slow.next;
                }
                return fast;
            }
        }
        return null;
    }
}

3.哈希表

3.1有效的字母异味词

3.1.1有效的字母异味词

思路：用哈希表记录字符串字符的出现次数，用s进行插入，t进行删除，最后看一下哈希表是否还有元素即可

class Solution {
    public boolean isAnagram(String s, String t) {
        Map<Character, Integer> smap = new HashMap<>();
        char[] sChars = s.toCharArray();
        for(char sChar:sChars){
            if(smap.containsKey(sChar)){
                smap.put(sChar,smap.get(sChar) + 1);
            }else{
                smap.put(sChar,1);
            }
        }
        char[] tChars = t.toCharArray();
        for(char tChar:tChars){
            if(!smap.containsKey(tChar)){
                return false;
            }else{
                if(smap.get(tChar)>1){
                    smap.put(tChar, smap.get(tChar) -1);
                }else{
                    smap.remove(tChar);
                }
            }
        }
        if(smap.isEmpty()){
            return true;
        }else{
            return false;
        }
    }
}

思考：这道题字符其实是有限的而且并不多，可以用桶排的思想，直接用数组记录全部字符的次数

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length()!=t.length()){
            return false;
        }
        int[] a = new int[26];
        char[]sChars = s.toCharArray();
        for(char sChar:sChars){
            ++a[sChar-'a'];
        }
        for(char tChar:t.toCharArray()){
            if(--a[tChar-'a']<0){
                return false;
            }
        }
        return true;
    }
}   

3.1.2赎金信

思路1：还是跟上面用哈希表记录字符个数一样，一个插入，一个删除，最后查看哈希表是否为空

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character, Integer> map = new HashMap<>();
        for(char ch:ransomNote.toCharArray()){
            map.put(ch, map.getOrDefault(ch,0)+1);
        }
        for(char ch:magazine.toCharArray()){
            map.put(ch, map.getOrDefault(ch,0)-1);
            if(map.get(ch)<=0){
                map.remove(ch);
            }
        }
        if(map.isEmpty()){
            return true;
        }else{
            return false;
        }
    }
}

思路2：跟上面的改进一样，用桶排的思想记录字符个数

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] a = new int[26];
        for(char ch:magazine.toCharArray()){
            ++a[ch-'a'];
        }
        for(char ch:ransomNote.toCharArray()){
            if(--a[ch-'a']<0){
                return false;
            }
        }
        return true;
    }
}

3.1.3字母异位词分组

思路：最简单的方法就是双重循环逐个判断是否为异位词，但是双重循环加上判断异位词会导致时间复杂度是O（n^3）

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> ans = new ArrayList<>();
        for(int i =0;i<strs.length;i++){
            if(strs[i]==null){
                continue;
            }
            List<String> list = new ArrayList<>();
            ans.add(list);
            list.add(strs[i]);
            for(int j=i+1;j<strs.length;j++){
                if(strs[j]==null){
                    continue;
                }
                if(isAnagram(strs[i],strs[j])){
                    list.add(strs[j]);
                    strs[j]=null;
                }
            }
        }
        return ans;
    }
    public boolean isAnagram(String s, String t) {
        if(s.length()!=t.length()){
            return false;
        }
        int[] a = new int[26];
        char[]sChars = s.toCharArray();
        for(char sChar:sChars){
            ++a[sChar-'a'];
        }
        for(char tChar:t.toCharArray()){
            if(--a[tChar-'a']<0){
                return false;
            }
        }
        return true;
    }

}

思路2：可以把原字符串全部先排序，排序之后的异位词就全部都是相等的了

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map = new HashMap<>();
        for(String str:strs){
            char[] ch = str.toCharArray();
            Arrays.sort(ch);
            String newString = new String(ch);
            List<String> list = map.getOrDefault(newString, new ArrayList<>());
            list.add(str);
            map.put(newString,list);
        }
        return new ArrayList<>(map.values());
        
    }
}

3.1.4找到字符串中所有字母异位词

思路：滑动窗口维护一个一个字串然后比较他们是否为异位词即可

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        for(int i =0;i<=s.length()-p.length();i++){
            String newString = s.substring(i,i+p.length());
            if(isAnagram(newString, p)){
                 ans.add(i);
            }
        }
        return ans;

    }
    public boolean isAnagram(String s, String t) {
        if(s.length()!=t.length()){
            return false;
        }
        int[] a = new int[26];
        char[]sChars = s.toCharArray();
        for(char sChar:sChars){
            ++a[sChar-'a'];
        }
        for(char tChar:t.toCharArray()){
            if(--a[tChar-'a']<0){
                return false;
            }
        }
        return true;
    }
}

思路：但是用时比较抽象，题中字符都是小写字母，其实可以用桶排解决，还有就是滑动窗口其实只有头尾字符次数会变，可以用数组维护滑动窗口的字符出现个数

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if(s.length()<p.length()){
            return new ArrayList<>();
        }
        List<Integer> ans = new ArrayList<>();
        int[] pCnt = new int[26];
        int[] sCnt = new int[26];
        char[] pChars = p.toCharArray();
        for(char pChar:pChars){
            ++pCnt[pChar-'a'];
        }
        for(int i =0;i<p.length();i++){
            ++sCnt[s.charAt(i)-'a'];
        }
        if(Arrays.equals(pCnt, sCnt)){
            ans.add(0);
        }
        for(int i =0;i<s.length()-p.length();i++){
            --sCnt[s.charAt(i)-'a'];
            ++sCnt[s.charAt(i+p.length())-'a'];
            if(Arrays.equals(pCnt, sCnt)){
                ans.add(i+1);
            }
        }
        return ans;
    }
}

继续优化，每次都要整个数组遍历一遍比较太浪费时间，所以维护一个变长滑动窗口，当窗口长度跟p的长度相同时符合条件，这样就不用每次都比较数组相等了

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if(s.length()<p.length()){
            return new ArrayList<>();
        }
        int[] cnt = new int[26];
        int fast=0,slow=0;
        List<Integer> ans = new ArrayList<>();
        for(char ch:p.toCharArray()){
            ++cnt[ch-'a'];
        }
        while(fast<s.length()){
            if(cnt[s.charAt(fast)-'a']>0){
                --cnt[s.charAt(fast++)-'a'];
                if(fast-slow==p.length()){
                    ans.add(slow);
                }
            }else{
                ++cnt[s.charAt(slow++)-'a'];
            }
        }
        return ans;
    }
}

3.2两个数组的交集

3.2.1两个数组的交集

思路：将一个数组的元素放在一个set中自动去重，然后遍历另一个数组，找到前一个集合中出现过的元素即为交集

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> union1 = new HashSet<>();
        Set<Integer> union = new HashSet<>();
        for(int num:nums1){
            union1.add(num);
        }
        for(int num:nums2){
            if(union1.contains(num)){
                union.add(num);
            }
        }
        return union.stream().mapToInt(Integer::intValue).toArray();
    }
}

3.2.2两个数组的交集Ⅱ

思路：跟上题差不多，不过是用HsahMap记录了每个数的出现次数，然后转换成int[]

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer,Integer> map = new HashMap<>();
        List<Integer> ans = new ArrayList<>();
        for(int num:nums1){
            map.put(num, map.getOrDefault(num,0)+1);
        }
        for(int num:nums2){
            if(map.getOrDefault(num,0)>0){
                ans.add(num);
                map.put(num,map.get(num)-1);
            }
        }
        int[] a = new int[ans.size()];
        for(int i =0;i<ans.size();i++){
            a[i]=ans.get(i);
        }
        return a;
    }
}

3.3快乐数

思路：主要就是判断什么时候要继续循环直到平方和等于1，什么时候可以判断继续循环下去不能得到1，判断n为快乐数的条件显然易得，但是什么时候可以确定n不是快乐数呢，题目中提到了会无限循环，是不是说明如果非快乐数平方和相加的结果是一个循环呢，尝试了一下结果真的可以

class Solution {
    public boolean isHappy(int n) {
        int sum=0;
        int s=0;
        Set<Integer> set = new HashSet<>();
        set.add(n);
        while(true){
            while(n>0){
                s=n%10;
                n/=10;
                sum+=s*s;
            }
            if(sum==1){
                break;
            }
            if(set.contains(sum)){
                return false;
            }
            set.add(sum);
            n=sum;
            sum=0;
        }
        return true;
    }
}

看看题解，数组不断平方和会有三种结果

1. 最终得到1
2. 最终进入循环
3. 值越来越大，最后接近无穷

但是第三个结果不太可能，官方题解是这么说的

即使是十三位数的最大值的平方和也才到1053，所以第三种情况是不可能出现的，所以非快乐数只有平方和陷入循环的情况

3.4两数之和

思路：首先非常容易想到的就是双重循环，实现起来也很简单，但是用时比较长

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for(int i=0;i<nums.length;i++){
            for(int j=i+1;j<nums.length;j++){
                if(nums[i]+nums[j]==target){
                    return new int[]{i,j};
                }
            }
        }
        return new int[2];
    }
}

怎么优化呢，题目中是要在数组中找到两个数相加等于target，那么如果有一个数num是这题的答案，那么就要在数组中找到另一个数等于target-num，对于这种是否存在的问题可以使用哈希的方式快速确定

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i<nums.length;i++){
            if(map.containsKey(target-nums[i])){
                return new int[]{map.get(target-nums[i]),i};
            }else{
                map.put(nums[i],i);
            }
        }
        return new int[2];
    }
}

3.5四数相加

3.5.1四数相加Ⅱ

思路：最简单自然想到的肯定还是四重循环遍历，但是有了上题的铺垫，我们想一下有什么办法可以优化呢。上题是用HashMap记录了已经出现的数和对应的索引，从O(n^2)优化到了O(n)，现在从四个数组找相加等于0，那么我们可以仿照上题的思路，将四数分为两组，用HashMap记录一组数据相加的全部和，然后计算另一组的和，从HashMap中找到另一组中是否存在和的相反数，为了尽可能的降低时间复杂度，我们可以两两一组，这样两组计算和的时间复杂度都是O(n^2)

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer,Integer> map = new HashMap<>();
        int res=0;
        for(int i=0;i<nums1.length;i++){
            for(int j=0;j<nums2.length;j++){
                int sum1 = nums1[i]+nums2[j];
                map.put(sum1,map.getOrDefault(sum1,0)+1);
            }
        }
        for(int i=0;i<nums3.length;i++){
            for(int j=0;j<nums4.length;j++){
                res+=map.getOrDefault(-nums3[i]-nums4[j],0);
            }
        } 
        return res;
    }
}

3.5.2三数之和

思路：这题有点复杂，最先想到的还是暴力遍历，三重循环然后用set去重

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> ans = new HashSet<>();
        for(int i =0;i<nums.length;i++){
            for(int j=i+1;j<nums.length;j++){
                if(i==j){
                    continue;
                }
                for(int k=j+1;k<nums.length;k++){
                    if(i==k||j==k){
                        continue;
                    }
                    if(nums[i]+nums[j]+nums[k]==0){
                        List<Integer> sum = new ArrayList<>();
                        sum.add(nums[i]);
                        sum.add(nums[j]);
                        sum.add(nums[k]);
                        sum.sort((a,b)->a-b);
                        ans.add(sum);
                    }
                }
            }
        }
        return new ArrayList<List<Integer>>(ans);
    }
}

三重循环O(n^3)毫无意外的超时了，那么有什么办法可以优化呢，这种相加问题很容易就想到要用哈希表去寻找，但是在这题不太适用，哈希表不能很好的解决去重的问题，后来看了其他人的思路，大概就是可以先排序数组，然后遍历数组，固定一个节点，然后双指针从头尾开始往中间逼近寻找，这样的时间复杂度在O(n^2)，比上面的用时要少

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> set = new HashSet<>();
        int left,right;
        for(int i=0;i<nums.length-2;i++){
            left=i+1;
            right=nums.length-1;
            while(left<right){
                int sum=nums[i]+nums[left]+nums[right];
                if(sum==0){
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    set.add(list);
                    --right;
                    ++left;
                }else if (sum>0){
                    --right;
                }else{
                    ++left;
                }
            }
        }
        return new ArrayList<List<Integer>>(set);
    }
}

但是这种做法耗时好像还是比较久，那么有什么办法可以更快呢，这里可以做一些简单的优化，如果是相同的元素可以加一层循环直接跳过，这样也不用Set去重，最后还要转回List

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        int left,right;
        for(int i=0;i<nums.length-2;i++){
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            left=i+1;
            right=nums.length-1;
            while(left<right){
                int sum=nums[i]+nums[left]+nums[right];
                if(sum==0){
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    ans.add(list);
                    do{
                        --right;
                    }while(nums[right]==nums[right+1]&&left<right);
                    do{
                        ++left;
                    }while(nums[left]==nums[left-1]&&left<right);
                }else if (sum>0){
                    do{
                        --right;
                    }while(nums[right]==nums[right+1]&&left<right);
                }else{
                    do{
                        ++left;
                    }while(nums[left]==nums[left-1]&&left<right);
                }
            }
        }
        return ans;
    }
}

可以看到耗时大幅的减少，由此可见样例给出的重复元素还是挺多的，然后再看一下其他人的解，发现一个跳出循环的判断，当最小的指针大于0的时候，三个数的和一定大于零，加上这个特判之后，用时又减少了

但是其实最后两个优化并没有从时间复杂度上优化，但是在这道题的样例点还是能优化不少时间的，最难想的还是这个排序后用固定一个点然后双指针遍历

3.5.3四数之和

思路：这题跟上题差不多，只是多了一个数多了一层循环

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        int left,right;
        long sum=0;
        for(int i =0;i<nums.length-3;i++){
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            if(nums[i]>0&&nums[i]>target){
                break;
            }
            for(int j=i+1;j<nums.length-2;j++){
                if(j>i+1&&nums[j]==nums[j-1]){
                    continue;
                }
                if(nums[i]+nums[j]>0&&nums[i]+nums[j]>target){
                    break;
                }
                left=j+1;
                right=nums.length-1;
                while(left<right){
                    sum=(long)nums[i]+nums[j]+nums[left]+nums[right];
                    if(sum==target){
                        ans.add(new ArrayList<>(Arrays.asList(nums[i],nums[j],nums[left],nums[right])));
                        do{
                            ++left;
                        }while(nums[left]==nums[left-1]&&left<right);
                        do{
                            --right;
                        }while(nums[right]==nums[right+1]&&left<right);
                    }else if(sum>target){
                        do{
                            --right;
                        }while(nums[right]==nums[right+1]&&left<right);
                    }else{
                        do{
                            ++left;
                        }while(nums[left]==nums[left-1]&&left<right);
                    }
                }
            }
        }
        return ans;
    }
}

看了题解，方法其实都是一致的，只是在剪枝上做了优化，在官方给出的样例中能够更快的通过

最接近的三数之和

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int res = nums[0]+nums[1]+nums[2];
        int left,right;
        for(int i=0;i<nums.length-2;++i){
            left=i+1;
            right=nums.length-1;
            while(left<right){
                int sum = nums[i]+nums[left]+nums[right];
                if(sum>target){
                    if(Math.abs(res-target)>Math.abs(sum-target)){
                        res = sum;
                    }
                    do{
                        --right;
                    }while(left<right&&nums[right]==nums[right+1]);
                }else if(sum<target){
                    if(Math.abs(res-target)>Math.abs(sum-target)){
                        res = sum;
                    }
                    do{
                        ++left;
                    }while(left<right&&nums[left]==nums[left-1]);
                }else{
                    return sum;
                }
            }
        }
        return res;
    }
}

4.字符串

4.1反转字符串

思路：很简单的一个循环交换

class Solution {
    public void reverseString(char[] s) {
        int left=0;
        int right=s.length-1;
        char tem;
        while(left<right){
            tem=s[left];
            s[left++]=s[right];
            s[right--]=tem;
        }
    }
}

也可以用 ^ 运算计算值，主要是利用了 a^b^a=b这个式子

class Solution {
    public void reverseString(char[] s) {
        int left=0;
        int right=s.length-1;
        char tem;
        while(left<right){
            s[left]^=s[right];
            s[right]^=s[left];
            s[left++]^=s[right--];
        }
    }
}

4.2反转字符串Ⅱ

思路：题目虽然看着很复杂，但是还是很容易看出模型的，就是把字符串k个反转，然后跳过k个不断循环

class Solution {
    public String reverseStr(String s, int k) {
        char[]sChar = s.toCharArray();
        int cnt=0;
        while(cnt*k<=s.length()){
            reverseString(sChar,cnt*k,Math.min((cnt+1)*k,s.length())-1);
            cnt+=2;
        }
        return new String(sChar);
    }

    public void reverseString(char[] s,int left,int right) {
        while(left<right){
            s[left]^=s[right];
            s[right]^=s[left];
            s[left++]^=s[right--];
        }
    }
}

4.3翻转字符串的单词

思路：这题用trim和split函数做出来挺简单的，但是在不使用这些函数的情况下要处理这些边界问题还是比较麻烦的，这里主要是用一个List把空格存取来，还要判断什么时候应该要存空格

class Solution {
    public String reverseWords(String s) {
        char[] sChar = s.toCharArray();
        List<Integer> list = new ArrayList<>();
        list.add(-1);
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)==' '){
                list.add(i);
            }
        }
        list.add(s.length());
        StringBuilder sb = new StringBuilder();
        boolean first = true;
        boolean flag = false;
        for(int i=list.size()-1;i>0;i--){
            for(int j=list.get(i-1)+1;j<list.get(i);j++){
                if(!first&&flag){
                    sb.append(" ");
                    flag=false;
                }
                first=false;
                sb.append(s.charAt(j));
            }
            if(!first){
                flag=true;
            }
        }
        return sb.toString();
    }
}

思路二：先总体反转再单词反转

class Solution {
    public String reverseWords(String s) {
        char[] trims = s.trim().toCharArray();
        int slow=0;
        for(int i=0;i<trims.length;++i){
            if(trims[i]!=' '){
                trims[slow++]=trims[i];
            }else{
                while(trims[i+1]==' '){
                    ++i;
                }
                trims[slow++]=' ';
            }
        }
        reverseCharArray(trims,0,slow-1);
        reverWords(trims,0,slow-1);

        return new String(trims).substring(0,slow);
    }

    public void reverWords(char[] words, int left, int right){
        int virtual = left;
        while(virtual<right){
            while(virtual<right && words[virtual+1]!=' '){
                ++virtual;
            }
            reverseCharArray(words,left,virtual);
            left=virtual+2;
            ++virtual;
        }
    }
    public void reverseCharArray(char[] chars, int left, int right){
        while(left<right){
            char tem = chars[left];
            chars[left]=chars[right];
            chars[right]=tem;
            ++left;
            --right;
        }
    }
}

4.4旋转字符串

4.4.1右旋转字符串

思路：字符串拼接分开拼接一下就好了

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int k = scanner.nextInt();
        String next = scanner.next();
        System.out.println(next.substring(next.length()-k)+next.substring(0,next.length()-k));
        scanner.close();
    }
}

*4.5实现strStr()

思路：不使用index函数的情况下，最容易想到的还是暴力循环

class Solution {
    public int strStr(String haystack, String needle) {
        for(int i=0;i<haystack.length();i++){
            int index=0;
            while(i+index<haystack.length()&&
                index<needle.length()&&
                haystack.charAt(i+index)==needle.charAt(index)){
                    ++index;
            }
            if(index==needle.length()){
                return i;
            }
        }
        return -1;
    }
}

但是这题其实还可以用KMP算法来解决，KMP的特点就是当出现字符串不匹配的情况可以不用从头匹配，只需要一次循环就能够找到字串，那么他是怎么做到的呢，下面介绍一下KMP算法

KMP算法的核心思想就是：当字符串出现不匹配的时候，会有一个数组（记作next）告诉你，可以从字串的哪个位置（记作i）继续往后匹配，避免从头再去匹配，因为next保证了字串的开头前next[i]个字符和从i往前数next[i]个字符是一样的，这个数组称为前缀表，主要的作用就是字符不匹配的时候进行回退

上图中当文本串指针到达第二个b的时候，模式串是f，跟文本串不一致，这时候模式串的指针只需要回到第一个b的位置就可以和文本串的指针继续往后匹配了，因为模式串的开头aa出现了两次，第二个aa跟模式串的前缀aa是一样的，指针在f说明前面已经出现过了aa，所以这个时候模式串的指针只需要从b开始比较就可以了，而不需要从头开始，文本串也不需要往前回溯，这样比较的时间复杂度就成了O(n)

前缀表的构成分为三个部分：

1. 初始化
2. 处理前后缀不相同的情况
3. 处理前后缀相同的情况

下面是实现代码

public int[] getNext(String s){
        //初始化
        int[] next = new int[s.length()];
        int j =-1;
        next[0]=j;
        for(int i=1;i<s.length();i++){
            //处理前后缀不相同情况
            while(j>=0&&s.charAt(i)!=s.charAt(j+1)){
                j=next[j];
            }
            //处理前后缀相同情况
            if(s.charAt(i)==s.charAt(j+1)){
                j++;
            }
            next[i]=j;
        }
        return next;
    }

那么这道题目的答案也就出来了

class Solution {
    public int strStr(String haystack, String needle) {
        int[]next = getNext(needle);
        int j=-1;
        for(int i=0;i<haystack.length();i++){
            while(j>=0&&needle.charAt(j+1)!=haystack.charAt(i)){
                j=next[j];
            }
            if(haystack.charAt(i)==needle.charAt(j+1)){
                j++;
                if(j==needle.length()-1){
                    return i-j;
                }
            }
        }
        return -1;
    }

    public int[] getNext(String s){
        //初始化
        int[] next = new int[s.length()];
        int j =-1;
        next[0]=j;
        for(int i=1;i<s.length();i++){
            //处理前后缀不相同情况
            while(j>=0&&s.charAt(i)!=s.charAt(j+1)){
                j=next[j];
            }
            //处理前后缀相同情况
            if(s.charAt(i)==s.charAt(j+1)){
                j++;
            }
            next[i]=j;
        }
        return next;
    }
}

*4.6重复的子字符串

思路1：这题可以用暴力求解，注意一些细节的处理就好了

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        for(int i =1;i<s.length()/2;i++){
            if(s.length()%i!=0){
                continue;
            }
            boolean flag=true;
            for(int j=i;j<s.length();j++){
                if(s.charAt(j)!=s.charAt(j-i)){
                    flag=false;
                    break;
                }
            }
            if(flag){
                return true;
            }
        }
        return false;
    }
}

思路2：如果s是重复的子字符串，那么s+s去掉头尾后应该还存在一个s

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        String newString=s+s;
        newString=newString.substring(1,newString.length()-1);
        if(newString.indexOf(s)!=-1){
            return true;
        }
        return false;
    }
}

思路3：KMP算法就是用来寻找重复字串的，放在这题正好可以判断，如果s可以由多个字串构成，那么最后一个字符跟回退索引的差就是字串长度，他应该是s长度的公因数

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int[] next = new int[s.length()];
        int j =-1;
        next[0]=j;
        for(int i=1;i<s.length();i++){
            //处理前后缀不相同情况
            while(j>=0&&s.charAt(i)!=s.charAt(j+1)){
                j=next[j];
            }
            //处理前后缀相同情况
            if(s.charAt(i)==s.charAt(j+1)){
                j++;
            }
            next[i]=j;
        }
        if(next[s.length()-1]!=-1&&s.length()%(s.length()-next[s.length()-1]-1)==0){
            return true;
        }
        return false;
    }
}

5.双指针法

比较版本号

思路1：直接split，但是注意转义字符 .

class Solution {
    public int compareVersion(String version1, String version2) {
        
        String[] v1 = version1.split("\\.");
        String[] v2 = version2.split("\\.");
        for(int i=0;i<v1.length||i<v2.length;++i){
            int n1=0;
            int n2=0;
            if(i<v2.length){
                n2=Integer.parseInt(v2[i]);
            }
            if(i<v1.length){
                n1=Integer.parseInt(v1[i]);
            }
            if(n1>n2){
                return 1;
            }else if(n1<n2){
                return -1;
            }else{
                continue;
            }
        }
        return 0;
    }
}

思路2：双指针

class Solution {
    public int compareVersion(String version1, String version2) {
        int p1 = 0;
        int p2 = 0;
        while(p1<version1.length()&&p2<version2.length()){
            int v1=p1+1;
            int v2=p2+1;
            while(v1<version1.length()&&version1.charAt(v1)!='.'){
                ++v1;
            }
            while(v2<version2.length()&&version2.charAt(v2)!='.'){
                ++v2;
            }
            int n1=Integer.parseInt(version1.substring(p1,v1));
            int n2=Integer.parseInt(version2.substring(p2,v2));
            if(n1>n2){
                return 1;
            }else if(n2>n1){
                return -1;
            }
            p1=v1+1;
            p2=v2+1;
        }
        if(p1<version1.length()){
            while(p1<version1.length()){
                int v1=p1+1;
                while(v1<version1.length()&&version1.charAt(v1)!='.'){
                    ++v1;
                }
                int n1=Integer.parseInt(version1.substring(p1,v1));
                if(n1>0){
                    return 1;
                }
                p1=v1+1;
            }
        }else if(p2<version2.length()){
            while(p2<version2.length()){
                int v2=p2+1;
                while(v2<version2.length()&&version2.charAt(v2)!='.'){
                    ++v2;
                }
                int n2=Integer.parseInt(version2.substring(p2,v2));
                if(n2>0){
                    return -1;
                }
                p2=v2+1;
            }
        }
        return 0;
    }
}

6.栈和队列

6.1用栈实现队列

思路：用两个栈实现，栈的特点是后进先出，队列的特点是先进先出，每次插入元素的时候把栈中的元素存到另一个栈，然后插入元素使其落入栈底，然后按顺序把原来的元素入栈即可维持一条队列

class MyQueue {

    Stack<Integer> stack1;
    Stack<Integer> stack2;
    int size;

    public MyQueue() {
        this.stack1 = new Stack<>();
        this.stack2 = new Stack<>();
        this.size=0;
    }
    
    public void push(int x) {
        while(!stack2.empty()){
            stack1.push(stack2.pop());
        }
        stack2.push(x);
        while(!stack1.empty()){
            stack2.push(stack1.pop());
        }
    }
    
    public int pop() {
        return stack2.pop();
    }
    
    public int peek() {
        return stack2.peek();
    }
    
    public boolean empty() {
        return stack2.empty();
    }
}

7.二叉树

7.1前序遍历

思路：简单的递归，按照根节点，左子树，右子树的顺序遍历这棵树

class Solution {
    List<Integer> ans = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        preTraversal(root);
        return ans;
    }
    public void preTraversal(TreeNode root){
        if(root==null){
            return;
        }
        ans.add(root.val);
        preTraversal(root.left);
        preTraversal(root.right);
    }
}

思路2：非递归，利用栈后进先出的特性，将根节点的左右子节点进栈

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(stack.size()>0){
            TreeNode now = stack.pop();
            if(now != null){
                ans.add(now.val);
                stack.push(now.right);
                stack.push(now.left);
            }
        }
        return ans;
    }
}

7.2后序遍历

思路：递归，跟先序遍历的递归差不多，但是要注意遍历的顺序改变了。现在是根据左子树，右子树，根节点的数据遍历

class Solution {
    List<Integer> ans = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        postTraversal(root);
        return ans;
    }
    public void postTraversal(TreeNode root){
        if(root==null){
            return;
        }
        postTraversal(root.left);
        postTraversal(root.right);
        ans.add(root.val);
    }
}

思路2：迭代，还是用一个栈维护先前的节点，然后按照左节点，右节点，根节点的顺序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre= null;
        while(root!=null || stack.size()>0){
            while(root!=null){
                stack.push(root);
                root=root.left;
            }
            root=stack.pop();
            if(root.right==null || pre==root.right){
                ans.add(root.val);
                pre=root;
                root=null;
            }else{
                stack.push(root);
                root=root.right;
            }
        }
        return ans;
    }
}

7.3中序遍历

思路：递归，还是跟上面两题的递归方法差不多，只需要改变遍历和访问节点的顺序即可

class Solution {
    List<Integer> ans = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        midTraversal(root);
        return ans;
    }
    public void midTraversal(TreeNode root){
        if(root==null){
            return;
        }
        midTraversal(root.left);
        ans.add(root.val);
        midTraversal(root.right);
    }
}

思路2：迭代，还是跟上面两题的迭代方法差不多，注意遍历的顺序是左节点，根节点，右节点

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while(root!=null || stack.size()>0){
            while(root!=null){
                stack.push(root);
                root=root.left;
            }
            root=stack.pop();
            ans.add(root.val);
            root=root.right;
        }   
        return ans;
    }
}

7.4层序遍历

7.4.1二叉树的层序遍历

思路：可以用一个队列维护一层的元素，他的下一层元素就是改队列的每个节点的左右节点依次入队

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if(root==null){
            return ans;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(queue.size()>0){
            List<Integer> level = new ArrayList<>();
            for(int i=queue.size()-1;i>=0;--i){
                root = queue.poll();
                level.add(root.val);
                if(root.left!=null){
                    queue.offer(root.left);
                }
                if(root.right!=null){
                    queue.offer(root.right);
                }
            }
            ans.add(level);
        }
        return ans;
    }
}

7.4.2二叉树的层序遍历Ⅱ

思路：跟上题一样，只是每层插入的位置都是从头插入

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if(root==null){
            return ans;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(queue.size()>0){
            List<Integer> level = new ArrayList<>();
            for(int i=queue.size()-1;i>=0;--i){
                root = queue.poll();
                level.add(root.val);
                if(root.left!=null){
                    queue.offer(root.left);
                }
                if(root.right!=null){
                    queue.offer(root.right);
                }
            }
            ans.add(0,level);
        }
        return ans;
    }
}

7.4.3二叉树的右视图

思路：广度优先搜索，将相同深度即同一层的节点放在队列中，每次都将队列中最后一个节点添加到链表中

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if(root==null){
            return ans;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(queue.size()>0){
            int level =0;
            for(int i=queue.size()-1;i>=0;--i){
                root = queue.poll();
                level= root.val;
                if(root.left!=null){
                    queue.offer(root.left);
                }
                if(root.right!=null){
                    queue.offer(root.right);
                }
            }
            ans.add(level);
        }
        return ans;
    }
}

思路2：深度优先搜索，从上到下，从右到左进行深度优先搜索，将同一深度第一个遍历到的添加到队列

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        dfs(root,0,ans);
        return ans;
    }
    public void dfs(TreeNode root, int depth, List<Integer> ans){
        if(root==null){
            return; 
        }
        if(ans.size()==depth){
            ans.add(root.val);
        }
        ++depth;
        dfs(root.right,depth,ans);
        dfs(root.left,depth,ans);
    }
}

7.4.4层平均值

思路：由于要算层平均值，所以一层一层的处理会简单很多，首先用广度优先搜索做

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> ans = new ArrayList<>();
        if(root==null){
            return ans;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(queue.size()>0){
            int size = queue.size();
            double sum=0;
            for(int i=0;i<size;++i){
                root = queue.poll();
                sum+=root.val;
                if(root.left!=null){
                    queue.offer(root.left);
                }
                if(root.right!=null){
                    queue.offer(root.right);
                }
            }
            ans.add(sum/size);
        }
        return ans;
    }
}

思路2：用深度优先搜索，用两个链表分别记录每一层的个数和节点之和，最后统一算出

    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> ans = new ArrayList<>();
        List<Double> sum = new ArrayList<>();
        List<Integer> size = new ArrayList<>();
        dfs(root,0,sum,size);
        for(int i=0;i<sum.size();++i){
            ans.add(sum.get(i)/size.get(i));
        }
        return ans;
    }
    public void dfs(TreeNode root, int depth,List<Double> sum,List<Integer> size){
        if(root==null){
            return ;
        }
        if(depth<sum.size()){
            size.set(depth,size.get(depth)+1);
            sum.set(depth,sum.get(depth)+root.val);
        }else{
            size.add(1);
            sum.add(1.0*root.val);
        }
        ++depth;
        dfs(root.left,depth,sum,size);
        dfs(root.right,depth,sum,size);
    }
}

7.4.4 N叉树的层序遍历

思路：广度优先搜索，处理还是跟二叉树一样，将一层的节点依次入队，不过二叉树是左右节点依次入队，现在是list子节点依次入队

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ans = new ArrayList<>();
        if(root==null){
            return ans;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while(queue.size()>0){
            List<Integer> level = new ArrayList<>();
            for(int i=queue.size();i>0;--i){
                root=queue.poll();
                level.add(root.val);
                if(root.children!=null){
                    for(int j=0;j<root.children.size();++j){
                        queue.offer(root.children.get(j));
                    }
                }
            }
            ans.add(level);
        }
        return ans;
    }
}

思路2：深度优先搜索，具体做法跟上面的题目差不多

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ans = new ArrayList<>();
        dfs(root,0,ans);
        return ans;
    }
    public void dfs(Node root, int depth, List<List<Integer>>ans){
        if(root==null){
            return;
        }
        if(depth<ans.size()){
            ans.get(depth).add(root.val);
        }else{
            List<Integer> level =new ArrayList<>();
            level.add(root.val);
            ans.add(level);
        }
        ++depth;
        for(int i=0;i<root.children.size();++i){
            dfs(root.children.get(i),depth,ans);
        }
    }
}

7.4.5 在每个树行中找最大值

思路：广度优先搜索，找到每层元素的最大值

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if(root==null){
            return ans;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(queue.size()>0){
            int level =Integer.MIN_VALUE;
            for(int i=queue.size();i>0;--i){
                root = queue.poll();
                level=Math.max(level, root.val);
                if(root.left!=null){
                    queue.offer(root.left);
                }
                if(root.right!=null){
                    queue.offer(root.right);
                }
            }
            ans.add(level);
        }
        return ans;
    }
}

思路2：深度优先搜索，用ArrayList的索引和值把层数和最大值映射起来

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        ArrayList<Integer> ans = new ArrayList<>();
        dfs(root,0,ans);
        return ans;
    }
    public void dfs(TreeNode root, int depth, ArrayList<Integer>ans){
        if(root==null){
            return;
        }
        if(depth<ans.size()){
            ans.set(depth,Math.max(root.val,ans.get(depth)));
        }else{
            ans.add(depth,root.val);
        }
        ++depth;
        dfs(root.left,depth,ans);
        dfs(root.right,depth,ans);
    }
}

7.4.6 填充每个节点的下一个右侧节点指针

思路：广度优先搜索，将同一层的节点依次放在队列中，同一层的节点中，上一个节点的next指向下一个节点

class Solution {
    public Node connect(Node root) {
        if(root==null){
            return root;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        Node pre=null;
        Node cur = null;
        while(queue.size()>0){
            for(int i=queue.size();i>0;--i){
                cur=queue.poll();
                if(pre!=null){
                    pre.next=cur;
                }
                pre=cur;
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
            }
            pre=null;
        }
        return root;
    }
}

思路2：迭代，首先分析一下题目，给出的二叉树是完全二叉树，所以一个节点的next只有两种情况

第一种情况：该节点是他的父节点的左子节点，那么他的next是他的父节点的右子节点

第二种情况：该节点是他的父节点的右子节点，那么他的next是他的父节点的next的左子节点

分析出这两种情况之后我们就可以利用已经构建好next的一层节点去构建下一层的next

class Solution {
    public Node connect(Node root) {
        if(root==null){
            return root;
        }
        Node start= root;
        while(start.left!=null){
            Node cur = start;
            while(cur!=null){
                cur.left.next=cur.right;
                if(cur.next!=null){
                    cur.right.next=cur.next.left;
                }
                cur = cur.next;
            }
            start=start.left;
        }
        return root;
    }
}

7.4.7 填充每个节点的下一个右侧节点指针Ⅱ

思路1：这题跟上一题唯一的差别就是二叉树不一定是完全二叉树，所以上题的思路1也可以做出这一题，甚至代码都不用修改，因为上题的思路1使用队列存储每一层的非空节点，所以在非完全二叉树中也能找到他的下一个右侧节点

思路2：迭代，还是跟上题一样根据上层的结构构建下层的结构，但是本体不是完全二叉树，所以不能分为上题的两种情况，可以用三个指针分别记录下一层的开始节点，下一层构建好的最后一个节点和当前节点

class Solution {
    public Node connect(Node root) {
        if(root==null){
            return root;
        }
        Node pre= null;
        Node cur = null;
        Node start = root;
        while(start!=null){
            cur=start;
            pre=null;
            start=null;
            while(cur!=null){
                if(cur.left!=null){
                    if(pre!=null){
                        pre.next=cur.left;
                    }
                    if(start==null){
                        start=cur.left;
                    }
                    pre=cur.left;
                }
                if(cur.right!=null){
                    if(pre!=null){
                        pre.next=cur.right;
                    }
                    if(start==null){
                        start=cur.right;
                    }
                    pre=cur.right;
                }
                cur=cur.next;
            }
        }
        return root;
    }
}

7.4.8 二叉树的最大深度

思路：深度优先搜索，如果我们知道了左子树和右子树的最大深度l和r，那么二叉树的最大深度为max（l，r）+1，而左子树和右子树的最大深度又可以以同样的方式进行计算，因此我们可以递归算出最大深度

class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }
}

思路2：广度优先搜索，用一个变量记录当前遍历的最大层级，每次循环完一层之后+1，最后即可算出最大深度

class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int depth=0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(queue.size()>0){
            for(int i=queue.size();i>0;--i){
                root=queue.poll();
                if(root.left!=null){
                    queue.offer(root.left);
                }
                if(root.right!=null){
                    queue.offer(root.right);
                }
            }
            ++depth;
        }
        return depth;
    }
}

7.4.9 二叉树的最小深度

思路：广度优先搜索，还是用一个变量记录当前遍历的层级，然后当一个节点的左右子节点都是空的时候即为最小叶子节点

class Solution {
    public int minDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int depth=0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(queue.size()>0){
            ++depth;
            for(int i=queue.size();i>0;--i){
                root=queue.poll();
                if(root.left==null&&root.right==null){
                    return depth;
                }
                if(root.left!=null){
                    queue.offer(root.left);
                }
                if(root.right!=null){
                    queue.offer(root.right);
                }
            }
        }
        return depth;
    }
}

思路2：深度优先搜索，当节点的左右子节点都为空，那么该节点就是叶子节点，如果节点同时存在左节点或右节点，那么他的最小深度就是max（l，r）+1，如果只存在左右子节点之一，那么他的最小深度就是存在的之一节点的深度

class Solution {
    public int minDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }
        int depth=Integer.MAX_VALUE;
        if(root.left!=null){
            depth=Math.min(minDepth(root.left),depth);
        }
        if(root.right!=null){
            depth=Math.min(minDepth(root.right),depth);
        }
        return depth+1;
    }
}	

7.5 翻转二叉树

思路：深度优先搜索，递归遍历每一个节点，将他的左右节点交换位置即可

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null){
            return root;
        }
        TreeNode tem = root.left;
        root.left=root.right;
        root.right=tem;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

思路2：广度优先搜索，链表记录每一个节点，然后取出反转

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null){
            return root;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode cur;
        while(queue.size()>0){
            for(int i =queue.size();i>0;--i){
                cur = queue.poll();
                TreeNode tem = cur.left;
                cur.left=cur.right;
                cur.right=tem;
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
            }
        }
        return root;
    }
}

7.6 对称二叉树

7.6.1 对称二叉树

思路：递归，如果两个数互为镜像，那么应该满足两个条件

1. 两个树的根节点具有相同的值
2. 一个树的左右子节点分别和另一个树的右左子节点成镜像

确定了这个条件后我们就可以利用递归判断该树是否成镜像

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isequals(root.left,root.right);
    }
    boolean isequals(TreeNode left, TreeNode right){
        if(left==null&&right==null){
            return true;
        }
        if(left==null||right==null||left.val!=right.val){
            return false;
        }
        boolean isleft = isequals(left.left,right.right);
        boolean isright = isequals(right.left,left.right);
        if(isleft&&isright){
            return true;
        }
        return false;
    }
}

思路2：迭代，每次把位置在镜像相等的两个元素入队，如果两个元素相同那么按顺序把两个节点的四个位置对称的子节点入队，比较是否对称

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isequals(root.left,root.right);
    }
    boolean isequals(TreeNode left, TreeNode right){
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(left);
        queue.offer(right);
        while(queue.size()>0){
            left=queue.poll();
            right=queue.poll();
            if(left==null&&right==null){
                continue;
            }
            if(left==null||right==null||left.val!=right.val){
                return false;
            }
            queue.offer(left.left);
            queue.offer(right.right);
            queue.offer(left.right);
            queue.offer(right.left);
        }
        return true;
    }
}

7.6.2 相同的树

思路：用相同的方式遍历两棵树，如果两棵树的全部节点都相同则相同，如果有一个节点不同则不同，以下是递归+深度优先搜索

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null){
            return true;
        }
        if(p==null||q==null||p.val!=q.val){
            return false;
        }
        return isSameTree(p.left,q.left)&&isSameTree(q.right,p.right);
    }
}

7.6.3另一个树的子树

思路：深度优先搜索+暴力匹配，用树的每一个节点为根节点

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        return dfs(root,subRoot);
    }
    public boolean dfs(TreeNode root, TreeNode subRoot){
        if(root==null){
            return false;
        }
        return isSameTree(root,subRoot)||dfs(root.left,subRoot)||dfs(root.right,subRoot);
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null){
            return true;
        }
        if(p==null||q==null||p.val!=q.val){
            return false;
        }
        return isSameTree(p.left,q.left)&&isSameTree(q.right,p.right);
    }
}

7.7 二叉树的最大深度

7.7.1 二叉树的最大深度

见7.4.8

7.7.2 N叉树的最大深度

思路：深度优先搜索+递归，跟上面二叉树的最大深度差不多，一个节点的最大深度为所有子节点的最大深度和最大值+1，通过递归方式找到节点的最大深度

class Solution {
    public int maxDepth(Node root) {
        if(root==null){
            return 0;
        }
        int depth=0;
        for(Node node: root.children){
            depth=Math.max(depth,maxDepth(node));
        }
        return depth+1;
    }
}

思路2：广度优先搜索，用一个数记录当前层数，每次遍历到下一层+1

class Solution {
    public int maxDepth(Node root) {
        if(root==null){
            return 0;
        }
        int depth=0;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while(queue.size()>0){
            ++depth;
            for(int i=queue.size();i>0;--i){
                root = queue.poll();
                for(Node node: root.children){
                    queue.offer(node);
                }
            }
        }
        return depth;
    }
}

7.8 二叉树的最小深度

见7.4.9

7.9完全二叉树的节点个数

思路：广度优先搜索，记录每一层节点的个数

class Solution {
    public int countNodes(TreeNode root) {
        if(root==null){
            return 0;
        }
        Queue<TreeNode>queue = new LinkedList<>();
        queue.offer(root);
        int ans =0 ;
        while(queue.size()>0){
            ans+=queue.size();
            for(int i=queue.size();i>0;--i){
                TreeNode node = queue.poll();
                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
            }
        }
        return ans;
    }
}

思路2：深度优先搜索，找到每个一个节点就+1

class Solution {
    public int countNodes(TreeNode root) {
        if(root==null){
            return 0;
        }
        return countNodes(root.left)+countNodes(root.right)+1;
    }
}

思路3：可以根据题目给出的完全二叉树的特点进行计算，对于满二叉树，假设他的层数为n，那么他的节点数量等于2的n次方-1，而一个完全二叉树可以存在多个满二叉树，可以借助满二叉树计算完全二叉树的节点个数，而对于完全二叉树，可以一直找到节点的左节点和右节点，判断他们的层数是否相等，如果相等则是二叉树

class Solution {
    public int countNodes(TreeNode root) {
        if(root==null){
            return 0;
        }
        TreeNode left = root.left;
        TreeNode right = root.right;
        int leftCnt = 0;
        int rightCnt = 0;
        while(left!=null){
            left=left.left;
            ++leftCnt;
        }
        while(right!=null){
            right=right.right;
            ++rightCnt;
        }
        if(leftCnt==rightCnt){
            return (2<<leftCnt)-1;
        }
        return countNodes(root.left)+countNodes(root.right)+1;
    }
}

7.10 平衡二叉树

思路：计算每个节点的深度，当一个节点的左右子节点深度大于1则不平衡

class Solution {
    public boolean isBalanced(TreeNode root) {
        return heigh(root)!=-1;
    }
    public int heigh(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftHeight = heigh(root.left);
        int rightHeight =heigh(root.right);
        if(leftHeight==-1||rightHeight==-1||Math.abs(leftHeight-rightHeight)>1){
            return -1;
        }
        return Math.max(leftHeight,rightHeight)+1;
    }
}

7.11 二叉树的所有路径

思路：深度优先搜索+递归，每次记录从头到当前节点的路径String，然后拼接

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> ans = new ArrayList<>();
        dfs(root,"",ans);
        return ans;
    }
    public void dfs(TreeNode root, String val, List<String> ans){
        String s = val;
        if(val.length()>0){
            s+="->";
        }
        s+=root.val;
        if(root.left!=null){
            dfs(root.left,s,ans);
        }
        if(root.right!=null){
            dfs(root.right,s,ans);
        }
        if(root.left==null&&root.right==null){
            ans.add(s);
        }
    }
}

用StringBuilder优化

class Solution {
    List<String> ans = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        dfs(root,"");
        return ans;
    }
    public void dfs(TreeNode root, String val){
        if(root.left==null&&root.right==null){
            ans.add(new StringBuilder(val).append(root.val).toString());
        }
        String s = new StringBuilder(val).append(root.val).append("->").toString();
        if(root.left!=null){
            dfs(root.left,s);
        }
        if(root.right!=null){
            dfs(root.right,s);
        }
    }
}

7.12 左叶子之和

思路：前序遍历，判断当前节点是否左叶子节点，如果是则直接加

class Solution {
    int ans=0;
    public int sumOfLeftLeaves(TreeNode root) {
        leftAdd(root,false);
        return ans;
    }
    public void leftAdd(TreeNode root,boolean isLeft){
        if(root==null){
            return;
        }
        if(root.left==null&&root.right==null&&isLeft){
            ans+=root.val;
        }
        leftAdd(root.left,true);
        leftAdd(root.right,false);
    }
}

7.13 找树左下角的值

思路：广度优先搜索，找到每一层的第一个元素并记录，最后一层的第一个节点即为最左下角

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int ans=root.val;
        while(queue.size()>0){
            ans=queue.peek().val;
            for(int i=queue.size();i>0;--i){
                root=queue.poll();
                if(root.left!=null){
                    queue.offer(root.left);
                }
                if(root.right!=null){
                    queue.offer(root.right);
                }
            }
        }
        return ans;
    }
}

思路2：深度优先搜索+递归，用一个链表维护每一层最左侧的节点数值

class Solution {
    List<Integer> level = new ArrayList<>();
    public int findBottomLeftValue(TreeNode root) {
        dfs(root,0);
        return level.get(level.size()-1);
    }
    public void dfs(TreeNode root, int depth){
        if(root==null){
            return;
        }
        if(level.size()<=depth){
            level.add(root.val);
        }
        ++depth;
        dfs(root.left,depth);
        dfs(root.right,depth);
    }
}

优化思路2：因为改用记录当前层数代替链表，减去操作链表的时间

class Solution {
    int res=0;
    int depth=0;
    int maxDepth=-1;
    public int findBottomLeftValue(TreeNode root) {
        dfs(root);
        return res;
    }
    public void dfs(TreeNode root){
        if(root==null){
            return;
        }
        if(depth>maxDepth){
            depth=maxDepth;
            res=root.val;
        }
        ++depth;
        dfs(root.left);
        dfs(root.right);
        --depth;
    }
}

7.14 路径总和

7.14.1 路径总和

思路：深度优先搜索，用一个值记录从根节点到当前节点的值的总和，如果当前节点为根节点且总和登录给定的目标总和，那么返回true，否则返回false

class Solution {
    int sum=0;
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null){
            return false;
        }
        sum+=root.val;
        if(root.left==null&&root.right==null&&sum==targetSum){
            return true;
        }
        boolean leftSum = hasPathSum(root.left,targetSum);
        boolean rightSum = hasPathSum(root.right,targetSum);
        sum-=root.val;
        return leftSum||rightSum;
    }
}

7.14.2 路径总和Ⅱ

思路：深度优先搜索，用栈记录一条路线上的节点值，当遍历到叶子节点且节点之和等于目标值，就用栈中的队列创建一条链表

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    Stack<Integer> path = new Stack<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root,targetSum);
        return ans;
    }
    public void dfs(TreeNode root, int targetSum){
        if(root==null){
            return ;
        }
        targetSum-=root.val;
        path.push(root.val);
        if(root.left==null&&root.right==null&&targetSum==0){
            ans.add(new ArrayList<>(path));
        }
        dfs(root.left,targetSum);
        dfs(root.right,targetSum);
        targetSum+=root.val;
        path.pop();
    }
}

7.15 从中序与后续遍历序列构造二叉树

7.15.1 从中序与后续遍历序列构造二叉树

思路：后序遍历的最后一个节点为根节点，题目给出的关键条件是inorder和postorder都由不同的值组成，所以我们可以根据后续遍历的最后一个节点把中序遍历分为左右子树的两部分，重复操作接口构造原二叉树

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return divide(inorder,0,inorder.length-1,postorder,0,postorder.length-1);
    }
    public TreeNode divide(int[] inorder,int inbegin,int inend,int[] postorder, int pobegin,int poend){
        if(inbegin==inend){
            return new TreeNode(inorder[inbegin]);
        }
        if(inbegin>inend){
            return null;
        }
        int index=0;
        for(int i=inbegin;i<=inend;++i){
            if(inorder[i]==postorder[poend]){
                index=i;
                break;
            }
        }
        TreeNode node = new TreeNode(inorder[index]);
        node.left = divide(inorder,inbegin,index-1,postorder,pobegin,pobegin+(index-1-inbegin));
        node.right = divide(inorder,index+1,inend,postorder,pobegin+(index-inbegin),poend-1);
        return node;
    }
}

优化：用map记录数值和索引中间的映射关系，优化每次遍历数组查找

class Solution {
    Map<Integer,Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for(int i=0;i<inorder.length;++i){
            map.put(inorder[i],i);
        }
        return divide(inorder,0,inorder.length-1,postorder,0,postorder.length-1);
    }
    public TreeNode divide(int[] inorder,int inbegin,int inend,int[] postorder, int pobegin,int poend){
        if(inbegin==inend){
            return new TreeNode(inorder[inbegin]);
        }
        if(inbegin>inend){
            return null;
        }
        int index=map.get(postorder[poend]);
        TreeNode node = new TreeNode(inorder[index]);
        node.left = divide(inorder,inbegin,index-1,postorder,pobegin,pobegin+(index-1-inbegin));
        node.right = divide(inorder,index+1,inend,postorder,pobegin+(index-inbegin),poend-1);
        return node;
    }
}

7.15.2 从前序与中序遍历序列构造二叉树

思路：跟上题思路基本一致，上题根据后续遍历最后一个节点不断分区域，而前序遍历可以根据第一个节点分区域

class Solution {
    Map<Integer,Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i=0;i<inorder.length;++i){
            map.put(inorder[i],i);
        }
        return divide(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }
    public TreeNode divide(int[] preorder,int prebegin,int preend,int[] inorder, int inbegin,int inend){
        if(inbegin==inend){
            return new TreeNode(inorder[inbegin]);
        }
        if(inbegin>inend||prebegin>=inorder.length){
            return null;
        }
        int index=map.get(preorder[prebegin]);
        TreeNode node = new TreeNode(inorder[index]);
        node.left = divide(preorder,prebegin+1,prebegin+(index-inbegin),inorder,inbegin,index-1);
        node.right = divide(preorder,prebegin+(index-inbegin)+1,preend,inorder,index+1,inend);
        return node;
    }
}

7.16 最大二叉树

思路：找到数组中的最大值，将数组分为两部分，再找到最大值继续构建二叉树

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return makeTree(nums,0,nums.length-1);
    }
    public TreeNode makeTree(int[]nums,int begin, int end){
        if(begin>end){
            return null;
        }
        if(begin==end){
            return new TreeNode(nums[begin]);
        }
        int index=begin;
        for(int i=begin+1;i<=end;++i){
            if(nums[i]>nums[index]){
                index=i;
            }
        }
        TreeNode root = new TreeNode(nums[index]);
        root.left = makeTree(nums,begin,index-1);
        root.right = makeTree(nums,index+1,end);
        return root;
    }
}

7.17 合并二叉树

思路：简单的模拟，注意空指针问题即可

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1==null&&root2==null){
            return null;
        }
        int value=0;
        TreeNode left1=null;
        TreeNode right1=null;
        TreeNode left2=null;
        TreeNode right2=null;
        if(root1!=null){
            value+=root1.val;
            left1=root1.left;
            right1=root1.right;
        }
        if(root2!=null){
            value+=root2.val;
            left2=root2.left;
            right2=root2.right;
        }
        TreeNode node = new TreeNode(value);
        node.left=mergeTrees(left1,left2);
        node.right=mergeTrees(right1,right2);
        return node;
    }
}

7.18 二叉搜索树的搜索

思路：根据二叉搜索树的特点，如果节点的值比目标值大，则去他的左子树找，如果节点的值比目标值小，则去他的右子树找，如果相等，则该节点即为所求

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if(root==null){
            return null;
        }else if(root.val==val){
            return root;
        }else if(root.val>val){
            return searchBST(root.left,val);
        }
        return searchBST(root.right,val);
    }
}

7.19 验证二叉搜索树

思路：二叉搜索树每个节点的右子树节点都比自身节点的数值大，左子树节点都比自身的数值小，利用这个特性，记录节点数值的范围，递归判断

class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }
    public boolean isValidBST(TreeNode root, long min,long max){
        if(root==null){
            return true;
        }
        if(min>=root.val||max<=root.val){
            return false;
        }
        return isValidBST(root.left,min,root.val)&&isValidBST(root.right,root.val,max);
    }
}

7.20 二叉搜索树的最小绝对差

思路：中序遍历，记录上一个节点的值，中序遍历二叉搜索树可以保证上一个节点的值比当前节点值要小，每次计算出差值并且比较找到最小差值即可

class Solution {
    int min = Integer.MAX_VALUE;
    int pre=-1;
    public int getMinimumDifference(TreeNode root) {
        dfs(root);
        return min;
    }

    public void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        if(pre==-1){
            pre=root.val;
        }else{
            min=Math.min(min,root.val-pre);
            pre=root.val;
        }
        dfs(root.right);
    }
}

7.21 二叉搜索树中的众数

思路：利用二叉搜索树左子树节点比当前节点小，右子树节点比当前节点大的特点，中序遍历二叉搜索树可以保证遍历到的数值从小到大，用链表记录当前出现次数最多的节点

class Solution {
    int pre=-1;
    int cnt=0;
    int max=0;
    List<Integer> ans = new ArrayList<>();
    public int[] findMode(TreeNode root) {
        inorderTraversal(root);
        int[] ansArray = new int[ans.size()];
        for(int i=0;i<ans.size();++i){
            ansArray[i]=ans.get(i);
        }
        return ansArray;
    }
    public void inorderTraversal(TreeNode root){
        if(root==null){
            return;
        }
        inorderTraversal(root.left);
        if(root.val==pre){
            ++cnt;
            if(cnt==max){
                ans.add(root.val);
            }else if (cnt>max){
                ans.clear();
                max=cnt;
                ans.add(root.val);
            }
        }else{
            pre=root.val;
            cnt=1;
            if(cnt==max){
                ans.add(root.val);
            }else if(cnt>max){
                ans.add(root.val);
                max=1;
            }
        }
        inorderTraversal(root.right);
    }
}

7.22 二叉树的最近公共祖先

思路：深度优先搜索+递归，可以根据返回值判断当前节点是否目标节点的祖先节点，如果是目标节点的祖先节点则返回目标节点，否则返回null，当有一个节点的左右子节点返回都不是null，则代表这个节点是两节点公共祖先

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return null;
        }
        if(root==p||root==q){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left!=null&&right!=null){
            return root;
        }
        if(left!=null){
            return left;
        }
        return right;
    }
}

7.23 二叉搜索树的最近公共祖先

思路：根据二叉搜索树的特点，两个节点的最近公共祖先的值一定位于这两个节点的值中间

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode ancestor = root;
        while(true){
            if(p.val<ancestor.val&&q.val<ancestor.val){
                ancestor=ancestor.left;
            }else if (p.val>ancestor.val&&q.val>ancestor.val){
                ancestor=ancestor.right;
            }else{
                break;
            }
        }
        return ancestor;
    }
}

7.24 二叉搜索树中的插入操作

思路：根据二叉搜索树的特点，如果目标值比当前节点大就往右子树遍历，如果比当前节点小就往左子树遍历，直到节点为空就创建一个目标值的节点

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root==null){
            return new TreeNode(val);
        }
        TreeNode ancestor = root;
        while(true){
            if(ancestor.val>val){
                if(ancestor.left!=null){
                    ancestor=ancestor.left;
                }else{
                    ancestor.left=new TreeNode(val);
                    break;
                }
            }else if(ancestor.val<val){
                if(ancestor.right!=null){
                    ancestor=ancestor.right;
                }else{
                    ancestor.right=new TreeNode(val);
                    break;
                }
            }
        }
        return root;
    }
}

7.25 删除二叉搜索树中的节点

思路：首先利用二叉搜索树的特性找到目标节点并记录目标节点的父节点，其次就是删除节点后对删除节点的子树的处理，特别多坑，有很多地方都需要注意

首先判断要删除节点的状态，如果左右子树都为空，那么直接删除节点即可

如果要删除节点的只存在左子树或右子树中的一个，那么将左右子树中存在的一个放到原来要删除节点的位置即可

如果要删除节点的左右子树都存在，那么为了维持二叉搜索树的特点，需要在保证子树不变的前提下，找到一个合适的节点代替被删除节点的位置，可以找到右子树最小的节点或左子树最大的节点保证二叉搜索树的性质不变，这里采用找到右子树的最小节点代替实现

首先我们要找到右子树的最小节点，就要从被删除节点的右子节点开始，因为比被删除节点大的元素节点都在他的右子树上，而要找到这个子树的最小节点，就要从子树的根节点开始一直往左子节点遍历直到左子节点为空，得到的节点即为所需的比被删除节点大的最小节点

然后就是将这个节点替换到被删除节点的位置，首先需要处理这个节点的子树，因为这个节点的左子树为空，所以直接将他的右子树迁移到该节点原本的位置即可，就是将这个节点顶替到被删除节点的位置，然后将这个节点的左右子节点绑定被删除节点的左右子节点

这个时候又需要分几种情况，首先是被删除节点的父节点为空，那么代表被删除节点是根节点，这时候直接返回顶替好的节点即可

当被删除节点的根节点存在，需要判断被删除节点是他的左节点还是右节点，然后绑定返回原根节点即可，这里只需注意空指针即可

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        TreeNode cur = root;
        TreeNode ancestor = null;
        while(cur!=null&&cur.val!=key){
            if(cur.val<key){
                ancestor=cur;
                cur=cur.right;
            }else if (cur.val>key){
                ancestor=cur;
                cur=cur.left;
            }
        }
        if(cur==null){
            return root;
        }
        if(cur.left==null&&cur.right==null){
            cur=null;
        }else if(cur.left==null){
            cur=cur.right;
        }else if(cur.right==null){
            cur=cur.left;
        }else{
            TreeNode minParent=cur;
            TreeNode min=cur.right;
            while(min.left!=null){
                minParent=min;
                min=min.left;
            }
            if(minParent==cur){
                minParent.right=min.right;    
            }else{
                minParent.left=min.right;
            }
            min.left=cur.left;
            min.right=cur.right;
            cur=min;
        }
        if(ancestor==null){
            return cur;
        }
        if(ancestor.left!=null&&ancestor.left.val==key){
            ancestor.left=cur;
        }else if(ancestor.right!=null&&ancestor.right.val==key){
            ancestor.right=cur;
        }
        return root;
    }
}

7.26 修剪二叉搜索树

思路：刚刚拿到这道题感觉很难，思维停留在上一题要删除节点后保持二叉搜索树的性质，删除一个小于low的节点后，节点的右子树可能有部分节点满足在low和high之间，要将这些节点找到并且重构一个二叉树比较复杂。

但是重新想一下二叉搜索树的特点，左子树的节点都比当前节点小，右子树的节点都比当前节点大，所以某一个节点不满足[low,high]条件时，左右子树至少有一方不满足条件，假设某个节点比low小，左子树的节点全都比当前节点小，那么必然比low小，所以左子树肯定不符合条件，这时只需要考虑右子树；假设节点比high大，右子树节点全部比当前节点大，那么必然比high大，所以右子树肯定不符合条件

所以如果要删除某个节点，最多只需要保留他的一个子树，只需要让该子节点顶替需要删除的节点位置即可

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if(root==null){
            return null;
        }
        if(root.val>=low&&root.val<=high){
            root.left=trimBST(root.left,low,high);
            root.right=trimBST(root.right,low,high);
            return root;
        }else if(root.val<low){
            return trimBST(root.right,low,high);
        }else{
            return trimBST(root.left,low,high);
        }
    }
}

7.27 将有序数组转换为二叉搜索树

思路：递归，要求一个平衡二叉搜索树，最简单的就是将数组中间的元素作为根节点，然后将数组分为左右两部分，左边作为左子树，右边作为右子树，不断分割递归

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBST(nums,0,nums.length-1);
    }
    public TreeNode sortedArrayToBST(int[]nums, int begin, int end){
        if(begin>end){
            return null;
        }
        if(begin==end){
            return new TreeNode(nums[begin]);
        }
        int mid=(begin+end)/2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left=sortedArrayToBST(nums,begin,mid-1);
        root.right=sortedArrayToBST(nums,mid+1,end);
        return root;
    }
}

7.28把二叉搜索树转换成累加数

思路：首先二叉搜索树是有序的，要将二叉搜索树的节点变成比自己大的节点的累加，只需要按照右子树，父节点，左子树的顺序，将路程遇到的节点累加即可

class Solution {
    int sum=0;
    public TreeNode convertBST(TreeNode root) {
        travel(root);
        return root;
    }
    public void travel(TreeNode root){
        if(root==null){
            return ;
        }
        travel(root.right);
        sum+=root.val;
        root.val=sum;
        travel(root.left);
    }
}

8.回溯算法

8.1 组合问题

思路：如果是确定了组合k的次数，那么只需要k层循环，每次循环选择一个数作到当前位置，一个数确定后的所有情况确定后换下一个数找到所有情况即可，但是这里k的个数是不确定的，这时候我们可以使用递归进行回溯，用一个全局变量path记录当前路径遍历到的元素，根据path的大小确定当前遍历的位置，每次回溯后去除path的最后一个节点重新维护下一个元素

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        backTracking(n,k,1);
        return ans;
    }
    public void backTracking(int n,int k,int index){
        if(path.size()==k){
            ans.add(new ArrayList<>(path));
            return;
        }
        for(int i=index;i<=n;++i){
            path.add(i);
            backTracking(n,k,i+1);
            path.remove(path.size()-1);
        }
    }
}

优化：剪枝，对于回溯后剩下元素和path中元素加起来总和小于k时，已经不可能再凑成k个元素的组合了，这时候就可以直接退出了

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        backTracking(n,k,1);
        return ans;
    }
    public void backTracking(int n,int k,int index){
        if(path.size()==k){
            ans.add(new ArrayList<>(path));
            return;
        }
        for(int i=index;i<=n-(k-path.size())+1;++i){
            path.add(i);
            backTracking(n,k,i+1);
            path.remove(path.size()-1);
        }
    }
}

8.2 组合总和Ⅲ

思路：还是回溯，跟上题类似，但是不同的是，这里不止是纯粹的组合回溯，只有当路径总结相加等于目标值的时候才要将路径组合值添加到答案中

首先确定这里需要两个全局变量记录当前的路径和符合条件的路径的集合，其次还需要在递归的时候传递一个起始索引保证不会重复

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int pathSum=0;
    public List<List<Integer>> combinationSum3(int k, int n) {
        backTracking(k,n,1);
        return ans;
    }
    public void backTracking(int k, int n, int index){
        if(path.size()==k){
            if(pathSum==n){
                ans.add(new ArrayList<>(path));
            }
            return;
        }
        for(int i=index;i<=9;++i){
            path.add(i);
            pathSum+=i;
            backTracking(k,n,i+1);
            path.remove(path.size()-1);
            pathSum-=i;
        }
    }
}

优化：剪枝，当当前元素和超过目标和的时候就没有必要继续往下遍历了

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int pathSum=0;
    public List<List<Integer>> combinationSum3(int k, int n) {
        backTracking(k,n,1);
        return ans;
    }
    public void backTracking(int k, int n, int index){
        if(pathSum>n){
            return;
        }
        if(path.size()==k){
            if(pathSum==n){
                ans.add(new ArrayList<>(path));
            }
            return;
        }
        for(int i=index;i<=9;++i){
            path.add(i);
            pathSum+=i;
            backTracking(k,n,i+1);
            path.remove(path.size()-1);
            pathSum-=i;
        }
    }
}

8.3 电话号码的字母组合

思路：先创建一张数字到对应字母的映射表，然后还是像上面的题一样，遍历电话号码的每一位，将每一个电话号码映射的字母都遍历回溯一遍，就可以得到全部的组合，但是这里是多集合取组合，每个数字对应一个集合，集合之间互不影响，所以不需要起始索引

class Solution {
    List<String> ans = new ArrayList<>();
    Map<Character,Character[]> map = new HashMap<>();
    {
        map.put('2',new Character[]{'a','b','c'});
        map.put('3',new Character[]{'d','e','f'});
        map.put('4',new Character[]{'g','h','i'});
        map.put('5',new Character[]{'j','k','l'});
        map.put('6',new Character[]{'m','n','o'});
        map.put('7',new Character[]{'p','q','r','s'});
        map.put('8',new Character[]{'t','u','v'});
        map.put('9',new Character[]{'w','x','y','z'});
    }
    public List<String> letterCombinations(String digits) {
        if(digits.length()==0){dj
            return ans;
        }
        char[]path = new char[digits.length()];
        backTracking(digits,0,path);
        return ans;
    }
    public void backTracking(String digits,int index,char[]path){
        if(index==digits.length()){
            ans.add(new String(path));
            return;
        }
        for(Character ch:map.get(digits.charAt(index))){
            path[index]=ch;
            backTracking(digits,index+1,path);
        }
    }
}

8.4 组合总和

思路：回溯，这题跟上面8.2组合总和Ⅲ差不多，唯一的区别就是这里数组中的元素是无限制的，所以在递归遍历的时候不需要关注层数，只需要关注路径总和是否大于target

首先我们确定需要的全局变量，这里需要的全局变量跟上面8.2组合总和Ⅲ差不多，都是一个记录符合条件路径list的list，还有就是记录当前递归路径的list和当前总和，最后还需要在递归的时候传递一个起始索引保证不重复

因为这里不限元素个数，索引递归的终止条件只需要考虑路径总和大于目标值

对于每次循环的，只需要从起始索引开始搜索数组，但是因为元素是可以被重复选取的，所以在递归调用的时候，下一次调用的起始索引就不是i+1了，而是i

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int pathSum=0;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backTracking(candidates,target,0);
        return ans;
    }
    public void backTracking(int[] candidates,int target,int index){
        if(pathSum>target){
            return;
        }
        if(pathSum==target){
            ans.add(new ArrayList<>(path));
            return;
        }
        for(int i=index;i<candidates.length;++i){
            path.add(candidates[i]);
            pathSum+=candidates[i];
            backTracking(candidates,target,i);
            path.remove(path.size()-1);
            pathSum-=candidates[i];
        }
    }
}

8.5 组合总和Ⅱ

思路：还是回溯，这题跟上一题 8.4组合总和的区别就是，上一题的元素可以重复无限使用，这里每个元素只能使用一次，并且元素可以重复且解集不能包含重复的组合，为了保证相同的元素被使用两次，就要保证每个位置只会出现一个相同的元素，可以将原数组排序后然后比较当前索引元素跟上一个位置的元素是否相同判断是否重复

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backTracking(candidates,target,0);
        return ans;
    }
    public void backTracking(int[] candidates,int target, int index){
        if(target==0){
            ans.add(new ArrayList<>(path));
            return;
        }
        for(int i=index;i<candidates.length;++i){
            if(i>index&&candidates[i]==candidates[i-1]){
                continue;
            }
            path.add(candidates[i]);
            backTracking(candidates,target-candidates[i],i+1);
            path.remove(path.size()-1);
        }
    }
}

但是没想到最后超时了，这里继续思考一下这个算法有什么可以优化的地方

数组已经排序过了，所以数组后边的元素一定比前边的元素大，如果数组添加到当前位置总和就大于目标值，那么继续往后遍历就更大与目标值了，这时候就没有必要继续遍历下去了，通过这个简单的剪枝操作，就可以通过了

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backTracking(candidates,target,0);
        return ans;
    }
    public void backTracking(int[] candidates,int target, int index){
        if(target==0){
            ans.add(new ArrayList<>(path));
            return;
        }
        for(int i=index;i<candidates.length;++i){
            if(i>index&&candidates[i]==candidates[i-1]){
                continue;
            }
            if(candidates[i]>target){	//剪枝
                return;
            }
            path.add(candidates[i]);
            backTracking(candidates,target-candidates[i],i+1);
            path.remove(path.size()-1);
        }
    }
}

8.6 分割回文串

思路：这里需要找到s分割的全部方案还是需要通过回溯进行枚举，回文字符串的判断可以通过双指针法判断，也可以通过动态规划进行判断

这里要将s分割成每个子串都是回文串，找到上一个回文子串后，需要枚举出以当前索引开始的全部回文串，很适合使用动态规划去做

class Solution {
    List<List<String>> ans = new ArrayList<>();
    List<String> path = new ArrayList<>();
    public List<List<String>> partition(String s) {
        int[][]dp=new int[s.length()][s.length()];
        for(int i=s.length()-1;i>=0;--i){
            for(int j=i;j<s.length();++j){
                if(s.charAt(i)==s.charAt(j)){
                    if(j-i<=1 || dp[i+1][j-1]==1){
                        dp[i][j]=1;
                    }
                }
            }
        }
        backTracking(s,0,dp);
        return ans;
    }
    public void backTracking(String s,int index, int[][]dp){
        if(index>=s.length() ){
            ans.add(new ArrayList<>(path));
            return;
        }
        for(int i=index;i<s.length();++i){
            if(dp[index][i]==1){
                path.add(s.substring(index,i+1));
                backTracking(s,i+1,dp);
                path.remove(path.size()-1);
            }
        }
    }
}

8.7 复原IP地址

思路：首先还是要用回溯找到全部的情况，首先确定递归需要的参数，这里每次回溯都是操作同一个字符串，所以需要一个起始索引确定每次分割的起始位置，另外这里ip地址确定了只能分割成四个子串，所以还需要一个参数记录当前分割了多少个字串

确定完回溯参数后，就是终止条件，这里ip地址只能分成四段，所以可以根据层级确定当前是否应该终止

每一层循环都从起始索引开始往后截取子串，因为有效值是[0,255]，所以最多只需要遍历三个元素即可跳出当前循环，然后需要判断子串大小是否在区间中且没有前导0

class Solution {
    List<String> ans = new ArrayList<>();
    List<String> path = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        backTracking(s,0,0);
        return ans;
    }

    public void backTracking(String s, int index, int level){
        if(index>=s.length()){
            return ;
        }
        if(level==3){
            if(isValited(s,index,s.length())){
                ans.add(path.get(0) + "." + path.get(1) + "." + path.get(2) + "." + s.substring(index,s.length()));
            }
            return;
        }
        for(int i=1;i<=3&&index+i<=s.length();++i){
            if(isValited(s,index,index+i)){
                path.add(s.substring(index,index+i));
                backTracking(s,index+i,level+1);
                path.remove(level);
            }else{
                break;
            }
        }
    }
    public boolean isValited(String s,int begin,int end){
        if(end-begin==1 || (end-begin <= 3 && s.charAt(begin)!='0' && Integer.valueOf(s.substring(begin,end))<=255)){
            return true;
        }
        return false;
    }
}

8.8 子集

思路：回溯列举出所有的情况，因为每次递归操作的都是同一个数组的元素，所以还是需要一个起始索引判断开始的位置

每次递归的终止条件也很容易看出来，当起始索引超过数组元素个数大小后就可以终止了

每层循环也只需要遍历添加起始索引后的元素即可，因为是求子集问题，所以不需要任何的剪枝

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        backTracking(nums,0);
        return ans;
    }
    public void backTracking(int[]nums, int index){
        ans.add(new ArrayList<>(path));
        if(index>=nums.length){
            return;
        }
        for(int i=index;i<nums.length;++i){
            path.add(nums[i]);
            backTracking(nums,i+1);
            path.remove(path.size()-1);
        }
    }
}

8.9 子集Ⅱ

思路：跟上题差不多，不过这里会出现相同的元素，并且元素相同的集合会看作是相同的自己，所以需要先对数组进行排序，然后比较是否选取了相同的元素

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        backTracking(nums,0);
        return ans;
    }
    public void backTracking(int[]nums, int index){
        ans.add(new ArrayList<>(path));
        if(index>=nums.length){
            return;
        }
        for(int i=index;i<nums.length;++i){
            if(i!=index &&nums[i]==nums[i-1]){
                continue;
            }
            path.add(nums[i]);
            backTracking(nums,i+1);
            path.remove(path.size()-1);
        }
    }
}

8.10 非递减子序列

思路：还是回溯找到全部的情况，这里是对一个数组进行操作，所以还是需要一个起始索引记录每次开始的位置，其次每次结束的条件都是起始索引大于数组元素

确定完参数和终止条件之后，就要看看每次遍历的逻辑了，这里需要找到的是非递增子序列，那么每次遍历都需要找到递增的元素，那么每次遍历只需要跟路径元素中的最后一个元素比较，只要大于等于最后一个元素即可，但是这样可能会出现两个重复的元素被使用两次当成不同子序列的问题，所以还需要在每层递归中用一个set维护已经使用过的元素，如果是已经使用过的元素就直接跳过，不再使用

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        backTracking(nums,0);
        return ans;
    }
    public void backTracking(int[]nums, int index){
        if(path.size()>1){
            ans.add(new ArrayList<>(path));
        }
        if(index>=nums.length){
            return;
        }
        Set<Integer> set = new HashSet<>();
        for(int i=index;i<nums.length;++i){
            if(set.contains(nums[i])){
                continue;
            }
            if(path.size()==0 || nums[i]>=path.get(path.size()-1)){
                set.add(nums[i]);
                path.add(nums[i]);
                backTracking(nums,i+1);
                path.remove(path.size()-1);
            }
        }
    }
}

8.11 全排列

思路：直接暴力全部搜索一遍，题目中说数组不含重复数字，所以每次遍历的时候，可以都当成一个新的集合，每次都从路径元素中判断是否出现过该元素，如果出现过则直接下一个，穷举出所有的情况，并借助路径元素集合去重

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        backTracking(nums);
        return ans;
    }
    public void backTracking(int[] nums){
        if(path.size()==nums.length){
            ans.add(new ArrayList<>(path));
        }
        for(int i=0;i<nums.length;++i){
            if(!path.contains(nums[i])){
                path.add(nums[i]);
                backTracking(nums);
                path.remove(path.size()-1);
            }
        }
    }
}

优化：上面这种思路虽然可以列举出全部的情况并且不会重复，但是每层递归使用的contains函数都要遍历一遍path，判断是否已经使用过该元素，时间复杂度一共来到O n的三次方，这里使用一个数组记录使用过的元素，可以将判断是否使用过一个元素的时间缩短到O(1)，总体的时间复杂度来到了O n的平方

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        boolean[]used = new boolean[nums.length];
        backTracking(nums,used);
        return ans;
    }
    public void backTracking(int[] nums,boolean[] used){
        if(path.size()==nums.length){
            ans.add(new ArrayList<>(path));
        }
        for(int i=0;i<nums.length;++i){
            if(!used[i]){
                path.add(nums[i]);
                used[i]=true;
                backTracking(nums,used);
                path.remove(path.size()-1);
                used[i]=false;
            }
        }
    }
}

8.12 全排列Ⅱ

思路：跟上题的回溯差不多，可以使用一个数组记录使用过的元素减少判断元素是否使用过的情况，然后这里跟上一题不一样的地方就是数组中会出现相同的元素，要返回的是不重复的全排列，所以还需要用一个数组判断当前位置是否已经使用过某个元素，注意到这里数组中的元素范围是[-10,10]，所以可以使用一个大小为21的数组记录使用过的元素

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] pathUsed = new boolean[nums.length];
        backTracking(nums,pathUsed);
        return ans;
    }
    public void backTracking(int[]nums,boolean[]pathUsed){
        if(path.size()==nums.length){
            ans.add(new ArrayList<>(path));
        }
        boolean[] indexUsed = new boolean[21];
        for(int i=0;i<nums.length;++i){
            if(!pathUsed[i]&&!indexUsed[nums[i]+10]){
                path.add(nums[i]);
                pathUsed[i]=true;
                indexUsed[nums[i]+10]=true;
                backTracking(nums,pathUsed);
                path.remove(path.size()-1);
                pathUsed[i]=false;
            }
        }
    }
}

*8.13 重新安排行程

思路：第一想法还是回溯，dfs找到全部的路径，如果某一条路线走不通再回溯到之前的其他路线

先确定好递归所需要的参数，首先需要一个变量path记录走到当前位置所经过的地点，然后为了防止路程中出现环形导致在循环里出不来，这里还要用一个数组记录当前索引的地点是否已经走过

接下来就是确定每一层遍历的逻辑，这里每一层都需要根据上一次行程的终点找到符合条件的机票，即需要找到起点是路径中最后一处地点的并且还是未使用过的机票，找到之后递归

值得注意的是这里的递归并不像之前一样不需要返回参数，因为要找到一条符合条件的路，所以这里需要传回一个boolean值判断当前路径是否能够走通

class Solution {
    List<String> path = new ArrayList<>();
    public List<String> findItinerary(List<List<String>> tickets) {
        Collections.sort(tickets,(a,b)->a.get(1).compareTo(b.get(1)));
        boolean[]used = new boolean[tickets.size()];
        path.add("JFK");
        backTracking(tickets,used);
        return path;
    }
    public boolean backTracking(List<List<String>> tickets, boolean[] used){
        if(path.size()==tickets.size()+1){
            return true;
        }
        for(int i=0;i<tickets.size();++i){
            if(!used[i] && path.get(path.size()-1).equals(tickets.get(i).get(0))){
                used[i]=true;
                path.add(tickets.get(i).get(1));

                if(backTracking(tickets,used)){
                    return true;
                }
                used[i]=false;
                path.remove(path.size()-1);
            }
        }
        return false;
    }
}

优化：上面的代码只差一个样例点没过，那么至少证明思路没有问题，那么有什么办法可以优化搜索的过程呢

我们注意到上面每次根据路径最后一个节点找到符合条件的机票，都要从头开始遍历全部机票并且比较起始位置和当前位置是否相同和是否使用过，这里耗费了较多时间，可以想办法对这个过程进行优化，这里使用了一个Map数组去记录一个机票的起点和他的索引的集合，这样每次找某个起点的机票只需要从map中找到key为该起点的集合，集合中的元素就是符合条件的机票的索引

class Solution {
    List<String> path = new ArrayList<>();
    public List<String> findItinerary(List<List<String>> tickets) {
        Collections.sort(tickets,(a,b)->a.get(1).compareTo(b.get(1)));
        boolean[]used = new boolean[tickets.size()];
        path.add("JFK");
        Map<String,List<Integer>> map = new HashMap<>();
        for(int i=0;i<tickets.size();++i){
            List<Integer> list = map.getOrDefault(tickets.get(i).get(0),new ArrayList<>());
            list.add(i);
            map.put(tickets.get(i).get(0),list);
        }
        backTracking(tickets,used,map);
        return path;
    }
    public boolean backTracking(List<List<String>> tickets, boolean[] used,Map<String, List<Integer>> map){
        if(path.size()==tickets.size()+1){
            return true;
        }
        if(map.containsKey(path.get(path.size()-1))){
            for(Integer index:map.get(path.get(path.size()-1))){
                if(!used[index]){
                    used[index]=true;
                    path.add(tickets.get(index).get(1));
                    if(backTracking(tickets,used,map)){
                        return true;
                    }
                    used[index]=false;
                    path.remove(path.size()-1);
                }
            }
        }
        
        return false;
    }
}

再优化：还是这一个样例点没过，看来优化机票的搜索过程并没有优化太多的时间，这里又注意到为了在有多个符合条件的路径时找到从小到大的路径，在一开始要对机票进行排序，这个过程可能会耗费比较多的时间，还有机票的map维护的是起点机票和他的索引的映射，这里可以直接将索引改为终点字符串，这样就只需要对map进行操作，不需要再去操作数组

class Solution {
    List<String> path = new ArrayList<>();
    Map<String,List<String>> tickerMap = new HashMap<>();
    int total = 0;
    public List<String> findItinerary(List<List<String>> tickets) {
        total=tickets.size();
        path.add("JFK");
        for(int i=0;i<tickets.size();++i){
            addNew(tickets.get(i).get(0),tickets.get(i).get(1));
        }
        backTracking("JFK");
        return path;
    }
    public boolean backTracking(String start){
        if(path.size()==total+1){
            return true;
        }
        if(tickerMap.containsKey(start)){
            List<String> tickets = tickerMap.get(start);
            for(int i=0;i<tickets.size();++i){
                String end = tickets.get(i);
                path.add(end);
                tickets.remove(i);
                if(backTracking(end)){
                    return true;
                }
                path.remove(path.size()-1);
                tickets.add(i,end);
            }
        }
        return false;
    }
    public void addNew(String start, String end){
        List<String> list = tickerMap.getOrDefault(start,new ArrayList<>());
        for(int i=0;i<list.size();++i){
            if(end.compareTo(list.get(i))<0){
                list.add(i,end);
                return;
            }
        }
        list.add(end);
        tickerMap.put(start,list);
    }
}

结果依然还是这个点超时了，有点蚌埠住了，这里用相同的逻辑换c++试一下

class Solution {
private:
// unordered_map<出发机场, map<到达机场, 航班次数>> targets
unordered_map<string, map<string, int>> targets;
bool backtracking(int ticketNum, vector<string>& result) {
    if (result.size() == ticketNum + 1) {
        return true;
    }
    for (pair<const string, int>& target : targets[result[result.size() - 1]]) {
        if (target.second > 0 ) { // 记录到达机场是否飞过了
            result.push_back(target.first);
            target.second--;
            if (backtracking(ticketNum, result)) return true;
            result.pop_back();
            target.second++;
        }
    }
    return false;
}
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        targets.clear();
        vector<string> result;
        for (const vector<string>& vec : tickets) {
            targets[vec[0]][vec[1]]++; // 记录映射关系
        }
        result.push_back("JFK"); // 起始机场
        backtracking(tickets.size(), result);
        return result;
    }
};

结果非常的amazing啊，换了c++就过了

8.14 N皇后

思路：递归遍历全部情况然后回溯，首先确定回溯的全局参数，这里需要一个path记录之前皇后放下的位置，还有一个记录符合条件的集合ans，还需要记录当前遍历到的索引的位置

接下来确定终止条件，因为只有n个皇后，所以遍历到第n个位置就可以停下终止

最后确定每一层的遍历循环条件，只需要判断当前位置是否符合要求即可，对于不同的列，只要他跟之前放的皇后行号不一样，就可以保证横竖方向不会冲突，这时候只需要解决斜向不会冲突即可，可以通过存放位置和索引之和和差进行判断是否冲突

class Solution {
    List<Integer> path = new ArrayList<>();
    List<List<String>> ans = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        backTracking(n,0);
        return ans;
    }
    public void backTracking(int n,int index){
        if(n==index){
            List<String> once = new ArrayList<>();
            for(int i=0;i<n;++i){
                StringBuilder sb = new StringBuilder();
                for(int j=0;j<path.get(i);++j){
                    sb.append(".");
                }
                sb.append("Q");
                for(int j=path.get(i)+1;j<n;++j){
                    sb.append(".");
                }
                once.add(sb.toString());
            }
            ans.add(once);
            return;
        }
        for(int i=0;i<n;++i){
            if(isValidated(i,index)){
                path.add(i);
                backTracking(n,index+1);
                path.remove(path.size()-1);
            }
        }
    }
    public boolean isValidated(int position,int index){
        for(int i=0;i<path.size();++i){
            if(path.get(i)==position || path.get(i)-i==position-index || path.get(i)+i==position+index){
                return false;
            }
        }
        return true;
    }
}

优化：用char二维数组代替字符串的拼接，减少对字符串操作耗费的时间

class Solution {
    List<List<String>> ans = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        char[][] chessBoard=  new char[n][n];
        for (char[] c : chessBoard) {
            Arrays.fill(c, '.');
        }
        backTracking(n,0,chessBoard);
        return ans;
    }
    public void backTracking(int n,int index,char[][]chessBoard){
        if(n==index){
            List<String> once = new ArrayList<>();
            for(int i=0;i<n;++i){
                once.add(new String(chessBoard[i]));
            }
            ans.add(once);
            return;
        }
        for(int i=0;i<n;++i){
            if(isValidated(i,index,chessBoard)){
                chessBoard[i][index]='Q';
                backTracking(n,index+1,chessBoard);
                chessBoard[i][index]='.';
            }
        }
    }
    public boolean isValidated(int position,int index,char[][]chessBoard){
        for(int i=0;i<chessBoard.length;++i){
            if(chessBoard[position][i]=='Q'){
                return false;
            }
        }
        int add=position+index;
        int minus=position-index;
        for(int i=0;i<chessBoard.length;++i){
            int addTem = add-i;
            int minusTem = minus+i;
            if(addTem>=0 && addTem<chessBoard.length && chessBoard[addTem][i]=='Q'){
                return false;
            }
            if(minusTem>=0&&minus+i<chessBoard.length &&chessBoard[minusTem][i]=='Q'){
                return false;
            }
        }
        return true;
    }
}

8.15 解数独

思路：还是穷举出所有的情况，如果不正确就回溯更换其他数字，这里还是需要返回一个boolean值判断当前情况是否符合条件

class Solution {
    public void solveSudoku(char[][] board) {
        solveSudokuHelper(board);
    }
    public boolean solveSudokuHelper(char[][] board){
        for(int i=0;i<board.length;++i){
            for(int j=0;j<board.length;++j){
                if(board[i][j]!='.'){
                    continue;
                }
                for(char k='1';k<='9';++k){
                    if(isValidated(board,i,j,k)){
                        board[i][j]=k;
                        if(solveSudokuHelper(board)){
                            return true;
                        }
                        board[i][j]='.';
                    }
                }
                return false;
            }
        }
        return true;
    }
    public boolean isValidated(char[][]board, int i,int j,char k){
        for(int m=0;m<board.length;++m){
            if(board[i][m]==k || board[m][j]==k){
                return false;
            }
        }
        i=i/3*3;
        j=j/3*3;
        for(int m=i;m<3+i;++m){
            for(int n=j;n<3+j;++n){
               if(board[m][n]==k){
                return false;
               } 
            }
        }
        return true;
    }
}

9.贪心算法

9.1分发饼干

思路：既然要尽可能满足越多数量的孩子，那么就要减少饼干的浪费，小的饼干能满足小胃口的孩子，就不要浪费大的饼干，先对孩子胃口和饼干大小排序，从小到大遍历饼干，寻找是否能满足剩余最小胃口的小孩

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int a=0;
        int cnt=0;
        for(int i=0;i<s.length;i++){
            if(s[i]>=g[a]){
                ++cnt;
                ++a;
                if(a>=g.length){
                    break;
                }
            }
        }
        return cnt;
    }
}

9.2摆动序列

思路：这题要注意的点比较多，首先是差值等于0不算摆动系列，所以cur等于0的情况不需要管。还有要注意头尾的元素也要计算摆动，还有单调的平坡不能重复计算，所以只需要在坡度变化的情况下改变pre就可以了

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if(nums.length==1){
            return 1;
        }
        int pre=0;
        int cur=0;
        int cnt=1;
        for(int i =0;i<nums.length-1;i++){
            cur=nums[i+1]-nums[i];
            if((pre<=0&&cur>0)||(pre>=0&&cur<0)){
                cnt++;
                pre=cur;
            }
        }
        return cnt; 
    }
}

9.3最大子序和

思路：第一眼看上去要找子数组最大感觉要用双指针维护一个滑动窗口，但是仔细一想，滑动窗口其实还不太能做这道题，因为很难保证快指针遇到负数之后后面不会有更大的数，所以想到了动态规划，创建了一个数组dp[i]，保证原数组从0到i至少包含一个元素的最大子序和为dp[i]

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp=new int[nums.length];
        dp[0]=nums[0];
        int ans=dp[0];
        for(int i=1;i<nums.length;i++){
            dp[i]=Math.max(0,dp[i-1])+nums[i];
            ans=Math.max(dp[i],ans);
        }
        return ans;
    }
}

上面只有一次遍历，其实可以把dp数组优化掉，其实也像是贪心算法，pre是从0到指针处的最大数

class Solution {
    public int maxSubArray(int[] nums) {
        int ans=nums[0];
        int pre=nums[0];
        for(int i=1;i<nums.length;i++){
            pre=Math.max(0,pre)+nums[i];
            ans=Math.max(pre,ans);
        }
        return ans;
    }
}

9.4买卖股票的最佳时机Ⅱ

思路：最不用动脑的一题，只要下一天股票涨了我就买，只要跌了我就卖

class Solution {
    public int maxProfit(int[] prices) {
        int ans=0;
        for(int i=1;i<prices.length;i++){
            ans+=Math.max(prices[i]-prices[i-1],0);
        }
        return ans;
    }
}

9.5跳跃游戏

思路：抽象成数学问题贪心算法其实挺好做的，只是一些特例比较恶心卡了我几次。

首先要明确不是所在位置元素有多大就一定要跳多远，即使数字很大我也可以只跳一格，那么我们就可以把跳跃这个行为抽象成一种能力，一个我还能往后走多少格的能力，所以每往后走一格我的这个能力就会-1，但是我可以选择跳到这个格子里，那么我的能力清零但是我获得大小等于这个数字的能力，贪心算法保证我的能力一直是最大的，如果某一时刻为0但是还没到结尾那么就不能到达

class Solution {
    public boolean canJump(int[] nums) {
    	//长度为一就在数组结尾
        if(nums.length==1){
            return true;
        }
        //开头就不能跳而且不是长度为一直接返回false
        if(nums[0]==0){
            return false;
        }
        int cur=nums[0];
        for(int i=1;i<nums.length;i++){
            cur=Math.max(cur-1,nums[i]);
            if(cur<=0&&i<nums.length-1){
                return false;
            }
        }
        return true;
    }
}

9.6跳跃游戏Ⅱ

思路：因为题目保证了最后一个节点一定可达，所以只需要计算最小跳跃次数就行，这里创建了一个数组，代表从头到当前索引位置的最小跳跃次数，每次往后一格都计算从当前格往后跳最小跳跃的次数

class Solution {
    public int jump(int[] nums) {
        int[] dp = new int[nums.length];
        for(int i=1;i<dp.length;i++){
            dp[i]=Integer.MAX_VALUE;
        }
        for(int i=0;i<nums.length;i++){
            for(int j=1;j<=nums[i];j++){
                if(i+j<nums.length){
                    dp[i+j]=Math.min(dp[i+j],dp[i]+1);
                }
            }
        }
        return dp[nums.length-1];
    }
}

虽然过了但是非常丑陋，耗时也很长，想一下还有什么办法，遍历数组的时候每到一个位置都要往他可达的地方刷新一遍最小步数，其实很浪费时间，其实只需要用覆盖范围的概念，找到可达范围内的覆盖范围最大的位置即可

class Solution {
    public int jump(int[] nums) {
        if(nums.length==1){
            return 0;
        }
        int cnt=1;
        int cover=nums[0];
        int next=cover;
        int end=nums.length-1;
        int cur=0;
        while(cover<end){
            for(int i=cur+1;i<=cover;i++){
                if(next<end&&i+nums[i]>cover){
                    next=Math.max(i+nums[i],next);
                    cur=i;
                }
            }
            cover=next;
            cnt++;
        }
        return cnt;
    }
}

看了题解后发现其实只用一层循环就可以解决了，不过思路差不多，时间复杂度也一样，但是太优雅了

9.7K次取反后最大化的数组和

思路：每次都找到最小的一个数取反

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        int min=0;
        while(k>0){
            for(int i=0;i<nums.length;i++){
                if(nums[min]>nums[i]){
                    min=i;
                }
            }
            if(nums[min]>=0){
                k=k%2;
            }
            if(k>0){
                nums[min]=-nums[min];
                --k;
            }
        }
        int sum=0;
        for(int i=0;i<nums.length;++i){
            sum+=nums[i];
        }
        return sum;
    }
}

但是耗时较长，可以先对数组排序，然后一直取反直到遇到非负数

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int sum=0;
        for(int i=0;i<nums.length;++i){
            if(nums[i]>=0){
                k%=2;
            }
            if(k>0){
                nums[i]=-nums[i];
                --k;
            }
            sum+=nums[i];
        }
        return sum;
    }
}

还是没过，推测是因为将-2变为2后k等于1，然后继续往后把4变成-4了，然后交了一次，还有k大于数组个数的情况，最终修改通过代码如下

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int sum=0;
        for(int i=0;i<nums.length;++i){
            if(nums[i]>=0){
                k%=2;
                //如果还要选一个做负数
                if(k==1){
                    //如果不是第一个元素并且上一个元素绝对值小
                    if(i!=0&&nums[i-1]<nums[i]){
                        sum-=(2*nums[i-1]);
                        --k;
                    }
                }
            }
            if(k>0){
                nums[i]=-nums[i];
                --k;
            }
            sum+=nums[i];
        }
        if(k>0&&k%2==1){
            int min=Integer.MAX_VALUE;
            for(int i=0;i<nums.length;++i){
                min=Math.min(min,nums[i]);
            }
            sum-=(2*min);
        }
        return sum;
    }
}

9.8加油站

思路：首先我们假设他可以绕行一周，计算从0开始到下一个位置剩下的油，如果到最后油量为负数，那么说明不能绕行一周，那么在保证可以绕行一周后怎么确定起点呢。

这个时候只需要找到过程中油量最少的索引即可，我们从开头的油量设为0，这个0只是相对值，并不会像真实场景那样没油了就会停下来，在遍历往下后到达下一个地点还剩多少油，找到油最少的情况，就能够保证其他所有时刻油量都大于等于0

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int min=Integer.MAX_VALUE;
        int index=0;
        int cur=0;
        for(int i=0;i<gas.length;++i){
            cur+=(gas[i]-cost[i]);
            if(cur<=min){
                min=cur;
                index=i;
            }
        }
        if(cur<0){
            return -1;
        }
        return (index+1)%gas.length;
    }
}

*9.9分发糖果

思路：一开始一直在想怎么让糖果最少，但是忽略找到局部最优，后来看了其他人的思路才想到，分别从左右两边寻找最少，从而让局部最优变成整体最优

class Solution {
    public int candy(int[] ratings) {
        int[] candies=new int[ratings.length];
        candies[0]=1;
        for(int i=1;i<ratings.length;++i){
            if(ratings[i]>ratings[i-1]){
                candies[i]=candies[i-1]+1;
            }else{
                candies[i]=1;
            }
        }
        int sum=0;
        for(int i=ratings.length-1;i>0;--i){
            if(ratings[i-1]>ratings[i]){
                candies[i-1]=Math.max(candies[i]+1,candies[i-1]);
            }
            sum+=candies[i];
        }
        sum+=candies[0];
        return sum;
    }
}

9.10柠檬水找零

思路：按流程模拟一遍就行了，记录当前剩余的5元和10元，如果顾客付5元不用找，10元只能找5元，20元可以找三张5元或10元和5元各一张，只有20元可以找10元，所以优先找10元

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five=0;
        int ten=0;
        for(int i=0;i<bills.length;++i){
            if(bills[i]==5){
                //5元不用找
                ++five;
            }else if (bills[i]==10){
                //10元找五元
                --five;
                ++ten;
            }else{
                //20元优先找10元
                if(ten>0){
                    --ten;
                    --five;
                }else{
                    five=five-3;
                }
            }
            if(five<0||ten<0){
                return false;
            }
        }
        return true;
    }
}

*9.11根据身高重建队列

思路：第一时间想到的是根据排名先排序，后面再移动身高，但是这样的方法要归纳出一个方法还是比较困难，所以还是得先用身高排序，然后再根据k值往后移动

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people,(p1,p2)->{
            return p1[0]-p2[0] == 0 ?
                        p2[1]-p1[1]:
                        p1[0]-p2[0];
        });
        for(int i=people.length-1;i>=0;--i){
            if(people[i][1]>0){
                int tem1=people[i][0];
                int tem2=people[i][1];
                for(int j=0;j<tem2;++j){
                    people[i+j][0]=people[i+j+1][0];
                    people[i+j][1]=people[i+j+1][1];
                }
                people[i+tem2][0]=tem1;
                people[i+tem2][1]=tem2;
            }
        }
        return people;
    }
}

但是耗时有点抽象，主要是移动耗了很多时间，这里可以先反向排序，然后用LinkedList插入重排序转回数组

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people,(p1,p2)->{
            return p1[0]-p2[0] == 0 ?
                        p1[1]-p2[1]:
                        p2[0]-p1[0];
        });
        List<int[]> list=new ArrayList<>();
        for(int[] p:people){
            list.add(p[1],p);
        }
        return list.toArray(new int[people.length][2]);
    }
}

9.12用最少数量的箭引爆气球

思路：一看到这道题的直觉就是要每支箭都尽可能多的去射到多的气球，但是要模拟出这个情况还是想了很久的，可以先将数组排序，然后确保下一个气球的左边界不回超过前面气球最小右边界就可以了

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (p1,p2)->{
            if( p1[0]-p2[0]==0){
                return Integer.compare(p1[1],p2[1]);
            }else{
                return Integer.compare(p1[0],p2[0]);
            }
        });
        int cnt=1;
        int right=points[0][1];
        for(int i=0;i<points.length;++i){
            if(points[i][0]>right){
                ++cnt;
                right=points[i][1];
            }
            right=Math.min(right,points[i][1]);
        }
        return cnt;
    }
}

9.13无重叠区间

思路：跟上题引爆气球思路差不多，都是找重复的区间，但是我这里是按右排序

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals,(i1,i2)->{
            if(i1[1]==i2[1]){
                return Integer.compare(i2[0],i1[0]);
            }else{
                return Integer.compare(i1[1],i2[1]);
            }
        });
        int cnt=0;
        int pre=0;
        for(int i=1;i<intervals.length;++i){
            if(intervals[i][1]==intervals[i-1][1]){
                ++cnt;
            }else if(intervals[i][0]<intervals[pre][1]){
                ++cnt;
            }else{
                pre=i;
            }
        }
        return cnt;
    }
}

这里看到一个左排序的，代码量少很多，可以品一下

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a,b)-> {
            return Integer.compare(a[0],b[0]);
        });
        int count = 1;
        for(int i = 1;i < intervals.length;i++){
            if(intervals[i][0] < intervals[i-1][1]){
                intervals[i][1] = Math.min(intervals[i - 1][1], intervals[i][1]);
                continue;
            }else{
                count++;
            }    
        }
        return intervals.length - count;
    }
}

9.14划分字母区间

思路：暴力循环，遍历整个字符串，找到开头字符最后出现的位置，然后把开头到整个位置之间的全部字符最后出现的位置找到，重复此操作，直到保证区间内全部元素都不出现在区间外，继续完成整个字符串的遍历

class Solution {
    public List<Integer> partitionLabels(String s) {
        Set<Character> set = new HashSet<>();
        List<Integer> ans =new ArrayList<>();
        int start=0;
        int cur=0;
        int end=1;
        while(end<=s.length()){
            while(cur<end){
                set.add(s.charAt(cur));
                for(int i=cur+1;i<s.length();++i){
                    if(s.charAt(i)==s.charAt(cur)){
                        end=Math.max(i+1,end);
                    }
                }
                do{
                    ++cur;
                }while(cur<end&&set.contains(s.charAt(cur)));
            }
            ans.add(end-start);
            start=cur;
            end=start+1;
            set.clear();
        }
        return ans;
    }
}

这题还可以用桶排思想，记录每个字符最后出现的位置

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> ans =new ArrayList<>();
        int[] edges = new int[26];
        for(int i=0;i<s.length();++i){
            edges[s.charAt(i)-'a']=i;
        }
        int start = 0;
        int end=0;
        for(int i=0;i<s.length();++i){
            end=Math.max(end,edges[s.charAt(i)-'a']);
            if(i==end){
                ans.add(i-start+1);
                start=i+1;
            }
        }
        return ans;
    }
}

9.15合并区间

思路：跟前面差不多，都是先排序，找公共区间

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals,(i1,i2)->{
            return Integer.compare(i1[0],i2[0]);
        });
        List<int[]>ans=new ArrayList<>();
        int start=intervals[0][0];
        int end=intervals[0][1];
        for(int i=1;i<intervals.length;++i){
            if(intervals[i][0]>end){
                ans.add(new int[]{start,end});
                start=intervals[i][0];
                end=intervals[i][1];
            }else{
                end=Math.max(end,intervals[i][1]);
            }
        }
        ans.add(new int[]{start,end});
        return ans.toArray(new int[ans.size()][2]);
    }
}

9.16单调递增的数字

思路：纯数学，从个位开始往前走，如果前一位比后一位数字大，那么就不是递增，该位数字就要减1，低位的数字为了最大那就全都为9

class Solution {
    public int monotoneIncreasingDigits(int n) {
        Stack<Integer> stack = new Stack<>();
        int m=n;
        int cnt=0;
        int pre=9;
        while(m>0){
            int cur=m%10;
            if(cur>pre){
                cnt=1;
                stack.push(cur-1);
                pre=cur-1;
            }else{
                ++cnt;
                stack.push(cur);
                pre=cur;
            }
            m/=10;
        }
        int res=0;
        for(int i=stack.size();i>0;--i){
            if(cnt>0){
                res=res*10+stack.pop();
                --cnt;
            }else{
                res=res*10+9;
            }
        }
        return res;
    }
}

9.17监控二叉树

思路：这题可以使用贪心算法，从叶子节点往上遍历，判断是否需要添加摄像头，节点分为三种情况，带摄像头，被监控和未被监控，分别用1，2，0表示，从叶子节点往上遍历，当子节点中存在未被监控的节点时，那么该节点一定要带摄像头，当子节点已被监控，那么该节点可以不需要带摄像头，可以返回0让父节点带摄像头保证节点被监控到

/**
 * Definition for a binary tree node.
 * public 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;
 *     }
 * }
 */
class Solution {
    //1 有摄像头，2被覆盖
    private Integer cnt = 0;
    public int minCameraCover(TreeNode root) {
        if(minCnt(root)==0){
            ++cnt;
        }
        return cnt;
    }
    public int minCnt(TreeNode root){
        if(root==null){
            return 2;
        }
        int left = minCnt(root.left);
        int right = minCnt(root.right);
        if(left==0||right==0){
            ++cnt;
            return 1;
        }
        if(left==1||right==1){
            return 2;
        }
        return 0;
    }
}

10.动态规划

10.1斐波那契数列

思路：经典问题，递归的入门，但是递归多了很多不必要的计算，所以用数组把已经计算过的数存起来，直接取就行了，从前面的状态推出后面的状态

class Solution {
    public int fib(int n) {
        if(n==0||n==1){
            return n;
        }
        int[]a=new int[n+1];
        a[0]=0;
        a[1]=1;
        for(int i=2;i<=n;++i){
            a[i]=a[i-1]+a[i-2];
        }
        return a[n];
    }
}

10.2爬楼梯

思路：又是一个经典问题，到一阶楼梯的方法等于到他的前一阶楼梯方法数加上前两阶方法数的和，根据前面状态推出后面状态即可，这里我采用的是从尾到头开始推

class Solution {
    public int climbStairs(int n) {
        if(n==1){
            return n;
        }
        int[]dp=new int[n+1];
        dp[n]=1;
        dp[n-1]=1;
        for(int i=n-2;i>=0;--i){
            dp[i]=dp[i+1]+dp[i+2];
        }
        return dp[0];
    }
}

10.3使用最小花费爬楼梯

思路：用前一个状态推出后一个状态，注意要跨过整个楼梯，所以最后一阶楼梯可以不踩

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[]dp=new int[cost.length+1];
        dp[0]=cost[0];
        dp[1]=cost[1];
        for(int i=2;i<=cost.length;++i){
            dp[i]=Math.min(dp[i-1],dp[i-2]);
            if(i<cost.length){
                dp[i]+=cost[i];
            }
        }
        return dp[cost.length];
    }
}

10.4不同路径

思路：二维数组计算到当前点的路径数，由于只能向右或向下，所以只需要加上左边和上边路径数就是到该点的路径数

class Solution {
    public int uniquePaths(int m, int n) {
        int[][]dp=new int[m][n];
        dp[0][0]=1;
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if(i>0){
                    dp[i][j]+=dp[i-1][j];
                }
                if(j>0){
                    dp[i][j]+=dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
}

10.5不同路径Ⅱ

思路：跟上题可以说是一模一样，代码都是直接超过去改的，不过有一个特例是地图只有障碍物，出生点都不能站

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if(obstacleGrid[0][0]==1){
            return 0;
        }
        int m=obstacleGrid.length;
        int n=obstacleGrid[0].length;
        int[][]dp=new int[m][n];
        dp[0][0]=1;
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if(obstacleGrid[i][j]==1){
                    continue;
                }
                if(i>0){
                    dp[i][j]+=dp[i-1][j];
                }
                if(j>0){
                    dp[i][j]+=dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
}

10.6整数拆分

思路：纯数学思维，乘3是最有性价比的，简单试了一下，没想到过了

class Solution {
    public int integerBreak(int n) {
        if(n==2){
            return 1;
        }
        if(n==3){
            return 2;
        }
        int cnt=1;
        while(n>=2){
            if(n==4){
                n-=4;
                cnt*=4;
            }else if(n>=3){
                n-=3;
                cnt*=3;
            }else{
                cnt*=n;
                break;
            }
        }
        return cnt;
    }
}

也可以用动态规划做，这里的dp[i]表示的是当n=i的最大乘积，每次拆分要做两次判断，是拆分两个数还是两个数以上

class Solution {
    public int integerBreak(int n) {
        if(n==2){
            return 1;
        }
        int[] dp=new int[n+1];
        dp[1]=1;
        dp[2]=1;
        for(int i=3;i<=n;++i){
            for(int j=1;j<i;++j){
                dp[i]=Math.max(dp[i],dp[i-j]*j);
                dp[i]=Math.max(dp[i],j*(i-j));
            }
        }
        return dp[n];
    }
}

10.7不同的二叉搜索树

思路：n个节点的树可以分成三部分，根节点、左右子树，确定好根节点后左右子树节点数也就确定了，排列组合相乘即可得到该根节点下的所有情况

class Solution {
    public int numTrees(int n) {
        if(n<=2){
            return n;
        }
        int[]dp=new int[n+1];
        dp[0]=1;
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;++i){
            for(int j=1;j<=i;++j){
                dp[i]+=(dp[i-j]*dp[j-1]);
            }
        }
        return dp[n];
    }
}

10.8 0-1背包问题

思路：用二维数组记录前m件物品用n个位置的最大价值

class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[][] value = new int[m][2];
        for(int i = 0; i < m; i++) {
            value[i][0] = sc.nextInt();
        }
        for(int i = 0; i < m; i++) {
            value[i][1] = sc.nextInt();
        }
        int[][] dp = new int[n+1][m];
        for(int i=value[0][0];i<=n;++i){
            dp[i][0]=value[0][1];
        }
        for(int i=1;i<m;++i){
            for (int j = 1; j <= n; ++j) {
                if(j>=value[i][0]) {
                    dp[j][i] = Math.max(dp[j-value[i][0]][i-1]+value[i][1],dp[j][i-1]);
                }else {
                    dp[j][i] = dp[j][i-1];
                }
            }
        }
        System.out.println(dp[n][m-1]);
    }
}

思路2：用一位数组记录使用i空间最大价值

class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[][] value = new int[m][2];
        for(int i = 0; i < m; i++) {
            value[i][0] = sc.nextInt();
        }
        for(int i = 0; i < m; i++) {
            value[i][1] = sc.nextInt();
        }
        int[]dp = new int[n+1];
        for(int i = 0; i < m; ++i) {
            for(int j=n;j>=value[i][0];--j){
                dp[j]=Math.max(dp[j],dp[j-value[i][0]]+value[i][1]);
            }
        }
        System.out.println(dp[n]);
    }
}

10.9分割等和子集

思路：分成两个子集那么子集的和肯定是原数组和的一半，dp数组记录索引数值是否能通过子元素相加得到

class Solution {
    public boolean canPartition(int[] nums) {
        int sum=0;
        for(int i=0;i<nums.length;++i){
            sum+=nums[i];
        }
        if(sum%2!=0){
            return false;
        }
        int len = sum/2;
        int[]dp=new int[len+1];
        dp[0]=1;
        for(int i=0;i<nums.length;++i){
            for(int j=len;j>=nums[i];--j){
                if(dp[j-nums[i]]==1){
                    dp[j]=1;
                }
            }
        }
        if(dp[len]==1){
            return true;
        }
        return false;
    }
}

10.10最后一块石头的重量Ⅱ

思路：跟上题差不多，dp数组表示索引重量是否可达，找到最接近重量总和一半的重量即可算出最后一块石头的重量

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum=0;
        for(int stone:stones){
            sum+=stone;
        }
        int avg = sum/2;
        int[]dp=new int[avg+1];
        dp[0]=1;
        for(int stone:stones){
            for(int i=avg;i>=stone;--i){
                if(dp[i-stone]==1){
                    dp[i]=1;
                }
            }
        }
        int i;
        for(i=avg;i>=0;--i){
            if(dp[i]==1){
                break;
            }
        }
        return sum-2*i;
    }
}

10.11目标和

思路：如果按照上面的思路就要同时兼顾加和减两种情况，可能会出现一个数被多次加减或同时加和减的情况，所以这里先数学推导一下，设加了减号的数字总和为x，那么sum-x-x=target，x=（sum-target）/2，这时候就只需要找到相加等于x的情况即可

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum=0;
        for(int num:nums){
            sum+=num;
        }
        if(sum<target||(sum-target)%2!=0){
            return 0;
        }
        int len=(sum-target)/2;
        int[]dp=new int [len+1];
        dp[0]=1;
        for(int num:nums){
            for(int i=len;i>=num;--i){
                dp[i]+=dp[i-num];
            }
        }
        return dp[len];
    }
}

10.12一和零

思路：还是动态规划01背包问题，dp二位数组记录最多m个0和n个1的最大字串数量

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][]dp=new int[m+1][n+1];
        for(String str:strs){
            int cnt0=0;
            for(char ch:str.toCharArray()){
                if(ch=='0'){
                    ++cnt0;
                }
            }
            int cnt1=str.length()-cnt0;
            for(int i=m;i>=cnt0;--i){
                for(int j=n;j>=cnt1;--j){
                    dp[i][j]=Math.max(dp[i][j],dp[i-cnt0][j-cnt1]+1);
                }
            }
        }
        return dp[m][n];
    }
}

10.13完全背包

思路：完全背包跟01背包基本一样，只是01背包每件物品只能有一个，而完全背包可以有无数个，这时候就不需要为了保证一件物品而倒序遍历，直接正向遍历就可以了

import java.util.*;


class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int v  = scanner.nextInt();
        int[] weights = new int[n];
        int[] values = new int[n];
        for(int i = 0; i < n; ++i){
            weights[i] = scanner.nextInt();
            values[i] = scanner.nextInt();
        }
        int []dp=new int [v+1];
        for(int i=0;i<n;++i){
            for(int j=weights[i];j<=v;++j){
                dp[j]=Math.max(dp[j],dp[j-weights[i]]+values[i]);
            }
        }
        System.out.println(dp[v]);
    }
}

10.14零钱兑换Ⅱ

思路：完全背包问题，跟上题思路基本一致，dp数组记录了金额到索引的组合数，然后不用再倒序遍历保证只加一遍

class Solution {
    public int change(int amount, int[] coins) {
        int[]dp=new int[amount+1];
        dp[0]=1;
        for(int coin:coins){
            for(int i=coin;i<=amount;++i){
                dp[i]+=dp[i-coin];
            }
        }
        return dp[amount];
    }
}

10.15组合总和Ⅳ

思路：还是完全背包问题，还是用dp数组记录达到索引的组合数，注意这里相同的数字不同顺序属于不同组合，{1,2,2}和{2,1,2}属于不同的组合，所以外层先遍历背包，内层遍历物品，这样就可以找到不同的组合顺序

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[]dp=new int [target+1];
        dp[0]=1;
        for(int i=0;i<=target;++i){
            for(int num:nums){
                if(i>=num){
                    dp[i]+=dp[i-num];
                }
            }
        }
        return dp[target];
    }
}

10.16爬楼梯Ⅱ

思路：这里还是使用完全背包解决爬楼梯的问题，dp数组记录到达索引位置的方法数，然后遍历找到到达索引的方法组合数

import java.util.*;

class Main {

    public static void main(String[] args) {
        int m,n;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        int[]dp = new int[n+1];
        dp[0]=1;
        for(int i=1;i<=n;++i){
            for(int j=Math.max(0,i-m);j<i;++j){
                dp[i]+=dp[j];
            }
        }
        System.out.println(dp[n]);
    }
}

10.17零钱兑换

思路：还是使用背包来解题，硬币数量不限，所以是完全背包，dp数组记录装索引容量空间所需最少的硬币，因为要求最少，所以一开始初始化就不能是0了，只有对于初始容量是0的才能0个硬币装满，其他就没什么特殊的了

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[]dp=new int[amount+1];
        for(int i=1;i<=amount;++i){
            dp[i]=Integer.MAX_VALUE;
        }
        for(int coin:coins){
            for(int i=coin;i<=amount;++i){
                if(dp[i-coin]!=Integer.MAX_VALUE){
                    dp[i]=Math.min(dp[i-coin]+1,dp[i]);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}

10.18完全平方数

思路：有了上题的铺垫，这题也很容易就能想出来，还是完全背包的问题，dp数组的含义就是平方和等于索引的个数，因为求最小，所以初始化还是不能等于0

class Solution {
    public int numSquares(int n) {
        int[]dp=new int[n+1];
        for(int i=1;i<=n;++i){
            int min=Integer.MAX_VALUE;
            for(int j=1;j*j<=i;++j){
                min=Math.min(1+dp[i-j*j],min);
            } 
            dp[i]=min;
        }
        return dp[n];
    }
}

10.19单词拆分

思路：还是可以使用背包来解题，这里单词使用次数不限制，所以可以用完全背包来解，dp数组的含义就是s从0到索引位置的字串是否能通过链表的字符串拼接得到

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int[]dp=new int[s.length()+1];
        dp[0]=1;
        for(int i=1;i<=s.length();++i){
            for(String word:wordDict){
                if(word.length()>i||dp[i-word.length()]==0){
                    continue;
                }
                if(s.substring(i-word.length(),i).equals(word)){
                    dp[i]=1;
                    break;
                }
            }
        }
        return dp[s.length()]==1?true:false;
    }
}

10.20多重背包

思路：跟01背包问题差不多，不过区别是物品可以有多件，其实把多件相同的物品看成是多件不同的物品就可以得到答案，虽然将多件相同的物品看作不同，但是在处理上遍历dp数组的时候可以作空间和件数相乘处理优化时间

import java.util.*;

/**
 * @author yinjunbiao
 * @version 1.0
 * @date 2024/2/1
 */
class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int c = scanner.nextInt();
        int n = scanner.nextInt();
        int[]w = new int[n];
        int[]v = new int[n];
        int[]k = new int[n];
        for (int i = 0; i < n; ++i) {
            w[i] = scanner.nextInt();
        }
        for (int i = 0; i < n; ++i) {
            v[i] = scanner.nextInt();
        }
        for (int i = 0; i < n; ++i) {
            k[i] = scanner.nextInt();
        }
        int[] dp = new int[c+1];
        for(int i=0;i<n;++i){
            for(int j=c;j>=w[i];--j){
                for(int l=1;l<=k[i]&&l*w[i]<=j;++l){
                    dp[j] = Math.max(dp[j],dp[j-l*w[i]]+l*v[i]);
                }
            }
        }
        System.out.println(dp[c]);
    }
}

10.21打家劫舍

思路：dp数组记录偷到索引位置最高金额，因为不能偷相邻的两间房屋，所以分为上一家偷不偷的情况，到状态方程为dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);

class Solution {
    public int rob(int[] nums) {
        if(nums.length==1){
            return nums[0];
        }
        int[]dp=new int[nums.length];
        dp[0]=nums[0];
        dp[1]=Math.max(nums[0],nums[1]);
        for(int i=2;i<nums.length;++i){
            dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[nums.length-1];
    }
}

10.22打家劫舍Ⅱ

思路：这题跟上题基本一直，唯一区别就是房屋围成了圈，如果偷了头就不能偷尾，偷了尾就不能偷头，所以这里我们分两种情况计算偷第一间和不偷第一间的情况

class Solution {
    public int rob(int[] nums) {
        if(nums.length==1){
            return nums[0];
        }
        int[][]dp=new int[nums.length][2];
        dp[0][0]=nums[0];
        dp[1][0]=nums[0];
        dp[0][1]=0;
        dp[1][1]=nums[1];
        for(int i=2;i<nums.length;++i){
            dp[i][0]=Math.max(dp[i-2][0]+nums[i],dp[i-1][0]);
            dp[i][1]=Math.max(dp[i-2][1]+nums[i],dp[i-1][1]);
        }
        return Math.max(dp[nums.length-2][0],dp[nums.length-1][1]);
    }
}

10.23打家劫舍Ⅲ

思路：跟上题相同的思路，但是从数组变成二叉树，相邻变成了父子节点，所以一个节点的最大价值等于该节点价值+孙子节点最大价值的和 跟 左右子节点最大价值和 的较大值，为了找到最大价值所以要从叶子节点开始向父节点走

class Solution {
    public int rob(TreeNode root) {
        robAction(root);
        return root.val;
    }

    public void robAction(TreeNode node){
        if(node==null){
            return;
        }
        robAction(node.left);
        robAction(node.right);
        int son=0;
        int grandSon = node.val;
        if(node.left!=null){
            son+=node.left.val;
            if(node.left.left!=null){
                grandSon+=node.left.left.val;
            }
            if(node.left.right!=null){
                grandSon+=node.left.right.val;
            }
        }
        if(node.right!=null){
            son+=node.right.val;
            if(node.right.left!=null){
                grandSon+=node.right.left.val;
            }
            if(node.right.right!=null){
                grandSon+=node.right.right.val;
            }
        }
        node.val=Math.max(son,grandSon);
    }
}

10.24买卖股票的最佳时机

思路：贪心，一次遍历数组记录索引前位置最小值，要在索引点卖出股票收益最大必在最小值处买入，然后找到卖出的最大值

class Solution {
    public int maxProfit(int[] prices) {
        int min=prices[0];
        int ans=0;
        for(int i=1;i<prices.length;++i){
            ans=Math.max(ans,prices[i]-min);
            min=Math.min(min,prices[i]);
        }
        return ans;
    }
}

思路2：动态规划，二位数组一行表示当前持有股票的最大收益，第二行表示当前不持有股票的最大收益

class Solution {
    public int maxProfit(int[] prices) {
        int[][]dp=new int[prices.length][2];
        dp[0][0]=-prices[0];
        for(int i=1;i<prices.length;++i){
            dp[i][0]=Math.max(dp[i-1][0],-prices[i]);
            dp[i][1]=Math.max(prices[i]+dp[i-1][0],dp[i-1][1]);
        }
        return dp[prices.length-1][1];
    }
}

10.25买卖股票的最佳时机Ⅱ

思路：在贪心算法 9.4已经有过贪心方法解题，这里再说一下动态规划。还是跟上题一样，一行表示当前持有股票的最大收益，一行表示当前不持有股票的最大收益

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[2][prices.length + 1];
        dp[0][0] = -prices[0];
        for (int i = 1; i < prices.length; ++i) {
            dp[0][i] = Math.max(dp[1][i - 1] - prices[i], dp[0][i - 1]);
            dp[1][i] = Math.max(dp[0][i - 1] + prices[i], dp[1][i - 1]);
        }
        return dp[1][prices.length - 1];
    }
}

10.26买卖股票的最佳时机Ⅲ

思路：跟上题一样，动态规划模拟当前持有或不持有股票，但是这里可以买卖两次，所以用4行模拟第一次持有，第一次卖，第二次持有，第二次卖即可

class Solution {
    public int maxProfit(int[] prices) {
        int[][]dp=new int[prices.length][4];
        dp[0][0]=-prices[0];
        dp[0][2]=-prices[0];
        for(int i=1;i<prices.length;++i){
            dp[i][0]=Math.max(dp[i-1][0],-prices[i]);
            dp[i][1]=Math.max(dp[i-1][1],prices[i]+dp[i-1][0]);
            dp[i][2]=Math.max(dp[i-1][2],dp[i][1]-prices[i]);
            dp[i][3]=Math.max(dp[i-1][3],prices[i]+dp[i][2]);
        }
        return dp[prices.length-1][3];
    }
}

10.27买卖股票的最佳时机Ⅳ

思路：跟上题一样，双数行dp数组记录当前不持有股票的最大值，其余行记录当前持有股票的最大值

class Solution {
    public int maxProfit(int k, int[] prices) {
        int[][]dp=new int[prices.length][2*k];
        for(int i=0;i<k;++i){
            dp[0][i*2]=-prices[0];
        }
        for(int i=1;i<prices.length;++i){
            for(int j=0;j<k;++j){
                dp[i][j*2]=Math.max(dp[i-1][j*2],dp[i][Math.max(0,j*2-1)]-prices[i]);
                dp[i][j*2+1]=Math.max(dp[i-1][j*2+1],dp[i][j*2]+prices[i]);
            }
        }
        return dp[prices.length-1][2*k-1];
    }
}

10.28买卖股票的最佳时机含冷冻期

思路：跟不含冷冻期一样的思路，dp数组一行记录持有股票最大价值，一行记录不持有股票最大价值，但是这里有冷冻期，在冷冻期不能购买股票，所以可以将不持有股票分为冷冻期和非冷冻期，记录三种情况的最大价值

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length==1){
            return 0;
        }
        int [][]dp=new int[prices.length][3];
        //0:持有 1：冷冻期 2：不持有且可买入
        dp[0][0]=-prices[0];
        for(int i=1;i<prices.length;++i){
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][2]-prices[i]);
            dp[i][1]=prices[i]+dp[i][0];
            dp[i][2]=Math.max(dp[i-1][2],dp[i-1][1]);
        }
        return Math.max(dp[prices.length-1][2],dp[prices.length-1][1]);
    }
}

10.29买卖股票的最佳时机含手续费

思路：跟不含手续费其实一样，只要在dp数组推导的时候要在卖出股票时扣去手续费即可

class Solution {
    public int maxProfit(int[] prices, int fee) {
        
        int[][]dp=new int[prices.length][2];
        dp[0][0]=-prices[0];
        for(int i=1;i<prices.length;++i){
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);
            dp[i][1]=Math.max(dp[i-1][1],dp[i][0]+prices[i]-fee);
        }
        return dp[prices.length-1][1];
    }
}

10.30最长递增子序列

思路：这题可以使用动态规划做出，首先确定dp数组的含义,dp数组表示索引前最大自增子序列长度，这时候状态方程也可以确定了，dp[i]=Math.max(max,dp[j]+1);明确这点之后就可以做题了

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[]dp=new int[nums.length];
        dp[0]=1;
        int max=1;
        int res=1;
        for(int i=1;i<nums.length;++i){
            for(int j=0;j<i;++j){
                if(nums[j]<nums[i]){
                    max=Math.max(max,dp[j]+1);
                }
            }
            dp[i]=max;
            res=Math.max(res,dp[i]);
            max=1;
        }
        return res;
    }
}

10.31最长连续递增序列

思路：贪心，记录当前当前索引结尾的最大连续递增序列长度，只要当前索引值比上一位置大就+1，否则清零，记录最大值即可

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int res=1;
        int cur=1;
        for(int i=1;i<nums.length;++i){
            if(nums[i]>nums[i-1]){
                res=Math.max(++cur,res);
            }else{
                cur=1;
            }
        }
        return res;
    }
}

10.32最长重复子数组

思路：这题如果用暴力解法只需要两层循环确定两个数组的起始位置，然后找到最长公共部分即可，但是这题也很适合用动态规划解决，首先确定dp数组的含义

dp[i][j]表示以num1[i]和num2[j]结尾的最大子数组长度是多少，这样就可以确定递推公式了。当num1[i]等于num2[j]时dp[i][j]=dp[i-1][j-1]+1，这里还要特殊初始化一下i和j等于0的特殊情况就可以了

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int[][]dp=new int[nums1.length][nums2.length];
        int res=0;
        for(int i=0;i<nums1.length;++i){
            if(nums1[i]==nums2[0]){
                dp[i][0]=1;
                res=1;
            }
        }
        for(int i=0;i<nums2.length;++i){
            if(nums2[i]==nums1[0]){
                dp[0][i]=1;
                res=1;
            }
        }
        for(int i=1;i<nums1.length;++i){
            for(int j=1;j<nums2.length;++j){
                if(nums1[i]==nums2[j]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                res=Math.max(res,dp[i][j]);
            }
        }
        return res;
    }
}

10.33最长公共子序列

思路：还是用动态规划去做，首先确定dp数组的含义，题目中的子序列不需要连续，所以dp[i][j]的含义就是text1从0到i和text2从0到j最长公共子序列，这时候就确定了递推公式，当字符相等时dp[i][j]=dp[i-1][j-1]+1;不相等时dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int[][]dp=new int [text1.length()+1][text2.length()+1];
        int res=0;
        for(int i=1;i<=text1.length();++i){
            for(int j=1;j<=text2.length();++j){
                if(text1.charAt(i-1)==text2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[text1.length()][text2.length()];
    }
}

10.34不相交的线

思路：还是动态规划，首先确定dp数组的含义，这里用二维dp数组表示nums1从0到i的子数组和nums2从0到j的子数组最多的不相交的线的数量，这时候的递推公式就能轻松推算出来了

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int[][]dp=new int[nums1.length+1][nums2.length+1];
        for(int i=1;i<=nums1.length;++i){
            for(int j=1;j<=nums2.length;++j){
                if(nums1[i-1]==nums2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[nums1.length][nums2.length];
    }
}

10.35最大子序和

思路：题目中要找到连续的子数组，并使子数组最大，首先想到的是滑动窗口，连续的数组很容易就想到了要用滑动窗口去维护，只要窗口内数字的和大于0就一直往后延申，找到最大和

class Solution {
    public int maxSubArray(int[] nums) {
        int fast=1;
        int slow=0;
        int ans=nums[0];
        int cur=nums[0];
        while(fast<nums.length){
            if(cur<0){
                slow=fast;
                cur=0;
            }
            cur+=nums[fast++];
            ans=Math.max(ans,cur);
        }
        return ans;
    }
}

思路2：贪心算法，其实这题贪心算法跟上题过程差不多，遍历数组，维护索引前一段子数组的和，如果子数组的和为负数则抛弃前面的子数组从当前索引开始算

class Solution {
    public int maxSubArray(int[] nums) {
        int ans=nums[0];
        int pre=nums[0];
        for(int i=1;i<nums.length;++i){
            pre=Math.max(pre,0)+nums[i];
            ans=Math.max(pre,ans);
        }
        return ans;
    }
}

思路3：动态规划，这题是动态规划的典型题目，首先确定dp数组的含义，dp数组代表从0到索引位置的子数组最大的连续子数组和，然后我们就可以确定递推公式了

class Solution {
    public int maxSubArray(int[] nums) {
        int[]dp=new int[nums.length];
        dp[0]=nums[0];
        int res=nums[0];
        for(int i=1;i<nums.length;++i){
            dp[i]=Math.max(dp[i-1],0)+nums[i];
            res=Math.max(res,dp[i]);
        }
        return res;
    }
}

10.36判断子序列

思路：两个指针分别遍历两个字符串，当t中所指字符跟s中字符相等时，s的指针后移，当s的指针遍历完s，代表t中存在字串s

class Solution {
    public boolean isSubsequence(String s, String t) {
        if(s.length()==0){
            return true;
        }
        int index=0;
        for(int i=0;i<t.length();++i){
            if(s.charAt(index)==t.charAt(i)){
                if(++index==s.length()){
                    return true;
                }
            }
        }
        return false;
    }
}

10.37不同的子序列

思路：这题还是可以使用动态规划，首先确定dp数组的含义，二维数组dp[i][j]表示以i-1结尾的s子序列中出现以j-1结尾的t序列的个数，也就可以确定了递推公式，当s的i等于t的j，dp[i][j]等于不包含s的i加上包含s的i的t的j-1的子序列之和，即dp[i-1][j-1]+dp[i-1][j]，如果不相等，那么dp[i][j]等于不包含s的i的t的j-1子序列之和，即dp[i-1][j]，确定之后这道题就简单了

class Solution {
    public int numDistinct(String s, String t) {
        int[][]dp=new int[s.length()+1][t.length()+1];
        for(int i=0;i<=s.length();++i){
            dp[i][0]=1;
            
        }
        for(int i=1;i<=s.length();++i){
            for(int j=1;j<=t.length();++j){
                if(s.charAt(i-1)==t.charAt(j-1)){
                    dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
                }else{
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        return dp[s.length()][t.length()];
    }
}

10.38两个字符串的删除操作

思路：还是动态规划，首先确定dp数组的含义，dp[i][j]表示以i结尾的word1和以j结尾的word2需要相同的最小步数。接下来就可以确定dp数组的递推公式，当word1的i等于word2的j，那么删除的最小步数就等于word的i-1和word2的j-1所需删除的最小步数，如果不相等，就等于word1的i和word2的j-1 与 word1的i-1和word2的j 所需最小步数的较小值加1，然后还需初始化边界值，保证步数正确

class Solution {
    public int minDistance(String word1, String word2) {
        int[][]dp=new int[word1.length()+1][word2.length()+1];
        for(int i=1;i<=word1.length();++i){
            dp[i][0]=i;
        }
        for(int j=1;j<=word2.length();++j){
            dp[0][j]=j;
        }
        for(int i=1;i<=word1.length();++i){
            for(int j=1;j<=word2.length();++j){
                if(word1.charAt(i-1) == word2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1];
                }else{
                    dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+1;
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }
}

10.39编辑距离

思路：这题跟上题基本一样，对一个字符串增加和删除等于对两个字符串删除，唯一不同的地方就是本题多了替换，可以替换的话在word1的i和word2的j不同时dp[i][j]可以等于dp[i-1][j-1]+1

class Solution {
    public int minDistance(String word1, String word2) {
        int[][]dp=new int [word1.length()+1][word2.length()+1];
        for(int i=1;i<=word1.length();++i){
            dp[i][0]=i;
        }
        for(int j=1;j<=word2.length();++j){
            dp[0][j]=j;
        }
        for(int i=1;i<=word1.length();++i){
            for(int j=1;j<=word2.length();++j){
                if(word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1];
                }else{
                    dp[i][j]=Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }
}

10.40回文字串

思路：这题还是可以用动态规划做出，首先确定dp数组的含义，一般来说题目要求什么dp数组的含义也就是什么，但是在这题，如果要dp数组表示以i结尾的回文字串，并不好推出下一个阶段的回文字串，如果要根据上一个阶段推出下一个阶段，就需要用到二维数组，dp[i][j]代表i到j的字串是否是回文字符串。

确定了dp数组的含义，接下来就需要确定递推公式，当要判断i到j的字符串是否为回文字符串，可以由i+1和j-1是否为回文字符串判断，如果是回文字符串，且i和j位置字符相等，那么就可以确定是回文字符串，如果不相等就不是回文，如果j-1小于等于1，且i和j位置字符相等，那么也是回文字符，可以把逻辑整理一下，分成i和j位置字符相不相同的情况处理

接下来还有一个地方需要注意的就是遍历的顺序，因为dp[i][j]需要根据dp[i+1][j-1]判断，后者在前者的左下角，所以需要从下到上，从左到右开始遍历

class Solution {
    public int countSubstrings(String s) {
        int[][]dp=new int[s.length()][s.length()];
        int cnt=0;
        dp[0][0]=1;
        for(int i=s.length()-1;i>=0;--i){
            for(int j=i;j<s.length();++j){
                if(s.charAt(i)==s.charAt(j)){
                    if(j-i<=1||dp[i+1][j-1]==1){
                        dp[i][j]=1;
                        ++cnt;
                    }
                }
            }
        }
        return cnt;
    }
}

10.41最长回文子序列

思路：跟上题思路差不多，但是二维dp数组表示从i到j字串中最大的字串长度，遍历的顺序也跟上题差不多，因为要根据dp[i+1][j-1]的状态推导出dp[i][j]的状态，所以还是要从下到上，从左到右

class Solution {
    public int longestPalindromeSubseq(String s) {
        int[][]dp=new int [s.length()+1][s.length()+1];
        for(int i=s.length()-1;i>=0;--i){
            dp[i][i]=1;
            for(int j=i+1;j<s.length();++j){
                if(s.charAt(i)==s.charAt(j)){
                    dp[i][j]=dp[i+1][j-1]+2;
                }else{
                    dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return dp[0][s.length()-1];
    }
}

11单调栈

11.1每日温度

思路：最简单的方法还是双重循环暴力，对于每个位置都往后遍历找到第一个比他大的元素

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] answer = new int[temperatures.length];
        for(int i=0;i<temperatures.length;++i){
            int j=i+1;
            while(j<temperatures.length&&temperatures[j]<=temperatures[i]){
                ++j;
            }
            if(j!=temperatures.length){
                answer[i]=j-i;
            }else{
                answer[i]=0;
            }
        }
        return answer;
    }
}

优化：上面暴力二重循环时间复杂度是O（n^2），有什么办法可以将时间复杂度压缩到O（n）呢，这里可以使用单调栈来解决这个问题，首先还是遍历数组，然后用一个栈把索引位置i前数字大于等于当前位置数字的索引记录下来，假设temperatures[i]>temperatures[j]，i就是j右边第一个比j大的数字的索引，如果temperatures[i]<=temperatures[j]，则将i入栈

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] answer = new int[temperatures.length];
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for(int i=1;i<temperatures.length;++i){
            while(stack.size()>0&&temperatures[i]>temperatures[stack.peek()]){
                answer[stack.peek()]=i-stack.peek();
                stack.pop();
            }
            stack.push(i);
        }
        return answer;
    }
}

其他

数组

有多少小于当前数字的数字

思路：最容易想到的还是双重暴力循环

class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int[] res = new int[nums.length];
        for(int i =0 ;i < nums.length;++i){
            int cnt = 0;
            for(int j=0;j<nums.length;++j){
                if(nums[i] > nums[j]){
                    ++cnt;
                }
            }
            res[i]=cnt;
        }
        return res;
    }
}

但是这里还是有点慢，怎么优化呢，这里要统计比数字小的有多少个数，很容易想到排序数组，然后用前缀和统计有多少个数，但是如果要用前缀和的化，怎么映射数字和数量是需要考虑的，最容易想到的就是用map映射，但是map进行前缀和相加的时候比较麻烦，观察到题目给出数字最大只有100，所以可以用长度为101的数组代替map

class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int[] cnt = new int[101];
        for(int i=0;i<nums.length;++i){
            ++cnt[nums[i]];
        }
        for(int i=1;i<cnt.length;++i){
            cnt[i]+=cnt[i-1];
        }
        int[] res = new int[nums.length];
        for(int i=0;i<res.length;++i){
            res[i]=nums[i] >0 ?cnt[nums[i]-1] : 0;
        }
        return res;
    }
}

有效的山脉数组

直接两次循环模拟

class Solution {
    public boolean validMountainArray(int[] arr) {
        if(arr.length<3){
            return false;
        }
        int i=1;
        while( i<arr.length && arr[i]>arr[i-1]){
            ++i;
        }
        if(i>arr.length-1 || i == 1){
            return false;
        }
        while( i<arr.length && arr[i] < arr[i-1]){
            ++i;
        }
        if(i==arr.length){
            return true;
        }
        return false;

    }
}

双指针法：一个从前往后，一个从后往前

class Solution {
    public boolean validMountainArray(int[] arr) {
        if(arr.length<3){
            return false;
        }
        int left = 1;
        int right = arr.length-2;
        while(left < arr.length && arr[left] > arr[left-1]){
            ++left;
        }
        while(right>=0 && arr[right] > arr[right+1]) {
            --right;
        }
        if (left == 1 || right == arr.length -2 || !(left>right)){
            return false;
        }
        return true;
    }
}

独一无二的出现次数

思路：用map记录每个数字出现的次数，然后把次数用set去重，比较map的key跟去重的个数是否相同，如果相同则每个数字的出现次数都是独一无二的

class Solution {
    public boolean uniqueOccurrences(int[] arr) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<arr.length;++i){
            map.put(arr[i], map.getOrDefault(arr[i],0)+1);
        }
        Set<Integer> set = new HashSet<>(map.values());
        return set.size()==map.keySet().size();
    }
}

移动零

思路：双指针，将0往后移

class Solution {
    public void moveZeroes(int[] nums) {
        if(nums.length<2){
            return ;
        }
        int left=0;
        int right=0;
        while(right<nums.length){
            while(right<nums.length&&nums[right]==0){
                ++right;
            }
            if(right<nums.length){
                int t=nums[left];
                nums[left++]=nums[right];
                nums[right++]=t;
            }
        }
    }
}

轮转数组

思路：用一个新数组存轮转后的

class Solution {
    public void rotate(int[] nums, int k) {
        int left = 0;
        int right = k;
        int[] array = new int[nums.length];
        for(int i=0;i<nums.length;++i){
            array[(i+k)%nums.length]=nums[i];
        }
        for(int i=0;i<nums.length;++i){
            nums[i]=array[i];
        }
    }
}

寻找数组的中心下标

思路：一次遍历先取总和，第二次遍历分别知道左右两边的和是多少

class Solution {
    public int pivotIndex(int[] nums) {
        int right = 0;
        for(int i=0;i<nums.length;++i){
            right+=nums[i];
        }
        int left=0;
        for(int i=0;i<nums.length;++i){
            right-=nums[i];
            if(left==right){
                return i;
            }
            left+=nums[i];
        }
        return -1;
    }
}

按奇偶排序数组 II

思路：把奇数和偶数分别存起来排序，然后赋值到数组中

class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        List<Integer> j = new ArrayList<>();
        List<Integer> o = new ArrayList<>();
        for(int i=0;i<nums.length;++i){
            if(nums[i]%2==1){
                j.add(nums[i]);
            }else{
                o.add(nums[i]);
            }
        }
        int index1 = 0;
        int index2=0;
        int i=0;
        while(i<nums.length){
            if(i%2==1){
                nums[i++]=j.get(index1++);
            }else{
                nums[i++]=o.get(index2++);
            }
        }
        return nums;
    }
}

思路二：双指针

class Solution {
    public int[] sortArrayByParityII(int[] nums) {
        int left =0;
        int right=1;
        while(right<nums.length){
            while(left<nums.length && nums[left]%2==0){
                left+=2;
            }
            while(right<nums.length && nums[right]%2==1){
                right+=2;
            }
            if(left>=nums.length || right>=nums.length){
                break;
            }
            int tem = nums[left];
            nums[left]=nums[right];
            nums[right]=tem;
        }
        return nums;
    }
}

搜索插入位置

思路：二分法

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        int mid = left + (right-left)/2;
        while(left<=right){
            mid = left + (right-left)/2;
            if(nums[mid]>target){
                right=mid-1;
            }else if(nums[mid]<target){
                left=mid+1;
            }else{
                return mid;
            }
        }
        return nums[mid]<target?mid+1:mid;
    }
}

链表

回文链表

思路：快慢指针找到中间节点，然后头插法翻转后半部分链表比较

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast!=null && fast.next != null){
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode virtual = new ListNode();
        while(slow.next!=null){
            ListNode tem = slow.next;
            slow.next = tem.next;
            tem.next = virtual.next;
            virtual.next=tem;
        }
        ListNode node = virtual.next;
        while(node!=null){
            if(node.val!=head.val){
                return false;
            }
            node=node.next;
            head=head.next;
        }
        return true;
    }
}

重排链表

思路：跟上题一样，先快慢指针找到中间节点，然后头插法反转，然后间隔插入

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if(head==null||head.next==null){
            return;
        }
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode virtual = new ListNode();
        while(slow.next!=null){
            ListNode tem = slow.next;
            slow.next=tem.next;
            tem.next=virtual.next;
            virtual.next=tem;
        }
        ListNode p = head;
        ListNode q = virtual.next;
        while(q!=null){
            ListNode t = q.next;
            q.next=p.next;
            p.next=q;
            p=q.next;
            q=t;
        }
    }
}

环形链表

思路：经典快慢指针

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }
}