LeetCode刷题第三周

梦里梦外; 2023-02-23 07:44 151阅读 0赞

在这里插入图片描述

我来啦，托更半天的我来啦。嘤嘤嘤，虽然并不是很想做算法题，但既然说了说每周一更新，那就保质保量的每周更一篇。放假半年，现在到了七月上旬，实在是学疲了，上周重装了系统，墨墨迹迹把电脑整舒服了很多，但是不管是看书还是看视频一会儿就犯困，果然有些理论学起来过于枯燥，这周得调整调整，下个月末就要开学啦~

文章目录

  • 数组专题
    • 简单
        1. 两数之和
        1. 删除排序数组中的重复项
        1. 移除元素
        1. 搜索插入位置
    • 中等
        1. 盛最多水的容器
        1. 三数之和
        1. 最接近的三数之和
        1. 四数之和
        1. 下一个排列
        1. 搜索旋转排序数组
        1. 在排序数组中查找元素的第一个和最后一个位置

数组专题

在这里插入图片描述

简单

1. 两数之和

题目链接：点击跳转至本题

题目大意：
有nums数组，和一个特定值target，要求：找到并返回两个下标，这两个下标要满足相加和为target。
注意：
①每种输入只会对应一个答案。
②数组中同一个元素不能使用两遍。

解题思路：
思路1：使用双层for循环
采用简单的双层for循环来完成这一匹配，需要注意一下返回的两个下标要以数组的形式呈现，使用一维数组 new int[ ]{i，j} 的形式。一层for循环的时间复杂度为 O ( n ) O(n) O(n)，双重的时间复杂度为 O ( n 2 ) O(n^2) O(n2) 。这里在开始直接定义一个返回的数组，可以省略非法参数异常的抛出。

思路2：使用哈希表
虽然本篇是数组专题，不过这里遇到了，就使用HashMap来做一下。若仍不理解，可以等本专栏后面更新到HashMap时，再详细分析。
整体思路是：定义一个空的map，对nums数组仅做一次遍历，遍历的同时，将nums的键值对依次装载进map中。每使用put向前装载一个键值对，都使用map.containsKey向后查询一遍是否包含其中的一个元素值。若找到，就返回它的value(即下标)和另一个下标i。

  1. // 1. 两数之和
  3. //方法1：
  4. class Solution { 
  5.     public int[] twoSum(int[] nums, int target) { 
  6.         int[] result = new int[2];
  7.         for(int i = 0;i < nums.length;i++){ 
  8.             for(int j = i + 1;j < nums.length;j++){ 
  9.                 if(nums[i] + nums[j] == target){ 
  10.                     result[0] = i;
  11.                     result[1] = j;
  12.                 }
  13.             }
  14.         }
  15.         return result;
  16.     }
  17. }
  19. //方法2: 
  20. class Solution { 
  21.     public int[] twoSum(int[] nums, int target) { 
  22.         int[] result = new int[2];
  23.         Map<Integer,Integer> map = new HashMap<>();
  24.         for(int i = 0;i < nums.length;i++){ 
  25.             int temp_num = target - nums[i];
  26.             if(map.containsKey(temp_num)){ 
  27.                 result[0] = i;
  28.                 result[1] = map.get(temp_num);
  29.             }
  30.             map.put(nums[i], i);//key=数组值，value=数组下标
  31.         }
  32.         return result;
  33.     }
  34. }

在这里插入图片描述

在这里插入图片描述

26. 删除排序数组中的重复项

题目链接：点击跳转至本题

题目大意：
给定一个排好序的数组nums，要求：原地删除重复出现的元素，使得每个元素只能出现一次，最后返回新数组的长度。
注意：不能使用额外的数组空间，且不需要考虑数组中超出新长度后面的元素。

