湛江网站建设开发,烟台手机网站建设电话,网页制作软件培训,长沙网警#左耳听风 ARST 打卡活动重启#
目录
一、题目
二、解决方法一
三、解决方法二 关于 ARTS 的释义 —— 每周完成一个 ARTS#xff1a; ● Algorithm: 每周至少做一个 LeetCode 的算法题 ● Review: 阅读并点评至少一篇英文技术文章 ● Tips: 学习至少一个技术技巧 ● Shar…#左耳听风 ARST 打卡活动重启#
目录
一、题目
二、解决方法一
三、解决方法二 关于 ARTS 的释义 —— 每周完成一个 ARTS ● Algorithm: 每周至少做一个 LeetCode 的算法题 ● Review: 阅读并点评至少一篇英文技术文章 ● Tips: 学习至少一个技术技巧 ● Share: 分享一篇有观点和思考的技术文章 希望通过此次活动能聚集一波热爱技术的人延续好奇、探索、实践、分享的精神。 一、题目 给定一个长度为 n 的整数数组 nums 。 假设 arrk 是数组 nums 顺时针旋转 k 个位置后的数组我们定义 nums 的 旋转函数 F 为 F(k) 0 * arrk[0] 1 * arrk[1] ... (n - 1) * arrk[n - 1] 返回 F(0), F(1), ..., F(n-1)中的最大值 。 生成的测试用例让答案符合 32 位 整数。 示例 1: 输入: nums [4,3,2,6] 输出: 26 解释: F(0) (0 * 4) (1 * 3) (2 * 2) (3 * 6) 0 3 4 18 25 F(1) (0 * 6) (1 * 4) (2 * 3) (3 * 2) 0 4 6 6 16 F(2) (0 * 2) (1 * 6) (2 * 4) (3 * 3) 0 6 8 9 23 F(3) (0 * 3) (1 * 2) (2 * 6) (3 * 4) 0 2 12 12 26 所以 F(0), F(1), F(2), F(3) 中的最大值是 F(3) 26 。 示例 2: 输入: nums [100] 输出: 0 提示: n nums.length 1 n 105 -100 nums[i] 100 二、解决方法一
class Solution:def maxRotateFunction(self, nums: List[int]) - int:n len(nums)f [0] * nfor i in range(n):cur nums[i]f[i] cur * (i 1)res f[0]for i in range(1, n):res max(res, f[i] f[i - 1])return res这段代码实现了一个函数 maxRotateFunction,用于计算给定整数数组 nums 顺时针旋转 k 个位置后所有旋转后的数组元素之和的最大值。 具体实现过程如下 1. 首先定义一个长度为 n 的列表 f,其中 f[i] 表示将数组 nums 顺时针旋转 i 个位置后所有元素之和。初始时f[i] i * nums[i]。 2. 然后遍历整个数组 nums,依次计算出每个位置的旋转后元素之和并将其保存到列表 f 中。 3. 最后从头开始遍历列表 f,找到其中的最大值即可。因为每次旋转都会使数组中的某个元素变为零所以最大的旋转后元素之和就是第一个元素加上最后一个元素的值乘以数组长度减一。因此最终返回的是 f[0] f[n-1] 的最大值。 总的来说这段代码的时间复杂度为 O(n),空间复杂度为 O(1)。 三、解决方法二
class Solution:def maxRotateFunction(self, nums: List[int]) - int:n len(nums)f [0] * nfor i in range(n):cur nums[i]f[i] cur * (i 1)res f[0]for i in range(1, n):# 将数组分为两部分前半部分为递增序列后半部分为递减序列left, right 0, i - 1while left right:# 如果当前元素小于它的下一个元素说明它应该在后半部分if nums[left] nums[right]:break# 否则将它移动到前半部分temp nums[left]nums[left] nums[right]nums[right] templeft 1right - 1# 计算前半部分和后半部分的元素之和并更新最大值res max(res, f[i] sum(f[:left]) sum(f[right1:]))return res这段代码实现了一个函数 maxRotateFunction,用于计算给定整数数组 nums 顺时针旋转 k 个位置后所有旋转后的数组元素之和的最大值。 具体实现过程如下 1. 首先定义一个长度为 n 的列表 f,其中 f[i] 表示将数组 nums 顺时针旋转 i 个位置后所有元素之和。初始时f[i] i * nums[i]。 2. 然后遍历整个数组 nums,依次计算出每个位置的旋转后元素之和并将其保存到列表 f 中。 3. 对于数组中的每个元素我们可以将其分为两部分前半部分为递增序列后半部分为递减序列。具体来说我们从数组的两端开始向中间扫描如果当前元素小于它的下一个元素说明它应该在后半部分否则将它移动到前半部分。这个过程可以用双指针法实现。 4. 将数组分为两部分后我们可以计算出前半部分和后半部分的元素之和并更新最大值 res。具体来说我们可以将前半部分的元素之和求出来然后加上后半部分的元素之和即可。 5. 如果旋转次数 k 小于等于数组长度 n,则将问题转化为求解 F(k1) 的最大值否则F(k) 就是最终答案。 总的来说这段代码的时间复杂度为 O(n^2),空间复杂度为 O(1)。
