未分類

Count and Say

Go, LeetCode, String

Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, …

  • 1 is read off as “one 1” or 11.
  • 11 is read off as “two 1s” or 21.
  • 21 is read off as “one 2, then one 1” or 1211.

Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

提示 解題應用 額外的package
String 規律觀察 strconv

Default:

1
2
3
func countAndSay(n int) string {
}

解答思路:

這題最大的難度應該在於看懂題目，看懂了就會覺得沒什麼了，這裡需要你回傳一個序列第n個值，至於這個序列的開頭初始為1，細節規則如下:

  • 1: 表示 1 個 1 故結果為 11 (將此值往下帶入，後續以此類推)
  • 11: 表示 2 個 1 故結果為 21
  • 21: 表示 2 個 1 及 1 個 1 故結果為 1211

一開始沒看清楚要的是第n個值，所以在網站上直接將序列的結果丟到網站上跑測試資料來推估這題的意思，一連又丟了好幾個，等到發現時網站就一口氣吐了包含先送的測資結果，變成好幾個天文數字合在一起連著瀏覽器也當掉了。

程式碼解說:

因為這個序列的初始為”1”，一開始便以”1”為結果來做起始，因為要回傳的結果為字串，同時字串也方便我們去將數量與該數字做合併，所以就”1”就以字串來表示，不過這邊要注意的是因為序列第n個值也包含了”1”，所以在一開始的時候就要減1，接著進一個迴圈來判斷拿到的結果要往回帶入幾次，同時將存結果的值丟給另一變數後清空，因為接下來要存新的結果，而這個變數就先取出第一個值判斷是否與下一個值相同
以方便計算此數的總量

1
2
3
4
5
6
7
8
9
10
var str string
result := "1"
n--
for n > 0 {
	n--
	str = result
	result = ""
	tmp := string(str[0])
	count := 1
}

存取變數第一個值後，便能開始一一比對是否和下個值的數字相同，不一樣才把數量與該數字加入結果，count要用strconv的package去處理，不然會變成ascii的轉換，接著才重新計算數量與該數字，最後要注意如果到最後一個數字時，才剛重新計算就跳開回圈了，所以要再最後再處理一次結果

1
2
3
4
5
6
7
8
9
10
11
var vs string
for _, v := range str[1:] {
	vs = string(v)
	if tmp != vs {
		result = result + strconv.Itoa(count) + tmp
		count = 0
		tmp = vs
	}
	count++
}
result = result + strconv.Itoa(count) + tmp

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func countAndSay(n int) string {
	var vs string
	var str string
	result := "1"
	n--
	for n > 0 {
		n--
		str = result
		result = ""
		tmp := string(str[0])
		count := 1
		for _, v := range str[1:] {
			vs = string(v)
			if tmp != vs {
				result = result + strconv.Itoa(count) + tmp
				count = 0
				tmp = vs
			}
			count++
		}
		result = result + strconv.Itoa(count) + tmp
	}
	return result
}

總結:

Count and Say為從1開始的序列，序列第n項以上一個的結果值的 “數量” + “該數字” 合併並往下重覆執行上述規則。

分享到