金三銀四復(fù)工高頻面試題java算法LeetCode396旋轉(zhuǎn)函數(shù)
題目描述
這是 LeetCode 上的 396. 旋轉(zhuǎn)函數(shù) ,難度為 中等。
Tag : 「前綴和」、「滑動窗口」
給定一個長度為 n 的整數(shù)數(shù)組 nums
F(k) = 0 * arrk[0] + 1 * arrk[1] + ... + (n - 1) * arrk[n - 1]
返回 F(0), F(1), ..., F(n-1)
中的最大值 。
生成的測試用例讓答案符合 32 位 整數(shù)。
示例 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
提示:
前綴和 + 滑動窗口
為了方便,我們將 numsnumsnums 的長度記為 nnn。
實現(xiàn)上,我們并不需要真正對 nums 進(jìn)行復(fù)制拼接,而只需要在計算前綴和數(shù)組 sum 進(jìn)行簡單的下標(biāo)處理即可。
代碼:
class Solution { public int maxRotateFunction(int[] nums) { int n = nums.length; int[] sum = new int[n * 2 + 10]; for (int i = 1; i <= 2 * n; i++) sum[i] = sum[i - 1] + nums[(i - 1) % n]; int ans = 0; for (int i = 1; i <= n; i++) ans += nums[i - 1] * (i - 1); for (int i = n + 1, cur = ans; i < 2 * n; i++) { cur += nums[(i - 1) % n] * (n - 1); cur -= sum[i - 1] - sum[i - n]; if (cur > ans) ans = cur; } return ans; } }
- 時間復(fù)雜度:O(n)
- 空間復(fù)雜度:O(n)
最后
這是我們「刷穿 LeetCode」系列文章的第 No.396
篇,系列開始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道題目,部分是有鎖題,我們將先把所有不帶鎖的題目刷完。
在這個系列文章里面,除了講解解題思路以外,還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應(yīng)的代碼模板。
為了方便各位同學(xué)能夠電腦上進(jìn)行調(diào)試和提交代碼,我建立了相關(guān)的倉庫:github.com/SharingSour… 。
在倉庫地址里,你可以看到系列文章的題解鏈接、系列文章的相應(yīng)代碼、LeetCode 原題鏈接和其他優(yōu)選題解。
以上就是金三銀四復(fù)工高頻面試題java算法LeetCode396旋轉(zhuǎn)函數(shù)的詳細(xì)內(nèi)容,更多關(guān)于java算法LeetCode旋轉(zhuǎn)函數(shù)的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
Java使用Callable接口實現(xiàn)多線程的實例代碼
這篇文章主要介紹了Java使用Callable接口實現(xiàn)多線程的實例代碼,實現(xiàn)Callable和實現(xiàn)Runnable類似,但是功能更強大,具體表現(xiàn)在可以在任務(wù)結(jié)束后提供一個返回值,Runnable不行,call方法可以拋出異,Runnable的run方法不行,需要的朋友可以參考下2023-08-08JNI實現(xiàn)最簡單的JAVA調(diào)用C/C++代碼
這篇文章主要介紹了JNI實現(xiàn)最簡單的JAVA調(diào)用C/C++代碼,具有一定的參考價值,感興趣的小伙伴們可以參考一下2017-08-08Java GraphQL數(shù)據(jù)加載器批處理的實現(xiàn)詳解
GraphQL 數(shù)據(jù)加載器是優(yōu)化 GraphQL API 的關(guān)鍵組件,旨在解決臭名昭著的 N+1 查詢問題,在本中,我們將深入研究其批處理功能,感興趣的小伙伴可以了解下2023-12-12Springboot解決跨域問題方案總結(jié)(包括Nginx,Gateway網(wǎng)關(guān)等)
跨域問題是瀏覽器為了保護(hù)用戶的信息安全,實施了同源策略(Same-Origin?Policy),即只允許頁面請求同源(相同協(xié)議、域名和端口)的資源,本文給大家總結(jié)了Springboot解決跨域問題方案包括Nginx,Gateway網(wǎng)關(guān)等),需要的朋友可以參考下2024-03-03