排序

148. 排序链表

思想是归并排序

public ListNode sortList(ListNode head) {
        if (head == null || head.next == null )return head;
        ListNode fast = head.next, slow = head;
        
        // 利用快慢指针移动中点
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode tmp = slow.next;
        slow.next = null;
        // 分为两边临界值,切割链表
        ListNode left = sortList(head);
        ListNode right = sortList(tmp); // 相当于 m +1
        ListNode h = new ListNode(0);	// 临时存储链表
        ListNode res = h;
        while(left != null && right != null){
            if(left.val < right.val){
                h.next = left;
                left = left.next;
            }else{
                h.next = right;
                right = right.next;
            }
            h = h.next;
        }
        h.next = left != null ? left : right;
        return res.next;
    }

27. 移除元素

这道题看题目可知，他需要返回原数组，所以不需要构建新数组或者链表

public int removeElement(int[] nums, int val) {
        Arrays.sort(nums);
        int j = 0;
        for(int i : nums){
            // 如果相同的时候，则跳过该数字不进行拷贝覆盖
            if(i != val){
                nums[j] = i;
                j++;
            }
        }
        return j;
    }

75. 颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

其实就是快排，把模板放上去即可！！

public void sortColors(int[] nums) {
        sort(nums, 0, nums.length - 1);
    }
    public void sort(int[] nums, int l, int r){
        if (l >= r)return;
        int i = l - 1, j = r + 1, x = nums[l];
        while(i < j){
            do i++; while(nums[i] < x);
            do j--; while(nums[j] > x);
            if(i < j){
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }
        sort(nums, l, j);
        sort(nums, j + 1, r);
    }

215. 数组中的第K个最大元素

快排的另一种变形，快速选择。主要是利用排序后查找某个特定元素。

基本思路与「快速排序」一致，每次敲定一个基准值 x，根据当前与 x 的大小关系，将范围在 [l,r] 的 nums[i] 划分为到两边。

同时利用，利用题目只要求输出第 k 大的值，而不需要对数组进行整体排序，我们只需要根据划分两边后，第 k 大数会落在哪一边，来决定对哪边进行递归处理即可。

public int findKthLargest(int[] nums, int k) {
        // 数组长度 - k 等于 升序后第几个元素
        return sort(nums,0,nums.length - 1, nums.length - k );
    }
    public int sort(int nums[], int l , int r, int k){
        if(l >= r)return nums[k];

        int i = l - 1, j = r + 1, x = nums[l];
        while(i < j){
            do i++; while(nums[i] < x);
            do j--; while(nums[j] > x);
            if(i < j){
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }
        if(k <= j)return sort(nums, l , j , k);
        else return sort(nums,j + 1,r, k);
    }

4. 寻找两个正序数组的中位数

目前只会简单暴力法

如果数组长度为奇数，中位数就等于中间数，否则，等于中间两个数之和 / 2

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int []nums = new int[nums1.length + nums2.length];
        int i = 0;
        for(; i < nums1.length; i++){
            nums[i] = nums1[i];
        }
        for(int j : nums2){
            nums[i++] = j;
        }
        Arrays.sort(nums);
        return (nums[(nums.length - 1)/ 2] + nums[(nums.length / 2)]) / 2.0;
    }

链表

92. 反转链表 II

注意这里的索引是从 1 开始的。迭代的思路大概是：先用一个 for 循环找到第 m 个位置，然后再用一个 for 循环将 m 和 n 之间的元素反转。

public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(0, head);
        ListNode p = dummy;
        for(int i = 0; i < left - 1; i++)
            p = p.next; // 反转节点前一个
        ListNode pre = null;
        ListNode cur = p.next;
        for(int i = 0; i < right - left + 1; i++){ // 反转所有节点
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        p.next.next = cur;	// 指向反转列表后面的第一个节点
        p.next = pre;		// 指向反转后的第一个节点
        return dummy.next;
    }

160. 相交链表

设「第一个公共节点」为 node ，「链表 headA」的节点数量为 a ，「链表 headB」的节点数量为 b ，「两链表的公共尾部」的节点数量为 c ，则有：

头节点 headA 到 node 前，共有 a−c 个节点；

头节点 headB 到 node 前，共有 b−c 个节点；

考虑构建两个节点指针 A , B 分别指向两链表头节点 headA , headB ，做如下操作：

指针 A 先遍历完链表 headA ，再开始遍历链表 headB ，当走到 node 时，共走步数为：a+(b−c)

指针 B 先遍历完链表 headB ，再开始遍历链表 headA ，当走到 node 时，共走步数为：b+(a−c)

如下式所示，此时指针 A , B 重合，并有两种情况：

a+(b−c)=b+(a−c)

若两链表有公共尾部 (即 c>0 ) ：指针 A , B 同时指向 [第一个公共节点] node 。

若两链表无公共尾部 (即 c=0 ) ：指针 A , B 同时指向 null 。

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

141. 环形链表

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(slow == fast) // 如果快慢指针都相等说明有环
                return true; 
            
        }
        return false;
    }

328. 奇偶链表

