首页 > 编程语言 >代码随想录算法训练营第二天|977.有序数组的平方 ,209.长度最小的子数组 ,59.螺旋矩阵II

代码随想录算法训练营第二天|977.有序数组的平方 ,209.长度最小的子数组 ,59.螺旋矩阵II

时间:2024-01-25 20:45:27浏览次数:35  
标签:977 temp nums int 随想录 ++ flag vector 数组

977.有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
题目链接:https://leetcode.cn/problems/squares-of-a-sorted-array/

  • 错误的vector遍历方式,这会导致访问越界!!!while(nums[flag]<0)flag++;

倒也不难,我的思路是先找到分界点然后向两头前进,用归并排序的思想解题。
下面是我的答案:

点击查看代码
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int flag = 0;
        while ((nums[flag] < 0) && (flag + 1 < nums.size()))
            flag++;
        if (flag >= nums.size())
            flag = nums.size() - 1;
        for (int i = 0; i < nums.size(); i++) {
            nums[i] = nums[i] * nums[i];
        }
        int j, k;
        j = 1, k = 1;
        vector<int> temp;
        if (flag != 0)
            if (nums[flag] > nums[flag - 1])
                flag--;
        temp.insert(temp.end(), nums[flag]);
        while ((flag - j >= 0) && (flag + k < nums.size())) {
            if (nums[flag - j] < nums[flag + k]) {
                temp.insert(temp.end(), nums[flag - j]);
                j++;
            } else {
                temp.insert(temp.end(), nums[flag + k]);
                k++;
            }
        }

        if (flag - j < 0)
            for (int i = flag + k; i < nums.size(); i++) {
                temp.insert(temp.end(), nums[i]);
            }
        else
            for (int i = flag - j; i >= 0; i--) {
                temp.insert(temp.end(), nums[i]);
            }

        return temp;
    }
};

我的答案pro版:

点击查看代码
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        int negative = -1;
        for (int i = 0; i < n; ++i) {
            if (nums[i] < 0) {
                negative = i;
            } else {
                break;
            }
        }

        vector<int> ans;
        int i = negative, j = negative + 1;
        while (i >= 0 || j < n) {
            if (i < 0) {
                ans.push_back(nums[j] * nums[j]);
                ++j;
            }
            else if (j == n) {
                ans.push_back(nums[i] * nums[i]);
                --i;
            }
            else 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;
            }
        }

        return ans;
    }
};

作者:力扣官方题解
链接:https://leetcode.cn/problems/squares-of-a-sorted-array/solutions/447736/you-xu-shu-zu-de-ping-fang-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
更优化的双指针,从首尾开始:
点击查看代码
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;) {
            if (nums[i] * nums[i] > nums[j] * nums[j]) {
                ans[pos] = nums[i] * nums[i];
                ++i;
            }
            else {
                ans[pos] = nums[j] * nums[j];
                --j;
            }
            --pos;
        }
        return ans;
    }
};

作者:力扣官方题解
链接:https://leetcode.cn/problems/squares-of-a-sorted-array/solutions/447736/you-xu-shu-zu-de-ping-fang-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
题目链接:https://leetcode.cn/problems/minimum-size-subarray-sum/
记录一下思路:首先窗口不断滑动,先动尾部,当超出target时移动首部直到不超出target,继续移动尾部。同时记录结果最小值。

点击查看代码
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int count=0;
        int start=0;
        int num=-1;
        for(int i=0;i<nums.size();i++){
        count+=nums[i];
        if(count>=target){           
        do{        
            if((num>i-start)||(num<0))num=i-start+1;

            count-=nums[start];
            start++;
        }while(count>=target);

        }
        }

        if(num>0)return num;
        return 0;
    }
};

59. 螺旋矩阵 II

给你一个正整数 n ,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
题目链接:https://leetcode.cn/problems/spiral-matrix-ii/
image
本题投降
可用模拟的思想,模拟矩阵的生成,跑一段直线到头削掉一层,这样的思路最清晰简洁了。

