漳州市建设局网站混凝土公示,网站建设 三乐,php是网站开发语言吗,广告联盟cpc目录
1、189. 轮转数组
1.1、题目介绍
1.2、解题思路
2、53. 最大子数组和
2.1、题目介绍
2.2、解题思路 1、189. 轮转数组
1.1、题目介绍
原题链接#xff1a;189. 轮转数组 - 力扣#xff08;LeetCode#xff09; 示例 1: 输入: nums [1,2,3,4,5,6,7], k 3输…目录
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)-10 k 10^5 1.2、解题思路
方法一 使用额外的数组 我们可以使用额外的数组来将每个元素放至正确的位置。用 len 表示数组的长度我们遍历原数组将原数组下标为 i 的元素放至新数组下标为 (ik) % 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[(ik)%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?spm1001.2014.3001.5502【LeetCode力扣】86. 分隔链表-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/133942678?spm1001.2014.3001.5502
【LeetCode力扣】297. 二叉树的序列化与反序列化-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/133827375?spm1001.2014.3001.5502 如果觉得作者写的不错求给博主一个大大的点赞支持一下你们的支持是我更新的最大动力
如果觉得作者写的不错求给博主一个大大的点赞支持一下你们的支持是我更新的最大动力
如果觉得作者写的不错求给博主一个大大的点赞支持一下你们的支持是我更新的最大动力
