当前位置：首页 > article >正文

代码随想录打卡Day 长度最小的子数组209 螺旋矩阵2 59

article 2024/10/24 9:26:15

day02 数组

1 长度最小的子数组

介绍数组操作中另一个重要的方法：滑动窗口。

所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。

在暴力解法中，是一个for循环滑动窗口的起始位置，一个for循环为滑动窗口的终止位置，用两个for循环完成了一个不断搜索区间的过程。

那么滑动窗口如何用一个for循环来完成这个操作呢。

首先要思考如果用一个for循环，那么应该表示滑动窗口的起始位置，还是终止位置。

如果只用一个for循环来表示滑动窗口的起始位置，那么如何遍历剩下的终止位置？

此时难免再次陷入暴力解法的怪圈。

所以只用一个for循环，那么这个循环的索引，一定是表示滑动窗口的终止位置。

那么问题来了，滑动窗口的起始位置如何移动呢？

这里还是以题目中的示例来举例，s=7，数组是 2，3，1，2，4，3，来看一下查找的过程：

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0, right = 0, sum = 0, minLen = Integer.MAX_VALUE;

        while (right < nums.length) {
            sum += nums[right];
            while (sum >= target) {
                minLen = Math.min(minLen, right - left + 1);
                sum -= nums[left];
                left++;
            }
            right++;
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;

    }
}
//leetcode submit region end(Prohibit modification and deletion)

2 螺旋数组59

package com.jiangxun.leetcode.editor.cn;//<p>给你一个正整数&nbsp;<code>n</code> ，生成一个包含 <code>1</code> 到&nbsp;<code>n<sup>2</sup></code>&nbsp;所有元素，且元素按顺时针顺序螺旋排列的&nbsp;<code>n x n</code> 正方形矩阵 <code>matrix</code> 。</p>
//
//<p>&nbsp;</p>
//
//<p><strong>示例 1：</strong></p> 
//<img alt="" src="https://assets.leetcode.com/uploads/2020/11/13/spiraln.jpg" style="width: 242px; height: 242px;" /> 
//<pre>
//<strong>输入：</strong>n = 3
//<strong>输出：</strong>[[1,2,3],[8,9,4],[7,6,5]]
//</pre>
//
//<p><strong>示例 2：</strong></p>
//
//<pre>
//<strong>输入：</strong>n = 1
//<strong>输出：</strong>[[1]]
//</pre>
//
//<p>&nbsp;</p>
//
//<p><strong>提示：</strong></p>
//
//<ul> 
// <li><code>1 &lt;= n &lt;= 20</code></li> 
//</ul>
//
//<div><div>Related Topics</div><div><li>数组</li><li>矩阵</li><li>模拟</li></div></div><br><div><li>👍 1340</li><li>👎 0</li></div>

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[][] generateMatrix(int n) {
        int[][] nums = new int[n][n];
        //从1开始放数字
        int number = 1;
        //循环次数count
        int count = 1;
        //起点（x，y）,i是行，j是列
        int startX = 0;
        int startY = 0;
        int i=1;
        int j=1;
        //初始化偏移值设为 1，固定某一循环，每一次填充数量
        int offset = 1;

        /**
         * 3*3的矩阵
         * 第一次填充上部 1 2，第二次填充右侧 3 4 左闭右开
         * 第三次填充下部 5 6，第四次填充左部 7 8
         * （以此循环）填充 9
         */
        while (count <= n / 2) {
            //上
            for (j = startY; j < n - offset; j++) {
                nums[i][j] = number++;
            }
            //右
            for (i = startX; i < n - offset; i++) {
                nums[i][j] = number++;
            }
            //下
            for(; j > startY; j--){
                nums[i][j] = number++;
            }
            //左
            for(; i > startX; i--){
                nums[i][j] = number++;
            }
            //更新起点
            startX++;
            startY++;
            //更新偏移值
            offset++;
            //更新循环次数
            count++;

        }
        //如果n是奇数，单独处理中间数字
        if(n % 2 == 1){
            nums[startX][startY] = number;
        }
        return nums;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

package com.jiangxun.leetcode.editor.cn;//<p>给你一个正整数&nbsp;<code>n</code> ，生成一个包含 <code>1</code> 到&nbsp;<code>n<sup>2</sup></code>&nbsp;所有元素，且元素按顺时针顺序螺旋排列的&nbsp;<code>n x n</code> 正方形矩阵 <code>matrix</code> 。</p>
//
//<p>&nbsp;</p>
//
//<p><strong>示例 1：</strong></p> 
//<img alt="" src="https://assets.leetcode.com/uploads/2020/11/13/spiraln.jpg" style="width: 242px; height: 242px;" /> 
//<pre>
//<strong>输入：</strong>n = 3
//<strong>输出：</strong>[[1,2,3],[8,9,4],[7,6,5]]
//</pre>
//
//<p><strong>示例 2：</strong></p>
//
//<pre>
//<strong>输入：</strong>n = 1
//<strong>输出：</strong>[[1]]
//</pre>
//
//<p>&nbsp;</p>
//
//<p><strong>提示：</strong></p>
//
//<ul> 
// <li><code>1 &lt;= n &lt;= 20</code></li> 
//</ul>
//
//<div><div>Related Topics</div><div><li>数组</li><li>矩阵</li><li>模拟</li></div></div><br><div><li>👍 1340</li><li>👎 0</li></div>

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[][] generateMatrix(int n) {
        int[][] nums = new int[n][n];
        //从1开始放数字
        int number = 1;
        //循环次数count
        int count = 1;
        //起点（x，y）,i是行，j是列
        int startX = 0;
        int startY = 0;
        int i=1;
        int j=1;
        //初始化偏移值设为 1，固定某一循环，每一次填充数量
        int offset = 1;

        /**
         * 3*3的矩阵
         * 第一次填充上部 1 2，第二次填充右侧 3 4 左闭右开
         * 第三次填充下部 5 6，第四次填充左部 7 8
         * （以此循环）填充 9
         */
        while (count <= n / 2) {
            //上
            for (j = startY; j < n - offset; j++) {
                i=startX;
                nums[i][j] = number++;
            }
            //右
            for (i = startX; i < n - offset; i++) {
                nums[i][j] = number++;
            }
            //下
            for(; j > startY; j--){
                nums[i][j] = number++;
            }
            //左
            for(; i > startX; i--){
                nums[i][j] = number++;
            }
            //更新起点
            startX++;
            startY++;
            //更新偏移值
            offset++;
            //更新循环次数
            count++;

        }
        //如果n是奇数，单独处理中间数字
        if(n % 2 == 1){
            nums[startX][startY] = number;
        }
        return nums;
    }
}
//leetcode submit region end(Prohibit modification and deletion)