目录
1、189. 轮转数组
1.1、题目介绍
1.2、解题思路
2、53. 最大子数组和
2.1、题目介绍
2.2、解题思路
文章来源地址https://www.toymoban.com/news/detail-713715.html
1、189. 轮转数组
1.1、题目介绍
原题链接：189. 轮转数组 - 力扣（LeetCode）
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
提示：
- 1 <= nums.length <= 10^5
- -2^31 <= nums[ i ] <= (2^31)-1
- 0 <= k <= 10^5
1.2、解题思路
方法一： 使用额外的数组
我们可以使用额外的数组来将每个元素放至正确的位置。用 len 表示数组的长度，我们遍历原数组，将原数组下标为 i 的元素放至新数组下标为 (i+k) % len 的位置，最后将新数组拷贝至原数组即可。
代码实现：
class Solution {
public void rotate(int[] nums, int k) {
int len = nums.length;
int[] tmp = new int[len];
for(int i = 0; i < len; i++) {
tmp[(i+k)%len] = nums[i];
}
for(int i = 0; i< len; i++) {
nums[i] = tmp[i];
}
}
}复杂度分析
- 时间复杂度： O(n)，其中 n 为数组的长度。
空间复杂度： O(n)。
方法二：整体移动
k = 3 就相当于最右边的3个数整体移到了最左边。
代码实现：
class Solution {
public void rotate(int[] nums, int k) {
int len = nums.length;
int[] tmp = new int[k];
k = k % len; //旋转一周等于原来数组，因此首先需要就行k%len操作
for(int i = len - k, index = 0; i < len; i++,index++) { //使用tmp数组保存需要旋转的元素
tmp[index] = nums[i];
}
for(int i = len - 1 - k; i >= 0; i--) { //将不需要旋转的元素整体向后移动
nums[i + k] = nums[i];
}
for(int i = 0; i < k; i++) { //将旋转的元素依次放到最前面
nums[i] = tmp[i];
}
}
}复杂度分析 ：
- 时间复杂度： O(n)，其中 n 为数组的长度。
空间复杂度： O(1)，因为只用到了有限空间k。
2、53. 最大子数组和
2.1、题目介绍
原题链接：53. 最大子数组和 - 力扣（LeetCode）
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
提示：
- 1 <= nums.length <= 105
- -104 <= nums[ i ] <= 104
2.2、解题思路
贪心算法：
从头开始对数组进行累加和，当之前的和小于0时，则丢弃之前的和，即将和设为0，再继续结算和，然后和依然小于0，则继续丢弃，同时记录每次算出的最大和。
图解说明：
按照这个规律继续执行，最后可以得出最大和为6，即为答案。
代码实现：
class Solution {
public int maxSubArray(int[] nums) {
int maxSum = nums[0];
int sum = 0;
for(int x : nums) {
if(sum >= 0) {
sum += x;
}else{ //贪心思想：如果之前的和小于0，则丢弃之前的和，再重新计算和
sum = 0;
sum += x;
}
maxSum = Math.max(maxSum,sum);
}
return maxSum;
}
}复杂度分析：
- 时间复杂度： O(n)，只遍历一次数组。
空间复杂度： O(1)，只使用了常数空间。
更多【LeetCode刷题】 推荐：
【LeetCode力扣】234 快慢指针 | 反转链表 | 还原链表-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/133958602?spm=1001.2014.3001.5502
【LeetCode力扣】86. 分隔链表-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/133942678?spm=1001.2014.3001.5502
【LeetCode力扣】297. 二叉树的序列化与反序列化-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/133827375?spm=1001.2014.3001.5502
如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！文章来源：https://www.toymoban.com/news/detail-713715.html
如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！
如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！
到了这里，关于【LeetCode力扣】189 53 轮转数组 | 最大子数组和的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
