本文主要是介绍【LC刷题】DAY02:977 209 59,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
#【LC刷题】DAY02:977 209 59
文章目录
- 977. 有序数组的平方 [link](https://leetcode.cn/problems/squares-of-a-sorted-array/description/)
- 第一思路:直接排序
- 优化:双指针
- 209. 长度最小的子数组 [link](https://leetcode.cn/problems/minimum-size-subarray-sum/description/)
- 第一思路:
- 59. 螺旋矩阵 II
977. 有序数组的平方 link
第一思路:直接排序
class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {for(int i = 0; i <= nums.size() - 1; i ++ ){nums[i] = nums[i] * nums[i];}sort(nums.begin(),nums.end());return nums;}
};
时间复杂度:时间复杂度:O(nlogn)
空间复杂度:O(logn)
优化:双指针
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;}
};
时间复杂度:O(n)O(n)O(n)
空间复杂度:O(1)O(1)O(1)
209. 长度最小的子数组 link
第一思路:
class Solution {
public:int minSubArrayLen(int s, vector<int>& nums) {int n = nums.size();if (n == 0) {return 0;}int ans = INT_MAX;vector<int> sums(n + 1, 0); for (int i = 1; i <= n; i++) {sums[i] = sums[i - 1] + nums[i - 1];}for (int i = 1; i <= n; i++) {int target = s + sums[i - 1];auto bound = lower_bound(sums.begin(), sums.end(), target);if (bound != sums.end()) {ans = min(ans, static_cast<int>((bound - sums.begin()) - (i - 1)));}}return ans == INT_MAX ? 0 : ans;}
};
59. 螺旋矩阵 II
class Solution {
public:vector<vector<int>> generateMatrix(int n) {int maxNum = n * n;int curNum = 1;vector<vector<int>> matrix(n, vector<int>(n));int row = 0, column = 0;vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 右下左上int directionIndex = 0;while (curNum <= maxNum) {matrix[row][column] = curNum;curNum++;int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];if (nextRow < 0 || nextRow >= n || nextColumn < 0 || nextColumn >= n || matrix[nextRow][nextColumn] != 0) {directionIndex = (directionIndex + 1) % 4; // 顺时针旋转至下一个方向}row = row + directions[directionIndex][0];column = column + directions[directionIndex][1];}return matrix;}
};
时间复杂度:O( n 2 n^2 n2)
空间复杂度:O(1)
这篇关于【LC刷题】DAY02:977 209 59的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!