Re: [閒聊] 每日leetcode

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

726. Number of Atoms

給一串字串formula代表一個化學公式

每個原子都是大寫開頭的

原子後面會接它的個數 EX:H2

或是有括號 EX: (H2Mg3)2

接的數字會大於1

請根據formula回傳每個原子的數量

用字串來表示

格式為:原子1數量原子2數量....

並且按照字母來排序

思路:

從formula最後一個元素開始處理到第一個元素

mul紀錄括號後面的數字 EX:(HO)2 這個2

並用stack來記錄mul

atomnum來記錄原子的數目 EX:H2 這個2

建立一個hash table紀錄每個元素出現的次數

接著會分4種情況

(1) ')' : 直接略過

(2) '1'~'9' :

一直找到非數字出現，並記錄這個數字:num

接著看下一個元素是不是')'

是的話mul*num，並且記錄到stack

不是的話那就表示遇到原子了

就把atomnum=num

(3) '(' :

如果stack裡有東西，把stack的最後一個數字pop出來，並且mul/=該數字

(4) 英文字母:

一直處理到大寫出來，可以得到原子的名字

原子的數量=mul*atomnum，加到hash table裡面

並把atomnum=1

最後就按照字母順序去排列

就可以得到答案了

golang code:

type Atom struct {
        name string
        num  int
}

func countOfAtoms(formula string) string {
        stack := make([]int, 0)
        i, mul, AtomNum := len(formula)-1, 1, 1
        rec := make(map[string]int)
        atom := []Atom{}
        var res strings.Builder
        for i > -1 {
                if formula[i] >= '0' && formula[i] <= '9' {
                        tmp := i
                        for formula[tmp] >= '0' && formula[tmp] <= '9' {
                                tmp--
                        }
                        num, _ := strconv.Atoi(formula[tmp+1 : i+1])
                        if formula[tmp] == ')' {
                                stack = append(stack, num)
                                mul *= num
                        } else {
                                AtomNum = num
                        }
                        i = tmp
                } else if formula[i] == '(' {
                        if len(stack) > 0 {
                                mul /= stack[len(stack)-1]
                                stack = stack[:len(stack)-1]
                        }
                        i--
                } else if formula[i] == ')' {
                        i--
                } else {
                        tmp := i
                        for formula[i] >= 'a' && formula[i] <= 'z' {
                                i--
                        }
                        rec[string(formula[i:tmp+1])] += mul * AtomNum
                        AtomNum = 1
                        i--
                }
        }
        for key, val := range rec {
                atom = append(atom, Atom{key, val})
        }
        slices.SortFunc(atom, func(i, j Atom) int {
                if i.name < j.name {
                        return -1
                }
                return 1
        })
        for _, val := range atom {
                res.WriteString(val.name)
                if val.num > 1 {
                        res.WriteString(strconv.Itoa(val.num))
                }

        }
        return res.String()
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.212.76 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1720973690.A.FF2.html
推 oin1104: 大師
推 DJYOMIYAHINA: 媽的白癡題目==