点击查看代码
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int k=1;
        int top=0;
        int buttom=n-1;
        int left=0;
        int right=n-1;
    vector<vector<int>>Max(n,vector<int>(n));
    while(k<=n*n){
        for(int i=left;i<=right;i++,k++) Max[top][i]=k;
        top++;
        for(int i=top;i<=buttom;i++,k++) Max[i][right]=k;
        right--;
        for(int i=right;i>=left;i--,k++)Max[buttom][i]=k;
        buttom--;
        for(int i=buttom;i>=top;i--,k++)Max[i][left]=k;
        left++;
    }
    return Max;
    }
};

标签:977,temp,nums,int,随想录,++,flag,vector,数组
From: https://www.cnblogs.com/Liubox/p/17988137

相关文章

  • 收集Stream流的数据到集合或数组中
    1publicstaticvoidmain(String[]args){2List<String>list=newArrayList<>();3list.add("张三");4list.add("李四");5list.add("王武");6list.add("王武"......
  • [代码随想录] 第十四天
    222.完全二叉树的节点个数[https://leetcode.cn/problems/count-complete-tree-nodes/submissions/498293461/]思路:递归法classSolution{publicintmaxDepth(TreeNoderoot){if(root==null){return0;}intleftDepth=maxDep......
  • P3374 【模板】树状数组 1(线段树)
    【模板】树状数组1题目描述如题,已知一个数列,你需要进行下面两种操作:将某一个数加上x求出某区间每一个数的和输入格式第一行包含两个正整数n,m,分别表示该数列数字的个数和操作的总个数。第二行包含n个用空格分隔的整数,其中第i个数字表示数列第i项的初始值......
  • P8659 [蓝桥杯 2017 国 A] 数组操作 题解
    题目链接:洛谷或者蓝桥杯或者C语言中文网几个OJ的AC记录:忘了哪个OJ的:洛谷:C语言中文网:蓝桥杯:emmmmmmm,好像每个OJ给的时限和空间还不一样,蓝桥杯官方还给了$3s$和$2G$,C语言中文网机子比较老可能,挺卡常的,开了个究极快读和指令集就过去了,也可以自己调下重构常数,偷懒......
  • P3374 【模板】树状数组 1
    part1#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;structnode1{intl,r,value;};node1node[2000020];inta[500010];voidmt(intp,intl,intr){intmid=(l+r)>>1;node[p].l=l;node[p].r=r;if(l==r)......
  • P3368 【模板】树状数组 2
    #include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintMax=500005;inta[Max];intn,m;intlowbit(intx){ returnx&-x;}voidadd(intx,inty){ while(x<=n){ a[x]+=y; x+=lowbit(x); }}intsum(intx)......
  • P9779_[HUSTFC 2023] 不定项选择题_题解
    rt题目有一道共n个选项的不定项选择题,它的答案至少包含一个选项,由于题目与选项的内容晦涩难懂,你打算通过尝试每一种可能的答案来通过这道题。初始时所有选项都没有被勾选,你可以执行任意次下述操作:勾选一个当前未被勾选的选项。取消勾选一个当前已被勾选的选项。当你......
  • #yyds干货盘点# LeetCode程序员面试金典:和为 K 的子数组
    题目给你一个整数数组nums和一个整数k,请你统计并返回该数组中和为k的子数组的个数。子数组是数组中元素的连续非空序列。 示例1:输入:nums=[1,1,1],k=2输出:2示例2:输入:nums=[1,2,3],k=3输出:2 代码实现publicclassSolution{publicintsubarr......
  • 第十二天:SHELL编程之常见工具、数组及字符串切片
    一、信号捕捉traptrap命令可以捕捉信号,修改信号原来的功能,实现自定义功能#列出所有信号trap-l#进程收到系统发出的指定信号后,将执行自定义指令,而不会执行原操作trap'触发指令'信号#忽略信号的操作trap''信号#恢复原信号的操作trap'-'信号......
  • [代码随想录] 第十三天
    226.翻转二叉树[https://leetcode.cn/problems/invert-binary-tree/description/]递归:递归三部曲:①确定递归函数的参数和返回值②确定终止条件③确定单层递归的逻辑/***Definitionforabinarytreenode.*publicclassTreeNode{*intval;*TreeNodeleft;*T......