LeetCode101(Java版)

一、贪心算法

贪心算法采用贪心的策略,保证每次操作都是局部最优的,从而使最后得到的结果也是全局最优的

🌟 分配问题

455.分配饼干

解题思路:先对孩子的饥饿度和饼干大小进行排序,然后从饥饿度最小的孩子开始分配

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int child = 0;
        int cookie = 0;
        while(child < g.length && cookie < s.length){
            if(g[child] <= s[cookie]){
                child++;
            }
            cookie++;
        }
        return child;
    }
}

135.分配糖果

  • 分配要求:每个孩子至少分配到 1 个糖果,且评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果
  • 解题思路:对孩子的得分进行两次遍历,第一次从左到右遍历,若右侧孩子得分大于左侧,则右侧孩子的糖果数 = 左侧孩子糖果数+1;第二次则从右往左遍历,若左侧孩子得分大于右侧,则左侧孩子糖果数为 =【右侧孩子糖果+1 与 左侧孩子当前糖果数 取最大值】
class Solution {
    public int candy(int[] ratings) {
        int size = ratings.length;
        if (size < 2){
            return size;
        }
        // 初始化,每个孩子一个糖果
        int[] num = new int[size];
        Arrays.fill(num,1);
        //从左到右遍历,如右侧孩子得分大于左侧,则右侧的糖果数为左侧孩子糖果数+1
        for(int i = 1; i< size; i++){
            if(ratings[i] > ratings[i-1]){
                num[i] = num[i-1] + 1;
            }
        }
        // 从右往左遍历,若左侧孩子得分大于右侧,则左侧孩子糖果数为 右侧孩子糖果+1 与 左侧当前糖果 取最大值
        for(int j = size-1; j > 0; j--){
            if(ratings[j] < ratings[j-1]){
                num[j-1] = Math.max(num[j-1], num[j]+1);
            }
        }
        // 统计结果数组
        int sum = 0;
        for(int i: num){
            sum += i;
        }
        return sum;
    }
}

🌟 区间问题

435.互不重叠区间

  • 题目要求:给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。
  • 解题思路:先把区间按照结尾元素的大小进行排序,每次选择 结尾元素最小且和前一个选择的区间不重叠的区间
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        int n = intervals.length;
        if(n < 2){
            return 0;
        }

        // 按照结尾大小,从小到大排序
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

        int ans = 0, prev = intervals[0][1];
        for(int i = 1; i < n; i++){
            if(intervals[i][0] < prev){
                ans++;
            }else{
                prev = intervals[i][1];
            }
        }

        return ans;
    }
}

此处通过比较器来自定义了规则,数组长度默认为2,则a[1]和b[1]就是末尾元素了,当a[1] - b[1]<0,即a[1]< b[1],此处自定义的比较器结合sort就会升序排列。经过lamba表达式简化,即为Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

Arrays.sort(intervals, new Comparator<int[]>(){
           // Compares its two arguments for order.  Returns a negative integer,
           //     * zero, or a positive integer as the first argument is less than, equal
           //     * to, or greater than the second
            @Override
            public int compare(int[] a, int[] b){
                return a[1] - b[1];
            }
        });

Java中手动创建二维数组并赋值:int [][] intervals = new int[][]{{4,5},{2,3},{1,6}};,全是大括号

二、双指针

167.有序数组的两数和

在有序数组中找出两个数,使他们的和为target

思路:使用双指针分别指向数组两端,左侧指针在Sum小于target时,往右移;右侧指针在Sum大于target时,向左移。

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int i= 0, j=numbers.length-1;

        while (i<j){
            int sum = numbers[i] + numbers[j];
            
            if(sum == target){
                return new int[]{i + 1, j + 1};  // java要返回数组
            } else if (sum > target){
                j--;
            }else{
                i++;
            }
        }
        return null;
    }
}       

88.归并两个有序数组

存在两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中使 nums1 成为一个有序数组。

思路:使用双指针分别指向两个有序数组的尾部元素,比较两元素,

  • 若左指针元素小于右指针元素,将左侧元素添加到结果数组中,左指针左移1位;右侧小,将右侧元素添加到结果数组中,右指针左移1位;
  • 若左侧元素已遍历完,直接将右侧元素添加到结果数组中,右侧元素遍历完时直接添加左侧元素。
  • 需要从尾开始遍历,否则在 nums1 上归并得到的值会覆盖还未进行归并比较的值。
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int index1 = m-1, index2 = n-1;
        int indexMerge = m+n-1;

        while(index1 >= 0  || index2 >= 0){
            // 左侧数组已遍历完,直接将右侧数组插入到结果数组中
            if (index1 < 0){
                nums1[indexMerge--] = nums2[index2--];
            }else if (index2 < 0){   // 右侧数组已遍历完,直接将左侧数组插入到结果数组中
                nums1[indexMerge--] = nums1[index1--];
            }else if (nums1[index1] >= nums2[index2]){    // 哪边元素大,哪边放入结果数组
                nums1[indexMerge--] = nums1[index1--];
            }else{
                nums1[indexMerge--] = nums2[index2--];
            }
        }
    }
}

76.滑动窗口

class Solution {
    public String minWindow(String s, String t) {
        if (s == null || s == "" || t == null || t == "" || s.length() < t.length()) {
            return "";
        }
        //维护两个数组,记录s和t中指定字符中出现次数
        //ASCII表总长128
        int[] chars = new int[128];  // 默认值0
        boolean[] flags = new boolean[128];  // 默认值false

        for (int i = 0; i < t.length(); i++) {
            flags[t.charAt(i)] = true;
            chars[t.charAt(i)]++;
        }

        // 移动滑动窗口,不断更改统计数据
        int cnt = 0, l = 0, min_l = 0, min_size = s.length()+1;
        for (int r = 0; r < s.length(); ++r) {
            if (flags[s.charAt(r)]){
                if (--chars[s.charAt(r)] >= 0){
                    ++cnt;
                }
                // 若目前统计窗口中已包含所需的全部字符,开始收缩左侧边界
                while (cnt == t.length()){
                    if (r-l+1 < min_size){
                        min_l = l;
                        min_size = r-l+1;
                    }
                    if (flags[s.charAt(l)] && ++chars[s.charAt(l)] > 0){
                        --cnt;
                    }
                    ++l;
                }
            }

        }
        System.out.println(min_l+"\n"+min_size);
        //返回的为以记录的起始位置为起点,记录的最短长度为距离的指定字符串中截取的子串
        if (min_size == s.length() + 1) {
            return "";
        }
        return s.substring(min_l, min_l+min_size);
    }
}

🌟 链表

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

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。进阶:你能尝试使用一趟扫描实现吗?

解题思路:使用两个指针 first 和 second同时对链表进行遍历,并且 first比 second 超前 n个节点。当 first 遍历到链表的末尾时,second就恰好处于倒数第 n 个节点。

  • 为何方便删除操作,我们设置second的初始位置为哑节点,这样当first到达尾部时,second刚好到n-1个节点
