golang 外观数列

2024-06-12 15:32

文章标签 golang 数列外观

本文主要是介绍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,0for 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.Builderfor _,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.Bufferfor ;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
}