数组
算法
|
|
|
239

9617 字
|
1.5 小时

文章目录[隐藏]

数组

1. LeetCode 896. 单调数列

题目地址：LeetCode

image-20230728214502967

image-20230728214520228

/**
     * 一次遍历
     *
     * @param nums
     * @return
     */
    public boolean isMonotonic(int[] nums) {
        boolean inc = true, dec = true;
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                inc = false;
            }
            if (nums[i] < nums[i + 1]) {
                dec = false;
            }
        }
        return inc || dec;
    }

2. LeetCode 35. 搜索插入位置

题目地址：LeetCode

image-20230728214719966

image-20230728214728642

解题思路：

image-20230728215431494

image-20230728215444129

image-20230728215454337

image-20230728215517831

image-20230728215527485

/**
     * 二分查找
     *
     * @param nums
     * @param target
     * @return
     */
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

3. LeetCode 88. 合并两个有序数组

题目地址：LeetCode

image-20230728215907437

image-20230728215916827

/**
     * 逆向双指针
     *
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int k = m + n;
        for (int index = k - 1, nums1Index = m - 1, nums2Index = n - 1; index >= 0; index--) {
            if (nums1Index < 0) {
                //nums1已经取完，完全取nums2的值即可
                nums1[index] = nums2[nums2Index--];
            } else if (nums2Index < 0) {
                //nums2已经取完，完全取nums1的值即可
                break;
            } else if (nums1[nums1Index] > nums2[nums2Index]) {
                //nums1的元素值大于nums2，取nums1值
                nums1[index] = nums1[nums1Index--];
            } else {
                //nums2的元素值大于nums1，取nums2值
                nums1[index] = nums2[nums2Index--];
            }
        }
    }

4. LeetCode 27. 移除元素

题目地址：LeetCode

image-20230730213012163

image-20230730213025857

解题思路：

image-20230730215548078

  1. 初始化两个指针：slow 和 fast。这两个指针都从数组的开头（索引 0）开始
  2. 通过fast指针遍历数组，从第一个元素（索引 0）开始，向数组的末尾移动
  3. 对于fast指针当前指向的元素，检查它是否等于指定的值val
  4. 如果当前元素不等于val，说明我们要保留这个元素在修改后的数组中（因为我们要移除所有的val）。在这种情况下，将该元素复制到slow指针的位置，然后将slow指针移动到下一个位置。这一步骤有效地将非val元素覆盖到数组中原来val的位置
  5. 如果当前元素等于val，则直接跳过，不做任何处理，然后将fast指针移到下一个元素的位置，slow指针保持不动
  6. 重复步骤 4 和 5，直到fast指针到达数组的末尾
  7. 此时slow指针的值表示修改后的新数组的长度，其中所有的val元素已经被移除
  8. 返回slow的值，即为修改后的数组中不包含val的元素个数
/**
     * 快慢双指针
     *
     * @param nums 待处理数组
     * @param val  待删元素
     * @return 不重复元素个数
     */
    public int removeElement(int[] nums, int val) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }

5. LeetCode 26. 删除有序数组中的重复项

题目地址：LeetCode

image-20230730215736966

image-20230730215750409

解题思路：

  1. 初始化两个指针：slow 和 fast。其中，slow 表示可以放入新元素的位置，初始值为 1（因为索引为 0 的元素不需要管，可以保留在新数组中）
  2. 使用循环来模拟快指针的移动，fast 指针从索引 0 开始，向数组的末尾移动
  3. 对于每个 fast 指针指向的元素，检查它是否与上一个位置（slow - 1索引处）的元素相同
  4. 如果当前元素与上一个元素不相同，说明该元素是新的不重复元素，应该放入新数组中。将该元素复制到 slow 指针的位置，然后将 slow 指针移动到下一个位置
  5. 如果当前元素与上一个元素相同，则跳过该元素，不将其放入新数组中，继续考察下一个元素
  6. 重复步骤 4 和 5，直到 fast 指针遍历完整个数组
  7. 此时 slow 指针的值表示新数组的长度，其中包含了不重复的元素
  8. 返回 slow 的值作为新数组的长度
/**
     * 快慢双指针
     *
     * @param nums 待处理数组
     * @return
     */
    public static int removeDuplicates(int[] nums) {
        //slow表示可以放入新元素的位置，索引为0的元素不用管
        int slow = 1;
        //循环起到了快指针的作用
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != nums[slow - 1]) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }

6. LeetCode 905. 按奇偶排序数组

题目地址：LeetCode

image-20230801191941649

image-20230801192024487

解题思路：

image-20230801193619993

  1. 创建两个指针 left 和 right，分别初始化为数组的开头和结尾
  2. 目标是将所有偶数移到数组的左侧，将所有奇数移到数组的右侧
  3. 进入一个 while 循环，循环条件是 left 小于 right
  4. 在循环中：
    • 检查索引 left 处的数是否为奇数（nums[left] % 2 == 1），以及索引 right 处的数是否为偶数（nums[right] % 2 == 0）
    • 如果上述条件为真，则交换索引 left 和 right 处的数，这样就把偶数移到了左侧，把奇数移到了右侧
    • 如果索引 left 处的数是偶数，则将 left 增加1；如果索引 right 处的数是奇数，则将 right 减少1。这样我们可以继续向数组中心移动，继续交换偶数和奇数
  5. 当 while 循环结束时，数组将按照奇偶性进行了分区，偶数位于数组的左侧，奇数位于数组的右侧
  6. 返回排序后的数组
/**
     * 对撞型双指针
     *
     * @param nums
     * @return
     */
    public int[] sortArrayByParity(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            if (nums[left] % 2 > nums[right] % 2) {
                int temp = nums[right];
                nums[right] = nums[left];
                nums[left] = temp;
            }
            if (nums[left] % 2 == 0) left++;
            if (nums[right] % 2 == 1) right--;
        }
        return nums;
    }

7. LeetCode 189. 轮转数组

题目地址：LeetCode

image-20230801194728585

解题思路：

image-20230801200043716

public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }

    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[end];
            nums[end] = nums[start];
            nums[start] = temp;
            start++;
            end--;
        }
    }

8. LeetCode 228. 汇总区间

题目地址：LeetCode

image-20230802215508636

image-20230802215613085

解题思路：

慢指针指向每个区间的起始位置，快指针从慢指针位置开始向后遍历直到不满足连续递增（或快指针达到数组边界），则当前区间结束；然后将 slow 指向更新为 fast + 1，作为下一个区间的开始位置，fast 继续向后遍历找下一个区间的结束位置，如此循环，直到输入数组遍历完毕