解题思路：双指针法
数组是排好序的，因此出现重复时可以使用后面的来覆盖，间接完成”删除操作”。使用双指针法，定义两个变量(慢指针p和快指针q)，一前一后遍历一遍数组。当发现nums[p] == nums[q]时，快指针q后移，当发现nums[p] != nums[q]时，慢指针p后移并将快指针q处的值赋给慢指针p处。可以想见被覆盖处一定是重复的数据。p和q代表的都是下标，新数组的长度为q+1，但去重后的数据长度只有p+1。

  1. class Solution { 
  2.     public int removeDuplicates(int[] nums) { 
  3.         if(nums.length == 0){ 
  4.             return 0;
  5.         }
  6.         //p作为慢指针
  7.         int p = 0;
  8.         //q作为快指针
  9.         int q = 1;
  10.         while(q < nums.length){ 
  11.             if(nums[p] != nums[q]){ 
  12.                 p++;
  13.                 nums[p]=nums[q];
  14.             }
  15.             q++;
  16.         }
  17.         return p+1;
  18.     }
  19. }

27. 移除元素

题目链接：点击跳转至本题

题目大意
给定一个数组nums和一个值val，要求删除nums中元素值等于val的元素，返回新数组的长度。
注意：不能使用额外的数组空间，且不需要考虑数组中超出新长度后面的元素。

解题思路：双指针法
27题和26题很相似，关键点在于快指针q的初始值是0还是1。由于26题是和数组中前一个值比较，所以快指针q初始值为1；27题是和数组外的一个定值比较，所以快指针q初始值为0。

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

35. 搜索插入位置

题目链接：点击跳转至本题

题目大意
给定一个排好序的数组nums和一个目标值target，要求：在数组中找到该目标值，并返回其索引。如果没有此目标值，则返回目标值按顺序应该被插入的位置。

解题思路：二分查找
使用二分查找，分别设定左下标left和右下标right，再计算中间下标mid。然后每次根据 nums[mid] 和 target 之间的大小进行判断：

  • ①nums[mid] < target：直接返回下标。
  • ②nums[mid] < target ： left 右移。
  • ③nums[mid] > target ： right 左移。

本题中，如果查找结束没有找到与target相等的元素，则直接返回 下标left 即可，因为 下标left 就是符合题意该插入的位置。

  1. class Solution { 
  2.     public int searchInsert(int[] nums, int target) { 
  3.         int left = 0, right = nums.length;
  4.         while(left < right) {  
  5.             int mid = (left + right) / 2; 
  6.             if(nums[mid] == target) { 
  7.                 return mid;
  8.             } else if(nums[mid] < target) { 
  9.                 left = mid + 1; 
  10.             } else { 
  11.                 right = mid; 
  12.             }
  13.         }
  14.         return left;
  15.     }
  16. }

在这里插入图片描述

中等

11. 盛最多水的容器

题目链接：点击跳转至本题

题目大意
a i a_i ai​代表坐标中的一个点(i， a i a_i ai​)，点(i， a i a_i ai​)和点(i，0)作为垂直线的两个端点，数组为a[1,8,6,2,5,4,8,3,7]。要求：找出两条垂直线，使它们与x轴共同构成的容器可以盛最多的水。
注意：容器不能倾斜，且n≥2。

解题思路：双指针法
盛最多的水，即求构成的矩形面积最大。设定左右指针 l 和 r 分别位于数组的左右两端，他们构成的面积为： m i n ( l , r ) ∗ ( r − l ) min(l , r) * (r - l) min(l,r)∗(r−l)，定义一个变量ans作为最大面积，在遍历中不断更新ans的值，遍历结束时，ans即为最大的面积。每一步当比较l和r的高度时，最小的那个高度向中间移动一位。

  1. class Solution { 
  2.     public int maxArea(int[] height) { 
  3.         int l = 0;
  4.         int r = height.length - 1;
  5.         int ans = 0;
  6.         while(l < r){ 
  7.             //矩形面积=底x高(木桶原则)
  8.             int area = Math.min(height[l],height[r]) * (r - l);
  9.             ans = Math.max(ans,area);
  10.             if(height[l] < height[r]){ 
  11.                 l++;
  12.             }else{ 
  13.                 r--;
  14.             }
  15.         }
  16.         return ans;
  17.     }
  18. }

15. 三数之和

题目链接：点击跳转至本题

题目大意
有nums数组，要求找出nums中的三个元素a、b、c，满足a+b+c=0。答案中不可以包含重复的组合。