/**
 * 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 ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = head;
        ListNode second = dummy;
        
        for (int i = 0; i < n; ++i) {
            first = first.next;
        }

        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;

        ListNode ans = dummy.next;
        return ans;
    }
}

141.判断链表是否存在环

题目描述:给定一个链表,判断链表中是否有环。

思路:使用双指针分别指向链接头部,其中一个指针每次移动一个节点,另一个指针每次以移动两个节点,如果存在环,则两者必相遇。

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null){
            return false;
        }
        ListNode l1 =head, l2 = head.next;

        // l1,l2均不为空,且由于l2每次走两步,也要考虑l2.next
        while(l1 != null && l2 != null && l2.next != null){
            if (l1 == l2){
                return true;
            }
            l1 = l1.next;
            l2 = l2.next.next;
        }
        return false;        
    }
}

142.环形链表Ⅱ

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null

思路:给定快慢指针slow和fast,起始位置均为链表头部,每次快指针移动两格,慢指针移动一格;

  • 如果两者没有走到链表尾部,而是相遇了,那么就证明了存在环路;

  • 此时,将快指针移动到链表头部,每次也是移动一格,当再次和满指针邂逅时,就是环路的起始点。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null) return null;
        ListNode slow = head, fast = head;
        // 第一次相遇
        do{
            if(slow == null || fast == null || fast.next == null){
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        }while(slow != fast);
        // 将快指针移动到首节点,开始准备第二次邂逅
        fast = head;
        while(fast != slow){
           slow = slow.next;
            fast = fast.next; 
        }
        return fast;
    }
}

三、二分查找

🌟 求开方

69.求开方

要求:给定一个整数,求他的开方,向下取整

解题思路:二分查找

class Solution {
    public int mySqrt(int x) {
        if (x == 0) return x;
        int l = 1, r = x, mid, sqrt;
        while (l <= r){
            mid = l + (r-l)/2;
            sqrt = x/mid;
            if (sqrt == mid){  
                return mid;
            } else if (sqrt < mid){  // mid^2 > x,右边界左移
                r = mid - 1;
            }else {
                l = mid + 1;
            }
        }
        return r;
    }
}

牛顿迭代法

class Solution {
    public int mySqrt(int x) {
        //if (x < 2) return x;
        long a = x;
        while(a*a > x){
            a = (a+x/a)/2;
        }
        return (int)a;
    }
}

🌟 查找区间

34.查找区间

直观的思路肯定是从前往后遍历一遍。用两个变量记录第一次和最后一次遇见 target 的下标,但这个方法的时间复杂度为 O(n),没有利用到数组升序排列的条件。

由于数组已经排序,因此整个数组是单调递增的,我们可以利用二分法来加速查找的过程。

考虑 target开始和结束位置,其实我们要找的就是数组中「第一个等于 target的位置」(记为 leftIdx)和「第一个大于 target的位置减一」(记为 rightIdx)。

二分查找中,寻找 leftIdx 即为在数组中寻找第一个大于等于 target 的下标,寻找 rightIdx即为在数组中寻找第一个大于 target的下标,然后将下标减一。两者的判断条件不同,为了代码的复用,我们定义 binarySearch(nums, target, lower) 表示在 nums 数组中二分查找 target的位置,如果 lower为 true,则查找第一个大于等于 target的下标,否则查找第一个大于 target的下标。

最后,因为 target可能不存在数组中,因此我们需要重新校验我们得到的两个下标 leftIdx和 rightIdx,看是否符合条件,如果符合条件就返回 [leftIdx,rightIdx],不符合就返回 [−1,−1]。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return new int[]{leftIdx, rightIdx};
        } 
        return new int[]{-1, -1};
    }

    // 二分查找
    public int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

🌟 旋转数组查找数字

81.旋转数组查找数字

存在一个旋转排序数组,编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true,否则返回 false

解题思路:虽然数组整体上已经不符合递增性了,但部分依然存在。先比较当前中点索引的元素值和尾部元素,若中点元素小,则可证明右侧区间为递增的,此时若目标元素在右侧区间内(目标元素和中点值、尾部元素比较即可),直接丢弃左侧区间,在右侧区间中继续寻找;否则丢弃右侧区间,在左侧区间中继续寻找。

class Solution {
    public boolean search(int[] nums, int target) {
        int start = 0, end = nums.length-1;
        while (start <= end){
            int mid = start+ (end -start)/2;
            if (nums[mid] == target){
                return true;
            }
            if (nums[mid] == nums[end]){
                end--;
            }else if (nums[mid] < nums[end]){  // 右边递增的
                if (target > nums[mid] && target <= nums[end]){ // 如果目标元素在右区间中,丢弃左区间
                    start = mid + 1;
                }else{
                    end = mid - 1;
                }
            }else{  // 左边递增的
                 if (target >= nums[start] && target < nums[mid]){ // 如果目标元素在左区间中,丢弃右区间
                    end = mid - 1;  //
                }else{
                    start = mid + 1;
                }
            }
        }
        return false;
    }
}

154.寻找旋转排序数组中的最小值 II

四、排序算法

🌟 常用排序算法整理

🌟 快速排序

选择 p 到 r 之间的任意一个数据作为 pivot(分区点),遍历 p 到 r 之间的数据,将小于 pivot 的放到左边,将大于 pivot 的放到右边,将 pivot 放到中间。

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

import java.util.Random;

class Solution {

    private static Random random = new Random(System.currentTimeMillis());

    public int findKthLargest(int[] nums, int k) {
        int left = 0, right = nums.length - 1;
        int target = nums.length - k;
        while(true){
            int mid = partition(nums, left, right);
            if (mid == target){
                return nums[mid];
            }else if (mid > target){  // mid左侧的数小,右侧的数大;丢弃右侧
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
    }

    public int partition(int[] nums, int left, int right){
        // 打乱数组先, 在区间随机选择一个元素作为标定点
        if (right > left) {
            int randomIndex = right - 1 - random.nextInt(right - left);
            swap(nums, right, randomIndex);
        }

        int pivot = nums[right];
        int i = left;
        for(int j = left; j < right; j++){
            if (nums[j] < pivot){
                swap(nums, i, j);   // left~i-1 都小于pivot
                i++;
            }
        }
        swap(nums, i, right);
        return i;
    }
    


    public void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

🌟 桶排序

347.前 K 个高频元素

给定一个非空的整数数组,返回其中出现频率前 k 高的元素。

解题思路

【基于桶排序】,首先根据题干中的整数数组构造HashMap,统计每个元素出现的次数;然后构造一个桶的集合,集合中的每个元素都是一个桶,第 i 个桶中存放 nums 中出现次数为 i 的所有数字;之后我们倒序遍历这些桶,填充要返回的结果数组即可。

//基于桶排序求解「前 K 个高频元素」
class Solution {
    public int[] topKFrequent(int[] nums, int k) {        
        // 统计每个元素出现的次数,
        HashMap<Integer,Integer> map = new HashMap();
        for(int num : nums){
            if (map.containsKey(num)) {
               map.put(num, map.get(num) + 1);
             } else {
                map.put(num, 1);
             }
        }
        
        // 一个数字最多出现 nums.length 次,因此定义一个长度为 nums.length + 1 的数组
        List<Integer>[] list = new List[nums.length+1]; 
        for(int key : map.keySet()){
      		 // 第 i 个桶中存放 nums 中出现次数为 i 的所有数字
            int freq = map.get(key);
            // 如果某个桶还未放入过数字(即未初始化),则初始化其为一个数组
            if(list[freq] == null){
               list[freq] = new ArrayList();
            } 
            list[freq].add(key);  // 然后将数字放到桶中
        }
    
        
        int[] res = new int[k];
        int idx = 0;
        // 倒序遍历每个桶
        for (int freq = list.length - 1; freq > 0 && idx < k; freq--) {
            if (list[freq] != null){ // 桶 不为空
                for (int num: list[freq]) {
                    res[idx++] = num;  // 将非空桶内的所有数字存到结果数组中
                }
            }
        }
        return res;
    }
}

【基于最小堆】

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 统计每个数字出现的次数
        HashMap<Integer,Integer> map = new HashMap();
        for(int num : nums){
            if (map.containsKey(num)) {
               map.put(num, map.get(num) + 1);
             } else {
                map.put(num, 1);
             }
        }
        // 定义小根堆,根据数字频率自小到大排序
        Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> map.get(v1) - map.get(v2));
        // 遍历数组,维护一个大小为 k 的小根堆:
        // 不足 k 个直接将当前数字加入到堆中;否则判断堆中的最小次数是否小于当前数字的出现次数,若是,则删掉堆中出现次数最少的一个数字,将当前数字加入堆中。
        map.forEach((num, cnt) -> {
            if (pq.size() < k) {
                pq.offer(num);
            } else if (map.get(pq.peek()) < cnt) {
                pq.poll();
                pq.offer(num);
            }
        });
        
        // 构造返回结果
        int[] res = new int[k];
        int idx = 0;
        for (int num: pq) {
            res[idx++] = num;
        }
        return res;
    }
}

五、搜索

🌟 深度优先搜索DFS

dfs的实现分为三步:条件判断、修改状态、递归子节点

695.岛屿的最大面积

给定一个二维的0-1矩阵,其中0表示海洋,1表示陆地。单独的或者相邻的陆地可以构成岛屿,每个格子只与其上下左右四个位置相连。求最大的岛屿面积

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
       if (grid.length == 0 || grid[0].length == 0) return 0; 
       int max_aera = 0;
       for (int i = 0; i< grid.length; i++){
           for (int j = 0; j< grid[0].length; j++){
               if (grid[i][j] == 1){  // 当前格子为岛屿,开始搜索周围岛屿
                   max_aera = Math.max(dfs(grid, i, j), max_aera);
               }               
           }
       }
       return max_aera;
    }

    public int dfs(int[][] grid, int i, int j){
        // 边界条件 或者 已经访问过
        if(i<0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != 1) return 0;

        grid[i][j] = 0;  // 已访问过的岛屿标记为0,避免再次访问
        
        // 当前位置的岛屿 + 上下左右位置的岛屿
        int ans = 1 + dfs(grid, i-1, j) + dfs(grid, i+1, j)  
                    + dfs(grid, i, j-1) + dfs(grid, i, j+1);
        return ans;
    }
}

200.岛屿数量

给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。

class Solution {
    public int numIslands(char[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) return 0;
        int num = 0;
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j] == '1'){
                    num ++;
                    dfs(grid, i, j);
                }
            }
        }
        return num;
    }

    public void dfs(char[][] grid, int i, int j){
        if(i<0 || i >= grid.length || j<0 || j >= grid[0].length || grid[i][j] != '1'){
            return ;  // return null 会报错,一个return即可
        }
        grid[i][j] = '0';
        
        dfs(grid, i-1, j);
        dfs(grid, i+1, j);
        dfs(grid, i, j-1);
        dfs(grid, i, j+1);
    }
}

547.朋友圈/省份数量

给你一个 n x n 的矩阵 isConnected ,其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连,而 isConnected[i][j] = 0 表示二者不直接相连。返回矩阵中 省份 的数量。

class Solution {
    public int findCircleNum(int[][] isConnected) {
        // int[][] isConnected 是无向图的邻接矩阵,n 为无向图的顶点数量
        int n = isConnected.length;
        // 定义 boolean 数组标识顶点是否被访问
        boolean[] visited = new boolean[n];
        // 定义 cnt 来累计遍历过的连通域的数量
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            // 若当前顶点 i 未被访问,说明又是一个新的连通域,则遍历新的连通域且cnt+=1.
            if (!visited[i]) { 
                cnt++;
                dfs(i, isConnected, visited);
            }
        }
        return cnt;
    }

    private void dfs(int i, int[][] isConnected, boolean[] visited) {
        // 对当前顶点 i 进行访问标记
        visited[i] = true;
        
        // 继续遍历与顶点 i 相邻的顶点(使用 visited 数组防止重复访问)
        for (int j = 0; j < isConnected.length; j++) {
            if (isConnected[i][j] == 1 && !visited[j]) {
                dfs(j, isConnected, visited);
            }
        }
    }
}

417.太平洋大西洋水流问题

给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界,而“大西洋”处于大陆的右边界和下边界。规定水流只能按照上、下、左、右四个方向流动,且只能从高到低或者在同等高度上流动。请找出那些水流既可以流动到“太平洋”,又能流动到“大西洋”的陆地单元的坐标

【DFS】

/**
    建立两个矩阵can_reach_p和can_reach_a, 当can_reach_p[i][j]和can_reach_a[i][j]同时为true时表示该位置可以同时到达Atlantic和Pacific
    便历时的技巧为: 只需要从四个边界开始遍历即可(类似泛洪的思想, 只要可以从边界出发到达, 就说明该位置的水可以流向对应的海洋)
**/
class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] matrix) {
        List<List<Integer>> res = new ArrayList<> ();
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return res;

