LeetCode_数组
- 977.有序数组的平方
- 1.题目描述
- 2.暴力法
- 3. 双指针法
- 209.长度最小的子数组
- 1.题目描述
- 2.暴力法
- 3.滑动窗口(双指针法)
- 59.螺旋矩阵
- 1.题目描述
- 2. 螺旋矩阵解法
977.有序数组的平方
1.题目描述
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
详情LeetCode题链接： https://leetcode.cn/problems/squares-of-a-sorted-array/
2.暴力法
暴力法：最直观的想法，莫过于：每个数平方之后，排个序。
代码逻辑：
/**
*思路：暴力法
* 依次遍历数组，分别获取每个下标的值进行平方后，将平方后的值赋值到新数组内，并比较大小进行排序
*时间复杂度：O(nlog n)，其中n是数组nums 的长度。
*空间复杂度：O(log n)。除了存储答案的数组以外，我们需要O(logn)的栈空间进行排序。
*/
public int[] sortedSquares(int[] nums) {
int[] newArray = new int[nums.length];
for (int i = 0; i < nums.length; i++){
newArray[i] = nums[i] * nums[i];
}
Arrays.sort(newArray);
return newArray;
}
3. 双指针法
思路： 还是利用day1的双指针思想。
对于此题来说，数组其实是有序的， 只不过负数平方之后可能成为最大数了。
那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。
此时可以考虑双指针法了，i指向起始位置，j指向终止位置。
定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。
如果A[i] * A[i] < A[j] * A[j] 那么result[k–] = A[j] * A[j]; 。
如果A[i] * A[i] >= A[j] * A[j] 那么result[k–] = A[i] * A[i]。
代码实现逻辑：
/**
*思路：双指针法
* 因为数组是有序的，由于负数的平方也是很大的数，所以此数组平方后数的大小是从两边向中间越来越小的。
* 因此采用双指针法，i指向起始位置，j指向终止位置。
* 定义一个新数组newArray，和nums数组一样的大小，让k指向newArray数组终止位置。
* 如果nums[left] * nums[left] < nums[right] * nums[right] 那么newArray[newArrayIndex--] = nums[right] * nums[right]。
* 如果nums[left] * nums[left] >= nums[right] * nums[right] 那么newArray[newArrayIndex--] = nums[left] * nums[left]。
*时间复杂度：O(n)，其中n是数组nums 的长度。
*空间复杂度：O(1),除了存储答案的数组以外，我们只需要维护常量空间.
*/
public int[] sortedSquares(int[] nums) {
int right = nums.length - 1;
int left = 0;
int[] newArray = new int[nums.length];
int newArrayIndex = nums.length - 1;
while (left <= right) {
if (nums[left] * nums[left] < nums[right] * nums[right]){
newArray[newArrayIndex--] = nums[right] * nums[right--];
}else {
newArray[newArrayIndex--] = nums[left] * nums[left++];
}
}
return newArray;
}
209.长度最小的子数组
1.题目描述
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
输入：target = 4, nums = [1,4,4]
输出：1
2.暴力法
不推荐此写法，超出LeetCode运行限制
思路：
暴力解法中，是一个for循环滑动窗口的起始位置，一个for循环为滑动窗口的终止位置，用两个for循环 完成了一个不断搜索区间的过程。
代码实现逻辑：
/**
*思路：暴力法
* 利用双指针思想，暴力法遍历数组；初始化子数组的长度为无穷大。
* 第一个for循环是子数组开始的位置，第二个for循环子数组结束的位置，当子数组内数值的和大于等于target时，将此时子数组的长度更新到初始的子数组长度。
* 直至第一个for循环遍历结束为止。
* 时间复杂度O(n^2)
* 空间复杂度O(1)
*/
public int minSubArrayLen(int target, int[] nums) {
int n = nums.length;
if (n == 0){
return 0;
}
int ans = Integer.MAX_VALUE;
for (int i = 0; i < n; i++){
int sum = 0;
for (int j = i; j < n; j++){
sum += nums[j];
if (sum >= target){
ans = Math.min(ans,j-i+1);
break;
}
}
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
3.滑动窗口(双指针法)
思路：
所谓滑动窗口，就是用一个for循环来不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
-
思考问题1： 如果用一个for循环，那么应该表示 滑动窗口的起始位置，还是终止位置？
假设用一个for循环来表示滑动窗口起始位置的话，剩余遍历的终止位置难免再陷入暴力法中了。
所以只用一个for循环，那么循环的索引一定表示 滑动窗口的终止位置。
-
思考问题2： 滑动窗口的起始位置如何移动？
如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。
-
思考问题3： 窗口内是什么？
窗口内是 满足其和 ≥ s 的长度最小的 连续 子数组。
代码实现：
/**
*思路：滑动窗口(双指针法)
* 所谓滑动窗口即不断的调节子序列的起始和终止位置，从而得出我们要想的结果。
* 窗口内是 满足其和 ≥ s 的长度最小的 连续 子数组。
* 只用一个for循环，循环的索引用来表示滑块的终止位置。
* 滑动窗口的起始位置如何移动则是重点：
* 窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了（也就是
* 该缩小了）。
* 窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的
* 索引。
* 相比暴力法：滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列
* 的起始位置。从而将O(n^2)暴力解法降为O(n)。
* 时间复杂度O(n)
* 空间复杂度O(1)
*/
public int minSubArrayLen(int target, int[] nums) {
int sum = 0; //滑动窗口的数值之和
int left = 0; //滑动窗口的起始位置
int result = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++){
sum += nums[right];
//动态的调节窗口的起始位置
// 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
while (sum >= target){
result = Math.min(result,right-left+1);//right-left+1为子序列的长度
sum -= nums[left++];// 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
}
}
// 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
return result == Integer.MAX_VALUE ? 0 : result;
}
时间复杂度O(n)的理解：
不要以为for里放一个while就以为是O(n^2)，主要是看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度是 2 × n 也就是O(n)
59.螺旋矩阵
1.题目描述
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix
示例：
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]
输入：n = 1
输出：[[1]]
LeetCode题目详情链接：https://leetcode.cn/problems/spiral-matrix-ii/
2. 螺旋矩阵解法
1. 思路
根据螺旋矩阵特点，模拟画螺旋矩阵的过程：
- 填充上行从左到右
- 填充右列从上到下
- 填充下行从右到左
- 填充左列从下到上
由外向内一圈一圈这么画下去。
例举当n=3，n=4,n=5…时的螺旋矩阵，如下图：
填充螺旋矩阵需要确定的边界：
- 根据模拟螺旋矩阵的画法，需要确定随n的增大需循环几圈(即确定while的边界条件，转n/2圈，奇数时需要处理最后一个数字)
- 遍历边填充元素时，需要遵循循环不变量原则(LeetCode_Day1中有示例题目)，要么都是左闭右闭，要么都是左闭右开。
2. 代码实现：
/**
* 思路：根据螺旋矩阵特点，模拟画螺旋矩阵的过程：
* 填充上行从左到右，填充右列从上到下，填充下行从右到左，填充左列从下到上,即遍历了一圈。
* 当n = 2时，需要按照上边遍历1圈；n=3时遍历1圈，n=4遍历...n=5....
* 所以填充二维矩阵时，首先确定边界：即转几圈(转n/2圈，奇数时需要处理最后一个数字)，和遍历时坚持循环不变量原则(即开闭区间需一致)。
* 时间复杂度：O(n^2)
* 空间复杂度：
*/
public int[][] generateMatrix(int n) {
int loop = 0;//控制循环次数
int[][] res = new int[n][n];//初始化需要输出的结果数组
int start = 0; //每次循环的开始位置下标 [start][start]
int count = 1; //用于填充数字
int i,j;
while (loop++ < n/2){
// 模拟上侧从左到右,左闭右开
for (j = start; j < n - loop; j++){
res[start][j] = count++;
}
//模拟右侧从上到下，左闭右开
for (i = start; i < n - loop; i++){
res[i][j] = count++;
}
//模拟下侧从右到左，左闭右开
for (;j > start; j--){
res[i][j] = count++;
}
//模拟左侧从下到上，左闭右开
for (;i > start; i--){
res[i][j] = count++;
}
start ++;
}
if (n % 2 == 1){//如果n为基数，需要处理最后一个数字
res[start][start] = count++;
}
return res;
}
