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

看板Marginalman作者oinishere (是oin捏)時間1年前 (2024/04/30 15:59)推噓4(4推 0噓 17→)

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

※ 引述《Rushia (早瀬ユウカの体操服)》之銘言： : 　 : 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] 翻轉一個位元的狀態共有幾個，全部累加起來就好。思路: 哇靠這三小這是dp嗎? (30分鐘之後) 幹拎娘誰他媽給這標成medium 的摧毀別人自尊很好玩是不是怎麼不去給狗幹對不起對不起對不起對不起對不起對不起然後我跑去留言區看提示 bitset prefix sum 好我試試看結果成功好爽 https://i.imgur.com/oBstnsI.jpeg

先把他弄成只有四個字母的bitset試試看為什麼只有0跟1? 因為有幾個根本不重要重點是他字串開頭到結尾有幾個奇數的開始進入word 然後先看第一個字改變當時bitset 並且記錄同時去前面看有沒有能接的bitset 然後再繼續幹到最後怎麼看有沒有能接的bitset? 他進來的時候如果要只有一個以下是奇數那這樣代表 1: 他就都沒有 2: 他有一個然後往回找要找什麼? 1: 要找的是最多一個奇數的 2: 要找的就是可以跟他弄成剛好沒有奇數的所以往回找時要看兩個情況 1: 剛好跟他差一個bit的也就是說他們之間剛好多一個或是少一個奇數 2: 找到跟他bitset長一樣就是一樣的這樣他們兩個之間就一定是都是偶數然後1跟2都可以直接加上在那個位子出現的子字串也就是那一種bitset的數量 ```cpp class Solution { public: long long wonderfulSubstrings(string word) { long long res = 0; int len = word.size(); bitset<10> now; bitset<10> nowone; unordered_map<bitset<10>,long long> paper; paper[now]++; for(int i = 0 ; i < len ; i ++) { now[word[i]-'a'] = now[word[i]-'a'] ^ 1; for(int j = 0 ; j < 10 ; j ++) { nowone = now; nowone[j] = nowone[j] ^ 1; res += paper[nowone]; } res += paper[now]; paper[now] ++; } return res; } }; ``` -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.62.124 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1714463998.A.D87.html

推

wu10200512

04/30 16:00, 1年前 , 1^F

04/30 16:00, 1^F

→

oinishere

04/30 16:01, 1年前 , 2^F

04/30 16:01, 2^F

推

sustainer123

04/30 16:01, 1年前 , 3^F

04/30 16:01, 3^F