        int m = matrix.length, n = matrix[0].length;
        boolean[][] can_reach_p = new boolean[m][n];
        boolean[][] can_reach_a = new boolean[m][n];;
       

        for(int i = 0; i < m; i++){
            // 左右两条边
            dfs(matrix, can_reach_p, i, 0);
            dfs(matrix, can_reach_a, i, n-1);
        }

        for(int j = 0; j < n; j++){
            // 上下两条边
            dfs(matrix, can_reach_p, 0, j);
            dfs(matrix, can_reach_a, m-1, j);
        }

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if (can_reach_a[i][j] && can_reach_p[i][j]){
                    res.add(Arrays.asList(i,j));
                }
            }
        }

        return res;        
    }

    public void dfs(int[][] matrix, boolean[][] can_reach, int i, int j){
        if(can_reach[i][j]) return;
        
        can_reach[i][j] = true;
        
        int offset[][] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int x,y;
        for(int temp = 0; temp < 4; temp++){
            x = i + offset[temp][0];
            y = j + offset[temp][1];
            if (x>=0 && x < matrix.length && y>=0 && y < matrix[0].length
                && matrix[i][j] <= matrix[x][y]){
                    dfs(matrix, can_reach, x, y);
                }
        }
    }
}

另一种DFS的写法

class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] matrix) {
        List<List<Integer>> res = new ArrayList<> ();
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return res;

        int m = matrix.length, n = matrix[0].length;
        boolean[][] can_reach_p = new boolean[m][n];
        boolean[][] can_reach_a = new boolean[m][n];;
       

        for(int i = 0; i < m; i++){
            // 左右两条边
            dfs(matrix, can_reach_p, i, 0, matrix[i][0]);
            dfs(matrix, can_reach_a, i, n-1, matrix[i][n-1]);
        }

        for(int j = 0; j < n; j++){
            // 上下两条边
            dfs(matrix, can_reach_p, 0, j, matrix[0][j]);
            dfs(matrix, can_reach_a, m-1, j, matrix[m-1][j]);
        }

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if (can_reach_a[i][j] && can_reach_p[i][j]){
                    res.add(Arrays.asList(i,j));
                }
            }
        }

        return res;        
    }

    public void dfs(int[][] matrix, boolean[][] can_reach, int i, int j, int pre){
        if(i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length || can_reach[i][j] || matrix[i][j] < pre){
            return;
        }

        can_reach[i][j] = true;
        dfs(matrix, can_reach, i-1, j, matrix[i][j]);  // 找比当前位置海拔高的
        dfs(matrix, can_reach, i+1, j, matrix[i][j]);
        dfs(matrix, can_reach, i, j-1, matrix[i][j]);
        dfs(matrix, can_reach, i, j+1, matrix[i][j]);
    }
}

🌟 回溯法

46.全排列

给定一个『没有重复数字』的序列,返回其所有可能的全排列。

解题思路:回溯相比于DFS,多了一层撤销修改状态,即【修改当前节点状态】—> 【递归子节点】—>【撤销修改状态】

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        // 结果数组
        List<List<Integer>> res = new ArrayList<>();
        
        // 中间变量,将原先int[]类型的nums转换为List形式,便于交换元素和最终添加到结果数组
        List<Integer> temp = new ArrayList<>();
        for (int num: nums){
            temp.add(num);
        }

        int n = nums.length;
        backtrack(res, output, 0, n);
        return res;
    }

    public void backtrack(List<List<Integer>> res, List<Integer> temp, int level, int n) {
        // 所有位置都填上数了,可以添加到结果数组中了
        if(level == n){
            res.add(new ArrayList<Integer>(temp));
        }
        
        for(int i = level; i < n; i++){
            Collections.swap(temp, i, level);   // 修改当前节点状态
            backtrack(res, temp, level+1, n);   // 递归子节点
            Collections.swap(temp, i, level);   // 撤销修改
        }
    }
}

其中,Collection.swap只能对List进行操作,无法对int[]进行操作

不采用中间变量数组也可以,但最终添加到结果数组时要进行转换:

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList();
        backtrackiing(nums, 0, ans);
        return ans;
    }

    public void backtrackiing(int[] nums, int level, List<List<Integer>> ans){
        if(level == nums.length - 1){
            ans.add(Arrays.stream(nums).boxed().collect(Collectors.toList())); // int[]转换为List
            return;
        }
        for(int i = level; i < nums.length; i++){
            swap(nums, i, level);
            backtrackiing(nums, level+1, ans);
            swap(nums, i, level);
        }
    }

    public void swap(int[] nums, int i ,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

第三种写法:不再交换nums中元素的位置,通过List的contain()方法判断当前元素是否已经在临时数组中了,没有的话就添加,有的话跳过

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();

        backtrack(res, list, nums);
        return res;        
    }
    
    public void backtrack(List<List<Integer>> res, List<Integer> list, int[] nums) {
        if(list.size() == nums.length) {
            res.add(new ArrayList<Integer>(list));
            return;
        }
        for(int num : nums) {
            if(!list.contains(num)) {
                list.add(num);
                //System.out.println("前"+num+","+list);
                backtrack(res, list, nums);
                list.remove(list.size() - 1);
                //System.out.println("后"+list);
            }
        }
    }
}

77.组合

给定两个整数 nk,返回 1 … n 中所有可能的 k 个数的组合。

解题思路:回溯法,此处回溯的是是否将当前数字添加到集合中

class Solution {
    private List<List<Integer>> res;
    private int n, k;
    public List<List<Integer>> combine(int n, int k) {
        res = new ArrayList<>();   // List是接口,无法实例化;
        this.n = n;
        this.k = k;
        if(k > n) return res; // 每组有k个元素

        backtracking(new ArrayList<>(), 1, 0);  // 统计1~n之间的k个正整数
        return res;
    }

