【基础】leetcode 704 二分查找
居然做出来了（python3），说明这个知识点以前看的基本还记得
注意细节，例如大数越界问题，看视频之前完全没想到核心思路：保持左闭右开或者左闭右闭的核心一致性
总结：如果是左闭右开，进入条件就是小于，条件里面l或r只更新一个；如果是左闭右闭，进入条件就是小于等于，条件里面l或r都要更新；当然，不要死记硬背，灵活使用
todo：二分算法的变形，掌握得很差
# python3 左闭右开写法
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) # 左闭右开
while l < r:
mid = l + (r - l) // 2 # python3里面要用地板除
if nums[mid] < target:
l = mid + 1
elif nums[mid] > target:
r = mid
else:
return mid
return -1
// c++ 左闭右闭写法
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] < target) l = mid + 1;
else if (nums[mid] > target) r = mid - 1;
else return mid;
}
return -1;
}
};
【基础】leetcode 27 移除元素
用了20-30min做出来了，走了不少弯路：
弯路一：读错题了，以为是要把需要的元素放在最前面
弯路二：想在弯路一的基础上修改伪代码，搞了很久，发现搞不定。所以一旦发现理解错了，就要从0开始整理思路啊！（很重要！！）核心思路：讲解是用快慢指针的思路，把快指针的值赋给慢指针，相当于原地复用数组的前段空间
我自己做的用的是前后指针，前指针向后，后指针向前，遇到目标val，就交换，不过这样做有个缺点，会打乱前面的顺序其实就是练习自己实现vector的erase操作，使用O（n）时间复杂度的方式
遇题不慌，先用伪代码整体考虑所有的场景、每个场景做什么处理操作，再开始写代码，再边写边看哪里可以合并和优化
双指针和二分法都很难，基础很简单，一变形就懵了
// c++
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int s = 0;
for (int f = 0; f < nums.size(); f++) { // 注意声明f为int并初始化为0
if (nums[f] != val) {
nums[s++] = nums[f];
}
}
return s;
}
};
# python3
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
i, j = 0, 0 // 不可以写作 i, j = 0
for j in range(len(nums)):
if nums[j] != val:
nums[i] = nums[j]
i += 1
return i
【扩展】leetcode 35 搜索插入位置
虽然说也是做出来了，但是场景没有合并，显得很冗余和不高级
核心思路：其实重点是想清楚l和r最终停留在什么位置，把几个可能的场景都分析一遍（空、插在第一个、插在中间、插在最后），就会发现都可以统一返回l：
- 列表为空，不进循环，直接return 0
- 插在列表头，最后一次进循环一定是l=r=0，那么在最后一次循环中，l不变，r又减了1，所以return l=0
- 插在列表中间，最后一次进循环l=r，如果且该位置的值小于目标值，那么l又加了1，返回l合理；如果该位置的值大于目标值，那么l不变，返回l也合理
- 插在列表最后，最后一次进循环一定是l=r=len-1，那么在最后一次循环中，l又加了1，返回l合理
这一题感觉用左闭右闭来做分析比较简单，因为最后一次进循环l=r
写惯了python，写C++还是会经常忘记写分号、写大括号
# python3
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l <= r:
mid = l + (r - l) // 2
if nums[mid] < target:
l = mid + 1
elif nums[mid] > target:
r = mid - 1
else:
return mid
return l
// c++
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l = 0, r = nums.size(); // 试试左闭右开解法
while (l < r) {
int mid = l + (r - l) / 2;
if (nums[mid] < target) {
l = mid + 1;
}
else if (nums[mid] > target) {
r = mid;
}
else {
return mid;
}
}
return l;
}
};
day1 语法积累
- python的初始化 vs C++的初始化
l, r = 0, len(nums) // python3
int l = 0, r = nums.size() - 1; // C++
- python的整数除 vs C++的整数除
mid = l + (r - l) // 2 // python3用地板除的方法
int mid = l + (r - l) / 2;
- python变量直接拿来用 vs C++变量需要声明类型
- python的elif vs C++的else if
- python的len(n) vs C++的n.size()
- python的while、if等条件不加括号 vs C++条件加括号
- python讲究严格缩进 vs C++以分号结尾
- python和C++的数组取数都是nums[i]的格式