/**
     * 快慢指针
     *
     * @param nums
     * @return
     */
    public List<String> summaryRanges(int[] nums) {
        ArrayList<String> res = new ArrayList<>();
        // slow 初始指向第 1 个区间的起始位置
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            // fast 向后遍历，直到不满足连续递增(即 nums[fast] + 1 != nums[fast + 1])
            // 或者 fast 达到数组边界，则当前连续递增区间 [slow, fast] 遍历完毕，将其写入结果列表
            if (fast + 1 == nums.length || nums[fast] + 1 != nums[fast + 1]) {
                // 将当前区间 [slow, fast] 写入结果列表
                StringBuilder sb = new StringBuilder();
                sb.append(nums[slow]);
                if (slow != fast) {
                    sb.append("->").append(nums[fast]);
                }
                res.add(sb.toString());
                // 将 slow 指向更新为 fast + 1，作为下一个区间的起始位置
                slow = fast + 1;
            }
        }
        return res;
    }

9. 剑指 Offer 05. 替换空格

题目地址：剑指 Offer

image-20230802222536210

/**
     * 字符串拼接
     *
     * @param s
     * @return
     */
    public String replaceSpace(String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ' ') {
                sb.append("%20");
            } else {
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }

10. LeetCode 169. 多数元素

题目地址：LeetCode

image-20231026162610466

解题思路（链接）：

  1. 初始化：票数统计 votes = 0， 众数 x

  2. 循环：遍历数组 nums 中的每个数字 num

    • 当票数 votes 等于 0，则假设当前数字 num 是众数

    • 当 num == x 时，票数 votes 自增 1；当 num != x 时，票数 votes 自减 1

  3. 返回值：返回 x 即可

class Solution {
    public int majorityElement(int[] nums) {
        int x = 0, votes = 0;
        for(int num : nums){
            if(votes == 0) x = num;
            votes += num == x ? 1 : -1;
        }
        return x;
    }
}

11. LeetCode 136. 只出现一次的数字

题目地址：LeetCode

image-20231026163525659

解题思路：

image-20231026165146047

异或运算满足交换律 a⊕b = b⊕a，即以上运算结果与 nums 的元素顺序无关。代码如下：

class Solution {
    public int singleNumber(int[] nums) {
        int flag = 0;
        for(int num : nums) flag ^= num;
        return flag;
    }
}

12. LeetCode 75. 颜色分类

题目地址：LeetCode

image-20231027214018416

解题思路1：

img

  1. index 位置为 2 进行交换后为什么只进行 right--，而不用 index++ 呢？

    因为我们 right 位置交换过来的元素可能是 0，也可能是 1。如果是 0 自然没问题，但是如果是 1 则执行 index++ 就将 1 跳过了无法处理了

  2. nums[index] == 2 判断后为什么还要判断 index != right?

    因为首先 nums[index] == 2 并且 index == right 则说明指向同一位置且不用交换了

class Solution {
    public void sortColors(int[] nums) {
        int left = 0, right = nums.length - 1;
        int index = 0;
        while(index <= right){
            if(nums[index] == 0){
                swap(nums,index++,left++);
            } else if(nums[index] == 2 && index != right){
                swap(nums,index,right--);
            } else{
                index++;
            }
        }
    }

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

解题思路2：

  1. 首先，所有数都 ≤2，那么索性把所有数组置为 2
  2. 然后遇到所有 ≤1 的，就再全部置为 1，覆盖了错误的 2，这时候所有 2 的位置已经正确
  3. 最后所有 ≤0 的全部置为 0，也就覆盖了一些错误的 1，这时候，0 和 1 的位置都正确
class Solution {
    public void sortColors(int[] nums) {
        int n0 = 0, n1 = 0;
        for(int i = 0; i < nums.length; i++){
            int num = nums[i];
            nums[i] = 2;
            if(num < 2) nums[n1++] = 1;
            if(num < 1) nums[n0++] = 0;
        }
    }
}

13. LeetCode 268. 丢失的数字

题目地址：LeetCode

image-20231116223057113

解题思路：

利用 nums 的数值范围为 [0,n]，且只有一个值缺失，我们可以直接开一个大小为 n+1 的数组充当哈希表，进行计数，没被统计到的数值即是答案

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        boolean[] hash = new boolean[n + 1];
        for(int i = 0; i < n; i++) hash[nums[i]] = true;
        for(int i = 0; i < n; i++) {
            if(!hash[i]) return i;
        }
        return n;
    }
}

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

题目地址：LeetCode

image-20231117170424678

快速排序

public void quickSort(int[] arr, int low, int high) {
  // low,high 为每次处理数组时的首、尾元素索引

  //当low==high是表示该序列只有一个元素，不必排序了
  if (low == high) {
      return;
  }
  // 选出哨兵元素和基准元素。这里左边的哨兵元素也是基准元素
  int i = low, j = high, base = arr[low];
  while (i < j) {
      //右边哨兵从后向前找
      while (arr[j] >= base && i < j) {
          j--;
      }
      //左边哨兵从前向后找
      while (arr[i] <= base && i < j) {
          i++;
      }
      swap(arr,i,j);  //交换元素
  }
  swap(arr,low,j);  //基准元素与右哨兵交换

  //递归调用，排序左子集合和右子集合
  quickSort(arr,low,j-1);  
  quickSort(arr,j+1,high);

}

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

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        return quickSelect(nums, 0, n - 1, n - k);
    }

    private int quickSelect(int[] nums, int low, int high, int index){
        if(low == high) return nums[index];
        int i = low - 1, j = high + 1, base = nums[low];
        while(i < j){
            do i++; while(nums[i] < base);
            do j--; while(nums[j] > base);
            if(i < j){
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        if(index <= j) return quickSelect(nums, low, j, index);
        else return quickSelect(nums, j + 1, high, index);
    }
}

15. LeetCode 852. 山脉数组的峰顶索引

题目地址：LeetCode

image-20231114204718633

解题思路：

  1. 初始化变量：
    • n：数组 arr 的长度
    • left 和 right：分别是二分查找的左右指针，初始时指向数组的第二个元素和倒数第二个元素，因为峰值不会出现在数组的两端
    • ans：存储答案，即峰值的索引
  2. 二分查找：
    • 循环条件是 left <= right，表示还有元素待检查
    • 计算中间索引 mid
    • 检查 arr[mid] 是否大于其右侧的元素 arr[mid + 1]：
      • 如果是，说明峰值在左侧或就是 mid 本身，因此更新 ans 为 mid，并将 right 移动到 mid - 1 继续在左侧查找
      • 如果不是，说明峰值在右侧，将 left 移动到 mid + 1 继续在右侧查找
  3. 返回结果：
    • 循环结束后，ans 存储的就是峰值的索引
class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int n = arr.length;
        int left = 1, right = n - 2, ans = 0;

        while(left <= right){
            int mid = left + ((right - left) >> 1);
            if(arr[mid] > arr[mid + 1]){
                ans = mid;
                right = mid - 1;
            } else{
                left = mid + 1;
            }
        }
        return ans;
    }
}

