天涯头条

代码随想录算法训练营第一天|704二分查找、27移除元素、977有序数组的平方

2024-10-16 15:06 由 小方呀0524 发表于 #后端开发

代码随想录算法训练营第一天|704二分查找、27移除元素、977有序数组的平方

1 Leetcode 704 二分查找

题目链接：[704.二分查找](704. 二分查找 - 力扣（LeetCode）)

文章链接：[代码随想录](代码随想录 (programmercarl.com))

视频链接：[手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode：704. 二分查找](手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode：704. 二分查找_哔哩哔哩_bilibili)

状态：知道题目思路，但是每次在判断大于号和小于号需要思考一下，容易出错，还有开闭区间容易出错

思路：首先去找到一个数组中间的数值，然后判断中间数和目标数的大小，如果是比目标数小则移动左边的索引，否则移动右边索引，相等则返回中间值的索引

1.1这是一个左闭右闭的写法

1.1.1python版本的代码
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left,right = 0,len(nums)-1
        while left<=right:
            middle = left+(right-left)//2
            if nums[middle]<target:
                left = middle+1
            elif nums[middle]>target:
                right = middle-1
            else:
                return middle
        return -1

左闭右闭区间在于其索引值与数组下标索引值是一一对应的关系，所以有左边的索引等于右边的索引，代码内部的索引也是对应相等的

1.1.2 C++版本
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left= 0,right = nums.size()-1;
        while (left<=right){
            int middle = (left+right)/2;
            if (nums[middle]<target){
                left = middle+1;
            }
            else if (nums[middle]>target){
                right = middle-1;
            }
            else {return middle;}
        } 
        return -1;
    }
};

1.2 左闭右开区间的写法

1.2.1 python版本
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left,right = 0,len(nums)
        while left<right:
            middle = left+(right-left)//2
            if nums[middle]<target:
                left = middle+1
            elif nums[middle]>target:
                right = middle
            else:
                return middle
        return -1
C++版本
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left= 0,right = nums.size();
        while (left<right){
            int middle = (left+right)/2;
            if (nums[middle]<target){
                left = middle+1;
            }
            else if (nums[middle]>target){
                right = middle;
            }
            else {return middle;}
        } 
        return -1;
    }
};

1.3小结

1.3.1 python注意细节

python内部需要注意最后返回值在循环以外，不然会有报错的情况

1.3.2 C++注意细节

​ a.每行代码结束的时候是有英文状态下的;的，每次忘记则会报错
​
​ b.和python不同的点事python赋值是链表赋值，但是C++语言是一个一个给值的，所以如果想要一行赋值，则需要进行一句一句的等于，不然会报错

2 Leetcode 27 移除元素

题目链接：27. 移除元素

文章链接：[移除元素](代码随想录 (programmercarl.com))

视频链接：[数组中移除元素并不容易！ | LeetCode：27. 移除元素](数组中移除元素并不容易！ | LeetCode：27. 移除元素_哔哩哔哩_bilibili)

思路：无从下手，，，

2.1 暴力搜索

才开始没看明白为什么，然后纸上画了一遍明白了这个是先搜索数值，如果出现了预期值，则进行一个相加，否则的话就是继续去寻找，数组是覆盖而不是删除，用覆盖的思想表示了删除的意思

2.1.1 python版本

错误原因：开始的时候想用for循环，然后i从range里面取值，进行i-=1后变成了-1，在进行下一轮的时候还是从range内取值，对其没影响，导致错误

更改：将其转换为while的时候，这个值是一个可控变量

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i,n =0,len(nums)
        while i<n:
            if nums[i]==val:    
                for j in range(i+1,n):
                    nums[j-1]=nums[j]
                n -=1
                i -=1
            i +=1
        return n
2.1.2 C++版本
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int n =nums.size();
        for (int i=0;i<n;i++){
            if (nums[i]==val){
                for (int j =i+1;j<n;j++){
                    nums[j-1]=nums[j];
                }
                i--;
                n--;
            }
        }
        return n;
    }
};

