网上代理 建网站,网站建设好友,网站建设用什么开源程序好,网站基本功能马上要开始找实习了#xff0c;又开始重启刷题计划了#xff01;加油冲冲冲#xff01;刷题的顺序follow代码随想录的60天刷题计划#xff01;感谢FuCosmo的总结#xff01;之前都是按照C的语法进行刷题的#xff0c;这次也同样使用C。
Day 1 数组
这些题过年前都刷过了…马上要开始找实习了又开始重启刷题计划了加油冲冲冲刷题的顺序follow代码随想录的60天刷题计划感谢FuCosmo的总结之前都是按照C的语法进行刷题的这次也同样使用C。
Day 1 数组
这些题过年前都刷过了所以过的快一些。通过写一些题解的方式来帮助自己回顾这些方法记住一些核心点。
704. 二分查找
训练是否取等号这里选择的是双边都闭合的空间对于mid的计算方式有两种mid (left right) / 2或者是mid left (left - right) / 2
class Solution {
public:int search(vectorint 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(vectorint 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的创建 vectorint ans;vectorint ans(n); vector中添加元素 ans.push_back(num); vector的排序 sort(ans.begin(), ans.end()); 时间复杂度是 O(nlogn)其中 n 是数组 nums的长度。空间复杂度是 O(logn)除了存储答案的数组以外我们需要 O(logn) 的栈空间进行排序
class Solution {
public:vectorint sortedSquares(vectorint nums) {int i 0;vectorint 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:vectorint sortedSquares(vectorint nums) {int i 0;vectorint 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:vectorint sortedSquares(vectorint nums) {int n nums.size();vectorint 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;}
};Day 2
209.长度最小的子数组
双指针的思想 左右两个指针当当前区间内的值小于target则移动右指针反之移动左指针区间是左闭右开的利用cnt来记录最短的长度right - left 1这道题感觉是滑动窗口的思想 基本语法知识 三目运算符条件表达式True : FalseINT的最大值int ans INT_MAX
// 有点冗余的写法
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int left 0;int right left 1;int cnt nums[0];int n nums.size();int minlength n 1;while(right n) {if (cnt target) {cnt nums[right];right;} else if (cnt target) {if ((right - left) minlength) {minlength right - left;}cnt - nums[left];left;}}// 当right已经走到最右端了,但cnt依旧大于0while(left n) {if (cnt target) {if ((right - left) minlength) {minlength right - left;}cnt - nums[left];left;} else {break;}}return (minlength n) ? 0 : minlength;}
};// 看完题解后的优化代码
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int left 0;int right 0;int cnt 0;int n nums.size();int minlength n 1;while(right n) {cnt nums[right];while (cnt target) {minlength min(minlength, right - left 1);cnt - nums[left];left;}right;}return (minlength n) ? 0 : minlength;}
};时间复杂度为O(n)空间复杂度为O(1)
Day 3 栈与队列
239. 滑动窗口最大值
用一个队列来存储当前窗口内的元素对队列中的元素进行排序取出最大值
347.前K个高频元素
使用字典key为对应的元素value为对应的出现次数遍历整个数组然后按照value进行排序然后输出前K个结果思想是上述的思想但是如何根据value排序是一个难点这里用到了堆的思想也就是优先队列的思想基本语法 priority_queue的基本函数push(), pop(), top(), empty(), size();默认为大根堆如果想要小元素放在队首则可以使用以下的方式 priority_queueint,vectorint,greaterintqC11中的STL 可以使用emplace()与emplace_back()来代替insert()与push_back()
class Solution {public:vectorint topKFrequent(vectorint nums, int k) {unordered_mapint,int ans;for (int num : nums) {ans[num];}// 排序priority_queuepairint, int q;for (auto item : ans) {q.emplace(item.second, item.first);}//求解vectorint res;while(k) {res.emplace_back(q.top().second);q.pop();--k;}return res;}
};