16. LeetCode 153. 寻找旋转排序数组中的最小值

题目地址：LeetCode

image-20231114211434253

解题思路：

左边界为 low，右边界为 high，区间的中点为 pivot，最小值就在该区间内。我们将中轴元素 nums[pivot] 与右边界元素 nums[high] 进行比较，可能会有以下的两种情况：

  1. nums[pivot] < nums[high]，如下图所示，这说明 nums[pivot] 是最小值右侧的元素，因此我们可以忽略二分查找区间的右半部分

fig2

  1. nums[pivot] > nums[high]，如下图所示，这说明 nums[pivot] 是最小值左侧的元素，因此我们可以忽略二分查找区间的左半部分

    fig3

    由于数组不包含重复元素，并且只要当前的区间长度不为 1，pivot 就不会与 high 重合；而如果当前的区间长度为 1，这说明我们已经可以结束二分查找了。因此不会存在 nums[pivot] = nums[high] 的情况

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;

        while(left < right){
            int mid = left + ((right - left) >> 1);
            if(nums[mid] < nums[right]){
                right = mid;
            } else{
                left = mid + 1;
            }
        }
        return nums[left];
    }
}

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

题目地址：LeetCode

image-20231114220854966

解题思路：

左边界为 low，右边界为 high，区间的中点为 pivot，最小值就在该区间内。我们将中轴元素 nums[pivot] 与右边界元素 nums[high] 进行比较，可能会有以下的三种情况：

  1. nums[pivot] < nums[high]，如下图所示，这说明 nums[pivot] 是最小值右侧的元素，因此我们可以忽略二分查找区间的右半部分

    fig2

  2. nums[pivot] > nums[high]，如下图所示，这说明 nums[pivot] 是最小值左侧的元素，因此我们可以忽略二分查找区间的左半部分

    fig3

  3. nums[pivot] == nums[high]，如下图所示，由于重复元素的存在，我们并不能确定 nums[pivot] 究竟在最小值的左侧还是右侧，因此我们不能莽撞地忽略某一部分的元素。我们唯一可以知道的是，由于它们的值相同，所以无论 nums[high] 是不是最小值，都有一个它的「替代品」nums[pivot]，因此我们可以忽略二分查找区间的右端点

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

18. LeetCode 643. 子数组最大平均数 I

题目地址：LeetCode

image-20231118090845149

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int n = nums.length;
        int sum = 0;
        for(int i = 0; i < k; i++){
            sum += nums[i];
        }
        int maxSum = sum;
        for(int i = k; i < n; i++){
            sum += nums[i] - nums[i - k];
            maxSum = Math.max(maxSum,sum);
        }
        return (double) maxSum / k;
    }
}

19. LeetCode 674. 最长连续递增序列

题目地址：LeetCode

image-20231118091100189

解题思路：

  1. 如果当前遍历到的元素比它左边的那一个元素要严格大，right 就增加
  2. 否则就将 left 跳到 right 的起始位置，重新开始计算
class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int res = 0;
        int left = 0, right = 0;
        while(right < nums.length){
            if(right > 0 && nums[right - 1] >= nums[right]){
                left = right;
            }
            right++;
            res = Math.max(res, right - left);
        }
        return res;
    }
}

20. LeetCode 3. 无重复字符的最长子串

题目地址：LeetCode

image-20231119093903301

解题思路：

  1. 哈希表 map 统计：指针 j 遍历字符 s，哈希表统计字符 s[j] 最后一次出现的索引

  2. 更新左指针 i：根据上轮左指针 i 和 map[s[j]]，每轮更新左边界 i，保证区间 [i+1,j] 内无重复字符且最大。i = max(i,map[s[j]])

  3. 更新结果 res：取上轮 res 和本轮双指针区间 [i + 1,j] 的宽度（即j-i）中的最大值。res = max(res,j-i)

    image-20231119101710484

    image-20231119101731656

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character,Integer> map = new HashMap<>();
        int i = -1, res = 0, len = s.length();
        for(int j = 0; j < len; j++){
            if(map.containsKey(s.charAt(j))){
                i = Math.max(i, map.get(s.charAt(j))); // 更新左指针 i
            }
            map.put(s.charAt(j),j); // 哈希表记录
            res = Math.max(res, j - i); // 更新结果
        }
        return res;
    }
}

21. LeetCode 209. 长度最小的子数组

题目地址：LeetCode

image-20231119202908186

解题思路：

  1. 把数组中的元素不停的入队，直到总和大于等于 target 为止
  2. 接着记录下队列中元素的个数，然后再不停的出队，直到队列中元素的和小于 target 为止
    • 如果不小于 target，也要记录下队列中元素的个数，这个个数其实就是不小于 target 的连续子数组长度，我们要记录最小的即可
  3. 接着再把数组中的元素添加到队列中，重复上面的操作，直到数组中的元素全部使用完为止
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0, right = 0, sum = 0, min = Integer.MAX_VALUE;
        while(right < nums.length){
            sum += nums[right++];
            while(sum >= target){
                min = Math.min(min, right - left);
                sum -= nums[left++];
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }
}

22. LeetCode 11. 盛最多水的容器

题目地址：LeetCode

image-20231121102255359

解题思路：

设两指针 i、j，指向的水槽板高度分别为 h[i]、h[j]，此状态下水槽面积为S(i,j) 。由于可容纳水的高度由两板中的短板决定，因此可得如下面积公式 ：S(i,j) = min(h[i],h[j])×(j−i)

image-20231121104256830

在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽底边宽度−1 变短：

  • 若向内移动短板，水槽的短板 min(h[i],h[j]) 可能变大，因此下个水槽的面积可能增大
  • 若向内移动长板，水槽的短板 min(h[i],h[j]) 不变或变小，因此下个水槽的面积一定变小

因此，只要初始化双指针分列水槽左右两端，循环每轮将短板向内移动一格，并更新面积最大值，直到两指针相遇时跳出；即可获得最大面积

class Solution {
    public int maxArea(int[] height) {
        int i = 0, j = height.length - 1, res = 0;
        while(i < j){
            res = height[i] < height[j] ?
                Math.max(res, (j - i) * height[i++]) :
                Math.max(res, (j - i) * height[j--]);
        }
        return res;
    }
}

23. LeetCode 567. 字符串的排列

题目地址：LeetCode

image-20231121104739161

解题思路：

由于排列不会改变字符串中每个字符的个数，所以只有当两个字符串每个字符的个数均相等时，一个字符串才是另一个字符串的排列

  1. 根据这一性质，记 s1 的长度为 len1,我们可以遍历 s2 中的每个长度为 len1 的子串，判断子串和 s1 中每个字符的个数是否相等，若相等则说明该子串是 s1 的一个排列
  2. 使用两个数组 char1 和 char2,char1 统计 s1 中各个字符的个数，char2 统计当前遍历的子串中各个字符的个数
  3. 由于需要遍历的子串长度均为 len1，我们可以使用一个固定长度为 len1 的滑动窗口来维护 char2：
    • 滑动窗口每向右滑动一次，就多统计一次进入窗口的字符，少统计一次离开窗口的字符
    • 然后，判断 char1 是否与 char2 相等，若相等则意味着 s1 的排列之一是 s2 的子串
