Day02——数组专题

淡淡的烟草味﹌ 2024-04-03 10:29 87阅读 0赞

#### 文章目录 ####

*   *   *  3.有序数组的平方：
         *   *  双指针法:
         *  4.长度最小的子数组：
         *  5.螺旋矩阵II:

--------------------

#### 3.有序数组的平方： ####

##### 双指针法: #####

数组是有序的， 但是负数平方之后可能成为最大数,那么数组平方的最大值就在数组的两端，不是最左边就是最右边。

此时可以考虑双指针法了，left指向起始位置，right指向终止位置。

定义一个新数组result，和原来A数组一样的大小，让index指向result数组终止位置。

如果`A[left] * A[left] < A[right] * A[right]` 那么`result[index--] = A[right] * A[right]; right--;`

如果`A[left] * A[left] >= A[right] * A[right]` 那么`result[k--] = A[left] * A[left]; left++;`

public int[] sortedSquares(int[] nums) {
        
            int right = nums.length - 1;
            int left = 0;
            int[] result = new int[nums.length];
            int index = nums.length - 1;
            while (right <= left){
        
                if(nums[right] * nums[right] > nums[left] * nums[left]){
        
                    result[index--] = nums[right] * nums[right];
                    right--;
                }
                else {
        
                    result[index--] = nums[left] * nums[left];
                    left++;
                }
            }
            return result;
        }

#### 4.长度最小的子数组： ####

**滑动窗口：双指针法**

(1)在本题中实现滑动窗口，主要确定如下三点：

*  窗口内是什么？**就是满足其和 ≥ target 的长度最小的连续子数组。**
 *  如何移动窗口的起始位置？**如果当前窗口的值大于target了，窗口就要向前移动了**
 *  如何移动窗口的结束位置？**窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。**

(2) 补充的知识点：

**`Integer.MAX_VALUE`表示int数据类型的最大取值数：2 147 483 647  
`Integer.MIN_VALUE`表示int数据类型的最小取值数：-2 147 483 648**

(3)代码实现：

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++];
                }
            }
            return result == Integer.MAX_VALUE ? 0 : result;
        }

#### 5.螺旋矩阵II: ####

模拟顺时针画矩阵的过程:坚持**循环不变量原则**。

*  填充上行从左到右
 *  填充右列从上到下
 *  填充下行从右到左
 *  填充左列从下到上

**每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来。**

实现代码：

class Solution {
        
        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) {
         // 判断边界后，loop从1开始
                // 模拟上侧从左到右
                for (j = start; j < n - loop; j++) {
        
                    res[start][j] = count++;
                }
    
                // 模拟右侧从上到下
                for (i = start; i < n - loop; i++) {
        
                    res[i][j] = count++;
                }
    
                // 模拟下侧从右到左
                for (; j >= loop; j--) {
        
                    res[i][j] = count++;
                }
    
                // 模拟左侧从下到上
                for (; i >= loop; i--) {
        //在一轮循环中，loop为1
                    res[i][j] = count++;
                }
                start++;
            }
    
            if (n % 2 == 1) {
        //当为奇数时候，将最后一个数填充进去。
                res[start][start] = count;
            }
    
            return res;
        }
    }

**补充的知识点：**

**1. i，j常识**

int x[i][j] i表示行  j表示列

![be64f592f60e5b13b54f7815d68d2170.png][]

**2. for循环的执行顺序**

for(int i =0; i<5;i++)\{  
// 循环体  
\}  
执行顺序解抛  
执行的顺序如下：  
第一步 ： i=0 初始化值  
第二步 ： i<5 进行条件判断，如果为真，则继续执行  
第三步 ： 执行循环体的内容  
第四步 ： i++ 变量i自增  
第五步 ： 回到第二步，条件判断为真，则执行循环体内容，再到i++一直循环，  
直到第二步的判断条件为假，则退出该循环

[be64f592f60e5b13b54f7815d68d2170.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/1ee3f440f95b40a189aed43af1bb7606.png