马上要开始找实习了,又开始重启刷题计划了!加油冲冲冲!刷题的顺序follow代码随想录的60天刷题计划!感谢FuCosmo的总结!之前都是按照C++的语法进行刷题的,这次也同样使用C++。
Day 1 数组
这些题过年前都刷过了,所以过的快一些。通过写一些题解的方式来,帮助自己回顾这些方法,记住一些核心点。
704. 二分查找
- 训练是否取等号,这里选择的是双边都闭合的空间
- 对于mid的计算方式,有两种mid = (left + right) / 2或者是mid = left + (left - right) / 2
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
int mid;
while (left <= right) {
mid = (left + right) / 2;
if (nums[mid] == target){
return mid;
} else if (nums[mid] < target){
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
};
27. 移除元素
- 双指针的思想
- 一个指针用来遍历数组中的所以元素(指向当前将要处理的元素)
- 一个指针用来记录下一个将要赋值的位置
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int i = 0;
int j = 0;
while (i < nums.size()) {
if (nums[i] != val) {
nums[j] = nums[i];
j++;
}
i++;
}
return j;
}
};
977. 有序数组的平方
- 暴力的解放,利用sort函数
- 基本的语法
- vector的创建
vector<int> ans;
vector<int> ans(n);
- vector中添加元素
ans.push_back(num);
- vector的排序
sort(ans.begin(), ans.end());
- vector的创建
- 时间复杂度是 O(nlogn),其中 n 是数组 nums的长度。
- 空间复杂度是 O(logn),除了存储答案的数组以外,我们需要 O(logn) 的栈空间进行排序
- 基本的语法
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int i = 0;
vector<int> ans;
while (i < nums.size()){
ans.push_back(nums[i] * nums[i]);
i++;
}
sort(ans.begin(), ans.end());
return ans;
}
};
- 双指针的解法
- 非递减数组,元素当中存在负数
- 第一个指针指向找到第一个大于等于0的元素
- 如果第一个指针为0,则不需要第二个指针
- 反之,第二个指针指向第一个元素左侧的元素
- 比较左右指针两个元素的大小,逐个加入
- 这里需要用到三个循环
- 同时移动两个指针
- 当一个指针已经移动完,则只移动单侧的指针
- 时间复杂度是O(n)。其中 n 是数组 nums 的长度。
- 空间复杂度是O(1)。除了存储答案的数组以外,我们只需要维护常量空间。
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int i = 0;
vector<int> ans;
for (int num : nums) {
if (num < 0) {
i++;
} else {
break;
}
}
if (i == 0) {
for (int num : nums) {
ans.push_back(num * num);
}
return ans;
} else {
int j = i - 1;
while (i < nums.size() && j >= 0) {
if (nums[i] * nums[i] < nums[j] * nums[j]) {
ans.push_back(nums[i] * nums[i]);
i++;
} else {
ans.push_back(nums[j] * nums[j]);
j--;
}
}
while (i < nums.size()) {
ans.push_back(nums[i] * nums[i]);
i++;
}
while (j >= 0){
ans.push_back(nums[j] * nums[j]);
j--;
}
}
return ans;
}
- 双指针的解法二
- 一个指针指向第一个元素
- 另一个指针指向最后一个元素
- 从后往前加元素
- 时间复杂度是O(n)。其中 n 是数组 nums 的长度。
- 空间复杂度是O(1)。除了存储答案的数组以外,我们只需要维护常量空间。
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n);
for (int i = 0, j = n - 1, pos = n - 1; i <= j; pos--) {
if (nums[i] * nums[i] > nums[j] * nums[j]) {
ans[pos] = nums[i] * nums[i];
i++;
} else {
ans[pos] = nums[j] * nums[j];
j--;
}
}
return ans;
}
};