class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int len1 = s1.length(), len2 = s2.length();
        if(len1 > len2) return false;

        int[] char1 = new int[26];
        int[] char2 = new int[26]; 
        for(int i = 0; i < len1; i++){
            char1[s1.charAt(i) - 'a']++;
            char2[s2.charAt(i) - 'a']++;
        }
        if(Arrays.equals(char1,char2)) return true;

        for(int i = len1; i < len2; i++){
            char2[s2.charAt(i) - 'a']++;
            char2[s2.charAt(i - len1) - 'a']--;
            if(Arrays.equals(char1,char2)) return true;
        }
        return false;
    }
}

24. LeetCode 455. 分发饼干

题目地址：LeetCode

image-20231122114813129

解题思路：

这里既要满足小孩的胃口，也不要造成饼干尺寸的浪费。大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子，那么就应该优先满足胃口大的。这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩

所以，这里可以使用贪心策略，先将饼干数组和小孩数组排序。 然后从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量就可以了。也就是这样：

image.png

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int count = 0, j = s.length - 1;
        for(int i = g.length - 1; i >= 0; i--){
            if(j >= 0 && g[i] <= s[j]){
                count++;
                j--;
            }
        }
        return count;
    }
}

25. LeetCode 860. 柠檬水找零

题目地址：LeetCode

image-20231122125905932

解题思路：

由于顾客只可能给你三个面值的钞票，而且我们一开始没有任何钞票，因此我们拥有的钞票面值只可能是5美元，10美元和20美元三种。基于此，我们可以进行如下的分类讨论:

  • 5美元，由于柠檬水的价格也为5美元，因此我们直接收下即可
  • 10美元，我们需要找回5美元，如果没有5美元面值的钞票，则无法正确找零
  • 20美元，我们需要找回15美元，此时有两种组合方式，一种是一张10美元和5美元的钞票，一种是 3 张5美元的抄票，如果两种组合方式都没有，则无法正确找零。当可以正确找零时，两种找零的方式中我们更倾向于第一种，即如果存在5美元和10美元，我们就按第一种方式找零，否则按第二种方式找零，因为需要使用5美元的找零场景会比需要使用10美元的找零场景多，我们需要尽可能保留5美元的钞票

基于此，我们维护两个变量 five 和 ten 表示当前手中拥有的5美元和10美元钞票的张数，从前往后遍历数组分类讨论即可

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0, ten = 0;
        for(int bill : bills){
            if(bill == 5){
                five++;
            } else if(bill == 10){
                if(five == 0){
                    return false;
                }
                five--;
                ten++;
            } else{
                if(five > 0 && ten > 0){
                    five--;
                    ten--;
                } else if(five >= 3){
                    five -= 3;
                } else{
                    return false;
                }
            }
        }
        return true;
    }
}

26. LeetCode 135. 分发糖果

题目地址：LeetCode

image-20231123100329731

解题思路：

我们可以将「相邻的孩子中，评分高的孩子必须获得更多的糖果」这句话拆分为两个规则，分别处理

  • 左规则：当 ratings[i - 1] < ratings[i] 时，i 号学生的糖果数量将比 i-1 号孩子的糖果数量多
  • 右规则：当 ratings[i] > ratings[i + 1] 时，i 号学生的糖果数量将比 i+1 号孩子的糖果数量多

我们遍历该数组两次，处理出每一个学生分别满足左规则或右规则时，最少需要被分得的糖果数量。每个人最终分得的糖果数量即为这两个数量的最大值

具体地，以左规则为例：我们从左到右遍历该数组，假设当前遍历到位置 i,如果有 ratings[i - 1] < ratings[i] 那么 i 号学生的糖果数量将比 i-1 号孩子的糖果数量多，我们令 left[i] = left[i - 1] + 1 即可，否则我们令 left[i] = 1

在实际代码中，我们先计算出左规则 left 数组，在计算右规则的时候只需要用单个变量记录当前位置的右规则，同时计算答案即可

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

27. LeetCode 252. 会议室

题目地址：LeetCode

给定一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [start, end] ，请你判断一个人是否能够参加这里面的全部会议

示例 1：

输入: intervals = [[0,30],[15,20],[5,10]]

解释: 存在重叠区间，一个人在同一时刻只能参加一个会议

解题思路：

image.png

因为一个人在同一时刻只能参加一个会议，因此题目实质是判断是否存在重叠区间，将区间按照会议开始时间进行排序，然后遍历一遍判断后面的会议开始的时候是否前面的还没有结束即可。也就是上图中如果出现重叠的部分就直接返回 false 即可

public boolean canAttendMeetings(int[][] intervals) {
        // 将区间按照会议开始实现升序排序
        Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
        // 遍历会议，如果下一个会议的开始时间比前一个会议的结束时间小，返回 false
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < intervals[i - 1][1]) {
                return false;
            }
        }
        return true;
    }

28. LeetCode 56. 合并区间

题目地址：LeetCode

image-20231123102232414

解题思路：

由于 res 的长度和原数组 intervals 的长度一样（这是为了处理最坏情况，即没有区间可以合并），但实际使用的长度可能小于这个值。在我们的例子中，实际合并后的区间数是 3，所以我们需要返回 res 的前 3 个元素。这就是 Arrays.copyOf(res, idx + 1) 的作用，它创建一个新数组，只包含 res 中的前 idx + 1 个元素。在这个例子中，idx = 2（因为有三个合并后的区间），所以返回的是 res 的前 3 个元素

class Solution {
    public int[][] merge(int[][] intervals) {
        // 先按照区间起始位置排序
        Arrays.sort(intervals,(v1,v2) -> v1[0] - v2[0]);

        int[][] res = new int[intervals.length][2];
        int idx = -1;
        // 遍历区间
        for(int[] interval : intervals){
            // 如果结果数组是空的，或者结果数组中最后区间的终止位置 < 当前区间的起始位置
            // 则不合并，直接将当前区间加入结果数组
            if(idx == -1 || res[idx][1] < interval[0]){
                res[++idx] = interval;
            } else{
                // 反之将当前区间合并至结果数组的最后区间
                res[idx][1] = Math.max(res[idx][1],interval[1]);
            }
        }
        return Arrays.copyOf(res,idx + 1);
    }
}

29. LeetCode 57. 插入区间

题目地址：LeetCode

image-20231124212431314

解题思路：

