LeetCode-Go 題解1208. Get Equal Substrings Within Budget 滑動窗口解法深度解析【免費(fèi)下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項(xiàng)目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇文章以 LeetCode-Go 倉庫中 1208.Get-Equal-Substrings-Within-Budget/README.md 為骨架結(jié)合該題目的 Go 源碼實(shí)現(xiàn)與單元測試完整講解「預(yù)算內(nèi)最長可轉(zhuǎn)換子串」問題的滑動窗口雙指針解法。讀完本文你將掌握如何把最大連續(xù)子數(shù)組類問題轉(zhuǎn)化為滑動窗口 預(yù)算增減模型并能直接在 Go 中寫出 100% 測試覆蓋的 AC 代碼。題目原文給定兩個長度相同的字符串s和t。將s中的第i個字符變成t中的第i個字符需要花費(fèi)|s[i] - t[i]|即兩個字符 ASCII 碼值之差的絕對值。再給定一個整數(shù)maxCost預(yù)算。返回s中能轉(zhuǎn)換成與t對應(yīng)子串相同、且總花費(fèi)不超過maxCost的最長子串長度。如果s中不存在任何能轉(zhuǎn)換成t中對應(yīng)子串的子串返回0。示例示例 1Input: s abcd, t bcdf, maxCost 3 Output: 3 Explanation: abc of s can change to bcd. That costs 3, so the maximum length is 3.解釋s abcd與t bcdf逐位計算開銷|a-b|1、|b-c|1、|c-d|1、|d-f|2。取前三位的累計開銷恰好為3因此最長可轉(zhuǎn)換子串長度為3。示例 2Input: s abcd, t cdef, maxCost 3 Output: 1 Explanation: Each character in s costs 2 to change to charactor in t, so the maximum length is 1.解釋每一位的開銷均為|a-c|2、|b-d|2、|c-e|2、|d-f|2。預(yù)算3不足以覆蓋兩個字符224 3因此最長長度為1。示例 3Input: s abcd, t acde, maxCost 0 Output: 1 Explanation: You cant make any change, so the maximum length is 1.解釋預(yù)算為0只有開銷為0的字符位才能免費(fèi)轉(zhuǎn)換。第一位|a-a|0滿足條件其余位均有開銷因此最長長度為1。約束條件1 s.length, t.length 10^50 maxCost 10^6s和t只包含小寫英文字母題目大意中文解讀給你兩個長度相同的字符串s和t將s中的第i個字符變到t中的第i個字符需要|s[i] - t[i]|的開銷開銷可能為 0也就是兩個字符 ASCII 碼值的差的絕對值。用于變更字符串的最大預(yù)算是maxCost。在轉(zhuǎn)化字符串時總開銷應(yīng)當(dāng)小于等于該預(yù)算這也意味著字符串的轉(zhuǎn)化可能是不完全的。如果你可以將s的子字符串轉(zhuǎn)化為它在t中對應(yīng)的子字符串則返回可以轉(zhuǎn)化的最大長度。如果s中沒有子字符串可以轉(zhuǎn)化成t中對應(yīng)的子字符串則返回0。解題思路滑動窗口雙指針核心模型把預(yù)算當(dāng)作窗口容量這一題給出 2 個字符串s、t和一個預(yù)算要求把預(yù)算盡可能花完求s中最多連續(xù)有幾個字母能變成t中的字母。預(yù)算的定義是|s[i] - t[i]|。這是一個典型的最長連續(xù)子數(shù)組問題滿足單調(diào)性窗口越大累計開銷只增不減。因此可以用滑動窗口可變窗口雙指針在線性時間內(nèi)求解右邊界擴(kuò)張滑動窗口右邊界每移動一格就消耗一定的預(yù)算減去|s[right] - t[right]|左邊界收縮當(dāng)預(yù)算不足以容納新字符時maxCost - cost 0移動滑動窗口左邊界把左側(cè)字符的開銷還原回去加回|s[left] - t[left]|直到預(yù)算重新滿足條件統(tǒng)計答案當(dāng)整個窗口把字符s或t都滑動完了的時候取出滑動過程中窗口的最大值即為結(jié)果。單調(diào)性的正確性依據(jù)每一位的轉(zhuǎn)換開銷|s[i] - t[i]| 0非負(fù)因此對于任意固定左邊界left隨著右邊界right增大窗口內(nèi)累計開銷單調(diào)不減一旦累計開銷超過maxCost必須收縮左邊界左邊界收縮后累計開銷單調(diào)不增所以能容納的開銷 maxCost 的最長窗口可以用雙指針線性求解不需要對每個起點(diǎn)做二分或暴力枚舉。倉庫源碼級實(shí)現(xiàn)解析倉庫中的核心實(shí)現(xiàn)位于 1208. Get Equal Substrings Within Budget.go完整代碼如下package leetcode func equalSubstring(s string, t string, maxCost int) int { left, right, res : 0, -1, 0 for left len(s) { if right1 len(s) maxCost-abs(int(s[right1]-a)-int(t[right1]-a)) 0 { right maxCost - abs(int(s[right]-a) - int(t[right]-a)) } else { res max(res, right-left1) maxCost abs(int(s[left]-a) - int(t[left]-a)) left } } return res } func max(a int, b int) int { if a b { return a } return b } func abs(a int) int { if a 0 { return a } return -a }關(guān)鍵實(shí)現(xiàn)細(xì)節(jié)逐行拆解1. 指針初始化left, right, res : 0, -1, 0left從0開始right初始化為-1表示窗口為空res記錄歷史最大窗口長度初始為0對應(yīng)沒有任何子串可轉(zhuǎn)換時的答案。2. 右邊界嘗試擴(kuò)張if right1 len(s) maxCost-abs(int(s[right1]-a)-int(t[right1]-a)) 0 { right maxCost - abs(int(s[right]-a) - int(t[right]-a)) }先檢查right1是否越界再計算把s[right1]轉(zhuǎn)成t[right1]的開銷若剩余預(yù)算足以支付該開銷則右邊界前進(jìn)一格并扣減預(yù)算注意這里先將s/t字符減去a再取差雖然因?yàn)閨s[i]-t[i]|是絕對差直接相減效果相同但統(tǒng)一到0..25的字母序號區(qū)間語義更清晰、可讀性更好。3. 左邊界收縮 統(tǒng)計答案res max(res, right-left1) maxCost abs(int(s[left]-a) - int(t[left]-a)) left當(dāng)右邊界無法繼續(xù)擴(kuò)張越界或預(yù)算不足時先記錄當(dāng)前窗口長度right-left1更新res再把左邊字符的開銷歸還給預(yù)算加回|s[left]-t[left]|左邊界left循環(huán)回到第 2 步繼續(xù)嘗試右邊界擴(kuò)張形成右進(jìn)左退的窗口滑動。4. 邊界情況若某一位轉(zhuǎn)換開銷本身就大于maxCost例如示例 3 中預(yù)算為 0 且該位開銷非 0右邊界無法擴(kuò)張res更新為max(res, right-left1)。此時right1 left窗口為單個字符left窗口長度right-left1計算正確當(dāng)所有字符都無法轉(zhuǎn)換時res保持為 0符合題目返回 0的要求。復(fù)雜度分析時間復(fù)雜度O(n)其中n len(s)。left和right各自最多移動n次總移動次數(shù)不超過2n屬于標(biāo)準(zhǔn)的線性滑動窗口復(fù)雜度空間復(fù)雜度O(1)只使用了left、right、res三個整數(shù)變量沒有任何輔助數(shù)據(jù)結(jié)構(gòu)。在1 s.length, t.length 10^5的約束下O(n) 的滑動窗口是本題的最優(yōu)解之一。測試用例驗(yàn)證倉庫提供了配套的單元測試 1208. Get Equal Substrings Within Budget_test.go覆蓋了題目給出的 3 個示例以及 2 組額外用例stmaxCost期望輸出abcdbcdf33abcdcdef31abcdacde01thjdoffkaqhrnlntls113krrgwzjxss192測試采用表驅(qū)動table-driven風(fēng)格用para1208結(jié)構(gòu)體承載參數(shù)s、t、maxCost用ans1208結(jié)構(gòu)體承載期望答案one每個用例調(diào)用equalSubstring(p.s, p.t, p.maxCost)并打印輸入與輸出方便對照驗(yàn)證。例如額外用例s krrgw, t zjxss, maxCost 19逐位開銷為|k-z|15、|r-j|8、|r-x|5、|g-s|12、|w-s|4。預(yù)算 19 下能容納開銷不超過 19 的最長連續(xù)子串長度為 2如|r-x|5與|g-s|12合計 17或|r-j|8與|r-x|5合計 13與期望輸出 2 一致。如何運(yùn)行測試倉庫根目錄是 Go module見 go.modmodule 名為github.com/halfrost/LeetCode-GoGo 版本 1.19可直接在任意題解目錄下運(yùn)行# 單題測試帶詳細(xì)輸出 go test -v ./leetcode/1208.Get-Equal-Substrings-Within-Budget/ # 全部題解測試 go test ./leetcode/...倉庫的 gotest.sh 展示了全量覆蓋率測試的標(biāo)準(zhǔn)做法go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...該腳本會對整個leetcode目錄生成原子模式atomic的覆蓋率報告與倉庫100% test coverage的目標(biāo)保持一致——本題的equalSubstring同樣有完整測試覆蓋。思路延伸滑動窗口模板化本題是滑動窗口Sliding Window的經(jīng)典代表其右邊界擴(kuò)張扣預(yù)算、左邊界收縮還預(yù)算的模式可以抽象為通用模板適用于「最長連續(xù)子數(shù)組滿足某條件」類問題left, right : 0, -1 res : 0 for left len(s) { // 1. 嘗試擴(kuò)張右邊界若加入新元素后仍滿足約束 if right1 len(s) 滿足約束條件(right1) { right // 更新窗口狀態(tài)扣減預(yù)算 / 增加計數(shù)等 } else { // 2. 記錄當(dāng)前窗口對答案的貢獻(xiàn) res max(res, right-left1) // 3. 收縮左邊界還原窗口狀態(tài)歸還預(yù)算 / 減少計數(shù)等 left } } return res同一模板稍加改動即可套用到其他題目例如最大連續(xù) 1 的個數(shù) III可翻轉(zhuǎn)最多 k 個 0把0 的個數(shù)當(dāng)作預(yù)算替換后的最長重復(fù)字符把非眾數(shù)字符的個數(shù)當(dāng)作預(yù)算無重復(fù)字符的最長子串把字符出現(xiàn)次數(shù)當(dāng)作約束條件。掌握預(yù)算扣減/歸還這一對操作就抓住了可變窗口滑動窗口的精髓窗口內(nèi)狀態(tài)隨右邊界進(jìn)入而消耗隨左邊界離開而恢復(fù)答案在所有合法窗口長度的最大值中產(chǎn)生。小結(jié)LeetCode 1208 題的 Go 解法核心可以總結(jié)為三點(diǎn)問題本質(zhì)求滿足累計開銷 maxCost的最長連續(xù)子數(shù)組長度算法選擇因開銷非負(fù)、窗口開銷單調(diào)采用滑動窗口雙指針可將暴力 O(n2) 優(yōu)化到 O(n) 時間、O(1) 空間工程實(shí)踐倉庫中的 源碼實(shí)現(xiàn) 與 表驅(qū)動測試 可直接復(fù)制運(yùn)行是面試與刷題時值得反復(fù)對照的模板。【免費(fèi)下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項(xiàng)目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考 LeetCode-Go 題解：1208. Get Equal Substrings Within Budget 滑動窗口解法深度解析
LeetCode-Go 題解1208. Get Equal Substrings Within Budget 滑動窗口解法深度解析【免費(fèi)下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項(xiàng)目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇文章以 LeetCode-Go 倉庫中 1208.Get-Equal-Substrings-Within-Budget/README.md 為骨架結(jié)合該題目的 Go 源碼實(shí)現(xiàn)與單元測試完整講解「預(yù)算內(nèi)最長可轉(zhuǎn)換子串」問題的滑動窗口雙指針解法。讀完本文你將掌握如何把最大連續(xù)子數(shù)組類問題轉(zhuǎn)化為滑動窗口 預(yù)算增減模型并能直接在 Go 中寫出 100% 測試覆蓋的 AC 代碼。題目原文給定兩個長度相同的字符串s和t。將s中的第i個字符變成t中的第i個字符需要花費(fèi)|s[i] - t[i]|即兩個字符 ASCII 碼值之差的絕對值。再給定一個整數(shù)maxCost預(yù)算。返回s中能轉(zhuǎn)換成與t對應(yīng)子串相同、且總花費(fèi)不超過maxCost的最長子串長度。如果s中不存在任何能轉(zhuǎn)換成t中對應(yīng)子串的子串返回0。示例示例 1Input: s abcd, t bcdf, maxCost 3 Output: 3 Explanation: abc of s can change to bcd. That costs 3, so the maximum length is 3.解釋s abcd與t bcdf逐位計算開銷|a-b|1、|b-c|1、|c-d|1、|d-f|2。取前三位的累計開銷恰好為3因此最長可轉(zhuǎn)換子串長度為3。示例 2Input: s abcd, t cdef, maxCost 3 Output: 1 Explanation: Each character in s costs 2 to change to charactor in t, so the maximum length is 1.解釋每一位的開銷均為|a-c|2、|b-d|2、|c-e|2、|d-f|2。預(yù)算3不足以覆蓋兩個字符224 3因此最長長度為1。示例 3Input: s abcd, t acde, maxCost 0 Output: 1 Explanation: You cant make any change, so the maximum length is 1.解釋預(yù)算為0只有開銷為0的字符位才能免費(fèi)轉(zhuǎn)換。第一位|a-a|0滿足條件其余位均有開銷因此最長長度為1。約束條件1 s.length, t.length 10^50 maxCost 10^6s和t只包含小寫英文字母題目大意中文解讀給你兩個長度相同的字符串s和t將s中的第i個字符變到t中的第i個字符需要|s[i] - t[i]|的開銷開銷可能為 0也就是兩個字符 ASCII 碼值的差的絕對值。用于變更字符串的最大預(yù)算是maxCost。在轉(zhuǎn)化字符串時總開銷應(yīng)當(dāng)小于等于該預(yù)算這也意味著字符串的轉(zhuǎn)化可能是不完全的。如果你可以將s的子字符串轉(zhuǎn)化為它在t中對應(yīng)的子字符串則返回可以轉(zhuǎn)化的最大長度。如果s中沒有子字符串可以轉(zhuǎn)化成t中對應(yīng)的子字符串則返回0。解題思路滑動窗口雙指針核心模型把預(yù)算當(dāng)作窗口容量這一題給出 2 個字符串s、t和一個預(yù)算要求把預(yù)算盡可能花完求s中最多連續(xù)有幾個字母能變成t中的字母。預(yù)算的定義是|s[i] - t[i]|。這是一個典型的最長連續(xù)子數(shù)組問題滿足單調(diào)性窗口越大累計開銷只增不減。因此可以用滑動窗口可變窗口雙指針在線性時間內(nèi)求解右邊界擴(kuò)張滑動窗口右邊界每移動一格就消耗一定的預(yù)算減去|s[right] - t[right]|左邊界收縮當(dāng)預(yù)算不足以容納新字符時maxCost - cost 0移動滑動窗口左邊界把左側(cè)字符的開銷還原回去加回|s[left] - t[left]|直到預(yù)算重新滿足條件統(tǒng)計答案當(dāng)整個窗口把字符s或t都滑動完了的時候取出滑動過程中窗口的最大值即為結(jié)果。單調(diào)性的正確性依據(jù)每一位的轉(zhuǎn)換開銷|s[i] - t[i]| 0非負(fù)因此對于任意固定左邊界left隨著右邊界right增大窗口內(nèi)累計開銷單調(diào)不減一旦累計開銷超過maxCost必須收縮左邊界左邊界收縮后累計開銷單調(diào)不增所以能容納的開銷 maxCost 的最長窗口可以用雙指針線性求解不需要對每個起點(diǎn)做二分或暴力枚舉。倉庫源碼級實(shí)現(xiàn)解析倉庫中的核心實(shí)現(xiàn)位于 1208. Get Equal Substrings Within Budget.go完整代碼如下package leetcode func equalSubstring(s string, t string, maxCost int) int { left, right, res : 0, -1, 0 for left len(s) { if right1 len(s) maxCost-abs(int(s[right1]-a)-int(t[right1]-a)) 0 { right maxCost - abs(int(s[right]-a) - int(t[right]-a)) } else { res max(res, right-left1) maxCost abs(int(s[left]-a) - int(t[left]-a)) left } } return res } func max(a int, b int) int { if a b { return a } return b } func abs(a int) int { if a 0 { return a } return -a }關(guān)鍵實(shí)現(xiàn)細(xì)節(jié)逐行拆解1. 指針初始化left, right, res : 0, -1, 0left從0開始right初始化為-1表示窗口為空res記錄歷史最大窗口長度初始為0對應(yīng)沒有任何子串可轉(zhuǎn)換時的答案。2. 右邊界嘗試擴(kuò)張if right1 len(s) maxCost-abs(int(s[right1]-a)-int(t[right1]-a)) 0 { right maxCost - abs(int(s[right]-a) - int(t[right]-a)) }先檢查right1是否越界再計算把s[right1]轉(zhuǎn)成t[right1]的開銷若剩余預(yù)算足以支付該開銷則右邊界前進(jìn)一格并扣減預(yù)算注意這里先將s/t字符減去a再取差雖然因?yàn)閨s[i]-t[i]|是絕對差直接相減效果相同但統(tǒng)一到0..25的字母序號區(qū)間語義更清晰、可讀性更好。3. 左邊界收縮 統(tǒng)計答案res max(res, right-left1) maxCost abs(int(s[left]-a) - int(t[left]-a)) left當(dāng)右邊界無法繼續(xù)擴(kuò)張越界或預(yù)算不足時先記錄當(dāng)前窗口長度right-left1更新res再把左邊字符的開銷歸還給預(yù)算加回|s[left]-t[left]|左邊界left循環(huán)回到第 2 步繼續(xù)嘗試右邊界擴(kuò)張形成右進(jìn)左退的窗口滑動。4. 邊界情況若某一位轉(zhuǎn)換開銷本身就大于maxCost例如示例 3 中預(yù)算為 0 且該位開銷非 0右邊界無法擴(kuò)張res更新為max(res, right-left1)。此時right1 left窗口為單個字符left窗口長度right-left1計算正確當(dāng)所有字符都無法轉(zhuǎn)換時res保持為 0符合題目返回 0的要求。復(fù)雜度分析時間復(fù)雜度O(n)其中n len(s)。left和right各自最多移動n次總移動次數(shù)不超過2n屬于標(biāo)準(zhǔn)的線性滑動窗口復(fù)雜度空間復(fù)雜度O(1)只使用了left、right、res三個整數(shù)變量沒有任何輔助數(shù)據(jù)結(jié)構(gòu)。在1 s.length, t.length 10^5的約束下O(n) 的滑動窗口是本題的最優(yōu)解之一。測試用例驗(yàn)證倉庫提供了配套的單元測試 1208. Get Equal Substrings Within Budget_test.go覆蓋了題目給出的 3 個示例以及 2 組額外用例stmaxCost期望輸出abcdbcdf33abcdcdef31abcdacde01thjdoffkaqhrnlntls113krrgwzjxss192測試采用表驅(qū)動table-driven風(fēng)格用para1208結(jié)構(gòu)體承載參數(shù)s、t、maxCost用ans1208結(jié)構(gòu)體承載期望答案one每個用例調(diào)用equalSubstring(p.s, p.t, p.maxCost)并打印輸入與輸出方便對照驗(yàn)證。例如額外用例s krrgw, t zjxss, maxCost 19逐位開銷為|k-z|15、|r-j|8、|r-x|5、|g-s|12、|w-s|4。預(yù)算 19 下能容納開銷不超過 19 的最長連續(xù)子串長度為 2如|r-x|5與|g-s|12合計 17或|r-j|8與|r-x|5合計 13與期望輸出 2 一致。如何運(yùn)行測試倉庫根目錄是 Go module見 go.modmodule 名為github.com/halfrost/LeetCode-GoGo 版本 1.19可直接在任意題解目錄下運(yùn)行# 單題測試帶詳細(xì)輸出 go test -v ./leetcode/1208.Get-Equal-Substrings-Within-Budget/ # 全部題解測試 go test ./leetcode/...倉庫的 gotest.sh 展示了全量覆蓋率測試的標(biāo)準(zhǔn)做法go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...該腳本會對整個leetcode目錄生成原子模式atomic的覆蓋率報告與倉庫100% test coverage的目標(biāo)保持一致——本題的equalSubstring同樣有完整測試覆蓋。思路延伸滑動窗口模板化本題是滑動窗口Sliding Window的經(jīng)典代表其右邊界擴(kuò)張扣預(yù)算、左邊界收縮還預(yù)算的模式可以抽象為通用模板適用于「最長連續(xù)子數(shù)組滿足某條件」類問題left, right : 0, -1 res : 0 for left len(s) { // 1. 嘗試擴(kuò)張右邊界若加入新元素后仍滿足約束 if right1 len(s) 滿足約束條件(right1) { right // 更新窗口狀態(tài)扣減預(yù)算 / 增加計數(shù)等 } else { // 2. 記錄當(dāng)前窗口對答案的貢獻(xiàn) res max(res, right-left1) // 3. 收縮左邊界還原窗口狀態(tài)歸還預(yù)算 / 減少計數(shù)等 left } } return res同一模板稍加改動即可套用到其他題目例如最大連續(xù) 1 的個數(shù) III可翻轉(zhuǎn)最多 k 個 0把0 的個數(shù)當(dāng)作預(yù)算替換后的最長重復(fù)字符把非眾數(shù)字符的個數(shù)當(dāng)作預(yù)算無重復(fù)字符的最長子串把字符出現(xiàn)次數(shù)當(dāng)作約束條件。掌握預(yù)算扣減/歸還這一對操作就抓住了可變窗口滑動窗口的精髓窗口內(nèi)狀態(tài)隨右邊界進(jìn)入而消耗隨左邊界離開而恢復(fù)答案在所有合法窗口長度的最大值中產(chǎn)生。小結(jié)LeetCode 1208 題的 Go 解法核心可以總結(jié)為三點(diǎn)問題本質(zhì)求滿足累計開銷 maxCost的最長連續(xù)子數(shù)組長度算法選擇因開銷非負(fù)、窗口開銷單調(diào)采用滑動窗口雙指針可將暴力 O(n2) 優(yōu)化到 O(n) 時間、O(1) 空間工程實(shí)踐倉庫中的 源碼實(shí)現(xiàn) 與 表驅(qū)動測試 可直接復(fù)制運(yùn)行是面試與刷題時值得反復(fù)對照的模板。【免費(fèi)下載鏈接】LeetCode-Go? Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 題解項(xiàng)目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考