【LeetCode力扣】189 53 轮转数组 | 最大子数组和
目录
1、189. 轮转数组
1.1、题目介绍
1.2、解题思路
2、53. 最大子数组和
2.1、题目介绍
2.2、解题思路
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
如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！
如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！
如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！