image.png

  1. 首先将新区间左边且相离的区间加入结果集（遍历时，如果当前区间的结束位置小于新区间的开始位置，说明当前区间在新区间的左边且相离）
  2. 接着判断当前区间是否与新区间重叠，重叠的话就进行合并，直到遍历到当前区间在新区间的右边且相离，将最终合并后的新区间加入结果集
  3. 最后将新区间右边且相离的区间加入结果集
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int idx = 0, i = 0, n = intervals.length;
        int[][] res = new int[n + 1][2];

        // 1. 首先将新区间左边且相离的区间加入结果集
        while(i < n && intervals[i][1] < newInterval[0]){
            res[idx++] = intervals[i++];
        }
        // 2. 判断当前区间是否与新区间重叠，重叠的话就进行合并，直到遍历到当前区间在新区间的右边且相离
        while(i < n && intervals[i][0] <= newInterval[1]){
            newInterval[0] = Math.min(intervals[i][0],newInterval[0]);
            newInterval[1] = Math.max(intervals[i][1],newInterval[1]);
            i++;
        }
        // 3. 将最终合并后的新区间加入结果集
        res[idx++] = newInterval;
        // 4. 最后将新区间右边且相离的区间加入结果集
        while(i < n){
            res[idx++] = intervals[i++];
        }
        return Arrays.copyOf(res,idx);
    }
}

30. LeetCode 763. 划分字母区间

题目地址：LeetCode

image-20231125203440744

解题思路：

  1. 首先，统计每一个字符最后出现的位置

  2. 然后，从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

    image.png
class Solution {
    public List<Integer> partitionLabels(String s) {
        int n = s.length();
        int[] end = new int[26];
        for(int i = 0; i < n; i++){
            end[s.charAt(i) - 'a'] = i;
        }

        List<Integer> list = new ArrayList<>();
        int idx = 0, last = -1;
        for(int i = 0; i < n; i++){
            idx = Math.max(idx,end[s.charAt(i) - 'a']);
            if(i == idx){
                list.add(i - last);
                last = i;
            }
        }
        return list;
    }
}

31. LeetCode 134. 加油站

题目地址：LeetCode

image-20231125210338860

解题思路：

示例给的两个数组只是代表从当前站可以提供多少油料，以及从前一个位置过来需要消耗多少油料，因为是环。所以这里 gas[0] = 1 和 cost[0] = 3 就表示第一个站有 1 升汽油，从第一个站到第二个站需要消耗 3 升汽油

很显然在第一个站只能加 1 升汽油，但是从第一到第二个站需要消耗 3 升汽油，因此不能从第一个站开始走。为此我们可以从第二个，第三个、第四个开始，因此我们想到了暴力解法，如下图所示：

image-20231125213205211

我们一直向后找，只要能找到就行，这里很明显的问题就是需要大量的重复计算，我们来优化一下

  1. 首先，如果总油量减去总消耗大于等于零，那么应该能跑完一圈，具体到每一段就是各个加油站的剩油量 rest[i] 相加一定是大于等于零的
  2. 每个加油站的剩余量 rest[i] 为 gas[i] - cost[i]。i 从 0 开始累加 rest[i]，和记为 curSum，一旦 curSum 小于零，说明 [0, i] 区间都不能作为起始位置，起始位置必须从 i+1 开始重新算，只有这样才能保证我们有可能完成
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int curSum = 0, totalSum = 0, start = 0;

        for(int i = 0; i < gas.length; i++){
            curSum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i];
            if(curSum < 0){
                start = i + 1;
                curSum = 0;
            }
        }
        if(totalSum < 0) return -1;
        return start;
    }
}

32. LeetCode 39. 组合总和

题目地址：LeetCode

image-20231126094957079

解题思路：

img

class Solution {
    // 记录答案
    List<List<Integer>> res = new ArrayList<>();
    // 记录当前正在访问的路径
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(candidates, 0, target);
        return res;
    }

    private void dfs(int[] c, int u, int target){
        if(target < 0) return;

        if(target == 0){
            res.add(new ArrayList(path));
            return;
        }
        for(int i = u; i < c.length; i++){
            if(c[i] <= target){
                path.add(c[i]);
                // 因为可以重复使用，所以还是 i
                dfs(c, i, target - c[i]);
                // 回溯
                path.remove(path.size() - 1);
            }
        }
    }
}

33. LeetCode 131. 分割回文串

题目地址：LeetCode

image-20231126101648782

解题思路：

img

class Solution {
    List<List<String>> res = new ArrayList<>();
    List<String> path = new ArrayList<>();

    public List<List<String>> partition(String s) {
        dfs(s, 0);
        return res;
    }

    private void dfs(String s, int start){
        // 如果起始位置大于s的大小，说明找到了一组分割方案
        if(start >= s.length()){
            res.add(new ArrayList(path));
            return;
        }

        for (int i = start; i < s.length(); i++) {
            // 如果是回文子串，则记录
            if (isPalindrome(s, start, i)) {
                String str = s.substring(start, i + 1);
                path.add(str);
            } else {
                continue;
            }
            // 起始位置后移，保证不重复
            dfs(s, i + 1);
            path.remove(path.size() - 1);
        }
    }

    //判断是否是回文串
    private boolean isPalindrome(String s, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }
}

34. LeetCode 78. 子集

题目地址：LeetCode

image-20231128111414882

解题思路：