分成快慢指针，一个指着偶数，一个奇数，快的为奇数。

遍历：

慢指针的下一个指向快指针的下一个（即使偶数）

快指针的下一个指向满指针的下一个（即使奇数）

最后把两个链表拼接起来

public ListNode oddEvenList(ListNode head) {
        if(head == null)return null;
        ListNode fast = head.next;
        ListNode slow = head;
        ListNode dummyFast = fast;

        while(fast != null && fast.next != null){
            slow.next = fast.next;
            slow = slow.next;
            fast.next = slow.next;
            fast = fast.next;
        }
        slow.next = dummyFast;
        return head;
    }

队列

225. 用队列实现栈

private LinkedList<Integer> list = null;
    public MyStack() {
        list = new LinkedList<>();
    }
    
    public void push(int x) {
        list.addLast(x);
    }
    
    public int pop() {
        if(empty()){
            return -1;
        }else{
            return list.remove(list.size() - 1);
        }

    }
    
    public int top() {
        return list.get(list.size() - 1);
    }
    
    public boolean empty() {
        return list.size() == 0;
    }

54. 螺旋矩阵

空值处理：当 matrix 为空时，直接返回空列表 [] 即可。

初始化：矩阵左、右、上、下四个边界 l , r , t , b ，用于打印的结果列表 res 。

循环打印： “从左向右、从上向下、从右向左、从下向上” 四个方向循环打印。

根据边界打印，即将元素按顺序添加至列表 res 尾部。

边界向内收缩 1 （代表已被打印）。

判断边界是否相遇（是否打印完毕），若打印完毕则跳出。

返回值：返回 res 即可。

public List<Integer> spiralOrder(int[][] matrix) {
        if(matrix.length == 0)return new ArrayList<Integer>();
        // 每一个边界
        int l = 0, r = matrix[0].length - 1, t =0 , b = matrix.length - 1, x =0;
        Integer[] res = new Integer[(r +1) * (b + 1)];
        while(true){
            for(int i = l; i <= r; i++)res[x++] = matrix[t][i];
            if(++t > b)break;
            for(int i = t; i <= b; i++)res[x++] = matrix[i][r];
            if(--r < l)break;
            for(int i = r; i >= l; i--)res[x++] = matrix[b][i];
            if(--b < t)break;
            for(int i = b; i >= t; i--)res[x++] = matrix[i][l];
            if(++l > r)break; 
        }
        return Arrays.asList(res);
    }

栈

当调用 push 让元素入队时，只要把元素压入 s1 即可，时间复杂度 O(1)：

使用 peek 或 pop 操作队头的元素时，若 s2 为空，可以把 s1 的所有元素取出再添加进 s2，这时候 **s2** 中元素就是先进先出顺序了，不过这样移动所有元素的复杂度是 O(n)：

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

155. 最小栈

每个元素入栈时，还要记下来当前栈中的最小值。

class MinStack {
    Stack<Integer> stack;
    Stack<Integer> minStack;
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
        if(minStack.isEmpty() || val <= minStack.peek()){
            minStack.push(val);
        }
    }
    
    public void pop() {
        if(stack.pop().equals(minStack.peek())){
            minStack.pop();
        }
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

150. 逆波兰表达式求值

利用栈存储数字，判断如果是符号，则取栈中元素出来计算。

但要判断第二个取出来元素是/ - 于第一个元素的

public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for(String token: tokens){
            if("+-*/".contains(token)){  // 判断符号
                int a = stack.pop(),b = stack.pop();
                switch(token){
                    case "+":
                    stack.push(a + b);
                    break;
                    case "-":
                    stack.push(b - a);
                    break;
                    case "*":
                    stack.push(a *b);
                    break;
                    case "/":
                    stack.push(b / a);
                    break;
                }
            }else{
                stack.push(Integer.valueOf(token));
            }
        }
        return stack.pop();
    }

20. 有效的括号