    public void backtracking(List<Integer> list, int index, int count){
        if(count == k){
            res.add(new ArrayList<>(list));  // 再复制一份,避免引用传递
            return;
        }

        // 剪枝:剩下的数已经不够了,直接退出吧
        if ((n-index+1) < k -count)  return;

        for(int i = index; i <= n; i++){   // 统计iindex~n之间的数
            list.add(i);  // 添加路径
            backtracking(list, i+1, count+1);  // 回溯子节点
            list.remove(list.size()-1);  // 撤销添加,回退状态
        }
    }
}

需要加强的Java语法点:

  1. List的remove方法既可以删除指定元素,也可以删除指定索引处的元素。
  2. List可以直接打印输出

79.单词搜索

/**
* 回溯法:相比于DFS,多了一步『撤销修改节点状态』
*/
class Solution {
    private boolean find;  // 定义为成员变量,方便以下两个成员方法使用和修改

    public boolean exist(char[][] board, String word) {
        if (board == null) return false;
        int m = board.length, n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        find = false;

        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                backtracking(i, j, board, word, visited, 0);  // 从左上角开始遍历棋盘每个格子
            }
        }
        return find;
    }

    /**
    * i,j,board:棋盘格及当前元素的坐标
    * word: 要搜索的目标单词
    * visited:记录当前格子是否已被访问过
    * pos: 记录目标单词的字符索引,只有棋盘格字符和pos指向的字符一致时,才有机会继续搜索接下来的字符;如果pos已经过了目标单词的尾部了,那么便说明找到目标单词了
    */
    public void backtracking(int i, int j, char[][] board, String word, boolean[][] visited, int pos){
        // 超出边界、已经访问过、已找到目标单词、棋盘格中当前字符已经和目标字符不一致了
        if(i<0 || i>= board.length || j<0 || j >= board[0].length || visited[i][j] || find
           || board[i][j]!=word.charAt(pos))  return;

        if(pos == word.length()-1){
            find = true;
            return;
        }

        visited[i][j] = true;  // 修改当前节点状态
        backtracking(i+1, j, board, word, visited, pos+1);  // 遍历子节点
        backtracking(i-1, j, board, word, visited, pos+1);
        backtracking(i, j+1, board, word, visited, pos+1);
        backtracking(i, j-1, board, word, visited, pos+1);
        visited[i][j] = false; // 撤销修改
    }

}

51.N 皇后

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。

解题思路:类似于在矩阵中寻找字符串,本题也是通过修改状态矩阵来进行回溯。不同的是,我们需要对每一行、列、左右对角线建立访问数组,来记录是否放置了皇后。

  • 左斜线上:横纵坐标之和固定
  • 右斜线上:(横左边-纵坐标)固定,为何避免出现负数索引,可采用n-1-(横左边-纵坐标)
  • n皇后问题,左右对角线分别有2*n-1
class Solution {

    List<List<String>> ans;

    public List<List<String>> solveNQueens(int n) {
        ans = new ArrayList<>();
        if(n == 0){
            return ans;
        }

        char[][] board = new char[n][n];
        // Arrays.fill只能作用于一维数组
        // for(int i = 0; i < n; i ++){
        //     for(int j = 0; j < n; j ++){
        //         board[i][j] = '.';
        //     }
        // }
        for(char[] i : board){
            Arrays.fill(i, '.');
        }

        // 记录该列、对角线上是否已经放置了皇后
        boolean[] column = new boolean[n];
        boolean[] ldiag = new boolean[2*n-1];
        boolean[] rdiag = new boolean[2*n-1];

        backtracking(ans, board, column, ldiag, rdiag, 0, n);
        return ans; 
    }


    /*
    * 回溯函数:
    * ans:结果数组、board:自己根据n构造的棋盘,默认填充为'.'
    * column,ldiag,rdiag:对每一行,建立列、左斜、左斜访问数组,来记录这些位置是否已经存放皇后了
    * row:当前的行数
    * n:几皇后问题,即棋盘有几行几列
    */
    public void backtracking(List<List<String>> ans, char[][] board, boolean[] column, boolean[] ldiag, boolean[] rdiag, int row, int n){
        // 已经走完所有行了,可以把当前棋盘放入结果数组了
        if(row == n){          
            // char[][] 转换为List<String>
            List temp = new ArrayList();
            for (char[] a : board){
                temp.add(String.valueOf(a));
            }
            ans.add(temp);  
            return;
        }

        for (int i = 0; i < n; i++){
            // 当前列、左斜线或者右斜线的某个位置已经有王后了,跳过该列,继续搜索
            // 左斜线上:横纵坐标之和固定
            // 右斜线上:(横左边-纵坐标)固定,为何避免出现负数索引,因此采用n-(横左边-纵坐标)
            if (column[i] || rdiag[n-1-row+i] || ldiag[row+i]){
                continue;
            }   
            // 修改当前节点状态
            board[row][i] = 'Q';
            column[i] = rdiag[n-1-row+i] = ldiag[row+i] = true;
            // 递归子节点
            backtracking(ans, board, column, ldiag, rdiag, row + 1, n);
            // 撤销修改
            board[row][i] = '.';
            column[i] = rdiag[n-1-row+i] = ldiag[row+i] = false;            
        }
    }
}

🌟 广度优先搜索BFS

934.最短的桥

最短的桥,即寻找两座岛之间的最短路径。

我们可以线通过dfs找到第一座岛屿的位置,然后基于这座岛屿开始一层层的bfs,当找到另一座岛时的层数就是所求的最短路径。

  • 此处使用LinkedList记录访问路径,采用ArrayDeque也行

  • 开始采用的是Queue<List<Integer>>,速度15ms,更改为Queue<int[]>后成功缩短到8ms

class Solution {
    private int m,n;
    private int[][] offset = {{-1,0},{1,0},{0,1},{0,-1}};
    private Queue<int []> queue = new LinkedList<>();

    public int shortestBridge(int[][] A) {
        m = A.length;
        n = A[0].length;
        boolean findFirst = false;

        // 通过dfs找到第一座岛屿
        for(int i = 0; i < A.length && !findFirst; i++){
            for(int j = 0; j < A[0].length; j++){
                if(A[i][j] == 1){
                    dfs(A, i, j);
                    findFirst = true;
                    break;
                }
            }
        } 

        // 从第一座岛屿出发,通过bfs查找与另一个岛屿的最短距离
        int step = 0;
        while(!queue.isEmpty()){
            // 依次取出第一个岛屿中每个点的坐标
            int q_size = queue.size();
            for(int i = 0; i < q_size; i++){
                int[] list = queue.poll();  // 岛屿的横纵坐标{x,y}
                for(int[] idx : offset){
                    // 上下左右搜索
                    int newX = list[0] + idx[0];
                    int newY = list[1] + idx[1];

                    // 未到边界、且未访问过
                    if(newX < 0 || newX >= m || newY < 0 || newY >= n 
                        || A[newX][newY] == 2){
                        continue;
                    }

                    if(A[newX][newY] == 1){  // 找到第二座岛屿了
                        return step;
                    }

                    A[newX][newY] = 2;  // 已访问过
                    queue.add(new int[] {newX, newY});  // 用作搜索相邻节点的相邻节点
                }     
            }
            ++step;
        }
        return step;
    }

    /**
    * 功能:找到第一座岛屿
    * A: 给定的二维数组;
    * i,j:横纵坐标
    */   
    public void dfs(int[][] A, int i, int j){
        if (i < 0 || i >= m || j < 0 || j >= n || A[i][j] != 1){
            return;
        }       
        queue.add(new int[] {i, j});  // 记录所有的1的位置(非1的在上一步就退出了)
        A[i][j] = 2;  // 修改节点状态为:已访问过

        dfs(A, i-1, j);  // 遍历子节点
        dfs(A, i+1, j);
        dfs(A, i, j-1);
        dfs(A, i, j+1);
    }
}

322.零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。你可以认为每种硬币的数量是无限的。

解题思路

BFS,从amount开始,每次减去coin,看几步能到0,步数就是待求的硬币个数

  • 为了加快速度,可以先对coins进行排序
  • 当剩下的金额小于coin时,就跳过
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) {
            return 0;
        }

        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[amount + 1];

        visited[amount] = true;
        queue.offer(amount);

        // 排序是为了加快广度优先遍历过程中,对硬币面值的遍历,起到剪枝的效果
        Arrays.sort(coins);

        int step = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Integer head = queue.poll();
                for (int coin : coins) {
                    int next = head - coin;                    
                    if (next == 0) {  // 只要遇到 0,就找到了一个最短路径
                        return step;
                    }

                    if (next >= coin && !visited[next]) {  // 剩下的金额还能凑、当前金额也没访问过
                        queue.offer(next);
                        visited[next] = true;
                    }
                }
            }
            step++;
        }
        
        // 能凑出当前面值在前面的循环中就已经return了
        return -1;
    }
}