解题思路：排序+双指针
三层for循环的时间复杂度是 O ( n 3 ) O(n^3) O(n3)，可以对数组排序后先固定一个值，然后使用双指针法，将时间复杂度降低到 O ( n 2 ) O(n^2) O(n2)。本题不难，复杂在去重上，更详细的思路在代码注释中。

  1. class Solution { 
  2.     public List<List<Integer>> threeSum(int[] nums) { // 总时间复杂度：O(n^2)
  3.         //由于结果可能返回多个数组，故采用链表中套链表的结构
  4.         List<List<Integer>> ans = new ArrayList<>();
  5.         //此处简单的优化提速(可忽略)，考虑了两种特殊情况
  6.         if (nums == null || nums.length <= 2){ 
  7.             return ans;
  8.         } 
  9.         //对nums数组进行快排O(nlogn)
  10.         Arrays.sort(nums); 
  12.         //for+while双层循环，O(n^2)，这里的i作为相对固定指针。
  13.         for (int i = 0; i < nums.length - 2; i++) {  
  14.             //此处简单的优化提速(可忽略)，考虑了排好序后的第一个数应>0
  15.             if (nums[i] > 0) break;
  17.             // 去掉指针i的重复情况
  18.             if (i > 0 && nums[i] == nums[i - 1]) { 
  19.                 continue; 
  20.             }
  21.             //定义首尾指针
  22.             int left = i + 1, right = nums.length - 1;
  23.             while (left < right) { 
  24.                 if (nums[left] + nums[right] +nums[i] == 0) { 
  25.                     ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
  26.                     left++; right--;
  27.                     //去掉指针left的重复情况
  28.                     while (left < right && nums[left] == nums[left - 1]) left++;
  29.                     //去掉指针right的重复情况
  30.                     while (left < right && nums[right] == nums[right + 1]) right--;
  31.                 } else if (nums[left] + nums[right] + nums[i] < 0) { 
  32.                     left++;
  33.                 } else if (nums[left] + nums[right] + nums[i] > 0) {   
  34.                     right--;
  35.                 }
  36.             }
  37.         }
  38.         return ans;
  39.     }
  40. }

16. 最接近的三数之和

题目链接：点击跳转至本题

题目大意
给定一个包括n个整数的数组nums和一个目标值target，要求找出nums中的三个整数使得它们的和与target最接近。假定每组输入只存在唯一的答案，返回这三个数的和。

解题思路：排序+双指针

此题与上一题 15. 三数之和 有很大相似之处，首先对数组进行排序，为使用双指针提供先决条件。固定指针i，定义 左指针left 和 右指针right ，假定三数之和为sum，
若sum == target，直接返回结果；
若sum < target，左指针left右移一位；
若sum > target，右指针right左移一位；
之后，对 target-sum 的绝对值不断更新，取较小值，不断赋给ans。

本题中对指针i、左右指针 left 和 right 都进行了类似15题那样的优化，不过，这些优化仅可以加快执行速度，不会改变时间复杂度 O ( n 2 ) O(n^2) O(n2)。

  1. class Solution { 
  2.     public int threeSumClosest(int[] nums, int target) { 
  3.         Arrays.sort(nums);
  4.         int ans = nums[0] + nums[1] + nums[2];
  5.         for(int i = 0;i < nums.length;i++){ 
  6.             //对指针i去重
  7.             if (i > 0 && nums[i] == nums[i - 1]) { 
  8.                 continue;
  9.             }
  11.             int left = i+1,right = nums.length - 1;
  12.             while(left < right){ 
  13.                 int sum = nums[i] + nums[left] + nums[right];
  14.                 //不断更新ans为最接近target的三数之和
  15.                 if(Math.abs(target - sum) < Math.abs(target - ans)){ 
  16.                     ans = sum;
  17.                 }
  19.                 if(sum == target){ 
  20.                         left++;
  21.                         right--;
  22.                         //去掉指针left的重复情况
  23.                         while (left < right && nums[left] == nums[left - 1]){ 
  24.                             left++;
  25.                         }
  26.                         //去掉指针right的重复情况
  27.                         while (left < right && nums[right] == nums[right + 1]){ 
  28.                             right--;
  29.                         }
  30.                     return target;
  31.                 }else if(sum < target){ 
  32.                     left++;
  33.                 }else if(sum > target){ 
  34.                     right--;
  35.                 } 
  36.             }
  37.         }
  38.         return ans;
  39.     }
  40. }

18. 四数之和

题目链接：点击跳转至本题