和上一题差不多思路，**每个右括号 **)** 的左边必须有一个左括号 **(** 和它匹配**。

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(char c : s.toCharArray()){
            if(c == '(' || c == '[' || c=='{')stack.push(c);
            else{
                if(!stack.isEmpty() && stack.peek() == left(c)){
                    stack.pop();
                }else{
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
    public char left(char c){
        if(c ==')')return '(';
        else if(c == ']')return '[';
        return '{';
    }
}

1472. 设计浏览器历史记录

双栈实现，通过一个新栈存储返回历史记录数据

class BrowserHistory {
    Stack<String> stack1 = new Stack<>();
    Stack<String> stack2 = new Stack<>();
    public BrowserHistory(String homepage) {
        stack1.push(homepage);
    }
    
    public void visit(String url) {
        stack1.push(url);
        stack2.clear();
    }
    
    public String back(int steps) {
       while(steps-- > 0 && stack1.size() > 1){
        stack2.push(stack1.pop());
       }
       return stack1.peek();
    }
    
    public String forward(int steps) {
        while(steps-- > 0 && stack2.size() > 0){
            stack1.push(stack2.pop());
        }
        return stack1.peek();
    }
}

1209. 删除字符串中的所有相邻重复项 II

迭代字符串：

- 如果当前字符与前一个相同，栈顶元素加 1。
- 否则，往栈中压入 1。
    * 如果栈顶元素等于 k，则从字符串中删除这 k 个字符，并将 k 从栈顶移除。

class Solution {
    public String removeDuplicates(String s, int k) {
        StringBuilder sb = new StringBuilder(s);
        Stack<Integer> stack = new Stack<>();
        for(int i =0; i < sb.length(); i++){
            if(i == 0 || sb.charAt(i) != sb.charAt(i - 1)){
                stack.push(1);
            }else{
                int inc = stack.pop() + 1;
                if(inc == k){
                    sb.delete(i - k + 1, i + 1);
                    i = i - k;
                }else{
                    stack.push(inc); 
            }
        }    
        return sb.toString();
    }
}

1249. 移除无效的括号

用一个ok数组记录无效括号的位置

遍历字符串

如果是( 则进入数组并且标记为无效，因为只有一个括号而已

如果是）判断栈是否为空，

是的话则说明它是无效数组

不是的话，则找到他前一个括号的位置，标记为有效数组

然后利用StringBuilder存储数据

class Solution {
    public String minRemoveToMakeValid(String s) {
        Stack<Integer> stack = new Stack<>();
        boolean[] ok = new boolean[s.length()];
        StringBuilder res = new StringBuilder();
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(c == '('){
                stack.push(i);
                ok[i] = true;
            }
            if(c == ')'){
                if(stack.isEmpty()){
                    ok[i] = true;
                }else{
                    ok[stack.pop()] = false;
                }
            }
        }
        for(int i = 0; i < s.length(); i++){
            if(!ok[i]){
                res.append(s.charAt(i));
            }
        }
        return res.toString();
    }
}

735. 小行星碰撞

遍历数组

设置boolean ok判断是否成功

当ok，栈不为空，并且栈顶 > 0 数组小于0

如果栈顶元素 >= 数组元素，就说明数组元素的行星被撞碎了;退出循环

如果栈顶元素 <= 数组元素，栈顶元素的行星被撞碎了

如果还是ok 则把行星添加进去

class Solution {
    public int[] asteroidCollision(int[] ast) {
        Stack<Integer> stack = new Stack<>();
        for(int i : ast){
            boolean ok = true;
            while(ok && !stack.isEmpty() && stack.peek() > 0 && i < 0){
                if(stack.peek() + i >= 0)ok = false;
                if(stack.peek() + i <= 0)stack.pop();
            }
            if(ok)stack.push(i);
        }
        int size = stack.size();
        int[] res = new int[size];
        while(!stack.isEmpty())res[--size] = stack.pop();
        return res;
    }
}

哈希

1. 两数之和

遍历数组，如果map中存在target - nums[i] 就说明

target - nums[i] 和 nums[i] 是我们要找的数。

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

128. 最长连续序列

1.将数组放进set中，去重

2.遍历set

如果set包含n - 1，说明他不是起点，continue

如果不包含，说明他是起点，循环找出最长序列

class Solution {
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for(int n : nums){
            set.add(n);
        }
        int res = 0;
        for(int n : set){
            if(!set.contains(n - 1)){
                int num = n;
                int len = 1;
                while(set.contains(num + 1)){
                    num += 1;
                    len += 1;
                }
                res = Math.max(res, len);
            }
        }
        return res;
    }
}

146. LRU 缓存

每次获取时，判断是否存在该元素，需要将数据重新放置最后的位置，标记最近使用

每次添加元素，需考虑是不是原有数据，是的话删除，重新放置

考虑容量，删除最旧最未使用

class LRUCache {
    LinkedHashMap<Integer,Integer> map = new LinkedHashMap<>();
    int cap;
    public LRUCache(int capacity) {
        this.cap = capacity;
    }
    
    public int get(int key) {
        if(!map.containsKey(key))return -1;
        int val = map.get(key);
        map.remove(key);
        map.put(key,val);
        return map.get(key);
    }
    
    public void put(int key, int value) {
        if(map.containsKey(key)){
            map.remove(key);
            map.put(key, value);
            return;
        }        
        if(map.size() >= cap){
            int old = map.keySet().iterator().next();
            map.remove(old);
        }
        map.put(key,value);
    }
}

73. 矩阵置零

先遍历一次，找到等于0的位置

在遍历一次，把含有0的位置的行列全置0

class Solution {
    public void setZeroes(int[][] matrix) {
       HashSet<Integer> set1 = new HashSet<>();
       HashSet<Integer> set2 = new HashSet<>();

       int m = matrix.length;
       int n = matrix[0].length;

       for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            if(matrix[i][j] == 0){
                set1.add(i);
                set2.add(j);
            }
        }
       }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(set1.contains(i) || set2.contains(j)){
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

380. O(1) 时间插入、删除和获取随机元素

insert 操作：使用哈希表判断 val 是否存在，存在的话返回 false，否则将其添加到 nums，更新 idx，同时更新哈希表；
remove 操作：使用哈希表判断 val 是否存在，不存在的话返回 false，否则从哈希表中将 val 删除，同时取出其所在 nums 的下标 loc，然后将 nums[idx] 赋值到 loc 位置，并更新 idx（含义为将原本处于 loc 位置的元素删除），同时更新原本位于 idx 位置的数在哈希表中的值为 loc（若 loc 与 idx 相等，说明删除的是最后一个元素，这一步可跳过）；
getRandom 操作：由于我们人为确保了 [0,idx] 均为存活值，因此直接在 [0,idx+1) 范围内进行随机即可。

class RandomizedSet {
    int[] nums = new int[200010];
    HashMap<Integer, Integer> map;
    static int idx = -1;
    Random random = new Random();
    public RandomizedSet() {
        map = new HashMap<>();    
    }
    
    public boolean insert(int val) {
        if(!map.containsKey(val)){
            map.put(val, ++idx);
            nums[idx] = val;
            return true;
        }
        return false;
    }
    
    public boolean remove(int val) {
        if(map.containsKey(val)){
            int loc= map.remove(val);
            if(loc != idx)map.put(nums[idx], loc);  // 不是最后的位置
            nums[loc] = nums[idx--];
            return true;
        }    
        return false;
    }
    
    public int getRandom() {
        return nums[random.nextInt(idx +1)];
    }
}

350. 两个数组的交集 II

1.首先判断最大数组，重新进入函数，减少哈希空间

2.遍历最大数组，计算每个元素的count值

3.遍历小数组，发现是否出现相同元素

如果count >0 则存在相同，count - 1，添加元素进入临时输入

如果还大于1，修改count值

不是的话，删除该元素

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if(nums1.length < nums2.length){
            intersect(nums2, nums1);
        }
        Map<Integer, Integer> map = new HashMap<>();
        for(int num : nums1){
            int count = map.getOrDefault(num, 0) + 1;
            map.put(num, count);
        }
        int[] innums = new int[nums1.length];
        int idx = 0;
        for(int num : nums2){
            int count = map.getOrDefault(num, 0);
            if(count > 0 ){
                 count--;
                innums[idx++] = num;
                if(count > 0){
                    map.put(num, count);
                }else{
                    map.remove(num);
                }
            }
           
        }
        return Arrays.copyOfRange(innums, 0 , idx);
    }
}

49. 字母异位词分组

map的value存的是对应单词的所有类型

遍历strs，对每个单词进行排序获得最简单的单词，找到存在map里的链表，如果没有则创建新的链表，然后把原来的strs存入链表

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, ArrayList<String>> map = new HashMap<>();
        for(String s : strs){
            char[] c = s.toCharArray();
            Arrays.sort(c);
            String t = String.valueOf(c);
            map.putIfAbsent(t,new ArrayList<>());
            map.get(t).add(s);
        }
        return new ArrayList<>(map.values());
    }
}

