299. 猜數(shù)字游戲

解題思路

對于這道題而言喂链，最容易想到的就是使用哈希表存儲是否出現(xiàn)過零酪。
此題有兩點:

• 當(dāng)數(shù)字與位置都相同時，應(yīng)該使bulls值加一窘茁。即

if secret[i] == guess[i] {
            bulls++
}

• 當(dāng)數(shù)字相同位置不同時躯畴，應(yīng)該使cows加一爵政。一開始我的想法是先遍歷一個列表及汉，存儲里面的值出現(xiàn)的個數(shù)，再遍歷第二個列表找到每當(dāng)出現(xiàn)相同的值就使cows加一焕阿，最后再減去bulls的值即可(即重復(fù)的值)咪啡。

    tmp := make(map[byte]int,len(secret))
    bulls,cows := 0,0
    for i := 0; i < len(secret);i++{
        if secret[i] == guess[i]{
            bulls++
        }
        tmp[secret[i]-'0']++
    }
    
    for i := 0; i < len(guess); i++{
        if tmp[guess[i]-'0'] != 0{
            cows++
            tmp[guess[i]-'0']--
        }
    }

看了一眼解答，方法為設(shè)兩個map暮屡，當(dāng)碰到不同時兩個map分別相加撤摸，最后加上最小值。

func getHint(secret, guess string) string {
    bulls := 0
    var cntS, cntG [10]int
    for i := range secret {
        if secret[i] == guess[i] {
            bulls++
        } else {
            cntS[secret[i]-'0']++
            cntG[guess[i]-'0']++
        }
    }
    cows := 0
    for i := 0; i < 10; i++ {
        cows += min(cntS[i], cntG[i]) //很巧妙褒纲，算是空間換時間
    }
    return fmt.Sprintf("%dA%dB", bulls, cows)
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

100251. 數(shù)組中的最短非公共子字符串

解題思路

在一開始首先想到動態(tài)規(guī)劃准夷，但并沒有找到遞推就放棄了，然后又想到dfs但dfs在面對一個string列表時沒有寫過也放棄了莺掠，直接選擇暴力解法衫嵌。

直接對每個string進(jìn)行遍歷，每個string都取出子字符串對整個arr進(jìn)行遍歷彻秆，若存在則跳過渐扮，走完所有后將最短的字符串放入答案论悴。

• 首先解決如何取出子字符串掖棉。

answer := make([]string, n)
    

    for i, s := range arr {
        substrings := make(map[string]bool)
        for j := 0; j < len(s); j++ {
            for k := j + 1; k <= len(s); k++ {
                substrings[s[j:k]] = true
            }
        }

• 第二步將子字符串與arr中所有string進(jìn)行匹配墓律，若有則刪除，無則加入答案幔亥。

for _, str := range arr {
            if str == s {
                continue
            }
            for sub := range substrings {
                if len(str) >= len(sub) && strings.Contains(str, sub) {
                    delete(substrings, sub)
                }
            }
        }

        shortest := ""
        for sub := range substrings {
            if shortest == "" || len(sub) < len(shortest) || (len(sub) == len(shortest) && sub < shortest) {
                shortest = sub
            }
        }

        answer[i] = shortest

• 最后這個代碼會在出現(xiàn)兩個相同字串時出錯

  
  
  
  

  于是進(jìn)行去重處理耻讽。

 tmp := make(map[string]int)
    result := make([]string, len(answer))
    for _,x := range answer{
        tmp[x]++
    }
    for i,x := range answer{
        if tmp[x] > 1{
            result[i] = ""
        }else{
            result[i] = x
        }
    }
    return result

3020. 子集中元素的最大數(shù)量

解題思路

• 先記錄下每個元素出現(xiàn)的次數(shù)，可以知道若滿足條件帕棉，那么該元素平方一定是大于1的针肥。

func maximumLength(nums []int) int {
    cnt := map[int]int{}

    for _,x := range nums{
        cnt[x]++
    }

    ans := cnt[1]-1 | 1 //對于x=1進(jìn)行特判
    delete(cnt,1) 

    for x := range cnt{
        res := 0
        for ;cnt[x] > 1; x *= x{
            res += 2
        }
        res += cnt[x]
        ans = max(ans,res-1|1) //保證一定是奇數(shù)。
    }

    return ans
}