0.引言
1.有序数组的平方
| Category | Difficulty | Likes | Dislikes |
|---|---|---|---|
| algorithms | Easy (68.47%) | 733 | - |
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
提示：
1 <= nums.length <= 10<sup>4</sup>-10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>-
nums已按 非递减顺序 排序
进阶：
- 请你设计时间复杂度为
O(n)的算法解决本问题
1.1.自己想法及代码实现
第一想法是平方后排序，或者把负数转为正数后排序再平方。
/*
* @lc app=leetcode.cn id=977 lang=cpp
*
* [977] 有序数组的平方
*/
// @lc code=start
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
for (auto& i : nums) {
i *= i;
}
std::sort(nums.begin(), nums.end());
return nums;
}
};
// @lc code=end
显然调用排序函数时间复杂度不是O(1)。还是要从排序入手。双指针法：
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
if (nums.empty()) return nums;
for (auto& i : nums) {
if (i < 0) i *= -1;
}
int nums_size = nums.size();
std::vector<int> res(nums_size);
for (int left = 0, right = nums.size() - 1; left <= right;) {
if (nums[left] > nums[right]) {
res[--nums_size] = nums[left];
left++;
// res[--nums_size] = nums[left++]; //可以简化为
} else {
res[--nums_size] = nums[right];
right--;
}
}
for (auto& i : res) {
i *= i;
}
return res;
}
};
- 思想：从两端开始找大的数，存储到新的数组中。
- 之前的想法一直在原地排序上，卡住了，时间和空间还真不能兼顾啊！
1.2.参考想法及代码实现
- 大差不差
image.png
2.长度最小的子数组
| Category | Difficulty | Likes | Dislikes |
|---|---|---|---|
| algorithms | Medium (47.32%) | 1589 | - |
给定一个含有 n个正整数的数组和一个正整数 target** 。**
找出该数组中满足其和≥ target的长度最小的 连续子数组 [nums<sub>l</sub>, nums<sub>l+1</sub>, ..., nums<sub>r-1</sub>, nums<sub>r</sub>] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4]
输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
提示：
1 <= target <= 10<sup>9</sup>1 <= nums.length <= 10<sup>5</sup>1 <= nums[i] <= 10<sup>5</sup>
进阶：
- 如果你已经实现
O(n)时间复杂度的解法, 请尝试设计一个O(n log(n))时间复杂度的解法。
2.1.自己想法及代码实现
第一想法是先排序，然后暴力查找，不对，他要求是连续子数组。
第二想法快慢指针，俩指针之间的数就是满足条件的，同时要遍历完也就需要维护一个 min_len:
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
if (nums.empty()) return 0;
int slow_idx = 0, fast_idx = 0;
int min_len = std::numeric_limits<int>::max();
while (fast_idx < nums.size()) {
int sum = nums_sum(nums, slow_idx, fast_idx);
if (sum >= target) {
min_len = std::min(min_len, fast_idx - slow_idx + 1);
slow_idx ++;
} else{
fast_idx++;
}
}
return min_len == std::numeric_limits<int>::max() ? 0 : min_len;
}
private:
int nums_sum(vector<int>& nums, int i, int j) {
int res = 0;
for (; i <= j; ++i) {
res += nums[i];
}
return res;
}
};
自己实现的代码有case没通过。
我再看了一下，不是case没通过，是超时了，思想应该是没问题的。
之前把题目条件看为==了：
// 题目是 >= target,这个搞成 == 了
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
if (nums.empty()) return 0;
int slow_idx = 0, fast_idx = 0;
int min_len = std::numeric_limits<int>::max();
while (fast_idx < nums.size()) {
int sum = nums_sum(nums, slow_idx, fast_idx);
// std::cout << sum << " ";
if (target == sum) {
min_len = std::min(min_len, fast_idx - slow_idx + 1);
if (min_len == 1) return min_len;
slow_idx = fast_idx;
} else if (sum < target) {
fast_idx++;
} else {
slow_idx++;
}
}
return min_len == std::numeric_limits<int>::max() ? 0 : min_len;
}
private:
int nums_sum(vector<int>& nums, int i, int j) {
int res = 0;
for (; i <= j; ++i) {
res += nums[i];
}
return res;
}
};
暴力解法：
- 两层for循环，一个为起始位置，一个为结束位置，记录最小的len:
// 暴力法
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
if (nums.empty()) return 0;
int start_idx = 0, end_idx = 0;
int min_len = std::numeric_limits<int>::max();
for (int start_idx = 0; start_idx < nums.size(); ++start_idx) {
for (int end_idx = start_idx; end_idx < nums.size(); ++end_idx) {
if (nums_sum(nums, start_idx, end_idx) >= target) {
min_len = std::min(min_len, end_idx - start_idx + 1);
}
}
}
return min_len == std::numeric_limits<int>::max() ? 0 : min_len;
}
private:
int nums_sum(vector<int>& nums, int i, int j) {
int res = 0;
for (; i <= j; ++i) {
res += nums[i];
}
return res;
}
};
这里的nums_sum函数可以优化，不用每次每次都求和，加减变动的元素就行。为了更好的理解思想先就这样吧，优化不难。
还是优化一下吧：
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
if (nums.empty()) return 0;
int slow_idx = 0, fast_idx = 0;
int min_len = std::numeric_limits<int>::max();
int nums_sum = 0;
while (fast_idx < nums.size()) {
nums_sum += nums[fast_idx];
std::cout << nums_sum << " ";
if (nums_sum >= target) {
min_len = std::min(min_len, fast_idx - slow_idx + 1);
nums_sum -= nums[slow_idx];
nums_sum -= nums[fast_idx]; // 进入这个逻辑后 fast_idx被加了两次
slow_idx++;
} else {
fast_idx++;
}
}
return min_len == std::numeric_limits<int>::max() ? 0 : min_len;
}
};
2.2.参考想法及代码实现
- 大差不差。有一个优化的地方，就是找到最小的后break，往后只会更长，不需要遍历了，算是剪枝，这点遗忘了：
// 暴力法
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
if (nums.empty()) return 0;
int start_idx = 0, end_idx = 0;
int min_len = std::numeric_limits<int>::max();
for (int start_idx = 0; start_idx < nums.size(); ++start_idx) {
int nums_sum = 0;
for (int end_idx = start_idx; end_idx < nums.size(); ++end_idx) {
nums_sum += nums[end_idx];
if (nums_sum >= target) {
min_len = std::min(min_len, end_idx - start_idx + 1);
break; // 往后只会更长
}
}
}
return min_len == std::numeric_limits<int>::max() ? 0 : min_len;
}
};
3. 螺旋矩阵 II
| Category | Difficulty | Likes | Dislikes |
|---|---|---|---|
| algorithms | Medium (73.96%) | 958 | - |
给你一个正整数 n ，生成一个包含 1 到 n<sup>2</sup> 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
示例 1：
image.png
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]
示例 2：
输入：n = 1
输出：[[1]]
提示：
1 <= n <= 20
3.1.自己想法及代码实现
感觉就是找规律，一圈一圈的填充：
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
if (n == 0) return {};
int rows = n, cols = n;
vector<vector<int>> matrix(rows, vector<int>(cols));
int i_ceil = 0;
int i_floor = rows - 1;
int j_ceil = 0;
int j_floor = cols - 1;
int val = 1;
while (i_ceil <= i_floor && j_ceil <= j_floor) {
fill_one_circle(matrix, i_ceil, i_floor, j_ceil, j_floor, val);
i_ceil++, i_floor--;
j_ceil++, j_floor--;
}
return matrix;
}
private:
void fill_one_circle(vector<vector<int>>& matrix, int i_ceil, int i_floor,
int j_ceil, int j_floor, int& val) {
for (int j = j_ceil; j <= j_floor; ++j) { // 上
matrix[i_ceil][j] = val++;
}
for (int i = i_ceil + 1; i <= i_floor; ++i) { // 右
matrix[i][j_floor] = val++;
}
for (int j = j_floor - 1; j >= j_ceil; --j) { // 下
matrix[i_floor][j] = val++;
}
for (int i = j_floor - 1; i > i_ceil; --i) { // 左
matrix[i][j_ceil] = val++;
}
}
};
3.2.参考思想及代码实现
先占坑
填坑：
算法流程：
- 空值处理： 当 matrix 为空时，直接返回空列表 [] 即可。
- 初始化： 矩阵 左、右、上、下 四个边界 l , r , t , b ，用于打印的结果列表 res 。
- 循环打印： “从左向右、从上向下、从右向左、从下向上” 四个方向循环，每个方向打印中做以下三件事 （各方向的具体信息见下表） ；
- 1.根据边界填充，即将元素按顺序添加；
- 2.边界向内收缩 1，（代表已被打印）；
- 3.判断是否填充完毕（边界是否相遇），若填充完毕则跳出。
- 返回值： 返回 res 即可。
image.png
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
if (n == 0) return {};
int left = 0, right = n - 1, top = 0, bottom = n - 1, val = 1;
vector<vector<int>> matrix(n, vector<int>(n));
while (true) {
for (int i = left; i <= right; ++i) matrix[top][i] = val++; // left to right.
if (++top > bottom) break; // top 内陷
for (int i = top; i <= bottom; ++i) matrix[i][right] = val++; // top to bottom.
if (left > --right) break; // right 内陷
for (int i = right; i >= left; --i) matrix[bottom][i] = val++; // right to left.
if (top > --bottom) break; // bottom 内陷
for (int i = bottom; i >= top; --i) matrix[i][left] = val++; // bottom to top.
if (++left > right) break; // left内陷
}
return matrix;
}
};
这个方法非方阵也能填充。内陷这个思路特别好！！！
4.总结
- 双指针
- 动态窗口
- 注意时间和空间的取舍
- 想不到好办法的时候暴力法也是不错的选择。
