常见算法题_ 209.长度最小的子数组、59.螺旋矩阵 II

简介: 【2月更文挑战第7天】

209.长度最小的子数组

题目

给定一个含有 n 个正整数的数组和一个正整数 target

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度如果不存在符合条件的子数组,返回 0

思路

暴力解法主要就是两个for循环,一个for循环固定一个数组元素,例如n,另一个for循环从n的下一个元素开始累加,当和大于等于target时终止内层循环,并记录该最小长度。

滑动窗口(其实可以看成队列)主要就是通过不断地调节子序列的起始位置和终止位置来得到相应的结果。

我们把数组中的元素不停的入队,直到总和大于等于 s 为止,接着记录下队列中元素的个数,然后再不停的出队,直到队列中元素的和小于 s 为止(如果不小于 s,也要记录下队列中元素的个数,这个个数其实就是不小于 s 的连续子数组长度,我们要记录最小的即可)。接着再把数组中的元素添加到队列中……重复上面的操作,直到数组中的元素全部使用完为止。

解法

暴力解法

代码示例:

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int result = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                if (sum >= target) {
                    result = Math.min(result, j - i + 1);
                    break; 
                }
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}
  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)

队列相加法(滑动窗口)

代码示例

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int result = Integer.MAX_VALUE;
        int startIndex=0;
        int endIndex=0;
        int sum = 0;
        for (endIndex=0; endIndex < nums.length; endIndex++) {
            sum+=nums[endIndex];
            while (sum>=target) {
                result=Math.min(result,endIndex-startIndex+1);
                sum-=nums[startIndex];
                startIndex++;
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

对列相减法(滑动窗口)

代码示例

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int result = Integer.MAX_VALUE;
        int startIndex=0;
        int endIndex=0;
        int sum = 0;
        for (endIndex=0; endIndex < nums.length; endIndex++) {
            target-=nums[endIndex];
            while (target<=0) {
                result=Math.min(result,endIndex-startIndex+1);
                target+=nums[startIndex];
                startIndex++;
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)



59.螺旋矩阵 II

题目

给你一个正整数 n ,生成一个包含 1n2 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix

思路

顺时针螺旋排列的正方形矩阵的分析过程:

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

由外向内一圈一圈这么画下去。

按照左闭右开的原则,画出相应的图。

解法

代码示例

class Solution {
    public int[][] generateMatrix(int n) {
        int startX = 0;
        int startY = 0;
        int[][] nums = new int[n][n];
        int mid = n / 2;// 如果n为奇数,那么最中间的位置为mid,例如 n 为3,中间的位置下标为【1,1】
        int m = 0;// 控制循环次数,每循环一圈加一
        int offset = 1;// 每循环一圈,右边界收缩一位
        int count = 1;
        int i, j;
        while (m++ < mid) {
            for (j = startY; j < n - offset; j++) {
                nums[startX][j] = count++;
            }
            for (i = startX; i < n - offset; i++) {
                nums[i][j] = count++;
            }
            for (; j > startY; j--) {
                nums[i][j] = count++;
            }
            for (; i > startX; i--) {
                nums[i][j] = count++;
            }
            startX++;
            startY++;
            offset++;
        }
        if (n % 2 != 0) {
            nums[mid][mid] = count;
        }
        return nums;
    }
}
  • 时间复杂度 O(n^2): 模拟遍历二维矩阵的时间
  • 空间复杂度 O(1)
目录
相关文章
|
5天前
|
算法
【算法】滑动窗口——长度最小的子数组
【算法】滑动窗口——长度最小的子数组
|
5天前
|
算法 C++
【算法】前缀和算法——和可被K整除的子数组
【算法】前缀和算法——和可被K整除的子数组
|
5天前
|
算法
【算法】前缀和算法——和为k的子数组之和
【算法】前缀和算法——和为k的子数组之和
|
10天前
|
算法 Java
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
21 0
|
2月前
|
存储 算法 数据挖掘
python5种算法模拟螺旋、分层填充、递归、迭代、分治实现螺旋矩阵ll【力扣题59】
python5种算法模拟螺旋、分层填充、递归、迭代、分治实现螺旋矩阵ll【力扣题59】
|
2月前
|
存储 算法 数据挖掘
螺旋矩阵 II:从理论到实践的五种算法解析
螺旋矩阵 II:从理论到实践的五种算法解析
|
2月前
|
算法 机器人 数据挖掘
LeetCode题目54:螺旋矩阵【python4种算法实现】
LeetCode题目54:螺旋矩阵【python4种算法实现】
|
2月前
|
人工智能 算法
【算法优选】 动态规划之子数组、子串系列——贰
【算法优选】 动态规划之子数组、子串系列——贰
|
5天前
|
算法
基于模糊控制算法的倒立摆控制系统matlab仿真
本项目构建了一个基于模糊控制算法的倒立摆控制系统,利用MATLAB 2022a实现了从不稳定到稳定状态的转变,并输出了相应的动画和收敛过程。模糊控制器通过对小车位置与摆的角度误差及其变化量进行模糊化处理,依据预设的模糊规则库进行模糊推理并最终去模糊化为精确的控制量,成功地使倒立摆维持在直立位置。该方法无需精确数学模型,适用于处理系统的非线性和不确定性。
基于模糊控制算法的倒立摆控制系统matlab仿真
|
5天前
|
机器学习/深度学习 算法 定位技术
MATLAB - 遗传算法(GA)求解旅行商问题(TSP)
MATLAB - 遗传算法(GA)求解旅行商问题(TSP)
9 3

热门文章

最新文章