※ 本文轉寄自 ptt.cc, 文章原始頁面
Re: [閒聊] 每日leetcode
※ 引述 《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
Re: 回文串
00
[閒聊] 每日Leetcode
Marginalman03/29 10:59
13
[閒聊] 每日LeetCode
Marginalman09/14 23:02
13
Re: [閒聊] 每日LeetCode
Marginalman09/15 12:15
22
Re: [閒聊] 每日LeetCode
Marginalman09/15 12:57
03
Re: [閒聊] 每日LeetCode
Marginalman09/21 15:41
35
Re: [閒聊] 每日LeetCode
Marginalman09/21 15:53
45
Re: [閒聊] 每日LeetCode
Marginalman09/22 10:40
16
Re: [閒聊] 每日LeetCode
Marginalman09/22 11:38
12
Re: [閒聊] 每日LeetCode
Marginalman09/22 16:12
27
Re: [閒聊] 每日LeetCode
Marginalman09/24 12:54
05
Re: [閒聊] 每日LeetCode
Marginalman09/25 15:51
24
Re: [閒聊] 每日LeetCode
Marginalman09/26 19:55
03
Re: [閒聊] 每日LeetCode
Marginalman09/27 23:40
25
Re: [閒聊] 每日LeetCode
Marginalman09/27 23:48
22
Re: [閒聊] 每日LeetCode
Marginalman09/28 10:06
35
Re: [閒聊] 每日LeetCode
Marginalman09/28 19:00
45
Re: [閒聊] 每日LeetCode
Marginalman09/29 10:22
36
Re: [閒聊] 每日LeetCode
Marginalman09/29 10:45
04
Re: [閒聊] 每日LeetCode
Marginalman09/29 23:33
33
Re: [閒聊] 每日LeetCode
Marginalman10/01 15:21
23
Re: [閒聊] 每日LeetCode
Marginalman10/01 23:23
38
Re: [閒聊] 每日LeetCode
Marginalman10/02 00:38
22
Re: [閒聊] 每日LeetCode
Marginalman10/02 09:00
45
Re: [閒聊] 每日LeetCode
Marginalman10/02 17:01
57
Re: [閒聊] 每日LeetCode
Marginalman10/03 09:12
44
Re: [閒聊] 每日LeetCode
Marginalman10/03 09:37
00
Re: [閒聊] 每日LeetCode
Marginalman10/03 11:25
56
Re: [閒聊] 每日LeetCode
Marginalman10/03 11:26
33
Re: [閒聊] 每日LeetCode
Marginalman10/04 09:52
55
Re: [閒聊] 每日LeetCode
Marginalman10/05 09:25
45
Re: [閒聊] 每日LeetCode
Marginalman10/05 09:40
46
Re: [閒聊] 每日LeetCode
Marginalman10/06 10:18
08
Re: [閒聊] 每日LeetCode
Marginalman10/06 10:27
13
Re: [閒聊] 每日LeetCode
Marginalman10/06 10:53
03
Re: [閒聊] 每日LeetCode
Marginalman10/06 15:02
25
Re: [閒聊] 每日LeetCode
Marginalman10/07 12:06
14
Re: [閒聊] 每日LeetCode
Marginalman10/07 19:36
33
Re: [閒聊] 每日LeetCode
Marginalman10/08 12:37
04
Re: [閒聊] 每日LeetCode
Marginalman10/08 13:02
24
Re: [閒聊] 每日LeetCode
Marginalman10/08 14:13
11
Re: [閒聊] 每日LeetCode
Marginalman10/08 16:09
22
Re: [閒聊] 每日LeetCode
Marginalman10/09 14:11
12
Re: [閒聊] 每日LeetCode
Marginalman10/10 14:38
22
Re: [閒聊] 每日LeetCode
Marginalman10/11 11:21
23
Re: [閒聊] 每日LeetCode
Marginalman10/12 10:06
610
Re: [閒聊] 每日LeetCode
Marginalman10/13 09:12
46
Re: [閒聊] 每日LeetCode
Marginalman10/13 12:17
67
Re: [閒聊] 每日LeetCode
Marginalman10/14 16:24
33
Re: [閒聊] 每日LeetCode
Marginalman10/15 18:59
47
Re: [閒聊] 每日LeetCode
Marginalman10/16 16:24
22
Re: [閒聊] 每日LeetCode
Marginalman10/17 09:42
23
Re: [閒聊] 每日LeetCode
Marginalman10/18 15:24
12
Re: [閒聊] 每日LeetCode
Marginalman10/18 16:37
23
Re: [閒聊] 每日LeetCode
Marginalman10/18 16:50
01
Re: [閒聊] 每日LeetCode
Marginalman10/19 09:45
13
Re: [閒聊] 每日LeetCode
Marginalman10/19 11:07
34
Re: [閒聊] 每日LeetCode
Marginalman10/20 09:21
66
Re: [閒聊] 每日LeetCode
Marginalman10/21 02:46
12
Re: [閒聊] 每日LeetCode
Marginalman10/21 09:12
34
Re: [閒聊] 每日LeetCode
Marginalman10/22 15:36
21 則留言
oinishere 作者的近期文章
lol高端進來一下
小c: 法師對線因為基傷的關係 前面很難有什麼差別 通常都是公式對線 要不就是搶線權 要不就是運營四波回推 補水滴戒指TP 5等開始有3級主力技能更容易洗線 然後洗線掛機 這是甚麼ㄚ 這是去哪裡學的 我會去偷看別人玩龍獸rp 可是還是看不懂
推
→
推
→
→
→
推
→
→
→
→
→
→
→
→
→
→
→
推
→
→