devbox
神奇cpp
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

代码随想录——Java刷题记录_代码随想录刷题方法

作者：神奇cpp | 2024-06-24 14:11:44

赞

踩

代码随想录刷题方法

数组（11.2-11.5）

定义：数组是存放在连续内存空间上的相同类型数据的集合，下标都是从0开始。

特点：连续 ==> 查找方便，新增/删除不方便【数组的元素是不能删的，只能覆盖】

1、二分查找

题目：704. 二分查找 - 力扣（LeetCode）

前提：数组为有序数组 + 数组中无重复元素

难点：对区间的定义想清楚 ==》 保持不变量（在while寻找中每一次边界的处理都要坚持根据区间的定义来操作） ==》循环不变量规则

  1. 左闭右闭 [left, right]

    • 范围包含right

    • left = right 时是有意义的，也就是在中间只有一个数的时候 ==》 while (left <= right)

    • 左右边界变的时候要多移一位

  2. 左开右闭 [left, right) ==> while (left < right)

    • 范围不包含right

    • left = right 时是没有意义的 ==》 while (left < right)

    • left需要多移动一位，right不需要，因为反正也不包含

    相当于[1，2，3]和[1，2，3）的区别

示例：Java左闭右闭区间

  1. class Solution {
  2.     public int search(int[] nums, int target) {
  3.     // 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
  4.         if (target < nums[0] || target > nums[nums.length - 1])      
  5.             return -1;
  6.         int left = 0, right = nums.length - 1;
  7.         while (left <= right) {
  8.             int mid = left + ((right - left) >> 1);
  9.             if (nums[mid] == target)
  10.                 return mid;
  11.             else if (nums[mid] < target)
  12.                 left = mid + 1;
  13.             else if (nums[mid] > target)
  14.                 right = mid - 1;
  15.         }
  16.         return -1;
  17.     }
  18. }

  • 时间复杂度：O(log n)

  • 空间复杂度：O(1)

2、移除元素【快慢指针】

题目：27. 移除元素 - 力扣（LeetCode）

前提：数组中在保持基本顺序不变的前提下，删除指定元素（主要是减少空间复杂度）

难点：理解快慢指针的具体含义

  • 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组

  • 慢指针：指向更新 新数组下标的位置

27.移除元素-双指针法

示例：

  1. class Solution {
  2.     public int removeElement(int[] nums, int val) {
  3.         // 快慢指针
  4.         int slowIndex = 0;
  5.         for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
  6.             if (nums[fastIndex] != val) {
  7.                 nums[slowIndex] = nums[fastIndex];
  8.                 slowIndex++;
  9.             }
  10.         }
  11.         return slowIndex;
  12.     }
  13. }

  • 时间复杂度：O(n)

  • 空间复杂度：O(1)

相关题目：

  • 26. 删除有序数组中的重复项 - 力扣（LeetCode）：额感觉没有用到快慢指针，如果前一项不等于这一项，那就要把这一项放进数组【有点绕】

    1. class Solution {
    2.     public int removeDuplicates(int[] nums) {
    3.         int next = 0;
    4.         for (int i=1; i<nums.length;i++) {
    5.             if (nums[i-1] != nums[i]) {
    6.                 next++;
    7.                 nums[next] = nums[i];
    8.             }
    9.         }
    10.         return next + 1;
    11.     }
    12. }

  • 283. 移动零 - 力扣（LeetCode）：先用快慢指针筛选出不含0的子数组，再在数组后面全部置0

    1. class Solution {
    2.     public void moveZeroes(int[] nums) {
    3.         int fast =0,slow=0;
    4.         for (; fast < nums.length; fast++) {
    5.            if(nums[fast]!=0){
    6.                nums[slow]=nums[fast];
    7.                slow++;
    8.            }
    9.         }
    10.  
    11.         // 后面置0
    12.         for(int j = slow;j<nums.length;j++){
    13.             nums[j]=0;
    14.         }
    15.     }
    16. }

  • 844. 比较含退格的字符串 - 力扣（LeetCode）：巧用StringBuilder，用append实现添加操作，deleteCharAt方法实现退格操作

    1. class Solution {
    2.     public boolean backspaceCompare(String s, String t) {
    3.         String processedS = processString(s);
    4.         String processedT = processString(t);
    5.         
    6.         // 判断是否一致
    7.         return processedS.equals(processedT);
    8.     }
    9.     
    10.     private String processString(String str) {
    11.         StringBuilder result = new StringBuilder();
    12.         
    13.         for (int i = 0; i < str.length(); i++) {
    14.             char c = str.charAt(i);
    15.             if(c!='#')
    16.                 result.append(c);
    17.             else{
    18.                 // 注意这里要判断一下，否则超界Error
    19.                 if(result.length()!=0)
    20.                     result.deleteCharAt(result.length() - 1);
    21.         }}
    22.         return result.toString();
    23.     }
    24. }

3、有序数组的平方【快慢指针】

题目： 977. 有序数组的平方 - 力扣（LeetCode）

前提： 非递减顺序 排序

难点：非递减 ==》 平方大小两边向中间递减 ==》 对向双指针移动的逻辑

实现：

  1. class Solution {
  2.     public int[] sortedSquares(int[] nums) {
  3.         int p=nums.length-1;
  4.         int[] arr=new int[nums.length];
  5.         int left=0;
  6.         int right=nums.length-1;
  7.         while(left <= right){
  8.             // 对向移动
  9.            if(Math.abs(nums[left]) > Math.abs(nums[right])){
  10.                 arr[p]=nums[left] * nums[left];
  11.                 left++;
  12.             }else{
  13.                 arr[p]=nums[right] * nums[right];
  14.                 right--;
  15.             }
  16.             p--;
  17.         }
  18.         return arr;
  19.     }
  20. }

  • 时间复杂度：O(n)

  • 空间复杂度：O(1)

4、长度最小的子数组【滑动窗口】

题目：209. 长度最小的子数组 - 力扣（LeetCode）

前提：问题涉及连续子数组或子字符串

难点：不断的调节子序列的起始位置和终止位置，注意for表示的是窗口的终止位置，每次for先确定终止位置再不断向前调整起始位置

209.长度最小的子数组

滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。

leetcode_209

示例：

  1. class Solution {
  2.     public int minSubArrayLen(int target, int[] nums) {
  3.         int result = nums.length + 1;
  4.         int sum = 0;
  5.         int left = 0;
  6. ​
  7.         // 滑动窗口，移动的是终止位置
  8.         for (int i = 0; i < nums.length; i++) {
  9.             sum += nums[i];
  10. ​
  11.             while (sum >= target) {
  12.                 result = Math.min(result, i - left + 1);
  13.                 // 每次直接从确定的初始位置开始移动，因为是已经计算过的长度最短
  14.                 sum -= nums[left];
  15.                 left++;
  16.             }
  17.         }
  18.         return result == nums.length + 1 ? 0 : result;
  19.     }
  20. }

相关题目推荐：【还没做捏】

5、螺旋矩阵Ⅱ【模拟】

题目：59. 螺旋矩阵 II - 力扣（LeetCode）

前提：好像没什么前提 本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/神奇cpp/article/detail/752971

推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。