img

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        if(nums.length == 0){
            return res;
        }
        subsetsHelper(nums, 0);
        return res;
    }

    private void subsetsHelper(int[] nums, int start){
        res.add(new ArrayList(path));
        if(start >= nums.length){
            return;
        }
        for(int i = start; i < nums.length; i++){
            path.add(nums[i]);
            subsetsHelper(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

35. LeetCode 46. 全排列

题目地址：LeetCode

image-20231128190825961

解题思路：

img

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;

    public List<List<Integer>> permute(int[] nums) {
        if(nums.length == 0){
            return res;
        }
        used = new boolean[nums.length];
        permuteHelper(nums);
        return res;
    }

    private void permuteHelper(int[] nums){
        if(path.size() == nums.length){
            res.add(new ArrayList(path));
            return;
        }
        for(int i = 0; i < nums.length; i++){
            if(used[i]) continue;
            used[i] = true;
            path.add(nums[i]);
            permuteHelper(nums);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

36. LeetCode 784. 字母大小写全排列

题目地址：LeetCode

image-20231129102334137

解题思路：

image.png

class Solution {
    public List<String> letterCasePermutation(String s) {
        List<String> ans = new ArrayList<>();
        dfs(s.toCharArray(), 0, ans);
        return ans;
    }

    private void dfs(char[] arr, int pos, List<String> res){
        while(pos < arr.length && Character.isDigit(arr[pos])){
            pos++;
        }
        if(pos == arr.length){
            res.add(new String(arr));
            return;
        }
        arr[pos] ^= 32;
        dfs(arr, pos + 1, res);
        arr[pos] ^= 32;
        dfs(arr, pos + 1, res);
    }
}

37. LeetCode 79. 单词搜索

题目地址：LeetCode

image-20231129105241001

解题思路：

  • 递归参数：当前元素在矩阵 board 中的行列索引 i 和 j，当前目标字符在 word 中的索引 k

  • 终止条件：

    • 返回 false：

    1. 行或列索引越界

    2. 当前矩阵元素与目标字符不同

    3. 当前矩阵元素已访问过（同 2）

    • 返回 true：k = len(word) - 1，即字符串 word 已全部匹配

  • 递推公式分析：

    1. 标记当前矩阵元素：将 board[i][j] 修改为空字符 ''，代表此元素已访问过，防止之后搜索时重复访问
    2. 搜索下一单元格：朝当前元素的下、上、右、左四个方向开启下层递归，使用或连接（代表只需找到一条可行路径就直接返回，不再做后续 DFS）,并记录结果至 res
    3. 还原当前矩阵元素：将 board[i][j] 元素还原至初始值，即 word[k]

  • 返回值：返回布尔量 res，代表是否搜索到目标字符串

    使用空字符（Python:''，Java/C++:'\0'）做标记是为了防止标记字符与矩阵原有字符重复。当存在重复时，此算法会将矩阵原有字符认作标记字符，从而出现错误

class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[i].length; j++){
                if(dfs(board, words, i, j, 0)) return true;
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, char[] word, int i, int j, int k){
        if(i < 0 || i >= board.length || j < 0 || j >= board[i].length || board[i][j] != word[k]){
            return false;
        }
        if(k == word.length - 1) return true;
        board[i][j] = '\0';
        boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||
                      dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i, j - 1, k + 1);
        board[i][j] = word[k];
        return res;
    }
}

38. LeetCode 62. 不同路径

题目地址：LeetCode

image-20231130094220939

解题思路：

image.png

在上图中除了第一行和第一列都是 1 外，每个位置都是其左侧和上访的格子之和，那我可以用一个大小为 n 的一维数组来解决：

  1. 遍历数组，将一维数组所有元素赋值为 1

    image.png

  2. 再次从头遍历数组，除了第一个，后面每个位置是其原始值和前一个位置之和 dp[j] = dp[j] + dp[j - 1]

    image.png

  3. 重复第二步，除了第一个，后面每个位置仍然是其原始值和前一个位置之和

    image.png

  4. 继续循环，题目给的 m 是几就循环几次，要得到结果，输出最后一个位置的 15 就可以了

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

39. LeetCode 63. 不同路径 II

题目地址：LeetCode

image-20231204220322028

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

40. LeetCode 64. 最小路径和

题目地址：LeetCode

image-20231130103920335

解题思路：

image.png

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

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

41. LeetCode 120. 三角形最小路径和

题目地址：LeetCode

image-20231201205139647

解题思路：

假设我们有一个三角形如下：

    2
   3 4
  6 5 7
 4 1 8 3
  • 初始化 dp 为 [0, 0, 0, 0, 0]（因为三角形高度为4，所以长度为5）
  • 第一轮迭代（i = 3）:
    • dp 更新为 [4, 1, 8, 3, 0]
  • 第二轮迭代（i = 2）:
    • 第1个元素更新：dp[0] = min(dp[0], dp[1]) + triangle[2][0] = min(4, 1) + 6 = 7
    • 第2个元素更新：dp[1] = min(dp[1], dp[2]) + triangle[2][1] = min(1, 8) + 5 = 6
    • 第3个元素更新：dp[2] = min(dp[2], dp[3]) + triangle[2][2] = min(8, 3) + 7 = 10
    • dp 更新为 [7, 6, 10, 3, 0]
  • 第三轮迭代（i = 1）:
    • 第1个元素更新：dp[0] = min(dp[0], dp[1]) + triangle[1][0] = min(7, 6) + 3 = 9
    • 第2个元素更新：dp[1] = min(dp[1], dp[2]) + triangle[1][1] = min(6, 10) + 4 = 10
    • dp 更新为 [9, 10, 10, 3, 0]
  • 最后一轮迭代（i = 0）:
    • 第1个元素更新：dp[0] = min(dp[0], dp[1]) + triangle[0][0] = min(9, 10) + 2 = 11
    • dp 更新为 [11, 10, 10, 3, 0]
  • 返回 dp[0] 的值，即 11，这是从顶部到底部的最小路径和
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] dp = new int[n + 1];
        for(int i = n - 1; i >= 0; i--){
            for(int j = 0; j <= i; j++){
                dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
            }
        }
        return dp[0];
    }
}

42. LeetCode 322. 零钱兑换

题目地址：LeetCode

image-20231201213943548

class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max);
        dp[0] = 0;
        for(int i = 1; i <= amount; i++){
            for(int j = 0; j < coins.length; j++){
                if(coins[j] <= i){
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

43. LeetCode 300. 最长递增子序列

题目地址：LeetCode

image-20231202110209542

解题思路：

  • 状态定义：

    • dp[i] 的值代表以 nums[i] 结尾的最长子序列长度

  • 转移方程：设 j∈ [0,i)，考虑每轮计算新 dp[i] 时，遍历 [0,i) 列表区间，做以下判断:

    1. 当 nums[i] > nums[j] 时：nums[i] 可以接在 nums[j] 之后（此题要求严格递增），此情况下最长上升子序列长度为 dp[j + 1]
    2. 当 nums[i] <= nums[j] 时：nums[i] 无法接在 nums[j] 之后，此情况上升子序列不成立，跳过
    • 上述所有 情况1 下计算出的 dp[j + 1] 的最大值，为直到 i 的最长上升子序列长度(即dp[i])。实现方式为遍历 j 时，每轮执行 dp[i] = max(dp[i], dp[j] + 1)

  • 初始状态：

    • dp[i] 所有元素置 1，含义是每个元素都至少可以单独成为子序列，此时长度都为 1

  • 返回值：

    • 返回 dp 列表最大值，即可得到全局最长上升子序列长度

image-20231202113128579

image-20231202113140742

image-20231202113159692

class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int res = 0;
        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(res, dp[i]);
        }
        return res;
    }
}

44. LeetCode 279. 完全平方数

题目地址：LeetCode

image-20231202115151489

解题思路：

  1. 定义状态：
    • 定义一个数组 dp，其中 dp[i] 表示整数 i 可以由最少的完全平方数之和组成。例如，dp[13] 将是组成整数 13 所需的最少完全平方数的数量
  2. 状态转移方程：
    • 对于每个数 i（从 1 到 n），遍历所有可能的完全平方数 j*j（其中 j*j <= i），并更新 dp[i] 为所有 dp[i - j*j] + 1 中的最小值。这里的 +1 表示加上 j*j 这个完全平方数
  3. 初始化：
    • 初始化 dp[0] 为 0，因为 0 可以视为 0 个平方数的和。
  4. 填充 DP 表：
    • 按顺序计算 dp[1] 到 dp[n] 的值。每次计算 dp[i]，都检查所有小于或等于 i 的 j*j，并在这些值中找到最小的 dp[i - j*j] + 1
  5. 解答：
    • 最终 dp[n] 就是答案，即整数 n 可以由最少的完全平方数之和组成的数量