二分

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

先遍历左边界，并且判断是否和target一致，不一致则返回-1

再遍历左边界。

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

33. 搜索旋转排序数组

设 x=nums[mid] 是我们现在二分取到的数。

现在需要判断 x 和 target 的位置关系，谁在左边，谁在右边？

核心思路

如果 x 和 target 在不同的递增段：

如果 target 在第一段（左），x 在第二段（右），说明 x 在 target 右边；

如果 target 在第二段（右），x 在第一段（左），说明 x 在 target 左边。

如果 x 和 target 在相同的递增段：比较 x 和 target 的大小即可。

下面只讨论 x 在 target 右边，或者等于 target 的情况。其余情况 x 一定在 target 左边。

如果 x>nums[n−1]，说明 x 在第一段中，那么 target 也必须在第一段中（否则 x 一定在 target 左边）且 x 必须大于等于 target。

写成代码就是 _target > nums[n - 1] && x >= target_。

如果 x≤nums[n−1]，说明 x 在第二段中（或者 nums 只有一段），那么 target 可以在第一段，也可以在第二段。

如果 target 在第一段，那么 x 一定在 target 右边。

如果 target 在第二段，那么 x 必须大于等于 target。

写成代码就是 _target > nums[n - 1] || x >= target_。

根据这两种情况，去判断 x 和 target 的位置关系，从而不断地缩小 target 所在位置的范围，二分找到 target。

细节

二分的范围可以是 [0,n−2]。

这是因为，如果 target 在数组中的位置是 n−1，那么上面分类讨论中的代码，计算结果均为 false。这意味着每次二分更新的都是 left，那么最终答案自然就是 n−1。

35. 搜索插入位置

普通二分查找

class Solution {
    public int searchInsert(int[] nums, int target) {
        if (nums.length == 0 || nums[0] >= target)return 0;
        if(nums[nums.length - 1] < target)return nums.length;

        int l = 0,  r = nums.length -1;
        while(l < r){
            int m = (l + r) / 2;
            if(nums[m] < target){
                l = m + 1;
            }else{
                r = m;
            }
        }
        return l;
    }
}

240. 搜索二维矩阵 II

也是二分查找，只是条件不一样了

从矩阵的左下角开始查找，

