代码随想录算法训练营第二天|LeetCode 977.有序数组的平方 、209.长度最小的子数组 、59.螺旋矩阵II
LeetCode 977.有序数组的平方
题目链接:977.有序数组的平方
思路:
1、先对每个数进行遍历平方,并插入新的容器中
2、对容器进行排序,返回就可以了
缺陷:开辟了新的容器空间
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
vector<int> v;
for (int i = 0; i < nums.size(); i ) {
v.push_back(pow(nums[i],2));
}
sort(v.begin(), v.end());
return v;
}
};
思路:
写此博客的过程中,突然想到我为什么还要重新开辟容器空间,直接在原数据上进行操作不就好了嘛,然后直接改了代码,这就没有额外的内存消耗了。
1、直接对原数据进行平方并进行替换
2、对容器进行排序,返回就可以了
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
for (int i = 0; i < nums.size(); i ) {
nums[i] = pow(nums[i],2);
}
sort(nums.begin(), nums.end());
return nums;
}
};
LeetCode 209.长度最小的子数组
题目链接:209.长度最小的子数组
解法一:暴力(不考虑超时)
以下代码为暴力方法,for循环里面嵌套一个for循环进行搜索,却只通过了17个测试用例,后面一直超时错误,也没想到其他方法,就看了别人的方法,在后面。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
vector<int> v;
int x,y;
int sum2 = 0;
for (int i = 0; i < nums.size(); i ) {
if (nums[i] >= target) {
v.push_back(1);
}
}
for (int i = 0; i < nums.size()-1; i ) {
int sum = nums[i];
for (int j = i 1; j < nums.size(); j ) {
sum = nums[j];
if (sum >= target) {
x = i;
y = j;
int sub = y-x 1;
v.push_back(sub);
break;
}
}
}
if (v.empty()) {
v.push_back(0);
}
sort(v.begin(),v.end());
return v[0];
}
};
官方的暴力更简便点,但都一个思路,我写的冗余点,但官方暴力还是无法AC。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
if ( n == 0) {
return 0;
}
int ans = INT_MAX;
for (int i = 0; i < n; i ) {
int sum = 0;
for (int j = i; j < n; j ) {
sum = nums[j];
if (sum >= target) {
ans = min(ans, j-i 1);
break;
}
}
}
return ans == INT_MAX ? 0 : ans;
}
};
解法二:滑动窗口
思路:不断的调节子序列的起始位置和终止位置,假如先设置起始位置,其思想和暴力没什么区别,所以得先设置终止位置。
1、设置j为终止位置指针,不断往后遍历,直到大于等于target的位置
2、滑动起始位置,往后移动一位(这时候窗口内的和会减去之前起始的一位,由于减去的这个数的值不知道大小,所以可能减去还是会大于等于target,所以要用while进行判断),然后不断进行更新判断就行
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int ans = INT32_MAX;
int sum = 0;
int i = 0;
for(int j = 0; j < nums.size(); j ){
sum = nums[j];
while(sum >= target) {
ans = min(ans, j-i 1);
sum = sum - nums[i];
i ;
}
}
return ans == INT_MAX ? 0 : ans;
}
};
LeetCode 59.螺旋矩阵II
题目链接:59.螺旋矩阵II
思路:按照螺旋的规律,对矩阵进行填充,先填外圈,再填内圈,直到最里面
根据下图可有效得到:
1、先判断要填几圈,也就是最外层的for循环要走多少次。
2、每一圈填充时,每次都走该圈的边长减1
即,走4X4最外圈时,每次都走3步,走里圈2X2时,每次都走1步。
走5X5最外圈时,每次都走4步,走里圈3X3时,每次都走2步,最后还剩下一个。
3、由于每圈的走法都是一样的,都分为四次,所以只需要写一圈的的走法就可以
设定四个指针变量,方便到内圈的时候也适用。
第一次走,横坐标不变(为heng),纵坐标从zong走到zong_wei - 1;
第二次走,纵坐标不变(为zong_wei),横坐标从heng走到heng_wei - 1;
第三次走,横坐标不变(为heng_wei),纵坐标从zong_wei走到zong 1;
第四次走,纵坐标不变(为zong),横坐标从heng_wei走到heng 1;
执行完,对zong ;zong_wei–;heng ;heng_wei–;即可进入下一圈。
注意:特殊奇数螺旋矩阵的时候,最里面一圈只填入一个,当zong和zong_wei都指向最中间时(heng和heng_wei也指向最中间)插入完,会再对它们进行 和–操作,这时候会报错,所以这时候需要判断以下。
4、走完输出即可。
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> v(n, vector<int>(n));
int heng = 0;
int heng_wei = n-1;
int zong = 0;
int zong_wei = n-1;
int k = n/2;
int m = 1;
if (n == 1){
v[0][0] = 1;
}
else{
for (int j = 0; j <= k-1; j ) {
for (int i = zong; i <= zong_wei-1; i ) {
v[heng][i] = m;
m ;
}
for (int i = heng; i <= heng_wei-1; i ) {
v[i][zong_wei] = m;
m ;
}
for (int i = zong_wei; i >= zong 1; i--) {
v[heng_wei][i] = m;
m ;
}
for (int i = heng_wei; i >= heng 1; i--) {
v[i][zong] = m;
m ;
}
heng ;
heng_wei --;
zong ;
zong_wei --;
if (heng == heng_wei){
v[heng][heng] = m;
}
}
}
return v;
}
};
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhggibgi
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13