写点什么

精选算法面试 - 数组 III

用户头像
李孟
关注
发布于: 2021 年 01 月 15 日
精选算法面试-数组III

一.示例

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

整体采用构建矩阵,填充矩阵的思路,填充过程分为四种情况:

  1. 从左到右填充一行

  2. 从上到下填充一列

  3. 从右到左填充一行,注意只有一行的情况

  4. 从下到上填充一列,注意只有一列的情况

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/


发布于: 2021 年 01 月 15 日阅读数: 17
用户头像

李孟

关注

还未添加个人签名 2017.10.18 加入

数据工程师 https://limeng.blog.csdn.net/

评论

发布
暂无评论
精选算法面试-数组III