如果大于target，则行数-1；
如果小于target，则列数+1；直到遍历结束

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int i  = matrix.length  -1, j = 0;
        while(i >= 0 && j < matrix[0].length){
            if(matrix[i][j] >target)i--;
            else if(matrix[i][j] < target)j++;
            else return true;
        }
        return false;
    }
}

287. 寻找重复数

nums	1	2	3	4
cnt	1	3	4	5

从上面数组分析，m = 2，经历遍历后 count = 3,

coumt > 3，说明重复数在左边，

反之重复数在右边。

class Solution {
    public int findDuplicate(int[] nums) {
        int l = 0, r = nums.length -1;
        while(l < r){
            int m = (l + r)/ 2;
            int count = 0;
            for(int num: nums){
                if(num <= m)
                    count++;
            }
            if(count > m)r = m;
            else l = m + 1;
        }
        return l;
    }
}

300. 最长递增子序列

当 nums[i]>nums[j] 时： nums[i] 可以接在 nums[j] 之后（此题要求严格递增），此情况下最长上升子序列长度为 dp[j]+1 ；

当 nums[i]<=nums[j] 时： nums[i] 无法接在nums[j]之后，此情况上升子序列不成立，跳过。

上述所有 1. 情况下计算出的 dp[j]+1 的最大值，为直到 i 的最长上升子序列长度（即 dp[i] ）。实现方式为遍历 j 时，每轮执行 dp[i]=max(dp[i],dp[j]+1)。

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

双指针

11. 盛最多水的容器

先计算容量长度length
然后判断哪边矮一点，然后利用矮的作用存储容量

最后移动矮的指针

class Solution {
    public int maxArea(int[] height) {
        int l =0, r = height.length -1;
        int res = 0;
        while(l < r){
            int length = r - l;
            int max = Math.min(height[l], height[r]);
            res = Math.max(res, max * length );
            if(height[l] > height[r])r--;
            else l++;
        }
        return res;
    }
}

15. 三数之和

这道题其实就算3个数之和为0，边界条件多一点而已，

首先如果num[0] > 0 , 说明后面的数都是> 0的，或者数组长度 < 3直接返回。

然后开始遍历数组，设置头尾指针开始遍历，

如果找到了一个符合条件，存入链表，还要查找是否存在指针的数据，迭代到下个不存在的元素。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        if(nums[0] > 0 || nums.length < 3)return res;
        for(int i = 0; i < nums.length; i ++){
            if(i > 0 && nums[i] == nums[i - 1])continue;

            int j = i + 1, k = nums.length -1;
            while(j < k){
                if(nums[j] + nums[i] + nums[k] == 0){
                    res.add(Arrays.asList(nums[i], nums[j],nums[k]));
                    while(j < k && nums[j] == nums[j + 1])j++;
                    while(j < k && nums[k] == nums[k - 1])k--;
                    j++; k--;
                }else if(nums[j] + nums[i] + nums[k] < 0) j++;
                else k--;
            }
        }
        return res;
    }
}

19. 删除链表的倒数第 N 个结点

先遍历n个元素，使得cur2移动n次

然后再次遍历，让cur1和cur2一起移动

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode p = new ListNode(0,head);
        ListNode cur1 = p;
        ListNode cur2 = p;
        while(n != 0){
            cur2 = cur2.next;
            n--;
        }
        while(cur2.next != null){
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        cur1.next = cur1.next.next;
        return p.next;
    }
}

31. 下一个排列

首先从后面遍历，直至前一个小于后一个元素，说明此处是转换位置记为i

然后又重新从后面遍历，与nums[i]进行比较，如果存在小于元素，说明是该元素与i互换位置，换转位置后，i位置后的元素需重新排序

class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while(i >= 0 && nums[i] >= nums[i + 1]){
            i--;
        }
        if(i >= 0){
            int j = nums.length - 1;
            while(j >= 0 && nums[i] >= nums[j]){
                j--;
            }
            swap(nums, i , j);
        }
        reverse(nums, i + 1);
    }
    public void swap(int nums[], int i , int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public void reverse(int[] nums, int i){
        int left = i, right = nums.length - 1;
        while(left < right){
            swap(nums, left, right);
            left++;right--;
        }
    }
}

75. 颜色分类
快排

