• LeetCode刷题

    一   【移除元素】

    原题链接：27. 移除元素 - 力扣（LeetCode）

    给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

    不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

    元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

    示例 1：

    输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

    示例 2：

    输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度5 并且 nums 中的前五个元素为 0,1,3,0,4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。 

         思路一：暴力解法

    让我们找到对应的val值并删除，我们可以先用一个for循环,判断数组中的值是否有与val相等的如果有，我们可以用后一个数据元素覆盖前一个元素实现覆盖效果，注意，我们覆盖了一次以后。后面的元素都要向前移动一个位置，要再次使用一个for循环，也就是要使用两个for循环。需要注意的时我们以下的方法，都是实现覆盖效果，最后一个元素没有做处理。

    动态效果： 

    代码实现：

    (c语言）

    1. int removeElement(int* nums, int numsSize, int val) {
    2.      int i,j;
    3.      for(i=0;i<numsSize;i++){//第一个循环遍历数组 
    4.          if(nums[i]==val){//判断是否数组有数据等于val 
    5.              for(j=i+1;j<numsSize;j++){//移动元素覆盖 
    6.                  nums[j-1]=nums[j];
    7.              } 
    8.          i--;
    9.          numsSize--;
    10.          }
    11.         
    12.      }
    13.      return numsSize;
    14. }

    第二个for循环后面为什么要执行i--操作呢？

    我们举个例子说明：

         思路二：双指针

    什么是双指针呢？
     

    双指针指的是在算法中使用两个指针来解决问题的一种技巧。这两个指针可以是在同一数组中移动的两个指针，也可以是在不同数组中移动的两个指针。

    在算法中，双指针技巧通常用于处理涉及数组、链表或字符串的问题。通过使用双指针，我们可以更有效地解决一些问题，降低时间复杂度或空间复杂度。

    双指针常见的应用场景有：

    1. 快慢指针：例如在链表中判断是否存在环或找到环的入口点时，可以使用快慢指针。快指针每次移动两步，慢指针每次移动一步，如果链表中存在环，则快指针最终会追上慢指针。

    2. 对撞指针：对于已排序的数组或链表，可以使用左右两个指针从两端向中间移动，以解决一些查找问题或判断问题。例如，在已排序的数组中查找两个数之和为目标值的问题，可以使用左右指针向中间移动并进行比较。

    3. 滑动窗口：滑动窗口是一个固定大小的窗口，在数组或字符串上滑动。它通常用于解决一些子串或子数组的问题。我们可以使用双指针分别表示窗口的左右边界，通过移动指针来调整窗口的大小或位置。

    使用双指针技巧时，需要注意指针的移动规则和退出条件，确保算法的正确性和高效性。双指针技巧可以帮助我们解决一些复杂的问题，提高算法的效率。

    解决这个问题我们就可以用到快慢指针，块指针用来寻找新数组中的元素（就是找出不等于val的值，慢指针就是用来记录新数组的下标.

    动态效果：

    代码实现

    (c语言)

    1. int removeElement(int* nums, int numsSize, int val) {
    2.     int fast=0;//快指针 
    3.     int slow=0;//慢指针 
    4.     for(fast=0;fast<numsSize;fast++){//快指针遍历数组寻找新数组元素 
    5.         if(nums[fast]!=val){
    6.             nums[slow]=nums[fast];
    7.             slow++;
    8.         }
    9.     }
    10.     return slow;//慢指针的下标是新数组的长度

    (Java):

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

    二   【二分查找】

    原题链接：704. 二分查找 - 力扣（LeetCode）

    给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。


    示例 1:

    输入: nums= [-1,0,3,5,9,12], target= 9输出: 4
解释: 9 出现在 nums中并且下标为 4

    示例 2:

    输入: nums= [-1,0,3,5,9,12], target= 2输出: -1
解释: 2 不存在 nums中因此返回 -1

     二分查找是一种高效的查找算法，也称为折半查找。它适用于已排序的数组或列表。其基本思想是每次将查找区间缩小为原来的一半，通过与目标值的比较，确定目标值是否在缩小后的区间内，从而最终找到目标值或确定不存在。

    以下是二分查找的详细步骤：

    1. 确定查找区间的起始和结束位置。通常，初始时起始位置为数组的第一个元素的索引，结束位置为数组的最后一个元素的索引。

    2. 计算查找区间的中间位置。可以使用公式 mid = (start + end) / 2 来计算中间位置。

    3. 比较中间位置的元素与目标值的大小：

      • 如果中间位置的元素等于目标值，表示找到了目标值，返回中间位置。
      • 如果中间位置的元素大于目标值，表示目标值可能在左半部分，将结束位置更新为中间位置减一，继续进行下一轮查找。
      • 如果中间位置的元素小于目标值，表示目标值可能在右半部分，将起始位置更新为中间位置加一，继续进行下一轮查找。

    4. 重复步骤 2 和步骤 3，直到找到目标值或确定不存在。如果起始位置大于结束位置，则表示目标值不存在。

    二分查找的时间复杂度是 O(log n)，其中 n 是数组或列表的长度。它是一种高效的查找算法，但要求在查找之前需要对数组或列表进行排序。如果数据是动态变化的，频繁进行插入、删除操作，就不适合使用二分查找。

    动态效果

     代码实现

    1. int search(int* nums, int numsSize, int target){
    2.     int low=0;
    3.     int high=numsSize-1;
    4.     int midle;
    5.     while(low<=high){
    6.         midle=(low+high)/2;
    7.         if(target>nums[midle]){
    8.             low=midle+1;
    9.         }else if(target<nums[midle]){
    10.             high=midle-1;
    11.         }else{
    12.             return midle;
    13.         }
    14.     }
    15.     return -1;
    16.  
    17. }

    三   【有序数组的平方】

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

    给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

    示例 1：

    输入：nums = [-4,-1,0,3,10]
    输出：[0,1,9,16,100]
    解释：平方后，数组变为 [16,1,0,9,100]
    排序后，数组变为 [0,1,9,16,100]


    示例 2：

    输入：nums = [-7,-3,2,3,11]
    输出：[4,9,9,49,121]

         思路一：直接排序

    先将数组中的每一个元素进行平方，然后结合各种排序算法实现。

    【代码实现】

    1. class Solution {
    2.     public int[] sortedSquares(int[] nums) {
    3.         int[] a = new int[nums.length];
    4.         for (int i = 0; i < nums.length; ++i) {
    5.             a[i] = nums[i] * nums[i];
    6.         }
    7.         Arrays.sort(a);
    8.         return a;
    9.     }
    10. }

         思路二：双指针

    对撞指针也被称为双指针法或双指针技巧，是一种在数组或列表中使用两个指针进行遍历的算法技巧。这两个指针通常分别位于数组或列表的起始位置和结束位置，通过向中间移动指针，以解决一些问题。

    对撞指针通常用于已排序的数组或列表中，利用有序性质来解决问题。它的基本思路是通过移动两个指针，同时从数组的两端向中间逼近，缩小搜索范围或判断条件。

    对撞指针的常见应用场景有：

    1. 查找问题：例如在有序数组中查找两个数之和为目标值的问题，可以使用两个指针从数组的两端向中间移动，根据两个指针指向的数之和与目标值的大小关系来调整指针的位置。

    2. 判断问题：例如判断一个字符串是否是回文字符串，可以使用两个指针从字符串的两端向中间移动，同时比较两个指针指向的字符是否相等。

    3. 反转问题：例如反转数组或列表中的元素，可以使用两个指针从数组或列表的两端向中间移动，并交换两个指针指向的元素。

    对撞指针的特点是指针的移动方向相反，且指针遍历的范围逐渐缩小。使用对撞指针可以在一次遍历的过程中解决问题，从而提高算法的效率。需要注意的是，在使用对撞指针时，需要定义好指针的起始和结束位置，并控制好指针的移动条件，确保算法的正确性。

    解决这个问题我们用到对撞指针，也就是一个指针在数组的末端，一个在起始端两个向中间移动。因为数组是有序的，所以我们主要的问题就是负数的平方的大小的问题，所以我们用i指向开头，j指向末尾，这时比较i与j对应的数据的平方，然后将大的数据放入新数组的末端，依次进行下去。

    动态效果：

    【代码实现】

    1. int* sortedSquares(int* nums, int numsSize, int* returnSize) {
    2.     int i,j;
    3.     int k=numsSize-1;
    4.     int *result = (int *)malloc(numsSize * sizeof(int));
    5.     for(i=0,j=numsSize-1;i<=j;k--){
    6.         if(nums[i]*nums[i]>=nums[j]*nums[j]){
    7.             result[k]=nums[i]*nums[i];
    8.             i++;
    9.         }else{
    10.             result[k]=nums[j]*nums[j];
    11.             j--;
    12.         }
    13.     }
    14.     *returnSize = numsSize;
    15.     return result;
    16. }

    四   【长度最小的子数组】

    原题链接：LCR 008. 长度最小的子数组 - 力扣（LeetCode）

    给定一个含有 n 个正整数的数组和一个正整数 target 。

    找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

    示例 1：

    输入：target = 7, nums = [2,3,1,2,4,3]
    输出：2
    解释：子数组 [4,3] 是该条件下的长度最小的子数组。
    示例 2：

    输入：target = 4, nums = [1,4,4]
    输出：1
    示例 3：

    输入：target = 11, nums = [1,1,1,1,1,1,1,1]
    输出：0

         思路一：暴力解法

    1. class Solution {
    2.     public int minSubArrayLen(int target, int[] nums) {
    3.         int result = Integer.MAX_VALUE; // 最终的结果
    4.         int sum = 0; // 子序列的数值之和
    5.         int subLength = 0; // 子序列的长度
    6.         for (int i = 0; i < nums.length; i++) { // 设置子序列起点为i
    7.             sum = 0;
    8.             for (int j = i; j < nums.length; j++) { // 设置子序列终止位置为j
    9.                 sum += nums[j];
    10.                 if (sum >= target) { // 一旦发现子序列和超过了s，更新result
    11.                     subLength = j - i + 1; // 取子序列的长度
    12.                     result = result < subLength ? result : subLength;
    13.                     break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break
    14.                 }
    15.             }
    16.         }
    17.         // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
    18.         return result == Integer.MAX_VALUE ? 0 : result;
    19.  
    20.     }
    21. }
    • 时间复杂度：O(n^2)
    • 空间复杂度：O(1)

    思路二：滑动窗口

    我们让终止位置j在数组中向前滑动，当满足数组中的元素加起来大于目标值时，起始位置开始移动缩小范围，同时每次记录下最小的长度，不断比较。

    动态效果：（以题目中例1为例）

    【代码实现】

    C:

    1. int minSubArrayLen(int target, int* nums, int numsSize){
    2.     int i=0;//起始指针
    3.     int j=0;//终止指针
    4.     int result=2147483647;
    5.     int sum=0;
    6.     int l;//记录满足要求的子数组长度
    7.     for(j=0;j<numsSize;j++){//终止指针移动
    8.         sum=sum+nums[j];//记录数据和
    9.         while(sum>=target){
    10.             l=j-i+1;
    11.             result=result<l? result:l;
    12.             sum=sum-nums[i];
    13.             i++;
    14.         }
    15.     }
    16.     return result==2147483647?0:result;
    17. }

    Java:

    1. class Solution {
    2.  
    3.     // 滑动窗口
    4.     public int minSubArrayLen(int s, int[] nums) {
    5.         int left = 0;
    6.         int sum = 0;
    7.         int result = Integer.MAX_VALUE;
    8.         for (int right = 0; right < nums.length; right++) {
    9.             sum += nums[right];
    10.             while (sum >= s) {
    11.                 result = Math.min(result, right - left + 1);
    12.                 sum -= nums[left++];
    13.             }
    14.         }
    15.         return result == Integer.MAX_VALUE ? 0 : result;
    16.     }
    17. }

    参考资料：

    1.代码随想录 (programmercarl.com)

    （强烈推荐新小白不会刷题的可以看这个结合B站代码随想录的课程）

    2.力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

  • 相关阅读:
    Java扩展Nginx之一：你好，nginx-clojure
    Linux系统离线安装RabbitMQ
    无线渗透理论_无线通信过程
    MySQL 优化，查询的原理，索引的使用，如何优化查询
    阴影（shadow mapping）（硬阴影）
    C语言assert函数:什么是“assert”函数
    容错计算和恢复
    编写HTTP协议代理的一些知识（源码）
    set_seed(args)
    Microsoft Dynamics 365：Dynamics NAV 2016 Setup 安装（澳洲版）
  • 原文地址：https://blog.csdn.net/2301_77599154/article/details/133065603