class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        for(int i = 1; i <= n; i++){
            int min = Integer.MAX_VALUE;
            for(int j = 1; j * j <= i; j++){
                min = Math.min(min, dp[i - j * j]);
            }
            dp[i] = min + 1;
        }
        return dp[n];
    }
}

45. LeetCode 55. 跳跃游戏

题目地址：LeetCode

image-20231203110617689

解题思路：

解题的关键是判断能否到达终点，不用每一步跳跃到哪个位置，而是尽可能的跳跃到最远的位置，看最多能覆盖到哪里，只要不断更新能覆盖的距离，最后能覆盖到末尾就行了

image.png

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

46. LeetCode 45. 跳跃游戏 II

题目地址：LeetCode

image-20231203112254819

解题思路：

  1. 如下图，开始的位置是 2，可跳的范围是橙色的。然后因为 3 可以跳的更远，所以跳到 3 的位置

    image.png

  2. 然后现在的位置就是 3 了，能跳的范围是橙色的，然后因为 4 可以跳的更远，所以下次跳到 4 的位置

    image.png

用 end 表示当前能跳的边界，对于上边第一个图的橙色 1，第二个图中就是橙色的 4，遍历数组的时候，到了边界，我们就重新更新新的边界

这里要注意一个细节，就是 for 循环中，i < nums.length - 1，少了末尾。因为开始的时候边界是第 0 个位置 steps 已经加1了

class Solution {
    public int jump(int[] nums) {
        int end = 0;
        int maxPosition = 0;
        int steps = 0;
        for(int i = 0; i < nums.length - 1; i++){
            // 找能跳的最远的
            maxPosition = Math.max(maxPosition, nums[i] + i);
            // 遇到边界，就更新边界，并且步数加一
            if(i == end){
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }
}

47. LeetCode 91. 解码方法

题目地址：LeetCode

image-20231204142756467

解题思路：

对于给定的字符串 s，设它的长度为 n，其中的字符从左到右依次为 s[1],s[2],...,s[n]。我们可以使用动态规划的方法计算出字符串 s 的解码方法数

具体地，设 fi 表示字符串 s 的前 i 个字符 s[1..i] 的解码方法数。在进行状态转移时，我们可以考虑最后一次解码使用了 s 中的哪些字符，那么会有下面的两种情况：

  1. 第一种情况是我们使用了一个字符，即 s[i] 进行解码，那么只要 s[i] != 0，它就可以被解码成 A~I 中的某个字母。由于剩余的前 i - 1 个字符的解码方法数为 f[i-1]，因此我们可以写出状态转移方程：

    • f[i] = f[i - 1]，其中 s[i] != 0

  2. 第二种情况是我们使用了两个字符，即 s[i-1] 和 s[i] 进行编码。与第一种情况类似，s[i一1] 不能等于 0，并且 s[i-1] 和s[i] 组成的整数必须小于等于 26，这样它们就可以被解码成 J~Z 中的某个字母。由于剩余的前 i - 2 个字符的解码方法数为 fi-2，因此我们可以写出状态转移方程：

    • f[i] = f[i - 2]
  • 需要注意的是，只有当 i > 1 时才能进行转移，否则 s[i-1] 不存在
  • 由于题目存在前导零，而前导零属于无效的解码。可以进行特判，但可以往字符串头部追加空格作为哨兵，追加空格既可以避免讨论前导零，也能使下标从 1 开始，简化 f[i-1] 等负数下标的判断
class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        s = " " + s;
        int[] f = new int[n + 1];
        f[0] = 1;
        for(int i = 1; i <= n; i++){
            if(s.charAt(i) != '0'){
                f[i] = f[i - 1];
            }
            if(i > 1 && s.charAt(i - 1) != '0' && ((s.charAt(i - 1) - '0') * 10 + (s.charAt(i) - '0') <= 26)){
                f[i] += f[i - 2];
            }
        }
        return f[n];
    }
}

48. LeetCode 5. 最长回文子串

题目地址：LeetCode

image-20231205145230366

解题思路：

  • 外层循环变量 r 表示右边界，从 1 开始遍历到字符串的末尾
  • 内层循环变量 l 表示左边界，从 0 开始遍历到 r
  • if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) 判断条件：
    • 首先，检查当前 l 和 r 所指向的字符是否相等
    • 然后，判断 (r - l <= 2 || dp[l + 1][r - 1])，这个条件有两部分：
    • 如果 r - l <= 2，表示当前子串的长度小于等于 3（例如 "a"、"aa"、"aba"），这种情况下肯定是回文的
    • 如果 dp[l + 1][r - 1] 为 true，表示去掉当前子串的首尾字符后的子串也是回文。这个部分是动态规划的核心，它利用之前已经计算过的子串信息来判断当前子串是否为回文
  • 如果当前子串是回文，并且长度大于 maxLen，则更新 maxLen、maxStart 和 maxEnd 的值，记录当前找到的最长回文子串
class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }
        int strLen = s.length();
        int maxStart = 0;  //最长回文串的起点
        int maxEnd = 0;    //最长回文串的终点
        int maxLen = 1;  //最长回文串的长度

        boolean[][] dp = new boolean[strLen][strLen];

        for (int r = 1; r < strLen; r++) {
            for (int l = 0; l < r; l++) {
                if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {
                    dp[l][r] = true;
                    if (r - l + 1 > maxLen) {
                        maxLen = r - l + 1;
                        maxStart = l;
                        maxEnd = r;
                    }
                }
            }
        }
        return s.substring(maxStart, maxEnd + 1);

    }
}

49. LeetCode 132. 分割回文串 II

题目地址：LeetCode

image-20231206151802443

解题思路：

假设字符串为 "abba"，我们想判断从第一个字符到第四个字符的子串是否是回文：

  • l = 1, r = 4（注意代码中字符位置从 1 开始计数）
  • cs[l - 1] == cs[r - 1] 代表 cs[0] == cs[3]，即 'a' == 'a'，这是成立的
  • 接下来检查 r - l == 1 || g[l + 1][r - 1]：
    • r - l == 1 不成立，因为 r - l = 4 - 1 = 3，不等于 1
    • 但 g[l + 1][r - 1] 需要检查 g[2][3]，即子串 "bb" 是否为回文。由于 "bb" 显然是回文，因此这个条件成立

所以整个子串 "abba" 被判断为回文