class Solution {
    public void sortColors(int[] nums) {
        sort(nums, 0 , nums.length - 1);
    }
    public void sort(int[]nums, int l , int r){
        if(l >= r)return;
        int i = l - 1,j = r + 1,x = nums[l];
        while(i < j){
            do i++; while(nums[i] < x);
            do j--; while(nums[j] > x);
            if(i < j) swap(nums, i , j);
        }
        sort(nums, l, j);
        sort(nums, j + 1, r);
    }
    public void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

141. 环形链表

使用快慢指针即可，注意循环条件

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

142. 环形链表 II

首先找到环开始的地方，然后让slow重新开始和fast一起遍历，如果重叠说明是环结束的地方

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

148. 排序链表

分割 cut 环节： 找到当前链表 中点，并从 中点 将链表断开（以便在下次递归 cut 时，链表片段拥有正确边界）；
- 我们使用 fast,slow 快慢双指针法，奇数个节点找到中点，偶数个节点找到中心左边的节点。
- 找到中点 slow 后，执行 slow.next = None 将链表切断。
- 归分割时，输入当前链表左端点 head 和中心节点 slow 的下一个节点 tmp(因为链表是从 slow 切断的)。
- cut 递归终止条件： 当 head.next == None 时，说明只有一个节点了，直接返回此节点。
合并 merge 环节： 将两个排序链表合并，转化为一个排序链表。
- 双指针法合并，建立辅助 ListNode h 作为头部
- 设置两指针 left, right 分别指向两链表头部，比较两指针处节点值大小，由小到大加入合并链表头部，指针交替前进，直至添加完两个链表。
- 返回辅助ListNode h 作为头部的下个节点 h.next。
- 时间复杂度 O(l + r)，l, r 分别代表两个链表长度。
当题目输入的 head == None 时，直接返回 None。

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)return head;
        ListNode fast = head.next, slow = head;
        if(fast != null && fast.next !=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode tmp = slow.next;
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(tmp);
        ListNode h = new ListNode(0);
        ListNode res = h;
        while(left != null && right != null){
            if(left.val < right.val){
                h.next = left;
                left = left.next;
            }else{
                h.next = right;
                right = right.next;
            }
            h = h.next;
        }
        h.next = left != null ? left : right;
        return res.next;
    }
}

160. 相交链表

遍历两个链表，如果为空说明到底了，从对面链表开始。

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

234. 回文链表

这道题关键是判断这个链表是奇数还是偶数，
因此首先遍历链表找到中位数，然后反转后面的链表即可。

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

        ListNode l = head;
        ListNode r = reverse(slow);

        while(r != null){
            if(r.val != l.val)return false;
            r = r.next;
            l = l.next;
        }
        return true;
    }
    public ListNode reverse(ListNode head){
        ListNode pre = null, cur = head;
        while(cur != null){
            ListNode tmp = cur.next;
            cur.next =  pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}

283. 移动零

双指针遍历，先遍历有数据的，再遍历0

class Solution {
    public void moveZeroes(int[] nums) {
        int j =0;
        for(int i =0 ; i < nums.length; i++){
            if(nums[i] != 0){
                nums[j++] = nums[i];
            }
        }
        for(; j < nums.length; j++){
            nums[j] = 0;
        }
    }
}

287. 寻找重复数

这题思路是二分查找

设置一个cnt，找到nums中小于等于mid 的元素，如果cnt > mid 说明，cnt里面存在重复元素，否则的话说明在另外一个区间里面。

class Solution {
    public int findDuplicate(int[] nums) {
        int l = 1, r = nums.length - 1;
        while(l < r){
            int m = (l + r )/ 2;
            int cnt = 0;
             // nums 中小于等于 mid 的元素的个数
            for(int num: nums){
                if(num <= m)cnt++;
            }
            if(cnt > m)r = m;
            else l = m + 1;
        }
        return l;
    }
}

581. 最短无序连续子数组

设置最大值max，最小值min，左边界l，右边界r

首先从头开始遍历，找到非单调递增区域，

如果存在nums[i] < max ，则可以认为i当前存在于非单调递增区域。所以存起来一直遍历，刷新r的位置。

同理可得：

l为非单调递增区域的最前位置。

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int max = nums[0];
        int min = nums[n - 1];
        int l = 0, r = -1;
        for(int i =0; i < n; i++){
            if(nums[i] < max){
                r = i;
            }else{
                max = nums[i];
            }
        }
        for(int i = n - 1; i >= 0; i--){
            if(nums[i] > min){
                l = i;
            }else{
                min = nums[i];
            }
        }
        return r -l + 1;
    }
}

动态规划

动态规划是一种“从底至顶”的方法：从最小子问题的解开始，迭代地构建更大子问题的解，直至得到原问题的解。

由于动态规划不包含回溯过程，因此只需使用循环迭代实现，无须使用递归。与回溯算法一样，动态规划也使用“状态”概念来表示问题求解的特定阶段，每个状态都对应一个子问题以及相应的局部最优解。例如，爬楼梯问题的状态定义为当前所在楼梯阶数 i 。

根据以上内容，我们可以总结出动态规划的常用术语。

将数组 dp 称为 dp 表，dp[i] 表示状态 i 对应子问题的解。
将最小子问题对应的状态（第 1 阶和第 2 阶楼梯）称为初始状态。
将递推公式 dp[i]=dp[i−1]+dp[i−2] 称为状态转移方程。

746. 使用最小花费爬楼梯

设 dp[i] 为爬到第 i 阶累计付出的代价，由于第 i 阶只可能从 i−1 阶或 i−2 阶走来，因此 dp[i] 只可能等于 dp[i−1]+cost[i] 或 dp[i−2]+cost[i] 。为了尽可能减少代价，我们应该选择两者中较小的那一个：

dp[i]=min(dp[i−1],dp[i−2])+cost[i]

