977.有序数组的平方
题目建议： 本题关键在于理解双指针思想
题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/
思路：找到第一个非负数，然后双指针往两边从小到大排序查找。
自己的解法虽然用到了双指针，但是太啰嗦，得用Carl的思路再实现一下，从index=0和index=length-1的位置从大往小排序查找。
/**
* 双指针解法
* 3种情况：
* 1. 全是负数，平方后倒序排；例如：[-5,-3,-2,-1], [-1]
* 2. 全是正数，平方后正序排
* 3. 从负数到正数
*
* @param nums
* @return
*/
public int[] sortedSquares(int[] nums) {
final int length = nums.length;
int[] newNums = new int[length];
// 第一个是否正数
boolean firstPositive = nums[0] >= 0;
// 全是负数，倒序即可
if (!firstPositive && nums[length - 1] < 0) {
for (int i = 0, j = length - 1; i < length && j >= 0; ) {
newNums[i] = nums[j] * nums[j];
i++;
j--;
}
return newNums;
}
int right = -1;
for (int i = 0; i < length; i++) {
final int num = nums[i];
if (right < 0 && num >= 0) {
right = i;
}
newNums[i] = nums[i] * nums[i];
}
// 全是正数，正序即可
if (firstPositive) {
return newNums;
}
// 从负数，到正数
int left = right - 1;
int[] newNums2 = new int[length];
int newIndex = 0;
do {
final int leftVal = newNums[left];
final int rightVal = newNums[right];
if (leftVal <= rightVal) {
newNums2[newIndex] = leftVal;
left--;
} else {
newNums2[newIndex] = rightVal;
right++;
}
newIndex++;
} while (left >= 0 && right <= (length - 1));
// 放入剩余的数
while (left >= 0) {
newNums2[newIndex++] = newNums[left--];
}
while (right <= (length - 1)) {
newNums2[newIndex++] = newNums[right++];
}
return newNums2;
}
209.长度最小的子数组
题目建议： 本题关键在于理解滑动窗口，这个滑动窗口看文字讲解 还挺难理解的，建议大家先看视频讲解。 拓展题目可以先不做。
题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/
思路：暴力解法超时了，滑动窗口的思路需要多练习。
/**
* 双指针，滑动窗口
* @param target
* @param nums
* @return
*/
public int minSubArrayLen(int target, int[] nums) {
int begin = 0;
int minLen = Integer.MAX_VALUE;
int sum = 0;
// 全加起来也小于目标值
boolean lessThanTarget = true;
for (int end = 0; end < nums.length; end++) {
sum += nums[end];
// 用while不用if，因为可能出现[1,1,1,1,1,100]
while (sum >= target) {
lessThanTarget = false;
minLen = Integer.min(end - begin + 1, minLen);
sum -= nums[begin];
begin++;
}
}
return lessThanTarget ? 0 : minLen;
}
59.螺旋矩阵II
题目建议： 本题关键还是在转圈的逻辑，在二分搜索中提到的区间定义，在这里又用上了。
题目链接：https://leetcode.cn/problems/spiral-matrix-ii/
思路：这种题第一次见到，以为会有高深的算法，其实主要是考虑清楚逻辑，然后处理边界值的问题，根据Carl的思路写出了解法。
public int[][] generateMatrix(int n) {
int[][] result = new int[n][n];
// 转几圈
int circleCount = n / 2;
int startX = 0;
int startY = 0;
int count = 1;
int offset = 1;
int val = 1;
while (count <= circleCount) {
int x = startX, y = startY;
//第1条边：从左到右
for (; x < n - offset; x++) {
result[y][x] = val++;
// System.out.println("[" + y + "][" + x + "]=" + result[y][x]);
}
//第2条边：从右上到右下
for (; y < n - offset; y++) {
result[y][x] = val++;
// System.out.println("[" + y + "][" + x + "]=" + result[y][x]);
}
//第3条边：从右下到左下
for (; x >= offset; x--) {
result[y][x] = val++;
// System.out.println("[" + y + "][" + x + "]=" + result[y][x]);
}
//第4条边：从左下到左上
for (; y >= offset; y--) {
result[y][x] = val++;
// System.out.println("[" + y + "][" + x + "]=" + result[y][x]);
}
// 圈数增加
count++;
startX++;
startY++;
offset++;
}
// 如果是奇数，填补中间的数
if (n % 2 != 0) {
result[startX][startY] = val;
}
return result;
}
网友评论