class Solution {
    public int minCut(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();

        // g[l][r] 代表 [l,r] 这一段是否为回文串
        boolean[][] g = new boolean[n + 1][n + 1];
        for(int r = 1; r <= n; r++){
            for(int l = r; l >= 1; l--){
                // 如果只有一个字符，则[l,r]属于回文
                if(l == r){
                    g[l][r] = true;
                } else{
                    // 在 l 和 r 字符相同的前提下
                    if(cs[l - 1] == cs[r - 1]){
                        // 如果 l 和 r 长度只有 2；或者 [l+1,r-1] 这一段满足回文，则[l,r]属于回文
                        if(r - l == 1 || g[l + 1][r - 1]){
                            g[l][r] = true;
                        }
                    }
                }
            }
        }

        // f[r] 代表将 [1,r] 这一段分割成若干回文子串所需要的最小分割次数
        int[] f = new int[n + 1];
        for(int r = 1; r <= n; r++){
            // 如果 [1,r] 满足回文，不需要分割
            if(g[1][r]){
                f[r] = 0;
            } else{
                // 先设定一个最大分割次数（r 个字符最多消耗 r - 1 次分割）
                f[r] = r - 1;
                // 在所有符合 [l,r] 回文的方案中取最小值
                for(int l = 1; l <= r; l++){
                    if(g[l][r]){
                        f[r] = Math.min(f[r], f[l - 1] + 1);
                    }
                }
            }
        }

        return f[n];
    }
}

50. LeetCode 1143. 最长公共子序列

题目地址：LeetCode

image-20231207152149059

解题思路：

image-20231207155622913

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++){
            char c1 = text1.charAt(i - 1);
            for(int j = 1; j <= n; j++){
                char c2 = text2.charAt(j - 1);
                if(c1 == c2){
                    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];
    }
}

51. LeetCode 72. 编辑距离

题目地址：LeetCode

image-20231207155741446

解题思路：

dp[i][j] 代表 word1 到 i 位置转换成 word2 到 j 位置需要最少步数

  • 当 word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]
  • 当 word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

其中，dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作

注意，针对第一行，第一列要单独考虑，我们引入 '' 下图所示：

image-20231207162225221

第一列，是 word1 为空变成 word2 最少步数，就是插入操作

第一行，是 word2 为空，需要的最少步数，就是删除操作

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();

        int[][] dp = new int[m + 1][n + 1];
        // 第一列
        for(int i = 1; i <= m; i++){
            dp[i][0] = dp[i - 1][0] + 1;
        }
        // 第一行
        for(int j = 1; j <= n; j++){
            dp[0][j] = dp[0][j - 1] + 1;
        }

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; 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 - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;
                }
            }
        }
        return dp[m][n];
    }
}

52. LeetCode 152. 乘积最大子数组

题目地址：LeetCode

image-20231208163211314

解题思路：

  1. 遍历数组时计算当前最大值，不断更新

  2. 令 imax 为当前最大值，则当前最大值为 imax = max(imax * nums[i], nums[i])

  3. 由于存在负数，那么会导致最大的变最小的，最小的变最大的。因此还需要维护当前最小值 imin，imin = min(imin * nums[i], nums[i])

  4. 当负数出现时则 imax 与 imin 进行交换再进行下一步计算

    1. image-20231208165024220
    2. image-20231208165036283
    3. image-20231208165048140
    4. image-20231208165102221
    5. image-20231208165113968
    6. image-20231208165300691
class Solution {
    public int maxProduct(int[] nums) {
        int max = Integer.MIN_VALUE, imax = 1, imin = 1;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] < 0){
                int temp = imax;
                imax = imin;
                imin = temp;
            }

            imax = Math.max(imax * nums[i], nums[i]);
            imin = Math.min(imin * nums[i], nums[i]);
            max = Math.max(max, imax);
        }
        return max;
    }
}

53. LeetCode 121. 买卖股票的最佳时机

题目地址：LeetCode

image-20231208165517957

解题思路：

  1. 更新前 i 天的最低价格，即最低买入成本 cost

  2. 更新前 i 天的最高利润 profit，即选择前 i − 1 天最高利润 profit 和第 i 天卖出的最高利润 price - cost 中的最大值

    1. image-20231208171747754
    2. image-20231208171801399
class Solution {
    public int maxProfit(int[] prices) {
        int cost = Integer.MAX_VALUE, profit = 0;
        for(int price: prices){
            cost = Math.min(price, cost);
            profit = Math.max(price - cost, profit);
        }
        return profit;
    }
}

54. LeetCode 122. 买卖股票的最佳时机 II

题目地址：LeetCode

image-20231209150212295

解题思路：

由于交易次数不受限，累加所有上坡之和，即可获得最大利润。本质上这种方式就是贪心算法

image.png

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        for(int i = 1; i < prices.length; i++){
            if(prices[i] > prices[i - 1]){
                profit += prices[i] - prices[i - 1];
            }
        }
        return profit;
    }
}

55. LeetCode 123. 买卖股票的最佳时机 III

题目地址：LeetCode

image-20231209151209327

解题思路：

官方题解

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int buy1 = -prices[0], sell1 = 0;
        int buy2 = -prices[0], sell2 = 0;

        for(int i = 1; i < n; i++){
            buy1 = Math.max(buy1, -prices[i]);
            sell1 = Math.max(sell1, buy1 + prices[i]);
            buy2 = Math.max(buy2, sell1 - prices[i]);
            sell2 = Math.max(sell2, buy2 + prices[i]);
        }
        return sell2;
    }
}

56. LeetCode 198. 打家劫舍

题目地址：LeetCode

image-20231210162138429

解题思路：

对于第 k（k > 2） 间房屋，有两个选项：

  1. 偷窃第 k 间房屋，那么就不能偷窃第 k−1 间房屋，偷窃总金额为前 k−2 间房屋的最高总金额与第 k 间房屋的金额之和
  2. 不偷窃第 k 间房屋，偷窃总金额为前 k−1 间房屋的最高总金额

在两个选项中选择偷窃总金额较大的选项，该选项对应的偷窃总金额即为前 k 间房屋能偷窃到的最高总金额

用 dp[i] 表示前 i 间房屋能偷窃到的最高总金额，那么就有如下的状态转移方程：dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])，边界条件为：

image-20231210170925012

最终的答案即为 dp[n−1]，其中 n 是数组的长度

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if(n == 1) return nums[0];
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);

        for(int i = 2; i < n; i++){
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[n - 1];
    }
}
🌟 如果您喜欢我的文章，欢迎赞赏支持，您的支持是我创作的最大动力！🌟
🖋 作者：Enndfp
🔗链接：https://blog.enndfp.cn
📜版权声明：您可以自由转载，但请务必注明原文地址，感谢您的尊重与支持~
算法
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
队列和Hash

							
							

							
二叉树

							
							

							
栈

							
							

							
链表