dfs

动态规划

1162.地图分析

你现在手里有一份大小为 N x N 的 网格 grid,上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋,1 代表陆地,请你找出一个海洋单元格,这个海洋单元格到离它最近的陆地单元格的距离是最大的。如果网格上只有陆地或者海洋,请返回 -1

解题思路

无标题

class Solution {
    public int maxDistance(int[][] grid) {
        int n = grid.length;
        Queue<int[]> queue = new LinkedList<>();

        // 所有陆地入队
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == 1){
                    queue.offer(new int[]{i,j});
                }else{
                    grid[i][j] = -1;
                }
            }
        }

        // 全是陆地或者海洋
        if(queue.size() == 0 || queue.size() == n*n) return -1;

        // 从每个陆地出发,一层层地寻找海洋,最后到达的海洋就是离陆地最远的海洋
        int offset[][] = {{0,1},{0,-1},{1,0},{-1,0}};
        int[] pos = null;

        while(!queue.isEmpty()){
            pos = queue.poll();
            int x = pos[0], y = pos[1];
            for(int i = 0; i < 4; i++){
                int new_X = x + offset[i][0];
                int new_Y = y + offset[i][1];
				// 未被访问过的海洋,且未出边界
                if(new_X >=0 && new_X < n && new_Y >= 0 && new_Y < n && grid[new_X][new_Y] == -1){
                    grid[new_X][new_Y] = grid[x][y] + 1;
                    queue.offer(new int[]{new_X, new_Y});
                }
            }
        }
		
        // 最后到大的海洋(由于起始值为1,还需减去1)
        return grid[pos[0]][pos[1]] - 1;

    }
}

六、动态规划

列动态规划方程,考虑初始状态

🌟 一维

70.爬楼梯

假设你正在爬楼梯,需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?(注意:给定 n 是一个正整数)

解题思路:第i阶楼梯可以从第 i-1 和 i-2 阶楼梯再走一步到达,因此:

考虑到 dp[i] 只与 dp[i - 1] 和 dp[i - 2] 有关,因此可以只用两个变量来存储 dp[i - 1] 和 dp[i - 2],使得原来的 O(N) 空间复杂度优化为 O(1) 复杂度。

class Solution {
    public int climbStairs(int n) {
        if(n < 2) return n;
        int pre_pre = 1;  // dp[1] 
        int pre = 2;   // dp[2]
        
        for(int i = pre; i < n ; i++){
            int cur = pre_pre + pre;  // dp[i] = dp[i-2] + dp[i-1]
            pre_pre = pre;  // g更新状态
            pre = cur;
        }
        return pre;
    }
}

198.打家劫舍

抢劫一排住户,但是不能抢邻近的住户,求最大抢劫量。

解题思路:定义 dp 数组用来存储最大的抢劫量,其中 dp[i] 表示抢到第 i 个住户时的最大抢劫量。由于不能抢劫邻近住户,如果抢劫了第 i -1 个住户,那么就不能再抢劫第 i 个住户,所以

考虑到 dp[i] 只与 dp[i - 1] 和 dp[i - 2] 有关,因此可以只用两个变量来存储 dp[i - 1] 和 dp[i - 2],使得原来的空间复杂度 O(N) 优化到 O(1) 。

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 0) return 0;
        if(nums.length == 1) return nums[0];

        int pre_pre = nums[0];   // dp[0],相当于有一个元素了已经,不等于0
        int pre = Math.max(nums[0], nums[1]);  // dp[1]

        for(int i = 2; i < nums.length; i++){
            int cur = Math.max(pre, pre_pre+nums[i]);   // dp[i] = max(dp[i-1], dp[i-2]+nums[i])
            pre_pre = pre;
            pre = cur;
        }
        return pre;
    }
}

213.打家劫舍 II

待抢劫的房屋是围成一圈的,首位相邻。依旧是无法抢劫连续相邻的房子,否则会报警。求解最大抢劫量。

解题思路:环状排列意味着第一个房子和最后一个房子中只能选择一个偷窃,因此可以把此环状排列房间问题约化为两个单排排列房间子问题

  • 不偷窃第一个房子,nums[1:]
  • 不偷窃最后一个房子,nums[:-1]

最后两种dp情况取最大值即可

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        
        return Math.max(dp(Arrays.copyOfRange(nums, 1, nums.length)),   // 不偷第一座房子
                        dp(Arrays.copyOfRange(nums, 0, nums.length-1)));   // 不偷最后一座房子
    }

    public int dp(int[] nums){
        // 传过来的数组长度可能为1
        if(nums.length == 1) return nums[0];

        int pre_pre = nums[0];  // dp[0]
        int pre = Math.max(nums[0], nums[1]);  // dp[1]

        for(int i = 2; i < nums.length; i++){
            int cur = Math.max(pre, pre_pre + nums[i]);
            pre_pre = pre;
            pre = cur;
        }
        return pre;
    }
}

413.等差数列划分

给定一个数组,求这个数组中连续且等差的子数组一共有多少个

解题思路: 等差数组,则A[i] - A[i-1] == A[i-1] - A[i-2]。由于dp通常是『以i结尾,满足某些条件的子数组数量』,而等差子数组可以在任意一个位置终结。

class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        int n = A.length;
        if (n < 3)  return 0;
        int[] dp = new int[n];   //默认填充0
        int sum = 0;

        for(int i=2; i < n; i++){
            if(A[i] - A[i-1] == A[i-1] - A[i-2]){
                dp[i] = dp[i-1] + 1;
                sum += dp[i]; 
            }
        }
        return sum;  //IntStream.of(dp).sum();
    }
}

🌟 二维

64.最小路径和

给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小,返回最小路径和。每次只能向下或者向右移动一步。

解题思路:我们可以定义一个二维dp数组,其中dp[i][j]表示从左上角开始到(i,j)位置的最小路径和。由于每次只能向下或者往右移动,则状态转移方程为dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。由于边界情况下可能只有一个方向可以走,因此需根据边界条件对状态转移方程进行相应的调整

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        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] = grid[i][j];
                }else if(i == 0){
                    dp[i][j] = dp[i][j-1] + grid[i][j];
                }else if(j == 0){
                    dp[i][j] = dp[i-1][j] + grid[i][j];
                }else{
                    dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
                }
            }
        }
        return dp[m-1][n-1];        
    }
}

由于dp矩阵的每一个值只与左边和上面的值有关,因此,我们可以将空间复杂度由O(MN)减小到O(N)。对于第i行,在遍历到第j列时,dp[j-1]代表的就是原先的dp[i][j],而dp[j]当前存储的是第i-1行时的值即dp[i-1][j],因此新的状态转移方程为dp[j] = min(dp[j-1], d[[j]) + grid[i][j]

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] dp = new int[n];

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(i==0 && j==0){
                    dp[j] = grid[i][j];   // 原点
                }else if(i == 0){
                    dp[j] = dp[j-1] + grid[i][j]; // 只能从左侧过来
                }else if(j == 0){
                    dp[j] = dp[j] + grid[i][j]; // 只能从上方过来
                }else{
                    dp[j] = Math.min(dp[j], dp[j-1]) + grid[i][j];
                }
            }
        }
        return dp[n-1];        
    }
}

62.不同路径

统计从矩阵左上角到右下角的路径总数,每次只能向右或者向下移动

解题思路:每次只能下移或者右移,状态转移方程可以为dp[i][j] = dp[i-1][j] + dp[i][j-1];二维dp数组是可以压缩到一维的,新得状态转移方程为dp[j] = dp[j] + dp[j-1]

class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1);  // 只有一行或者一列时,只有一条路径

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

542.01 矩阵

给定一个由 0 和 1 组成的矩阵,找出每个元素到最近的 0 的距离。两个相邻元素间的距离为 1 。

解题思路:对于当前元素(i,j),搜索距离最近的0,分上下左右4个方向搜索。当前节点为0是,最近路径为0,因此只需处理每个1即可,多源BFS问题。首先将每个0入队,然后从每个0出发同时一圈一圈地向1扩散,用int[][] dist 来记录距离(即扩散的层次)并同时标志是否访问过。