题目大意
给定一个包含n给整数的数组nums和一个目标值target，要求找出nums中是否包含四个元素a、b、c、d，满足a+b+c+d=target，且所有满足条件的组合不能重复。

解题思路：
此题是15. 三数之和 的增强版，不同之处在于应多加一层for循环，使时间复杂度变为 O ( n 3 ) O(n^3) O(n3) ，整体思路为，定义两个相对固定的指针，代表a和b，再使用双指针left和right代表c和d。复杂点在于考虑四个指针的去重情况，与前面类似，不再赘述。

  1. class Solution { 
  2.     public List<List<Integer>> fourSum(int[] nums, int target) { 
  3.         List<List<Integer>> ans = new ArrayList<>();
  4.         //数组为null或元素<4时返回空集合
  5.         if(nums == null || nums.length < 4){ 
  6.             return ans;
  7.         }
  8.         Arrays.sort(nums);
  9.         //第一层循环
  10.         for(int i = 0;i < nums.length-3;i++){ 
  11.             //对指针i进行去重
  12.             if(i>0 && nums[i] == nums[i-1]){ 
  13.                 continue;
  14.             }
  15.             //第二层循环
  16.             for(int j=i+1;j<nums.length-2;j++){ 
  17.                 //对指针j进行去重
  18.                 if(j>i+1 && nums[j] == nums[j-1]){ 
  19.                     continue;
  20.                 }
  21.                 //第三次循环
  22.                 int left = j+1,right = nums.length - 1;
  23.                 while(left < right){ 
  24.                     int sum = nums[i] + nums[j] + nums[left] + nums[right];
  25.                     if(sum == target){ 
  26.                         ans.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
  27.                         left++;
  28.                         right--;
  30.                         //去掉指针left的重复情况
  31.                         while (left < right && nums[left] == nums[left - 1]){ 
  32.                             left++;
  33.                         }
  34.                         //去掉指针right的重复情况
  35.                         while (left < right && nums[right] == nums[right + 1]){ 
  36.                             right--;
  37.                         }
  38.                     }else if(sum < target){ 
  39.                         left++;
  40.                     }else if(sum > target){ 
  41.                         right--;
  42.                     }
  43.                 }
  44.             }
  45.         }
  46.         return ans;
  47.     }
  48. }

31. 下一个排列

题目链接：点击跳转至本题

题目大意
给你一个数组nums，要求找出数组中数字全排列后，字典序中的下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列。
字典序的下一个值：比如对于1、2、3来说，可以组成这样的字典序列表[[1,2,3]，[1,3,2]，[2,1,3]，[2,3,1]，[3,1,2]，[3,2,1]]，让我们找到这其中一组排列的下一组排列，比如[1,2,3]的全排列的下一个组合是 [1,3,2]，如果到了最后一组，则将这些数字升序排列。

解题思路：倒序遍历+双指针
求全排列的下一个组合，解法是从右往左依次遍历，找到两个数，左边的数<右边的数。找到后进行交换，并且对左边数后面的数进行顺序排列，这样找到的就是全排列后的下一个数字，操作之后使用return终止程序。

  1. class Solution { 
  2.     public void nextPermutation(int[] nums) { 
  3.         for(int left = nums.length - 2;left >= 0;left--){ 
  4.             for(int right = nums.length - 1;left < right;right--){ 
  5.                 if(nums[left] < nums[right]){ 
  6.                     //交换这两个数字
  7.                     swap(nums,left,right);
  8.                     //对left指针后面数排序，就是按顺序全排列的下一个
  9.                     Arrays.sort(nums,left+1,nums.length);
  10.                     //找到后，程序直接终止执行
  11.                     return;
  12.                 }
  13.             }
  14.         }
  15.         //若不存在下一个更大的排列时升序排列
  16.         Arrays.sort(nums);
  17.     }
  19.     void swap(int[] arr,int i,int j){ 
  20.         int temp = arr[i];
  21.         arr[i] = arr[j];
  22.         arr[j] = temp;
  23.     }
  24. }

在这里插入图片描述

33. 搜索旋转排序数组

题目链接：点击跳转至本题

题目大意
有一个有序数组被分成两半后，将后一半拼接在最前端，构成一个新的数组，给出一个目标值target。要求找出数组中此target的索引，如果数组中不存在此target，返回-1。

