golang 外观数列

题面

给定一个正整数 n（1 ≤ n ≤ 30），输出外观数列的第 n 项。

注意：整数序列中的每一项将表示为一个字符串。

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：

1. 1 2. 11 3. 21 4. 1211 5. 111221

作者：力扣 (LeetCode) 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnpvdm/ 来源：力扣（LeetCode）

分析

双指针 i,j从待考察字符串首位出发计算连续字符字频数，并记录下来，同时载入该字符

迭代

php大法

function countAndSay($n) { if($n < 1) { return ""; } $s = "1"; for($k=1;$k<$n;$k++){ $arr =[]; for($i=0,$j=0;$i<strlen($s);$i++){ if ($s[$i]!=$s[$j]){ array_push($arr,$i-$j, $s[$j]); $j=$i; } if($i==strlen($s)-1){ array_push($arr,$i-$j+1, $s[$i]); } } $s = implode($arr); } return $s; }

递归

golang类型转换，字符串切片

import "strconv" import "strings" func countAndSay(n int) string { if n < 1 { return "" } return strings.Join(convert(n),"") } func convert(n int) []string { if n==1 { return []string{"1"} } level:= convert(n-1) l,i,j :=[]string{},0,0 for i<len(level){ if level[i]!=level[j] { l = append(l,strconv.Itoa(i-j)) l = append(l,level[j]) j = i } if i+1 == len(level){ l = append(l,strconv.Itoa(i-j+1)) l = append(l,level[i]) } i++ } return l }

非递归go版

import "strings" import "strconv" func countAndSay( n int ) string { if n < 1{ return "" } n-- rs :=[]int{1} for ;n>0;n--{ l:=make([]int,0) for i,k:=0,0;i<len(rs);i++{ if i==0 || rs[i]!=rs[i-1]{ if i>0{ l = append(l,i-k) l = append(l,rs[k]) } k=i } if i==len(rs)-1{ l=append(l,i-k+1) l=append(l,rs[k]) } } rs = l } var b strings.Builder for _,v := range rs { b.WriteString(strconv.Itoa(v)) } return b.String() }

终极版

类似于单链表中的dummy 节点，rs +="$" 故意为之，处理合理的数据越界，即减少代码量

import "bytes" import "strconv" func countAndSay( n int ) string { rs := "1" var buf bytes.Buffer for ;n>1;n--{ rs +="$" for k,i:=0,1;i< len(rs);i++{ if rs[i-1]!=rs[i]{ buf.WriteString(strconv.Itoa(i-k)) buf.WriteByte(rs[i-1]) k=i } } rs = buf.String() buf.Reset() } return rs }