每日一题——旋转函数

简介: 每日一题——旋转函数

396. 旋转函数

题目描述:

给定一个长度为 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(k) = 0 * arrk[0] + 1 * arrk[1] + … + (n - 1) * arrk[n - 1]

// k=0 顺时针旋转0个位置 arr0=[4,3,2,6]
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25 
// k=1 顺时针旋转1个位置 arr1=[6,4,3,2]
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
// k=2 顺时针旋转2个位置 arr2=[2,6,4,3]
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
// k=3 顺时针旋转3个位置 arr3=[3,2,6,4]
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 。

超时解:

思路:

采用双指针,一头一尾,每旋转一次,两个指针左移便是旋转后的切片。

func maxRotateFunction(nums []int) int {
  length := len(nums)
  if length==1 {
    return 0
  }
  // 每轮两指针左移一位
  pointHead := 0
  pointTail := length - 1
  ans := math.MinInt64
  for i := 0; i < length; i++ {
    f := 0
    head := pointHead
    for j := 0; j < length; j++ {
      f = j*nums[head] + f
      head = (head + 1) % length
    }
    // 如果头指针后推,为负,就指向队列末尾
    pointHead--
    if pointHead < 0 {
      pointHead = length - 1
    }
    pointTail--
    ans = int(math.Max(float64(ans),float64(f)))
  }
  return ans
}

正解:

思路:

观察F(0), …, F(k)的规律可得:

 每旋转一次数组,都是最后一个值的系数变为了0,而其他值的系数都是+1

所以定义sum用来存放数组和, 而F(k)+sum就等于所有系数都+1, 再减去最后一个变化后的值去掉就就是F(k+1)的值了

以示例1为例:

sum就是切片内所有元素的和,你每加一次sum,就相当于F(k)的每个系数都+1

例如:

 sum = 4 + 3 + 2 + 6 = 15

 F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25

 F(0)+sum = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6)+ 4 + 3 + 2 + 6

     = (1 * 4) + (2 * 3) + (3 * 2) + (4 * 6) = 40

而由上面观察到的规律:每旋转一次数组,都是最后一个值的系数变为了0,而其他值的系数都是+1

那么我们观察F(1)相对与F(0)+sum哪里有差别:

 F(1) = (1 * 4) + (2 * 3) + (3 * 2)+ (0 * 6)

 F(0)+sum = (1 * 4) + (2 * 3) + (3 * 2) + (4 * 6)

可以看到原本最后一个值应该对应的是0*6 而F(0)+sum里却是4*6

所以我们可以得出:

F(1) = F(0) + sum - 最后一个变化后的值 = 25 + 15 - 24 = 16

func maxRotateFunction(nums []int) int {
  // sum: 数组内所有元素的和
  // curSum: F(k) 就是每次旋转数组后,代入F(k)公式求的那个
  sum, curSum, ans := 0, 0, 0
  for i := 0; i < len(nums); i++ {
    // 求数组和
    sum = sum + nums[i]
    // 求F(0)
    curSum = curSum + i*nums[i]
  }
  ans = curSum
  for i := len(nums) - 1; i > 0; i-- {
    // F(K+1) = F(K) + sum - 最后一个变化后的值
    curSum = curSum + sum - len(nums)*nums[i]
    ans = max(ans, curSum)
  }
  return ans
}
func max(a, b int) int {
  if b > a {
    return b
  }
  return a
}

提交结果:

相关文章
|
1天前
|
机器学习/深度学习 人工智能 算法
LeetCode刷题--- 面试题 01.07. 旋转矩阵(原地旋转+翻转替旋转)
LeetCode刷题--- 面试题 01.07. 旋转矩阵(原地旋转+翻转替旋转)
|
1天前
每日一题——旋转图像
每日一题——旋转图像
|
1天前
|
Java
【剑指offer】-顺时针打印矩阵-19/67
【剑指offer】-顺时针打印矩阵-19/67
|
1天前
|
Java
每日一题《剑指offer》数组篇之顺时针打印矩阵
每日一题《剑指offer》数组篇之顺时针打印矩阵
32 0
每日一题《剑指offer》数组篇之顺时针打印矩阵
|
11月前
剑指offer 28. 顺时针打印矩阵
剑指offer 28. 顺时针打印矩阵
39 0
|
算法 测试技术
LeetCode每日一题(7)——旋转函数
旋转函数 1.题目 2.示例 3.思路 4.代码 5.复杂度分析
104 0
LeetCode每日一题(7)——旋转函数
|
测试技术
LeetCode——396. 旋转函数
LeetCode——396. 旋转函数
61 0
LeetCode——396. 旋转函数
|
机器学习/深度学习
【LeetCode】螺旋矩阵&&旋转图像
【LeetCode】螺旋矩阵&&旋转图像
【LeetCode】螺旋矩阵&&旋转图像