class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        Queue<int[]> queue = new LinkedList<>();
		
        // 所有0入队,且将1标记为-1 -->未被访问过
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] == 0){
                    queue.offer(new int[] {i,j});
                }else{
                    matrix[i][j] = -1;
                }
            }
        }

        int offset[][] = {{0,1},{0,-1},{1,0},{-1,0}};
        while(!queue.isEmpty()){
            int[] pos = queue.poll();
            int x = pos[0], y = pos[1];
            for(int i = 0; i < 4; i++){
                int new_X = x + offset[i][0];
                int new_Y = y + offset[i][1];
                // 未出界,且当前节点为未被访问过的1。当前节点的最近距离为原始节点最短距离+1
                if(new_X >= 0 && new_X < m && new_Y >= 0 && new_Y < n && matrix[new_X][new_Y] == -1){
                    matrix[new_X][new_Y] = matrix[x][y] + 1;
                    queue.offer(new int[] {new_X, new_Y});
                }
            } 
        }

        return matrix;
    }
}
  • 每个点入队出队一次,所以时间复杂度:O(n∗m)
  • 虽然我们是直接原地修改的原输入数组来存储结果,但最差的情况下即全都是 0时,需要把 m∗n个 0都入队,因此空间复杂度是 O(n∗m)

该题采用动态规划也可以,对于任一点 (i,j),距离最近的0的距离为:

$f(i, j)=\left{\begin{array}{ll}1+\min (f(i-1, j), f(i, j-1), f(i+1, j), f(i, j+1)) & \text { if matrix[i] }[\mathrm{j}]==1 \ 0 & \text { if matrix }[\mathrm{i}][\mathrm{j}]==0\end{array}\right.$

从左上到右下遍历一次,从右下到左上遍历一次,两次即可完成四个方向的搜索。

class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m][n];
        
        // 初始化
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                dp[i][j] = matrix[i][j]==0 ? 0 : 10000;   // 当前格子为0,最短路径即为0;
            }
        }

        // 左上角开始遍历
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(j > 0){
                    dp[i][j] = Math.min(dp[i][j], dp[i][j-1]+1);  // 左方
                }
                if(i > 0){
                    dp[i][j] = Math.min(dp[i][j], dp[i-1][j]+1);  // 上方
                }                
            }
        }

        //右下角开始遍历
        for(int i = m-1; i >= 0; i--){
            for(int j = n-1; j >= 0; j--){
                if(j < n-1){
                    dp[i][j] = Math.min(dp[i][j], dp[i][j+1]+1);  // 右方
                }
                if(i < m-1){
                    dp[i][j] = Math.min(dp[i][j], dp[i+1][j]+1);  // 下方
                }                
            }
        }

        return dp;

    }
}

221.最大正方形

在一个由 '0''1' 组成的二维矩阵内,找到只包含 '1' 的最大正方形,并返回其面积。

解题思路:创建一个二维动态规划数组dp,其中dp[i][j]表示以(i,j)为右下角组成的正方形的最大边长。有点类似于木桶效应,该点组成正方形的最大边长受限于其左侧、上侧、左上节点组成的最大正方形的最短边长,即dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1

class Solution {
    public int maximalSquare(char[][] matrix) {
        if(matrix.length == 0 || matrix[0].length == 0) return 0;
        
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m][n];
        int max_side = 0;

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] == '1'){   // 当前节点值为1,才可组成题干要求的正方形
                    if(i == 0 || j == 0) {  // 第一列、第一行
                        dp[i][j] = 1;
                    }else{
                        dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
                    }
                }

                max_side = Math.max(max_side, dp[i][j]);
            }
        }
        return max_side*max_side;
    }
}

🌟 分割类型题

279.完全平方数

给你一个整数 n ,返回和为 n 的完全平方数的 最少数量

解题思路:分割类型题,动态规划的状态转移方程通常不依赖相邻的位置,而是依赖于满足分割条件的位置。该题分割条件是满足完全平方分割,因此我们可以定义一个一维dp数组,其中dp[i]表示数字i 最少可有几个完全平方数组成。dp[i]依赖于dp[i-k]这些位置,如dp[i-1]、dp[i-4]、dp[i-9]。因此状态转移方程可以为dp[i] = 1 + min(dp[i-k]),其中1表示j*j这个数.

还是有点迷糊啊

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        Arrays.fill(dp,10000);
        dp[0] = 0;

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

91.解码方法

给你一个只含数字的 非空 字符串 num ,请计算并返回 解码 方法的 总数

解题思路:创建一个dp数组:到字符串s[i]为止,合法的方法为 dp[i+1] 个。

1.字符串长度为0,或者以0开头,无法解码,返回0;

2.字符串长度为1,只有一种解码结果

3.字符串长度大于1时,两位两位地看:

【×】00或者大于30、40这种情况无法解码,直接返回0;

【√】能解码的两位数分为10~2627~99这两种:

​ 对于10~26,若个位为0,即10、20,解码后的10或者20加入到前移两位的结果集中,并未另拓展结果集,改变前移两位的结果数量,即dp[i] = dp[i-2]…..联想120和20

​ 若个位不为0,即11-19、21~26,这两位数可以分别解码添加到前移一位的结果集中,也可一起解码添加到前移两位的结果集中,即dp[i] = dp[i-1] + dp[i-2]…联想1122—>11 2 2 和11 22,

​ 对于27~99,只能一位一位的解码,和前移一位的解码结果数量一样,即dp[i] = dp[i-1],联想12—>1 27

class Solution {
    public int numDecodings(String s) { 
        int n = s.length();
        // 空字符,或者以0开头,无法解码,返回0    
        if (n == 0 || s.charAt(0) == '0') return 0;
        // 只有一个字符(0~9),只有一种解码结果
        if (n == 1) return 1;

        int[] dp = new int[n+1];
        Arrays.fill(dp, 1);
        int pre = s.charAt(0) - '0';   // 十位是什么数字

        for(int i = 2; i <= n; i++){
            int cur = s.charAt(i-1) - '0';  // 个位是什么数字。
            if ((pre == 0 || pre > 2) && cur == 0) return 0;  // 00、30、40、50...
            
            if (pre == 1 || (pre == 2 && cur < 7)){  // 10-26
                if(cur != 0){  // 11-19、21-26
                    dp[i] = dp[i-1] + dp[i-2];
                }else{ // 10、20
                    dp[i] = dp[i-2];
                }
            }else{  // 27-99
                dp[i] = dp[i-1];
            }
            pre = cur;  // 右移
        }
        return dp[n];
    }
}

139.单词拆分

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明:拆分时可以重复使用字典中的单词;你可以假设字典中没有重复的单词。

解题思路:创建一维数组dp,其中dp[i]表示字符串s的前i位能否拆分为wordDict

类似于完全平方数分割问题(分割条件为能否被开方),此处分割条件为拆分后的字符串是否在wordDict中。因此,在考虑每个分割位置时,需要遍历wordDict,确认当前位置是否可以成功分割。默认dp[0]true

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
       int n = s.length();
       boolean[] dp = new boolean[n+1];
       dp[0] = true;

       for(int i = 1; i <= n; i++){
           for(String word: wordDict){
               int len = word.length();
               // java中字符串用==比较,比较的是内存地址,一般都会返回false
               if (i >= len && s.substring(i-len, i).equals(word)){
                   dp[i] = dp[i] || dp[i - len];
               }
           }
       }
       return dp[n]; 
    }
}

🌟 子序列问题

对于Leetcode,通常而言,子序列不必连续,子数组或者子字符串必须连续。

300.最长递增子序列

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。子序列不一定是连续的。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列)

解题思路:创建一个一维数组dp,用dp[i]表示到数组numsi个元素位置为止、最长递增子序列的长度。

对于每一个位置i,如果其之前的某个位置j对应的元素nums[j]小于nums[i],则dp[i]的长度为dp[j]的长度+1。两层遍历的时间复杂度为O(n^2)

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length, max_length = 0;
        if (n <= 1) return n;

        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        for(int i = 0; i < n; i++){
            for(int j = 0; j < i; j++){ // 寻找比当前元素小的元素
                if (nums[j] < nums[i]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);  // 更新i位置处为止、最长递增子序列的长度
                }
            }
            max_length = Math.max(max_length, dp[i]);   // 记录所有位置长度中最大的长度
        }
        return max_length;
    }
}

本题可以采用二分法将时间复杂度降低为O(nlogn)。首先创建一个数组tail来存储递增子序列,用end表示已填入元素的数量。遍历nums中所有元素:当nums当前元素大于tail尾部元素时,将该元素添加到tail中组成新的递增子序列;否则,tails中必然有大于等于该元素的元素,二分法找到第一个这种元素,更新为nums[i]。相当于把一个较大的元素替换为一个较小的元素,这样递增子序列的最大长度可能存在更大的可能,潜力更大。

