Re: [閒聊] 每日leetcode

[JIWP (神楽めあ的錢包)]

我要吐了，狗屎題目

想了好久，難怪我上不了姑姑魯

1915. Number of Wonderful Substrings

有一個字串由'a'~'j'組成

請回傳wonderful substring的數量

如果該字串裡只有一個字元的數量是奇數那就是wonderful substring

思路:

有10種字元，而且只要紀錄字元數量是奇數還是偶數

那就用10個bit分別去紀錄，'a'是第0個字元以此類推

XOR 1<<(s[i]-'a')

並且用hashmap去紀錄到目前為止出現過的組合

如何找符合條件的子字串?

假設index 0~i的字元組合為 111000110

那就要去找到index i之前有沒有出現過一樣的組合

或是跟該字元組合剛好差1個bit : 111000110 XOR 011000110 = 1000000000

這樣就能找出來了

GOLANG CODE:

func wonderfulSubstrings(word string) int64 {
    table:=[1024]int{}
    table[0]=1 //字元組合剛好全部是偶數
    val:=0
    res:=0
    for i:=0;i<len(word);i++{
        val^= (1<<(word[i]-'a'))
        res+=table[val]
        for j:=0;j<10;j++{
            idx:= val ^ (1<<j)
            res+=table[idx]
        }
        table[val]++
    }
    return int64(res)
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.11.31 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1714473278.A.3ED.html
推 wu10200512: 這是為了104啟動做的準備嗎
我每日都會解阿，已經150了
推 sustainer123: 大師
※ 編輯: JIWP (42.72.11.31 臺灣), 04/30/2024 18:37:24
→ sustainer123: 連續150?
推 wu10200512: 你好扯 連續150天
→ wu10200512: 我總共都沒150題
→ sustainer123: 我才連30而已 哭啊
→ sustainer123: 我總共好像快200 不過hard很少
→ JIWP: 對啊連續150
→ JIWP: 不過我很爛
推 oinishere: 小雞雞大師