这便可以引出最优子结构的含义：原问题的最优解是从子问题的最优解构建得来的。

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length - 1;
        int[] dp = new int[n + 1];
        dp[1] = cost[1]; dp[0] = cost[0];
        for(int i = 2; i <= n; i++){
            // 找到最优解
            dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
        }
        return Math.min(dp[n], dp[n - 1]);
    }
}

64. 最小路径和

每一次都会让棋子让右或者往下走一步，设当前格子为[i , j]，则往下或往右则变为[i + 1,j]或者[i , j + 1]
因此需要利用两个属性存储数据。

然后找出最优解，对于状态 [i,j] ，它只能从上边格子 [i−1,j] 和左边格子 [i,j−1] 转移而来。因此最优子结构为：到达 [i,j] 的最小路径和由 [i,j−1] 的最小路径和与 [i−1,j] 的最小路径和中较小的那一个决定。

根据以上分析，可推出图 14-12 所示的状态转移方程：

dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];

确定边界条件和状态转移顺序

在本题中，处在首行的状态只能从其左边的状态得来，处在首列的状态只能从其上边的状态得来，因此首行 i=0 和首列 j=0 是边界条件。

如图 14-13 所示，由于每个格子是由其左方格子和上方格子转移而来，因此我们使用循环来遍历矩阵，外循环遍历各行，内循环遍历各列。

class Solution {
    public int minPathSum(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int[][] dp = new int[n][m];
        dp[0][0] = grid[0][0];
        for(int i = 1; i < m; i++){
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }
        for(int j = 1; j < n; j++){
            dp[j][0] = dp[j - 1][0] + grid[j][0];
        }

        for(int i = 1; i < n; i++){
            for(int j = 1; j < m; j++){
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[n - 1][m - 1];
    }
}

0-1背包

由图所得，物品i对应的重量wgt[i]和价值val[i],每一个物品只能放一次。

/* 0-1 背包：动态规划 */
int knapsackDP(int[] wgt, int[] val, int cap) {
    int n = wgt.length - 1;
    int[][] dp = new int[n + 1][cap + 1];

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= cap; j++){
            if(wgt[i] > j){
                // 超重
                dp[i][j] = dp[i][j - 1];
            }else{
                // 不选物品和选物品进行比较
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - wgt[i - 1] + val[i - 1]);
            }
        }
    }
    return dp[n][cap];
}

完全背包

和0-1背包不同的是，它的物品可以放多次，在完全背包问题的规定下，状态 [i,c] 的变化分为两种情况。

不放入物品 ****i ：与 0-1 背包问题相同，转移至 [i−1,c] 。
放入物品 ****i ：与 0-1 背包问题不同，转移至 [i,c−wgt[i−1]] 。

从而状态转移方程变为：

dp[i,c]=max(dp[i−1,c],dp[i,c−wgt[i−1]]+val[i−1])

/* 完全背包：动态规划 */
int unboundedKnapsackDP(int[] wgt, int[] val, int cap) {
    int n = wgt.length;
    // 初始化 dp 表
    int[][] dp = new int[n + 1][cap + 1];
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                // 若超过背包容量，则不选物品 i
                dp[i][c] = dp[i - 1][c];
            } else {
                // 不选和选物品 i 这两种方案的较大值
                dp[i][c] = Math.max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]);
            }
        }
    }
    return dp[n][cap];
}

322. 零钱兑换

看作完全背包的另一种思路，但求得是最小值

dp[i,a]=min(dp[i−1,a],dp[i,a−coins[i−1]]+1)

/* 零钱兑换：动态规划 */
int coinChangeDP(int[] coins, int amt) {
    int n = coins.length;
    int MAX = amt + 1;
    // 初始化 dp 表
    int[][] dp = new int[n + 1][amt + 1];
    // 状态转移：首行首列
    for (int a = 1; a <= amt; a++) {
        dp[0][a] = MAX;
    }
    // 状态转移：其余行和列
    for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
            if (coins[i - 1] > a) {
                // 若超过目标金额，则不选硬币 i
                dp[i][a] = dp[i - 1][a];
            } else {
                // 不选和选硬币 i 这两种方案的较小值
                dp[i][a] = Math.min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1);
            }
        }
    }
    return dp[n][amt] != MAX ? dp[n][amt] : -1;
}

518. 零钱兑换 II

本题目标是求组合数量，因此子问题变为：前 i 种硬币能够凑出金额 a 的组合数量。而 dp 表仍然是尺寸为 (n+1)×(amt+1) 的二维矩阵。

当前状态的组合数量等于不选当前硬币与选当前硬币这两种决策的组合数量之和。状态转移方程为：

dp[i,a]=dp[i−1,a]+dp[i,a−coins[i−1]]

当目标金额为 0 时，无须选择任何硬币即可凑出目标金额，因此应将首列所有 dp[i,0] 都初始化为 1 。当无硬币时，无法凑出任何 >0 的目标金额，因此首行所有 dp[0,a] 都等于 0 。

