Re: [閒聊] 每日leetcode已回收

看板Marginalman作者Rushia (早瀬ユウカの体操服 )時間1年前 (2024/04/30 15:24)推噓3(3推 0噓 3→)

留言6則, 6人參與討論串170/1548 (看更多)

https://leetcode.com/problems/number-of-wonderful-substrings/description 1915. Number of Wonderful Substrings 給你一個包含小寫字母a~j的字串，如果一個子字串的所有字母只有一個字母出現奇數次那麼他就是一個超讚字串，求出s裏面有幾個超讚子字串。思路： 1.我們要判斷一個字串是不是超讚字串要檢查他的奇偶，我們可以用一個二進位數字表示，奇數為1偶數為0，因為有10個字母所以需要10位數的二進制就可以表示，狀態初始化為0000000000 -> i = -1 (什麼都不加必定是偶數) 假設加入一個a狀態變成1000000000 -> i = 0 加入一個b狀態變成1100000000 -> i = 1 加入一個a狀態變成0100000000 -> i = 2 加入一個b狀態變成0000000000 -> i = 3 ... 為了方便討論，後面我們稱二進位數字為"狀態" 2.如果 i 不同但是狀態相同(例如上面i=-1和i=3)，兩個"狀態"之間的字母必定只會出現偶數次(奇數不可能相同)，所以： b ... [xxxxx] ... b 如果最後一個b的狀態等於前面的那個b，可以不斷地擴展會變成： b -> [中間必定是偶數] -> b -> [中間必定是偶數] -> b 因為這個特性，只要當前的狀態前面出現過，他就可以跟前面的狀態接在一起變成一個新的超讚數字，就像是 b => bb => bbb 這樣所以我們只要找有幾個b就好，找的過程又可以分成奇偶兩個case。 3.可以使用前綴和技巧求解，因為最多有2^10個狀態所以可以把map換成array 假定 cnt[x] 表示二進位x這個狀態的出現次數: (1) 任何數加上偶數，奇偶性不變。同第二點所述，累加前面的 cnt[x] 總數(只要該狀態有出現過就一定可以累加) (2) 任何數加上奇數，奇數變偶數，偶數變奇數。假設前面存在一個前綴字串 x 可和 word[i] 組成一個超讚字串，那麼必定滿足: x ^ word[i] = 只有一個一的二進位數而該數x剛好會等於 word[i] 的狀態每個位數翻轉1，假定 word[i]=0000000010 0000000011 ^ 0000000010 = 0000000001 0000000000 ^ 0000000010 = 0000000010 0000000110 ^ 0000000010 = 0000000100 0000001010 ^ 0000000010 = 0000001000 0000010010 ^ 0000000010 = 0000010000 0000100010 ^ 0000000010 = 0000100000 0001000010 ^ 0000000010 = 0001000000 0010000010 ^ 0000000010 = 0010000000 0100000010 ^ 0000000010 = 0100000000 1000000010 ^ 0000000010 = 1000000000 所以我們去找前面所有 word[i] 翻轉一個位元的狀態共有幾個，全部累加起來就好。 pycode: --------------------------------------- class Solution: def wonderfulSubstrings(self, word: str) -> int: cnt = [0] * 1024 cnt[0] = 1 mask = 0 res = 0 for c in word: # 更新狀態 idx = ord(c) - ord('a') mask ^= (1 << idx) # 偶數 res += cnt[mask] # 奇數 for i in range(10): next = mask ^ (1 << i) res += cnt[next] cnt[mask] += 1 return res --------------------------------------- 幹幹幹幹幹這什麼死媽題目這題他媽只有Medium你敢信== -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.139.195.59 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1714461884.A.3B5.html

推

Che31128

04/30 15:25, 1年前 , 1^F

04/30 15:25, 1^F

→

lopp54321010

04/30 15:25, 1年前 , 2^F

04/30 15:25, 2^F

推

sustainer123

04/30 15:26, 1年前 , 3^F

04/30 15:26, 3^F