public class Solution {
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        if (len <= 1) return len;

        int[] tail = new int[len];
        tail[0] = nums[0];
        int end = 0;

        for (int i = 1; i < len; i++) {
            if (nums[i] > tail[end]) {  // 当前元素大于递增子序列的最后一个元素时,招安当前元素
                end++; 
                tail[end] = nums[i];
            } else {   // 找到递增子序列中第一个大于该元素的元素,更新为当前元素
                int idx = lower_bound(tail, nums[i], end);
                tail[idx] = nums[i];
            }
        }
        end++;
        return end;
    }

    public int lower_bound(int[] tail, int temp, int end){
        int left = 0;
        int right = end;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            //int mid = left + ((right - left) >>> 1);
            if (tail[mid] < temp) {
                left = mid + 1;  // 待查找的元素在右区间中,更新左边界
            } else {
                right = mid -1;
            }
        }
        return left;
    }
}
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return n;
        vector<int> dp;
        dp.push_back(nums[0]);
        for(int i = 1; i < n; i++){
            if(dp.back() < nums[i]){  // 当前元素大于递增子序列的最后一个元素时,招安当前元素
                dp.push_back(nums[i]);
            }else{  // 找到递增子序列中第一个大于该元素的元素,更新为当前元素
                auto itr = lower_bound(dp.begin(), dp.end(), nums[i]);  
                *itr = nums[i];
            }
        }
        return dp.size();
    }
};

1143.最长公共子序列

给定两个字符串 text1text2,返回这两个字符串的最长公共子序列的长度。

解题思路:创建一个二维数组dp,其中dp[i][j]表示到第一个字符串位置i为止,第二个字符串位置j为止,最长公共子序列的长度。

遍历两个字符串,如指向的字符相同,则原公共子序列长度+1;若不同,则比较(i-1, j)和(i, j-1)处元素大小,取较大值。

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

🌟 背包问题

基本介绍

背包问题是一种组合优化的NP完全问题:有N个物品和一个容量为W的背包,每个物品都有自己的体积w和价值v,求拿哪些物品可以使得背包所装下物品的总价值最大。

如果限制每种物品只能选0个或者1个,则该问题成为0-1背包问题;如果不限定每种物品的数量,则成为无界背包问题或者完全背包问题

😎 0-1背包:限制每种物品只能选0个或者1个

定义一个二维数组dp存储最大价值,其中dp[i][j]表示遍历到了第i个物品,体积不超过j

  • 如果将该物品放入,则dp[i][j] = dp[i-1][j - weight[i-1]] + value[i-1]
  • 不放入,则取前i-1个物品时的最大价值即可,即dp[i][j] = dp[i-1][j]
  • 此外,还需考虑当前背包的容量能否满足装下该物品,之后再考虑装还是不装.

时间复杂度和空间复杂度都是O(NW)

public int knapsack(int[] weights, int[] values, int N, int W) {
    int[][] dp = new int[N+1][W+1];
    for(int i = 1; i <= N; i++){
        int w = weights[i-1], v = values[i-1];  // 第i个物品的体积和价值
        for(int j = 1; j <= W; j++){
            if(j >= w){  // 当前背包容量j大于物品的体积
                dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w] + v);
            }else{  // 当前背包容量不满足要求,无法装入物品
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[N][W];        
}

0-1背包的空间优化:假设i=2,其体积w=2,价值v=3,对于背包容量j,则dp[2][j] = max(dp[1][j], dp[1][j-2] + 3)。观察发现,后面取最大值时,依赖的总是上一排i=1的信息。因此,第一个维度可以去掉,简化为dp[j] = max(dp[j], dp[j-w] + v)。但每一列必须逆向遍历,保证dp[j]dp[j-w]为上一排时存储的信息。

public int knapsack(int[] weights, int[] values, int N, int W) {
    int[] dp = new int[W+1];
    for(int i = 1; i <= N; i++){  // 外层是所需体积/价值,内层是物品的体积/价值反向迭代
        int w = weights[i-1], v = values[i-1];  // 第i个物品的体积和价值
        for(int j = W; j >= w; j--){
			dp[j] = Math.max(dp[j], dp[j-w] + v);
        }
    }
    return dp[W];        
}

😎 完全背包:一个物品可拿多次

public int ksnapsack(int[] weights, int[] values, int N, int W){
    int[][] dp = new int[N+1][W+1];
    for(int i = 1; i <= N; i++){
        int w = weight[i-1], v = values[i-1];
        for(int j = 1; j <= W; j++){
            if (j >= w){
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-w] + v);  // 和 0-1背包 的区别仅仅是dp[i-1][j-w] ——> dp[i][j-w]
            }else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[N][W];
}

完全背包的空间优化:和0-1背包思路一样,通过移除第一维信息简化空间复杂度为O(W)。由于需要当前物品在第j-w列的信息,因此正向遍历

public int ksnapsack(int[] weights, int[] values, int N, int W){
    int[] dp = new int[W+1];
    for(int i = 1; i <= N; i++){  
        int w = weights[i-1], v = values[i-1];
        for(int j = w; j <= W; j++){   // 正向遍历
            dp[j] = Math.max(dp[j], dp[j-w] + v);
        }
    }
    return dp[W];
}

416.分割等和子集

给定一个只包含正整数非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

解题思路:转换为0-1背包问题,每个数字只能取0或者1次,使组成的和为数组总和的一半。

dp[i][j]表示对于前i个数字中能否达到总和的一半:

  • 不选第i个数字,dp[i][j] = dp[i-1][j]
  • 选第i个数字,dp[i][j] = dp[i-1][j-w]

只与上一排的信息有关,则可压缩空间复杂度。但要反向遍历数字大小

如果已经找到了一半,可以提前退出,加快速度。

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        if (n == 0) return false;  // 数组长度为0
        int sum = IntStream.of(nums).sum();
        if(sum % 2 == 1) return false;  //总和的一半不是偶数,无法分割
        int target = sum/2;

        boolean[] dp = new boolean[target+1];
        dp[0] = true;

        for(int i = 1; i <= n; i++){
            for(int j = target; j >= nums[i-1]; j--){  // 反向遍历
                dp[j] = dp[j] || dp[j-nums[i-1]];
            }
            if(dp[target]) return true;  // 已经找到了,提前退出
        }
        return dp[target];
    }
}

474.一和零

322.零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。你可以认为每种硬币的数量是无限的。

解题思路:因为每个硬币可以用无数次,所以零钱兑换可以看作完全背包问题。创建一个一维dp数组,dp[i]表示恰好装满容量为i的背包,最少用多少硬币;由于dp时要取最小值,我们将dp数组初始化为amount+2(i ≤ amount+1,因此即使每次是1,次数也小于amount+2)。dp[0]初始化为0!

class Solution {
    public int coinChange(int[] coins, int amount) {
        if(coins == null) return -1;
        int[] dp = new int[amount+1];
        Arrays.fill(dp, amount+2);
        dp[0] = 0;

        for(int i = 1; i <= amount; i++){  // 外层一般是所需体积/价值遍历,内层是物品的体积/价值正向迭代
            for(int coin: coins){
                if(i >= coin){  // 当前背包放的下该硬币
                    dp[i] = Math.min(dp[i], dp[i-coin]+1);
                }  
            }
        }
        if(dp[amount] == amount+2){  // 没找到
            return -1;
        }else{
            return dp[amount];
        }  
    }
}

🌟 字符串编辑

72.编辑距离

650.只有两个键的键盘

10.正则表达式匹配

🌟 股票交易

121.最多可以交易一次

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易(即买入和卖出一支股票各一次),设计一个算法来计算你所能获取的最大利润。你不能在买入股票前卖出股票。

解题思路:只能交易一次,则记录『今天买入的最小值』,计算『今天卖出的最大获利』,比较『每天的获利』,取最大值即可

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length < 2){
            return 0;
        }

        int ans = 0;
        for(int i=1; i < prices.length; i++){
            prices[0] = Math.min(prices[0], prices[i]);  // 记录到当天为止买入的最小值
            ans = Math.max(ans, prices[i]-prices[0]);   // 比较每天的获利,取最大值
        }
        return ans;
    }
}

122.可以交易无数次

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票

输入: [7,1,5,3,6,4]
输出: 7
解释:(5-1)+(6-3)=7

解题思路

