{"id":2142,"date":"2018-03-16T09:48:53","date_gmt":"2018-03-16T16:48:53","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2142"},"modified":"2018-03-17T09:48:56","modified_gmt":"2018-03-17T16:48:56","slug":"leetcode-396-rotate-function","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/math\/leetcode-396-rotate-function\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 396. Rotate Function"},"content":{"rendered":"

Problem:<\/h1>\n
\n
\n

Given an array of integers\u00a0A<\/code>\u00a0and let\u00a0n<\/i>\u00a0to be its length.<\/p>\n

Assume\u00a0Bk<\/sub><\/code>\u00a0to be an array obtained by rotating the array\u00a0A<\/code>\u00a0k<\/i>\u00a0positions clock-wise, we define a “rotation function”\u00a0F<\/code>\u00a0on\u00a0A<\/code>\u00a0as follow:<\/p>\n

F(k) = 0 * Bk<\/sub>[0] + 1 * Bk<\/sub>[1] + ... + (n-1) * Bk<\/sub>[n-1]<\/code>.<\/p>\n

Calculate the maximum value of\u00a0F(0), F(1), ..., F(n-1)<\/code>.<\/p>\n

Note:<\/b>
\nn<\/i>\u00a0is guaranteed to be less than 105<\/sup>.<\/p>\n

Example:<\/b><\/p>\n

A = [4, 3, 2, 6]\r\n\r\nF(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25\r\nF(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16\r\nF(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23\r\nF(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26\r\n\r\nSo the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.\r\n<\/pre>\n<\/div>\n<\/div>\n
Solution 1: Brute Force<\/h1>\n
Time complexity: O(n^2) TLE<\/p>\n
Space complexity: O(1)<\/p>\n
Solution 2: Math<\/h1>\n
F(K)          =               0A[K] + 1A[K+1] + 2A[K+2] + ... + (n-2)A[K-2] + (n-1)A[K-1]\r\nF(K-1)        =     0A[K-1] + 1A[K] + 2A[K+1] + 3A[K+2] + ... + (n-1)A[K-2]\r\nF(K) - F(K-1) = (n-1)A[K-1] - 1A[K] - 1A[K+1] - 1A[K+2] - ... -     1A[K-2]\r\n              = (n-1)A[K-1] - (1A[K] + 1A[K+1] + ... + 1A[K-2] + 1A[K-1] - 1A[K-1])\r\n              = nA[K-1] - sum(A)\r\ncompute F(0)\r\nF(i)          = F(i-1) + nA[i-1] - sum(A)<\/pre>\n
 <\/p>\n
Time complexity: O(n)<\/p>\n
Space complexity: O(1)<\/p>\n
\/\/ Author: Huahua\r\n\/\/ Running time: 11 ms\r\nclass Solution {\r\npublic:\r\n  int maxRotateFunction(vector<int>& A) {\r\n    const int n = A.size();\r\n    int sum = 0;\r\n    int f = 0;\r\n    for (int i = 0; i < n; ++i) {\r\n      sum += A[i];\r\n      f += i * A[i];\r\n    }\r\n    int ans = f;\r\n    for (int i = 0; i < n - 1; ++i) {\r\n      f = f + sum - n * A[n - i - 1];\r\n      ans = max(ans, f);\r\n    }\r\n    return ans;\r\n  }\r\n};<\/pre>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
Problem: Given an array of integers\u00a0A\u00a0and let\u00a0n\u00a0to be its length. Assume\u00a0Bk\u00a0to be an array obtained by rotating the array\u00a0A\u00a0k\u00a0positions clock-wise, we define a “rotation function”\u00a0F\u00a0on\u00a0A\u00a0as…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184,49],"tags":[20,177,250],"class_list":["post-2142","post","type-post","status-publish","format-standard","hentry","category-array","category-math","tag-array","tag-medium","tag-rotate","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2142","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=2142"}],"version-history":[{"count":8,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2142\/revisions"}],"predecessor-version":[{"id":2150,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2142\/revisions\/2150"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2142"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2142"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2142"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}