977 有序数组的平方
https://leetcode.com/problems/squares-of-a-sorted-array/description/
暴力解法： 先平方得到平方后的array，后排序 O(N+NlogN)
这里不写解法，需要自己写sort algo或者直接用语言自带的sort function
双指针解法更快：
因为数组两端肯定出一个最大值，向中间得到越来越小的平方数，则我们可以使用左右双指针。
左指针和右指针的平方做对比，打的写在输出数组的最后的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution{
public int[] sortedSquares(int[] nums){
int left = 0, right = nums.length - 1;
int[] result = new int[nums.length];
int index = nums.length - 1;
while(left <= right){
int leftS = nums[left] * nums[left];
int rightS = nums[right] * nums[right];
if(leftS < rightS){
result[index--] = rightS;
right--;
} else {
result[index--] = leftS;
left++;
}
}
return result;
}
}
|
注意两者在更新右区间的区别，设置右起始值，和更新右值有区别。
209 长度最小的子数组
https://leetcode.com/problems/minimum-size-subarray-sum/description/
给定一个都是正数的数组，找出最小连续子数组之和大于或等于target。
暴力解法：
两个for循环找出所有可能性， 超时不具体实现
滑动窗口：
不断调节子序列的起始位置和终止位置，从而得到结果
因为所需时间复杂度为O（N）所以循环索引必定为滑动窗口的终止位置；
即滑动窗口的起始位置需要在用一个for loop里实现动态调节。
滑动窗口的精髓就在于：设置滑动窗口的终点位置为索引，动态调节滑动窗口的起始位置
具体实现：
sum += 终止位置的值；
如果（这一步的判断是while,不是if, 如果sum超过target，就把起始位置一直移到不超过为止，记录result）sum超过了target，记录result 后 sum减掉起始位置的值后起始位置前移一格。
最后比较result和Integer max
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution{
public int minSubArrayLen(int target, int[] nums){
int left = 0;
int sum = 0;
int result = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++){
sum+=nums[right];
while(sum >= target){
result = Math.min(result, right-left + 1);
sum -= nums[left];
left++;
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
}
|
59 螺旋矩阵II
https://leetcode.com/problems/spiral-matrix-ii/description/
给定一个整数n，画出从1到n^2的螺旋数组。
此题为模拟题型，模拟顺时针画法
循环不变量原则 （二分法也遵循了这一原则）
模拟顺时针画矩阵的过程:
填充上行从左到右
填充右列从上到下
填充下行从右到左
填充左列从下到上
遵循左闭右开原则一直顺时针画边。
以4为例 模拟总过程
二维数组new int [4][4]
first loop
[0,0][0,1][0,2]
[0,3][1,3][2,3]
[3,3][3,2][3,1]
[3,0][2,0][1,0]
起始位置+1 +1
second loop
[1,1]
[1,2]
[2,2]
[2,1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Solution {
public int[][] generateMatrix(int n) {
int[][] result = new int[n][n];
int count = 1;
int offset = 1;
int start = 0;
int loop = n/2;
int i = 0, j = 0;
while(loop-- > 0){
for(j = start; j < n - offset; j++){
result[start][j] = count++;
}
for(i = start; i < n - offset; i++){
result[i][j] = count++;
}
for(;j > start; j--){
result[i][j] = count++;
}
for(;i > start; i--){
result[i][j] = count++;
}
offset++;
start++;
}
if(n%2 == 1){
result[start][start] = count;
}
return result;
}
}
|