代码随想录算法训练营第一天|704二分查找、27移除元素、977有序数组的平方
代码随想录算法训练营第一天|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题目中的知识点
- 一些可以用指针思路做的题,其实也可以用最基础的暴力搜索的办法去写
- 手撕二分法,二分法的结构就是找中间数进行比较,如果是想要的数字就返回,否则继续进行中间数查找,循环这个过程
- 删除元素里面的知识点重点在于数组内的数据不是直接删除,而是通过移动替换的方式,即列表内数据是不可以直接删除的
- 有序数组平方的知识点在于一个有序列表,他们的最大值和最小值一定是在两边,所以可以直接比较
4.2一些写代码掌握的知识
4.2.1python
- 在语句中注意for循环中的range函数的使用,这个函数的值是根据range的值走的,不会因为我对值进行改变他就会有大的变化
- 列表中使用sort函数,是直接对原始数据进行排序的,如果写
python return nums.sort()
不会输出排序的结果,会报错
4.2.2 C++
- 这里面首先学习的就是两种标点符号所表达的意思不同,在python中
a,b=1,2
是正确语法,但是在C++就需要写成int a=1,b=2;
- C++的排序也是使用sort函数,但是这个sort函数写的规则为
sort(nums.begin(),nums.end())
来表示其起始和终点的位置