解题思路：二分法
将数组从中一分为二，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。此时对有序部分用二分法查找，无序部分再一分为二，其中又是一个有序，另一个可能有序，可能无序。就这样循环。
①nums[left] <= nums[mid]：这种情况下前半部分有序。
如果 nums[left] <= target <nums[mid]，则在前半部分找，否则去后半部分找。
②nums[left] > nums[mid]：后半部分有序。
如果 nums[mid] <target<=nums[right]，则在后半部分找，否则去前半部分找。

  1. class Solution { 
  2. public int search(int[] nums, int target) { 
  3.         int left = 0,right = nums.length - 1;
  4.         while(left <= right){ 
  5.             int mid = (left + right) / 2;
  6.             //如果中间值就是target，直接返回
  7.             if(nums[mid] == target){ 
  8.                 return mid;
  9.             }
  10.             //第一个值>中间值：代表后半段是有序的
  11.             if(nums[left] > nums[mid]){ 
  12.                 if(nums[mid] < target && target <= nums[right]){ 
  13.                     //若target在mid右边
  14.                     left = mid + 1;
  15.                 } else{ 
  16.                     //若target在mid左边
  17.                     right = mid - 1;
  18.                 }
  19.             //第一个值<中间值：代表前半段是有序的
  20.             }else { 
  21.                 if(nums[left] <= target && target < nums[mid]){ 
  22.                     //若target在mid左边
  23.                     right = mid - 1;
  24.                 }else{ 
  25.                     //若target在mid左边
  26.                     left = mid + 1;
  27.                 }
  28.             }  
  29.         }
  30.         return -1;
  31.     }
  32. }

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

题目链接：点击跳转至本题

题目大意：
给定一个升序数组nums和一个目标值target，要求找出给定目标值在数组中的开始位置和结束位置。时间复杂度限制在 O ( l o g n ) O(log^n) O(logn)级别。

解题思路：
本题关键在于使用二分查找查询左右边界，每次查找时，若nums[mid]==target找到符合条件的值时，继续令指针继续向左或向右查找，结束时返回的left指针和right指针就分别是左边界和右边界。需要注意其中指针越界或结果不是目标值的情况，这两种情况要返回-1。

  1. class Solution { 
  2.     public int[] searchRange(int[] nums, int target) { 
  3.         int[] ans = new int[2];
  4.         ans[0] = nums_left(nums,target);
  5.         ans[1] = nums_right(nums,target);
  6.         return ans;
  7.     }
  9.     int nums_left(int[] nums,int target){ 
  10.         int left = 0,right = nums.length - 1;
  11.         while(left <= right){ 
  12.             int mid = (left + right) / 2;
  13.             if(nums[mid] == target){ 
  14.                 //找到一个target后继续向左找
  15.                 right = mid - 1;
  16.             } else if(target < nums[mid]){ 
  17.                 right = mid - 1;
  18.             } else if(nums[mid] < target){ 
  19.                 left = mid + 1;
  20.             }
  21.         }
  22.         //left越界或中值不是目标值
  23.         if (left >= nums.length || nums[left] != target){ 
  24.             return -1;
  25.         }
  26.         return left;
  27.     }
  29.     int nums_right(int[] nums,int target){ 
  30.         int left = 0,right = nums.length - 1;
  31.         while(left <= right){ 
  32.             int mid = (left + right) / 2;
  33.             if(nums[mid] == target){ 
  34.                 //找到一个target后继续向右找
  35.                 left = mid + 1;
  36.             } else if(target < nums[mid]){ 
  37.                 right = mid - 1;
  38.             } else if(nums[mid] < target){ 
  39.                 left = mid + 1;
  40.             }
  41.         }
  42.         //right越界或中值不是目标值
  43.         if (right < 0 || nums[right] != target){ 
  44.             return -1;
  45.         }
  46.         return right;
  47.     }
  48. }

发表评论

表情：
评论列表 （有 0 条评论，151人围观）

还没有评论，来说两句吧...

相关阅读

    相关 第九周--题三

    类的定义和使用 > 任务描述 > 小明家要修一个院子，小明测量了院子的长和宽之后想编写一个程序告诉他院子的周长的面积，请你来帮帮他。 ![在这里插入图片描述][wa

    心已赠人心已赠人/ 0 赞/ 623 阅读