这977个有序数组的平方，209个长度最小的子数组，59个螺旋矩阵II，哪个最长尾？
- 内容介绍
- 文章标签
- 相关推荐
本文共计1749个文字，预计阅读时间需要7分钟。
977. 给定一个按非递减顺序排序的整数数组 `nums`，返回每个数字的平方组成的数组，也要求按非递减顺序排序。示例：输入 `nums=[1, 2, 3]`，输出 `[1, 4, 9]`。
977.有序数组的平方
力扣题目链接(opens new window)
给你一个按 非递减顺序 排序的整数数组 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]
思路：
数组元素有正有负但有序，平方后,大的数据都在数组两端，小的数据在数组中间.
用双指针方法在数组首尾定义指针，指针的数据平方后相互比较，将大的数据存放在事先定义好的数组中。大的数据所在指针可能在数组左右两端，左边的话，指针应该++，右边的话指针应该--.直至左指针比右指针大
代码如下
// 时间复杂度为O(n)
public class squareOrderedArray {
public static void main(String args[]) {
int[] nums = new int[]{-3,-2,-1,0,1,4,5};
int[] result = squareOrderedArray(nums);
System.out.println(result);
}
public static int[] squareOrderedArray(int[] nums){
int[] result = new int[nums.length];
int left = 0;
int right = nums.length-1;
int index = nums.length-1;
while(left <= right){
if(nums[left] * nums[left] < nums[right]*nums[right]){
result[index] = nums[right]*nums[right];
right--;
index--;
}else{
result[index] = nums[left] * nums[left];
left++;
index--;
}
}
return result;
}
}
问题
需要注意边界条件.如果边界条件是left < right,那么left = right的元素就不会在while循环中存放到新数组中.
让left <= right.
因为当left = right时.数组此时只剩下一个元素,肯定是最小的或者等于最小的.
如果此时去走while循环,执行else里的代码,此时index = 0,那么会将该元素放到新数组最开始的位置,也就满足了题目的要求.
209.长度最小的子数组
力扣题目链接(opens new window)
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：
- 输入：s = 7, nums = [2,3,1,2,4,3]
- 输出：2
- 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
提示：
- 1 <= target <= 10^9
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^5
思路：
双指针法。 暴力算法是通过双重for循环遍历数组所有元素，找出所有区间比对。先找到区间左侧，然后For循环遍历找区间右侧，也就是先找左区间，然后找右区间。 那么双指针算法如果也像暴力算法一样，先找区间左侧然后，再找区间右侧，跟暴力算法区别不大。所以需要先找区间右侧. 用right指针表示区间右侧，left指针表示区间左侧，不断累加区间之间的数组元素，直至区间之和大于等于target 此时移动左区间left指针，进一步缩小区间范围。找到数组长度并记录。然后继续移动区间右指针重复操作
代码如下
//时间复杂度：O(n)
//空间复杂度：O(1)
public class longestSubarrayLength {
public static void main(String args[]) {
int[] nums = new int[]{1, 1, 1, 1, 1, 1, 1, 1, 1};
int target = 6;
System.out.println(longestSubarrayLength(nums, target));
}
public static int longestSubarrayLength(int[] nums, int target) {
if (nums.length == 0) {
return 0;
}
int left = 0;
int right = 0;
int sum = 0;
int minLength = Integer.MAX_VALUE;
boolean flag = false;
while (right < nums.length) {
sum = sum + nums[right];
// 和大于target，移动left指针
while (sum >= target) {
sum = sum - nums[left];
left++;
flag = true;
}
if (flag && right - left + 2 < minLength) {
minLength = right - left + 2;
flag = false;
}
right++;
}
return minLength == Integer.MAX_VALUE ? 0 : minLength;
}
}
59.螺旋矩阵II
力扣题目链接(opens new window)
给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
思路
循环处理二维数组，循环处理次数等于n/2.
比如：边长为3，循环一圈即可，剩下最中间的元素单独处理，边长为4，循环两圈即可，没有最中间的元素需要处理 需要注意:对每一条边遍历时，要坚持循环不变量原则。即遍历二维数组使用同一个规则，不能这一条边左闭右开，下一条边左开右闭。这里使用左闭右开
比如一个长度为3的二维数组。遍历流程如下 1.处理上行 从左至右 1 2 0 0 0 0 0 0 0 2.处理右列 从上至下 1 2 3 0 0 4 0 0 0 3.处理下行 从右至左 1 2 3 0 0 4 0 6 5 4.处理左列 从下至上 1 2 3 8 0 4 7 6 5
5.边长为奇数，单独处理最中间的元素
代码如下
public class spiralMatrixII {
public static void main(String args[]) {
int n = 2;
System.out.println(spiralMatrixII(n));
}
// 时间复杂度 O(n^2): 模拟遍历二维矩阵的时间
// 空间复杂度 O(1)
public static int[][] spiralMatrixII(int n) {
int nums[][] = new int[n][n];
int loop = n / 2; // 边长为n的二维数组，循环几圈。比如：边长为3，循环一圈
int startx = 0;
int starty = 0;// 当前数组元素位置
int count = 1;// 数组元素赋值
int curNum = 1; // 当前处于第几次循环
while (loop > 0) {
// 处理上行 从左至右
while (starty < n - curNum) {
nums[startx][starty++] = count;
count++;
}
// 处理右列 从上至下
while (startx < n - curNum) {
nums[startx++][starty] = count;
count++;
}
// 处理下行 从右至左
while (starty >= curNum) {
nums[startx][starty--] = count;
count++;
}
// 处理左列 从下至上
while (startx >= curNum) {
nums[startx--][starty] = count;
count++;
}
loop--;
curNum++;
startx++;
starty++;
}
if (n % 2 != 0) {
nums[n / 2][n / 2] = count;
}
return nums;
}
}
本文共计1749个文字，预计阅读时间需要7分钟。
977. 给定一个按非递减顺序排序的整数数组 `nums`，返回每个数字的平方组成的数组，也要求按非递减顺序排序。示例：输入 `nums=[1, 2, 3]`，输出 `[1, 4, 9]`。
977.有序数组的平方
力扣题目链接(opens new window)
给你一个按 非递减顺序 排序的整数数组 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]
思路：
数组元素有正有负但有序，平方后,大的数据都在数组两端，小的数据在数组中间.
用双指针方法在数组首尾定义指针，指针的数据平方后相互比较，将大的数据存放在事先定义好的数组中。大的数据所在指针可能在数组左右两端，左边的话，指针应该++，右边的话指针应该--.直至左指针比右指针大
代码如下
// 时间复杂度为O(n)
public class squareOrderedArray {
public static void main(String args[]) {
int[] nums = new int[]{-3,-2,-1,0,1,4,5};
int[] result = squareOrderedArray(nums);
System.out.println(result);
}
public static int[] squareOrderedArray(int[] nums){
int[] result = new int[nums.length];
int left = 0;
int right = nums.length-1;
int index = nums.length-1;
while(left <= right){
if(nums[left] * nums[left] < nums[right]*nums[right]){
result[index] = nums[right]*nums[right];
right--;
index--;
}else{
result[index] = nums[left] * nums[left];
left++;
index--;
}
}
return result;
}
}
问题
需要注意边界条件.如果边界条件是left < right,那么left = right的元素就不会在while循环中存放到新数组中.
让left <= right.
因为当left = right时.数组此时只剩下一个元素,肯定是最小的或者等于最小的.
如果此时去走while循环,执行else里的代码,此时index = 0,那么会将该元素放到新数组最开始的位置,也就满足了题目的要求.
209.长度最小的子数组
力扣题目链接(opens new window)
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：
- 输入：s = 7, nums = [2,3,1,2,4,3]
- 输出：2
- 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
提示：
- 1 <= target <= 10^9
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^5
思路：
双指针法。 暴力算法是通过双重for循环遍历数组所有元素，找出所有区间比对。先找到区间左侧，然后For循环遍历找区间右侧，也就是先找左区间，然后找右区间。 那么双指针算法如果也像暴力算法一样，先找区间左侧然后，再找区间右侧，跟暴力算法区别不大。所以需要先找区间右侧. 用right指针表示区间右侧，left指针表示区间左侧，不断累加区间之间的数组元素，直至区间之和大于等于target 此时移动左区间left指针，进一步缩小区间范围。找到数组长度并记录。然后继续移动区间右指针重复操作
代码如下
//时间复杂度：O(n)
//空间复杂度：O(1)
public class longestSubarrayLength {
public static void main(String args[]) {
int[] nums = new int[]{1, 1, 1, 1, 1, 1, 1, 1, 1};
int target = 6;
System.out.println(longestSubarrayLength(nums, target));
}
public static int longestSubarrayLength(int[] nums, int target) {
if (nums.length == 0) {
return 0;
}
int left = 0;
int right = 0;
int sum = 0;
int minLength = Integer.MAX_VALUE;
boolean flag = false;
while (right < nums.length) {
sum = sum + nums[right];
// 和大于target，移动left指针
while (sum >= target) {
sum = sum - nums[left];
left++;
flag = true;
}
if (flag && right - left + 2 < minLength) {
minLength = right - left + 2;
flag = false;
}
right++;
}
return minLength == Integer.MAX_VALUE ? 0 : minLength;
}
}
59.螺旋矩阵II
力扣题目链接(opens new window)
给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
思路
循环处理二维数组，循环处理次数等于n/2.
比如：边长为3，循环一圈即可，剩下最中间的元素单独处理，边长为4，循环两圈即可，没有最中间的元素需要处理 需要注意:对每一条边遍历时，要坚持循环不变量原则。即遍历二维数组使用同一个规则，不能这一条边左闭右开，下一条边左开右闭。这里使用左闭右开
比如一个长度为3的二维数组。遍历流程如下 1.处理上行 从左至右 1 2 0 0 0 0 0 0 0 2.处理右列 从上至下 1 2 3 0 0 4 0 0 0 3.处理下行 从右至左 1 2 3 0 0 4 0 6 5 4.处理左列 从下至上 1 2 3 8 0 4 7 6 5
5.边长为奇数，单独处理最中间的元素
代码如下
public class spiralMatrixII {
public static void main(String args[]) {
int n = 2;
System.out.println(spiralMatrixII(n));
}
// 时间复杂度 O(n^2): 模拟遍历二维矩阵的时间
// 空间复杂度 O(1)
public static int[][] spiralMatrixII(int n) {
int nums[][] = new int[n][n];
int loop = n / 2; // 边长为n的二维数组，循环几圈。比如：边长为3，循环一圈
int startx = 0;
int starty = 0;// 当前数组元素位置
int count = 1;// 数组元素赋值
int curNum = 1; // 当前处于第几次循环
while (loop > 0) {
// 处理上行 从左至右
while (starty < n - curNum) {
nums[startx][starty++] = count;
count++;
}
// 处理右列 从上至下
while (startx < n - curNum) {
nums[startx++][starty] = count;
count++;
}
// 处理下行 从右至左
while (starty >= curNum) {
nums[startx][starty--] = count;
count++;
}
// 处理左列 从下至上
while (startx >= curNum) {
nums[startx--][starty] = count;
count++;
}
loop--;
curNum++;
startx++;
starty++;
}
if (n % 2 != 0) {
nums[n / 2][n / 2] = count;
}
return nums;
}
}