977. 有序数组的平方
- 简单的方法是平方后使用排序方法
- 第2种方法是双指针方法,从两边进行判断,将最大的从后往前放
public static int[] sortedSquares(int[] nums) {
// 输入:nums = [-4,-1,0,3,10]
// 输出:[0,1,9,16,100]
// 解释:平方后,数组变为 [16,1,0,9,100]
// 排序后,数组变为 [0,1,9,16,100]
// 从前往后来决定元素在哪个位置是不现实的
// 因此从后往前判断,比较right 和 left的平方
// 谁大就放在最后一个位置,然后移动那个比较大的元素的指针
int left = 0;
int right = nums.length - 1;
// 存储结果数组,i为下标
int i = nums.length-1;
int[] sortNum = new int[nums.length];
// 边界判断 可举例:一个元素的情况
while (left <= right) {
int leftValue = nums[left]*nums[left];
int rightValue = nums[right]*nums[right];
// 若右边元素大,则放置右边元素值,right指针左移
if (leftValue < rightValue) {
sortNum[i--] = rightValue;
right--;
}
else {
sortNum[i--] = leftValue;
left++;
}
}
return sortNum;
}
209.长度最小的子数组
- 滑动窗口方法:当大于等于给定值时,便收缩窗口,不断更新最小长度
public int minSubArrayLen(int target, int[] nums) {
int left = 0;
int right = 0;
int sum = 0;
int minLen = nums.length + 1;
while (right < nums.length) {
sum += nums[right];
// 当一旦大于给定值,便缩小窗口,看左边界收缩后是否最小长度会发生变化
while (sum >= target) {
minLen = Math.min(minLen, right - left+1);
sum -= nums[left++];
}
right++;
}
// 若不存在最小窗口(数组和 < target)或数组长度为0,则minLen应该赋为0
return minLen == nums.length + 1 ? 0 : minLen;
}
59. 螺旋矩阵 II
- 按照顺时针走路,注意边界的选取
- 一开始的起点和终点需要选取好,在这,我选择前闭后闭方法
public int[][] generateMatrix(int n) {
int[][] res = new int[n][n];
int num = 1;
int matrixNum = n * n;
int left = 0;
int right = n-1;
int top = 0;
int bottom = n-1;
while (num <= matrixNum) {
for (int i = left; i <= right; i++) {
res[top][i] = num++;
}
top++;
for (int i = top; i <= bottom; i++) {
res[i][right] = num++;
}
right--;
for (int i = right; i >= left; i--) {
res[bottom][i] = num++;
}
bottom--;
for (int i = bottom; i >= top; i--) {
res[i][left] = num++;
}
left++;
}
return res;
}
文章来源地址https://www.toymoban.com/news/detail-653459.html
文章来源:https://www.toymoban.com/news/detail-653459.html
到了这里,关于【leetcode】第一章数组-2的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!