【贪心算法】遍历整个股票交易日价格列表 price,所有上涨交易日都买卖(赚到所有利润),所有下降交易日都不买卖(永不亏钱):不考虑手续费,落袋为安,之后当天价格比前一天价格高,就卖出。连续上涨,可看做每天都进行买卖。pn-p1=(p2-p1)+(p3-p2)+...+(pn-pn-1);同一天可以进行多支股票的买入和卖出,但对同一只股票,只能买入或者卖出。

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;     
        for (int i = 1; i < prices.length; i++){  //遍历所有价格,如果当天价格比前一天高,就卖
            int tmp = prices[i] - prices[i-1]; 
            if (tmp > 0){
                profit += tmp;
            }
        }
        return profit;
    }
}

【动态规划】定义三维数组dp,其中dp[i][k][0] 表示第i天,操作了k次,未持有股票的最大利益

  • dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]) :前一天无股票、前一天有且卖出了

  • dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]):前一天有股票、前一天无且买入了

  • 由于k为无穷大,因此k这一维可以省略,定义状态dp[i][j]为第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-1][0]-prices[i]):当天持有股票

设定初始值,dp[0][0]=0未持有,dp[0][1]=-prices[i]持有股票

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if(len < 2){  // 1天时,只能买不能卖
            return 0;
        }
        
        // 定义状态数组,并初始化
        int[][] dp = new int[len][2];
        dp[0][0] = 0;  // 第0天未持有股票
        dp[0][1] = -prices[0];  // 第0天持有股票

        for(int i=1; i < len; 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-1][0]-prices[i]);    // 第i天持有股票
        }

        return dp[len-1][0];  // dp[len-1][0]必然大于dp[len-1][1]

    }
}

309.交易有冻结期

可以交易无数次,但卖出股票后无法在第二天买入股票 (即冷冻期为 1 天)

解题思路k为无穷大,且要隔一天才能买入/出,若第i天买,必须看第i-2天状态:

  • dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]):当天无股票
  • dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i]):当天有股票,此时前一天若无股票,需要用大前天时的收益买入
class Solution {
    public int maxProfit(int[] prices) {
        /*
            时间复杂度:O(N),空间复杂度:O(N)
        */
//        int days = prices.length;
//        int[][] dp = new int[days][2];
//
//        dp[0][0] = 0;
//        dp[0][1] = -prices[0];
//
//        for(int i = 1; i < days; i++){
//            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]); // 
//            if(i == 1){  // 此时木得i-2,单独考虑
//                dp[1][1] = Math.max(dp[i-1][1], - prices[i]);
//                continue;
//            }
//            dp[i][1] = Math.max(dp[i-1][1], dp[i-2][0] - prices[i]);
//        }
//        return dp[days-1][0];

        /*
            时间复杂度:O(N),空间复杂度:O(1)
        */
         int days = prices.length;
         int dp_i0 = 0, dp_i1 = Integer.MIN_VALUE;
         int dp_pre_0 = 0;     // 前天的max_profit,dp[i-2][0]
        
         for(int i = 0; i < days; i++){
             int tmp = dp_i0;  // 昨天的max_profit
             dp_i0 = Math.max(dp_i0, dp_i1 + prices[i]);
             dp_i1 = Math.max(dp_i1, dp_pre_0 - prices[i]);
             dp_pre_0 = tmp;
         }
         return dp_i0;
    }

714.交易有手续费

你可以无限次地完成交易,但是你每笔交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。

解题思路k为无穷大,且买卖时有手续费,则:

  • dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]):当天无股票
  • dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i] - fee):当天有股票,此时前一天若无股票,买入还需减去手续费
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int days = prices.length;
        if(prices == null || prices.length < 2){
            return 0;
        }

        /**
         * 时间复杂度:O(N),空间复杂度:O(N)
         */
//        int[][] dp = new int[days][2];
//        dp[0][0] = 0;
//        dp[0][1] = -prices[0] - fee;  // 别忘了手续费
//
//        for(int i = 1; i < days; 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-1][0] - prices[i] - fee);
//        }
//        return dp[days-1][0];

        /**
         * 时间复杂度:O(N),空间复杂度:O(1)
         */
        int dp_i0 = 0, dp_i1 = Integer.MIN_VALUE;
        for (int i = 0; i < days; i++) {
            int tmp = dp_i0;
            dp_i0 = Math.max(dp_i0, dp_i1 + prices[i]);
            dp_i1 = Math.max(dp_i1, tmp - prices[i] - fee);
        }
        return dp_i0;

    }
}

123.最多可以完成交易两次

设计一个算法来计算你所能获取的最大利润,你最多可以完成两笔交易

解题思路:定义三维数组dp,其中dp[i][k][0] 表示第i天,操作了k次,未持有股票的最大利益

  • 买入再卖出算一次,因此买入时次数-1或者卖出时-1,别乱了

  • dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]) :前一天无股票、前一天有且卖出了

  • dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]):前一天有股票、前一天无且买入了

class Solution {
    public int maxProfit(int[] prices) {       
        /*
            时间复杂度:O(N),空间复杂度:O(N)
        */
        // int days = prices.length;
        // int max_k = 2;
        // int[][][] dp = new int[days][max_k+1][2];

        // // 开始遍历每个状态
        // for(int i = 0; i < days; i++){
        //     for(int k = 1;k <= max_k; k++){
        //         if(i == 0){
        //            dp[i][k][0] = 0;
        //            dp[i][k][1] = -prices[0];  // 第0天过后,最多进行了k1次交易,手头持有股票,最大收益应该为 负的第0天的价格
        //            continue;
        //        }
        //         dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
        //         dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
        //     }
        // }
        // return dp[days-1][max_k][0];  // 最后一天,完全交易完了,已无股票

        
        /*
        	max_k = 2,则可以对空间复杂度进行优化,则k=1或者2,直接枚举上方的dp方程即可
            时间复杂度:O(N),空间复杂度:O(1)
        */
        int dp_i20 = 0, dp_i21 = Integer.MIN_VALUE;
        int dp_i10 = 0, dp_i11 = Integer.MIN_VALUE;

        for(int price: prices){
            dp_i20 = Math.max(dp_i20, dp_i21 + price);
            dp_i21 = Math.max(dp_i21, dp_i10 - price);
            dp_i10 = Math.max(dp_i10, dp_i11 + price);
            dp_i11 = Math.max(dp_i11, - price);
        }
        return dp_i20;

    }
}

188.最多可以交易K次

解题思路:和k=2一样,定义三维数组dp,其中dp[i][k][0] 表示第i天,操作了k次,未持有股票的最大利益。

但当k比较大时,内存可能会爆。因此考虑k的大小限制:

  • 一次交易由买入和卖出构成,至少需要两天。所以说有效的限制 k 应该不超过 n/2,此时和k=2时一样;如果超过,就没有约束作用了,相当于 k = +infinity
class Solution {
    public int maxProfit(int k, int[] prices) {
        // dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
        // dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])

        int days = prices.length;
        if(prices == null || prices.length < 2){
            return 0;
        }

        if(k > days/2){  // 交易次数大于总天数的一半,相当于k=正无穷大
            return maxProfit_inf(prices); 
        }

        int[][][] dp = new int[days][k+1][2];

        for (int i = 0; i < days; i++) {
            for (int k1 = 0; k1 <= k; k1++) {
                // 处理i-1和k-1越界
                if(i == 0){
                    dp[i][k1][0] = 0;
                    dp[i][k1][1] = -prices[0];  // 第0天过后,最多进行了k1次交易,手头持有股票,最大收益应该为 负的第0天的价格
                    continue;
                }
                if(k1 == 0){  // 未进行交易 
                    dp[i][k1][0] = 0;   
                    dp[i][k1][1] = Integer.MIN_VALUE;  // Integer.MIN_VALUE 表示这种情况不存在
                    continue;
                }
                
                dp[i][k1][0] = Math.max(dp[i-1][k1][0], dp[i-1][k1][1] + prices[i]);
                dp[i][k1][1] = Math.max(dp[i-1][k1][1], dp[i-1][k1-1][0] - prices[i]);
            }
        }
        return dp[days-1][k][0];
    }

    public int maxProfit_inf(int[] prices) {
        int dp_i0 = 0,dp_i1 = Integer.MIN_VALUE;
        for (int i = 0; i < prices.length; i++) {
            int tmp = dp_i0;
            dp_i0 = Math.max(dp_i0, dp_i1 + prices[i]);
            dp_i1 = Math.max(dp_i1, tmp - prices[i]);
        }
        return dp_i0;
    }
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!