2.2快慢指针的方法

2.2.1 python版本
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        slowind = 0
        for i in range(len(nums)):
            if nums[i] != val:
                nums[slowind] = nums[i]
                slowind +=1
        return slowind
2.2.2 C++版本
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slowind = 0;
        for (int fastind=0;fastind<nums.size();fastind++){
            if (nums[fastind]!=val){
                nums[slowind++] = nums[fastind];
            }
        }
        return slowind;
    }
};

2.3小结

思路：双指针的方法，本质是两层for循环，但是循环的话对于时间复杂度会很高，就会造成报错的情况，所以就想办法看可不可以将一层循环转换成数据标识，进行比较，如果有相等的，就去覆盖数值，否则就继续向前走的思路

遇到的问题：在理解了双指针以后，就是不知道两个指针的快慢应该怎么选择在这一块卡了一下，然后根据已有代码进行绘制走的过程，使用pycharm进行debug了一下，就理解了这个思路

3 Leetcode 977 有序数组的平方

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

文章链接：代码随想录 (programmercarl.com)

视频链接：双指针法经典题目 | LeetCode：977.有序数组的平方

3.1自己的思路和解题

先逐步求出他们的平方值，然后将其保存，最后使用sort函数对列表进行排序即可

3.1.1python版本
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        for i in range(len(nums)):
            nums[i]=nums[i]**2
        nums.sort()
        return nums
3.1.2C++版本

这种方法学习了C++排序的一个函数，sort函数，这个函数需要指定元素的起始和终止位置即可

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        for (int i =0;i<nums.size();i++){
            nums[i] = nums[i]*nums[i];
        }
        sort(nums.begin(),nums.end());
        return nums;
    }
};

3.2双指针的思路

3.2.1python版本的思路
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        i,j = 0,len(nums)-1
        result = list()
        while i<=j:
            if nums[i]**2<nums[j]**2:
                result.append(nums[j]**2)
                j -=1
            else:
                result.append(nums[i]**2)
                i +=1
        return result[::-1]
3.2.2C++版本

这道题就是让我理解了C++里面的,和;的区别，有一种直白的说法就是，一句话没说完就用,否则就用;，拿这道题来举例在循环中对i和j进行赋值的时候，他俩都需要定义为整型，所以用,但是里面一句话彻底结束，下一个不需要这个定义的时候就用分号

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n =nums.size()-1;
        vector<int> result(nums.size(),0);
        for (int i=0,j=nums.size()-1;i<=j;){
            if ((nums[i]*nums[i])<(nums[j]*nums[j])){
                result[n--]= nums[j]*nums[j];
                j --;
            }
            else{
                result[n--]=nums[i]*nums[i];
                i++;
            }
        }
        return result;
    }
};

4 今日学习小结

4.1题目中的知识点

  1. 一些可以用指针思路做的题，其实也可以用最基础的暴力搜索的办法去写
  2. 手撕二分法，二分法的结构就是找中间数进行比较，如果是想要的数字就返回，否则继续进行中间数查找，循环这个过程
  3. 删除元素里面的知识点重点在于数组内的数据不是直接删除，而是通过移动替换的方式，即列表内数据是不可以直接删除的
  4. 有序数组平方的知识点在于一个有序列表，他们的最大值和最小值一定是在两边，所以可以直接比较

4.2一些写代码掌握的知识

4.2.1python
  1. 在语句中注意for循环中的range函数的使用，这个函数的值是根据range的值走的，不会因为我对值进行改变他就会有大的变化
  2. 列表中使用sort函数，是直接对原始数据进行排序的，如果写python return nums.sort() 不会输出排序的结果，会报错
4.2.2 C++
  1. 这里面首先学习的就是两种标点符号所表达的意思不同，在python中a,b=1,2是正确语法，但是在C++就需要写成int a=1,b=2;
  2. C++的排序也是使用sort函数，但是这个sort函数写的规则为sort(nums.begin(),nums.end())来表示其起始和终点的位置