一.示例
1.1 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例
输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
实现 1
暴力破解法，效率比较低
public int minSubArrayLen(int s, int[] nums) { int min = Integer.MAX_VALUE; for (int i = 0; i < nums.length; i++) { int sum = nums[i]; if(sum >= s){ return 1; } for (int j = i+1; j < nums.length; j++) { sum += nums[j]; if(sum >= s){ min = Math.min(min,j-i+1); break; } } } return min == Integer.MAX_VALUE ? 0:min; }
复制代码
实现 2
模拟队列方式，lo 为前缀指针，hi 为后缀指针，lo 增加，代表弹出，前一个值。
public int minSubArrayLen(int s, int[] nums) { int lo = 0, hi = 0, sum = 0, min = Integer.MAX_VALUE; while (hi < nums.length) { sum += nums[hi++]; while (sum >= s) { min = Math.min(min, hi - lo); sum -= nums[lo++]; } } return min == Integer.MAX_VALUE ? 0 : min;}
复制代码
1.2 螺旋矩阵
给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
示例
输入: 3
输出:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
实现 1
整体采用构建矩阵，填充矩阵的思路，填充过程分为四种情况：
从左到右填充一行
从上到下填充一列
从右到左填充一行，注意只有一行的情况
从下到上填充一列，注意只有一列的情况
public int[][] generateMatrix(int n) { // 构建矩阵 int[][] resultMatrix = new int[n][n]; // 计算结果值 int resultNum = n * n; // 填充矩阵 int rowBegin = 0; int rowEnd = n - 1; int columnBegin = 0; int columnEnd = n - 1; int insertNum = 1; while (insertNum <= resultNum) { // 填充矩阵的上边，从左到右填充一行 // 每次循环行不变，列加一。并且循环结束后行加一 int columnTemp = columnBegin; while (columnTemp <= columnEnd) { resultMatrix[rowBegin][columnTemp] = insertNum; insertNum += 1; columnTemp += 1; } rowBegin += 1; // 填充矩阵的右边，从上到下填充一列 // 每次循环列不变，行加一。并且循环结束后列减一 int rowTemp = rowBegin; while (rowTemp <= rowEnd) { resultMatrix[rowTemp][columnEnd] = insertNum; insertNum += 1; rowTemp += 1; } columnEnd -= 1; // 填充矩阵下边，从右到左填充一行（注意只有一行的情况） // 每次循环行不变，列减一。并且循环结束后行加一 columnTemp = columnEnd; while (columnTemp >= columnBegin && rowEnd >= rowBegin) { resultMatrix[rowEnd][columnTemp] = insertNum; insertNum += 1; columnTemp -= 1; } rowEnd -= 1; // 填充矩阵左边，从下到上填充一列（注意只有一列的情况） // 每次循环列不变，行加一。并且循环结束后列加一 rowTemp = rowEnd; while (rowTemp >= rowBegin && columnEnd >= columnBegin) { resultMatrix[rowTemp][columnBegin] = insertNum; insertNum += 1; rowTemp -= 1; } columnBegin += 1; } return resultMatrix;}
复制代码
参考
https://leetcode-cn.com/problems/minimum-size-subarray-sum/
https://leetcode-cn.com/problems/spiral-matrix-ii/
评论