后端算法題解LeetCode前綴和示例詳解
面試題 01.09. 字符串輪轉
面試題 01.09. 字符串輪轉 難度：easy
字符串輪轉。給定兩個字符串 s1 和 s2，請編寫代碼檢查 s2 是否為 s1 旋轉而成（比如，waterbottle 是 erbottlewat 旋轉后的字符串）。
示例1:
輸入：s1 = "waterbottle", s2 = "erbottlewat"
輸出：True
示例2:
輸入：s1 = "aa", s2 = "aba"
輸出：False
提示：
- 字符串長度在 [0, 100000] 范圍內。
方法一：模擬
思路
通過模擬字符串輪轉的過程，來進行字符串的比較，最后得出結論，s2 是否為 s1 旋轉而成；
首先比較字符串的長度，如果兩個字符串的長度都不一樣，那肯定就不是有旋轉而成的，偽代碼如下：
if len(s1) != len(s2):
return False
else:
...
# 接著往下走
然后再通過遍歷將倆字符串進行一一比較，比如指針先指向 s1 的第一位，移動 s2 直到找到與之匹配的，再接著往下，如果不對則結束接下來的匹配，然后將指針指向 s1 的下一位，如此往復，一直到遍歷完 s1，偽代碼如下：
for ..s1:
for ..s2:
if s1[(i + j) % n] != s2[j]:
break
else:
return True
題解
Python：
class Solution:
def isFlipedString(self, s1: str, s2: str) -> bool:
m, n = len(s1), len(s2)
if m != n:
return False
if n == 0:
return True
for i in range(n):
for j in range(n):
if s1[(i + j) % n] != s2[j]:
break
else:
return True
return False
Java：
class Solution {
public boolean isFlipedString(String s1, String s2) {
int m = s1.length(), n = s2.length();
if (m != n) {
return false;
}
if (n == 0) {
return true;
}
for (int i = 0; i < n; i++) {
boolean flag = true;
for (int j = 0; j < n; j++) {
if (s1.charAt((i + j) % n) != s2.charAt(j)) {
flag = false;
break;
}
}
if (flag) {
return true;
}
}
return false;
}
}
方法二：搜索子字符串
思路
通過將兩個相同的 s1 進行拼接，獲得新的字符串，然后從這個新的字符串中搜索 s2，即 s2 是新字符串的子串；
比如，s1 為 abcd，s2 為 cdab，然后兩個 s1 拼接成 abcdabcd這個新字符串 s3，可以發(fā)現(xiàn) s2 就是 s3 的子串，如果 s1 無法通過旋轉得到 s2，那么自然就不是 s3 的子串了，所以偽代碼如下：
s3 = s1 + s1
if s2 in s3:
return True
else:
return False
題解
Python：
class Solution:
def isFlipedString(self, s1: str, s2: str) -> bool:
return len(s1) == len(s2) and s2 in s1 + s1
Java：
class Solution {
public boolean isFlipedString(String s1, String s2) {
return s1.length() == s2.length() && (s1 + s1).contains(s2);
}
}
1480. 一維數(shù)組的動態(tài)和
1480. 一維數(shù)組的動態(tài)和 難度：easy
給你一個數(shù)組 nums 。數(shù)組「動態(tài)和」的計算公式為：runningSum[i] = sum(nums[0]…nums[i]) 。
請返回 nums 的動態(tài)和。
示例 1：
輸入：nums = [1,2,3,4]
輸出：[1,3,6,10]
解釋：動態(tài)和計算過程為 [1, 1+2, 1+2+3, 1+2+3+4] 。
示例 2：
輸入：nums = [1,1,1,1,1]
輸出：[1,2,3,4,5]
解釋：動態(tài)和計算過程為 [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1] 。
示例 3：
輸入：nums = [3,1,2,10,1]
輸出：[3,4,6,16,17]
提示：
1 <= nums.length <= 1000
-10^6 <= nums[i] <= 10^6
方法一：前綴和
思路
這題比較基礎，適合用于了解什么是前綴和，以及初步的嘗試使用前綴和；
根據(jù)題目意思，是要求數(shù)組的動態(tài)和，即當前數(shù)應該等于這個數(shù)的舊值和前面一個值的和，fn = fn + fn-1；
題解
Python：
class Solution:
def runningSum(self, nums: List[int]) -> List[int]:
n = len(nums)
for i in range(1, n):
nums[i] += nums[i - 1]
return nums
Java：
class Solution {
public int[] runningSum(int[] nums) {
int n = nums.length;
for (int i = 1; i < n; i++) {
nums[i] += nums[i - 1];
}
return nums;
}
}
724. 尋找數(shù)組的中心下標
724. 尋找數(shù)組的中心下標 難度：easy
給你一個整數(shù)數(shù)組 nums ，請計算數(shù)組的 中心下標 。
數(shù)組 中心下標 是數(shù)組的一個下標，其左側所有元素相加的和等于右側所有元素相加的和。
如果中心下標位于數(shù)組最左端，那么左側數(shù)之和視為 0 ，因為在下標的左側不存在元素。這一點對于中心下標位于數(shù)組最右端同樣適用。
如果數(shù)組有多個中心下標，應該返回 最靠近左邊 的那一個。如果數(shù)組不存在中心下標，返回 -1 。
示例 1：
輸入：nums = [1, 7, 3, 6, 5, 6]
輸出：3
解釋：
中心下標是 3 。
左側數(shù)之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右側數(shù)之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。
示例 2：
輸入：nums = [1, 2, 3]
輸出：-1
解釋：
數(shù)組中不存在滿足此條件的中心下標。
示例 3：
輸入：nums = [2, 1, -1]
輸出：0
解釋：
中心下標是 0 。
左側數(shù)之和 sum = 0 ，（下標 0 左側不存在元素），
右側數(shù)之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。
提示：
1 <= nums.length <= 104
-1000 <= nums[i] <= 1000
方法一：前綴和
思路
題目要求我們尋找一個中心點，使得左邊之和與右邊之和相等，其實跟上一題的思路是相似的，也就是求數(shù)組的動態(tài)和，要等于總和 total 減去當前的數(shù)值 nums[i] 再除以2（因為左右要相等），偽代碼如下：
# 假設 fn 為數(shù)組的動態(tài)和 total == fn[i-1]*2 + nums[i] ? True : False
解題
Python：
class Solution:
def pivotIndex(self, nums: List[int]) -> int:
total = sum(nums)
_sum = 0
for i in range(len(nums)):
if total == _sum * 2 + nums[i]: return i
_sum += nums[i]
return -1
Java：
class Solution {
public int pivotIndex(int[] nums) {
int total = Arrays.stream(nums).sum();
int sum = 0;
for (int i = 0; i < nums.length; ++i) {
if (2 * sum + nums[i] == total) {
return i;
}
sum += nums[i];
}
return -1;
}
}以上就是后端算法題解LeetCode前綴和示例詳解的詳細內容，更多關于后端算法題解LeetCode前綴和的資料請關注腳本之家其它相關文章！
相關文章
造成1020錯誤的主要原因是代理問題，當打開代理時，登錄該網站會直接顯示上述錯誤“Access?denied?Error?code?1020”，怎么解決這個問題呢，下面小編給大家?guī)砹薱hatgpt?1020?錯誤碼成功解決的三種方案，感興趣的朋友一起看看吧2023-02-02
淺談Visual?Studio和Visual?Studio?Code(VSCode)的區(qū)別及如何選擇
Visual Studio和VSCode兩者都是 Microsoft 制造的,它們有著相似的名稱,盡管它們的名字相似,但它們的功能卻大不相同,本文主要介紹了Visual?Studio和Visual?Studio?Code(VSCode)的區(qū)別,感興趣的可以了解一下2024-06-06
本文主要介紹了音視頻 pts dts基本概念及理解，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-08-08
大數(shù)據(jù)可視化是進行各種大數(shù)據(jù)分析解決的最重要組成部分之一。這篇文章主要介紹了4個最受歡迎的大數(shù)據(jù)可視化工具,需要的朋友可以參考下2019-06-06
Win10中Dreamweaver等軟件界面字太小的問題解決
最近發(fā)現(xiàn)Win10系統(tǒng)中Dreamweaver等軟件界面字太小,所以下面這篇文章主要給大家介紹了關于Win10中Dreamweaver等軟件界面字太小的問題解決辦法,文中通過圖文介紹的非常詳細,需要的朋友可以參考下2007-10-10
網站統(tǒng)計中的數(shù)據(jù)收集原理及實現(xiàn)
目前主流的數(shù)據(jù)收集方式基本都是基于javascript的。本文將簡要分析這種數(shù)據(jù)收集的原理，并一步一步實際搭建一個實際的數(shù)據(jù)收集系統(tǒng)2013-09-09
這篇文章主要介紹了關于程序員生活的一份調查，看看你屬于哪一個群體吧,需要的朋友可以參考下2014-09-09
plot 函數(shù)語法使用plot繪制二維線圖，這篇文章主要介紹了MATLAB?plot函數(shù)詳解,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2023-01-01
gradle+shell實現(xiàn)自動系統(tǒng)簽名
這篇文章主要介紹了gradle+shell實現(xiàn)自動系統(tǒng)簽名的相關資料,需要的朋友可以參考下2019-08-08
這篇文章主要介紹了通過lms.samples熟悉lms微服務框架的使用，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2021-04-04