/* 零钱兑换 II：动态规划 */
int coinChangeIIDP(int[] coins, int amt) {
    int n = coins.length;
    // 初始化 dp 表
    int[][] dp = new int[n + 1][amt + 1];
    // 初始化首列
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 1;
    }
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
            if (coins[i - 1] > a) {
                // 若超过目标金额，则不选硬币 i
                dp[i][a] = dp[i - 1][a];
            } else {
                // 不选和选硬币 i 这两种方案之和
                dp[i][a] = dp[i - 1][a] + dp[i][a - coins[i - 1]];
            }
        }
    }
    return dp[n][amt];
}

72. 编辑距离

输入两个字符串 s 和 t ，返回将 s 转换为 t 所需的最少编辑步数。

你可以在一个字符串中进行三种编辑操作：插入一个字符、删除一个字符、将字符替换为任意一个字符。

若 s[n−1] 和 t[m−1] 相同，我们可以跳过它们，直接考虑 s[n−2] 和 t[m−2] 。
若 s[n−1] 和 t[m−1] 不同，我们需要对 s 进行一次编辑（插入、删除、替换），使得两字符串尾部的字符相同，从而可以跳过它们，考虑规模更小的问题。

不同的操作：

在 s[i−1] 之后添加 t[j−1] ，则剩余子问题 dp[i,j−1] 。
删除 s[i−1] ，则剩余子问题 dp[i−1,j] 。
将 s[i−1] 替换为 t[j−1] ，则剩余子问题 dp[i−1,j−1] 。

可得最优子结构：dp[i,j] 的最少编辑步数等于 dp[i,j−1]、dp[i−1,j]、dp[i−1,j−1] 三者中的最少编辑步数，再加上本次的编辑步数 1 。对应的状态转移方程为：

dp[i,j]=min(dp[i,j−1],dp[i−1,j],dp[i−1,j−1])+1

确定边界条件和状态转移顺序

当两字符串都为空时，编辑步数为 0 ，即 dp[0,0]=0 。当 s 为空但 t 不为空时，最少编辑步数等于 t 的长度，即首行 dp[0,j]=j 。当 s 不为空但 t 为空时，最少编辑步数等于 s 的长度，即首列 dp[i,0]=i 。

class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length(), m = word2.length();
        int[][] dp = new int[n + 1][m + 1];
        // 
        for(int i = 1; i <= n; i++){
            dp[i][0] = i;
        }
        for(int i = 1; i <= m; i++){
            dp[0][i] = i;
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j<= m; 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[n][m];
    }
}

674. 最长连续递增序列

前一个和后一个比较，小了+1，大了重新排序

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        if(nums.length < 1)return nums.length;
        int count = 1;
        int ans = 1;
        for(int i = 0; i < nums.length - 1; i++){
            if(nums[i + 1] > nums[i]){
                count++;
            }else{
                count = 1;
            }
            ans = count > ans ? count : ans;
        }
        return ans;
    }
}

62. 不同路径

跟背包差不多

如果是边界为0的话，则步数 + 1，不是的话等于上面的值+左边的值

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

**
**

121. 买卖股票的最佳时机**
**想卖出最大利润，则需要计算股价最小值，使用min统计，由于只能进行一次买卖，所以使用res维护最大值

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

55. 跳跃游戏

如果i > c 说明没法跳跃了或者c = 0，返回false

计算跳跃位置从i 跳跃到 i + nums[i]

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int c = nums[0];
        for(int i = 1; i < nums.length; i++){
           if(i > c)return false;
           c = Math.max(c, i + nums[i]);
        }
        return true;
    }
}

45. 跳跃游戏 II

这道题应该是贪心做法比较好，但这里举出dp形式的

注意 i + j < n;

class Solution {
    public int jump(int[] nums) {
        int[]dp = new int[nums.length];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i = 0; i < nums.length; i++){
            // 这里从可0遍历到最远地方.判断最小次数
            for(int j = 1; j <= nums[i] && i + j < nums.length; j++){
                dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
            }
        }
        return dp[nums.length - 1];
    }
}

198. 打家劫舍

跳格偷钱，如果拿了i 家的钱，下一家就必须是i + 2,因此有

dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]）。

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

337. 打家劫舍 III

和上一题相比这道题是使用树节点，这次抢了就要跳过下家，去下下家

class Solution {
    HashMap<TreeNode, Integer> map = new HashMap<>();
    public int rob(TreeNode root) {
        if(root == null)return 0;
        if(map.containsKey(root)){
            return map.get(root);
        }
        int d = root.val + (root.left == null ? 0 : rob(root.left.left) + rob(root.left.right))
        + (root.right == null ? 0 : rob(root.right.left) + rob(root.right.right));
        int nd = rob(root.left) + rob(root.right);
        int res = Math.max(d, nd);
        map.put(root, res);
        return res;
    }
}

121. 买卖股票的最佳时机

想卖出最大利润，则需要计算股价最小值，使用min统计，由于只能进行一次买卖，所以使用res维护最大值

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


class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        // 给第一次赋值
        dp[0][1] = -prices[0];
        for(int i = 1; i < n; 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], -prices[i]);
        }
        return dp[n - 1][0];
    }
}

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

这道题比上一道多了一个冷却时间，

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