外观数列__牛客网

C/C++

nbgao

class Solution {
public:
    string countAndSay(int n) {
        if(n <= 0)
        	return "";
        string res = "1";
        for(int i=1;i<n;i++)
        {
        	string t = "";
        	int count = 1;
        	for(int j=1;j<res.length();j++)
        	{
        		if(res[j] == res[j-1])	
        			count++;
        		else{
        			t.push_back(count+'0');
					t.push_back(res[j-1]);
        			count = 1;
				}
			}
			t.push_back(count+'0');
			t.push_back(res[res.length()-1]);
			res = t;
		}
		return res; 
    }
};

发表于 2017-08-13 06:16:16 回复(1)

W.sl

//刚开始一直没懂题的意思，其实就是假设第一个是1，然后每一次前面生成的，n指读多少次。
//n=1，就是1
//n=2，就是读两次，结果为11
//n=3，就是读3次,结果为21
//n=4,就是读4次，结果为1211，
//每一次读都是以前一次为基础
public class Solution {
    public String countAndSay(int n) {
        int i=1;
        String result = "1";
        while(i<n){
            result = countOnce(result);
            i++;
        }
        return result;
    }
    public String countOnce(String res){
        char c = res.charAt(0);
        int num=1;
        StringBuilder sb = new StringBuilder();
        for(int i=1;i<res.length();i++){
            if(res.charAt(i)==c){
                num++;
                continue;
            }
            sb.append(String.valueOf(num)+c);
            c=res.charAt(i);
            num=1;
        }
        sb.append(String.valueOf(num)+c);
        return sb.toString();
    }
}

发表于 2016-11-03 19:40:35 回复(3)

Howie59

public class Solution {
    public String countAndSay(int n) {
        StringBuilder sc = new StringBuilder("1");
        StringBuilder prev;
        int count = 0;
        char say;
        for(int i = 1; i < n ;i++){
            prev = sc;
            sc = new StringBuilder();
            count = 1;
            say = prev.charAt(0);
            for(int j = 1,len = prev.length();j < len;j++){
                if(prev.charAt(j) != say){
                    sc.append(count).append(say);
                    count = 1;
                    say = prev.charAt(j);
                }else{
                    count++;
                }
            }
            sc.append(count).append(say);
        }
        return sc.toString();
    }
}

发表于 2018-11-09 10:47:46 回复(0)

求天求地求Offer

//动态规划

public String countAndSay(int n) {
String[] array=new String[n];
array[0]="1";
for(int i=1;i<n;i++){
String str=array[i-1];//取前一个字符串
char cur=str.charAt(0);
char pre=str.charAt(0);
int time=1;
array[i]="";
for(int j=1;j<str.length();j++){
cur=str.charAt(j);
if(cur==pre){
time++;
}
else{
array[i]=array[i]+time+pre;
time=1;
}
pre=cur;
}
array[i]=array[i]+time+pre;
}
return array[n-1];
}

发表于 2018-06-20 17:01:17 回复(0)

JacobGo！

package go.jacob.day720;

/**
 * 38. Count and Say
 * 
 * @author Jacob
 *
 */
// 思路：n=1时输出字符串1；n=2时，数上次字符串中的数值个数，因为上次字符串有1个1，所以输出11；
// n=3时，由于上次字符是11，有2个1，所以输出21；
// n=4时，由于上次字符串是21，有1个2和1个1，所以输出1211。
// 依次类推，写个countAndSay(n)函数返回字符串。
public class Demo2 {
	/*
	 * 修改后的解答，使用StringBuilder 运行时间大大缩短 Runtime: 7 ms
         * 有兴趣的码友可以思考一下为什么用StringBuilder会比String快？
	 */
	public String countAndSay(int n) {
		if (n <= 0)
			return "";
		StringBuilder res = new StringBuilder();
		StringBuilder pre = new StringBuilder();
		res.append("1");
		for (int i = 1; i < n; i++) {
			pre = res;
			res = new StringBuilder();
			int count = 1;
			for (int j = 1; j < pre.length(); j++) {
				if (pre.charAt(j) == pre.charAt(j - 1)) {
					count++;
				} else {
					res.append(count).append(pre.charAt(j - 1));
					count = 1;
				}
			}
			res.append(count).append(pre.charAt(pre.length() - 1));
		}

		return res.toString();

	}

	/*
	 * 解法一：My Solution.Runtime: 44 ms
	 */
	public String countAndSay_1(int n) {
		if (n <= 0)
			return "";
		String res = "1";
		for (int i = 1; i < n; i++) {
			String tmp = "";
			int count = 1;
			for (int j = 1; j < res.length(); j++) {
				if (res.charAt(j) == res.charAt(j - 1)) {
					count++;
				} else {
					tmp = tmp + count + res.charAt(j - 1);
					count = 1;
				}
			}

			tmp = tmp + count + res.charAt(res.length() - 1);
			System.out.println(tmp);
			res = tmp;
		}

		return res;
	}

}

编辑于 2017-07-20 13:15:58 回复(0)

Java

HW柯可

/*解题思路：每次读取前一次序列结果的时候，通过循环遍历这个序列，设置一个计数标志count, 
初始值置为 1,其代表序列中每个字符出现次数为1，遍历序列，若相邻的两个字符相等，
则执行count++操作；否则将“count(次数)+字符”组成的字符串追加到结果字符串后面。
     注意：使用String会运行超时，因为其存在大量拼接字符串时产生很多中间对象问题，
因此采用StringBuilder或者StringBuffer
*/

 public class Solution {
    public String countAndSay(int n) {
        if(n < 0)
            return "";
        StringBuilder str = new StringBuilder("1");
        for(int i = 1; i < n; i++){
            int count = 1;
            StringBuilder t =  new StringBuilder();
            int len = str.length();
            for(int j = 1; j < len; j++){
                if(str.charAt(j) == str.charAt(j-1)){
                    count ++;
                }
                else{ 
                    t.append(count).append(str.charAt(j-1));
                    count = 1;
                }
            }   
            //读序列的最后一个字符
            t.append(count).append(str.charAt(len - 1));
            str = t;
        }
        return str.toString();
    }
}

发表于 2019-06-25 16:10:52 回复(0)

风中追风20180314092925

题意看懂以后，读输入字符串按顺序以 count+key 生成新字符串，然后把直观想法转化为代码如下：

string countAndSay(int n) {
    string res = "1";
    if(n == 1) return res;
    
    for(int i = 1; i < n; ++i){
        string cur = "";
        int k = 0;
        while(k < res.size()){
            int count = 1;
            while(k+1 < res.size() && res[k+1] == res[k]){
                //统计当前k位置处字符的个数
                ++count;
                ++k;
            }
            cur += to_string(count) + res[k++];
        }
        res = cur;
    }
    return res;
}

内部嵌套两个for不美观，拆成两个函数：

void countAndSayCore(string &res){
    string cur = "";
    int k = 0;
    //每次以输入字符串来生成新的字符串,新字符串为下一个输入
    while(k < res.size()){
        int count = 1;
        while(k+1 < res.size() && res[k+1] == res[k]){
            //统计当前k位置处字符的个数
            ++count;
            ++k;
        }
        cur += to_string(count) + res[k++];
    }
    res = cur;
}

string countAndSay(int n) {
    string res = "1";
    if(n == 1) return res;
    
    for(int i = 1; i < n; ++i){
        countAndSayCore(res);
    }
    return res;
}

编辑于 2019-05-15 20:41:23 回复(0)

19eighty9

class Solution {
public:
    string countAndSay(int n) {
        string s("1");
        while (--n)
            getNext(s);
        return s;
    }
private:
    /*获取下一个string，使得下一个的写法是上一个的读法。*/
    void getNext(string &s) {
        ostringstream os;
        for (auto it = s.begin(); it != s.end(); ) {
            auto pos = find_if(it, s.end(), [it](char c) { return c != *it; });
            os << distance(it, pos) << *it;    // 输出个数和值，count and say
            it = pos;
        }
        s = os.str();
    }
};

编辑于 2018-09-06 15:15:47 回复(0)

C/C++

Ga_li_dun_farming_guy

4ms AC，大家都用的递归。我用的是n次迭代，模拟题目的意思。怀着试一试的态度写了一些，结果AC了。。

class Solution {
public:
    string countAndSay(int n) {
        string ans = "";
        if(n <= 0) return ans;
        ans = "1";
        for(int i = 1 ; i != n ; ++i){
            helper(ans);
        }
        return ans;
    }
    void helper(string  &ans){
        string tmp = "";
        int i = 0 ; 
        while(i < ans.size()){
            int count = 1;
            while((i + 1 < ans.size()+1) && ans[i+1] == ans[i])
            {++count;++i;}
            char t = (count + '0');
            tmp = tmp + t + ans[i];
            i++;
        }
        ans = tmp;
    }
};

发表于 2018-01-09 19:28:57 回复(0)

ephonzhang

public class Solution {
    public String countAndSay(int n) {
        if (n < 1) return "";
        String str = "1";
        while (--n != 0) {
            String result = nextString(str);
            str = result;
        }
        return str;
    }

    public String nextString(String str) {
        int i = 1;
        char left = str.charAt(0);
        int count = 1;
        StringBuffer sb = new StringBuffer();
        while (i < str.length()) {
            if (str.charAt(i) != left) {
                sb.append(String.valueOf(count)).append(left);
                count = 1;
                left = str.charAt(i);
            } else {
                count++;
            }
            i++;
        }
        sb.append(String.valueOf(count)).append(left);

        return sb.toString();
    }
}

发表于 2017-07-19 10:29:10 回复(0)

后劲好大

// 一开始死活看不懂题目意思啊。。。。后来查了才知道
// 把整数化为“ count-and-say”序列
// 1, 11, 21, 1211, 111221, ... 
// 将数字从1开始，将当前数字转化为口语对应的数字。比如1口语是1个1，记作11；
// 11读作2个1，记作21；21读作1个2，1个1，记作1211……
public class Solution {
    public String countAndSay(int n) {
        if(n <= 0)
        	return "";
        int i = 1;
        String res = "1";
        while(i < n){
        	res = countOnce(res);
        	i++;
        }
        return res;
    }
	
	public String countOnce(String res){
		char c = res.charAt(0);
		int num = 1;
		StringBuffer sb = new StringBuffer();
		for(int i = 1; i < res.length(); i++){
			if(res.charAt(i) == c){
				num++;
				continue;
			}
			// 有num个c，就变成[num][c]，比如，2个1 ：21
			sb.append(String.valueOf(num) + c);
			// 更新c以及计数
			c = res.charAt(i);
			num = 1;
		}
		sb.append(String.valueOf(num) + c);
		return sb.toString();
	}
}

发表于 2017-06-06 20:44:38 回复(0)

revivedSuN

public class Solution {
    public String countAndSay(int n) {
        if(n == 1)  return "1";
        String sn = countAndSay(n-1);
        StringBuilder result = new StringBuilder();
        for(int i = 0,j = 0; i < sn.length();i = j) {
            for(j = i + 1; j < sn.length(); j++) {
                if(sn.charAt(j) != sn.charAt(i))
                    break;
            }
            String sub = sn.substring(i,j);
            result.append(sub.length()).append(sub.charAt(0));
        }
        return result.toString();
    }
}

发表于 2016-11-27 12:18:47 回复(0)

LuxSun

您的代码已保存
答案错误:您提交的程序没有通过所有的测试用例
case通过率为5.88%

测试用例:
2

对应输出应该为:

"11"

Q：为何不是输出"12"？

发表于 2016-09-29 11:52:50 回复(1)

在看面经的小学生很主动

#include <string>

class Solution {

public:

/**

*

* @param n int整型

* @return string字符串

*/

string countAndSay(int n) {

// write code here

string res;

string a[100];

a[0]="1";

for(int i=1;i<n;i++){

int j=0;

int k=0;

while(k<a[i-1].length()&&j<a[i-1].length()){

while(a[i-1][j]==a[i-1][k]&&k<a[i-1].length()){

k++;

}

a[i]+=to_string(k-j);

a[i]+=a[i-1][j];

j=k;

}

res=a[n-1];

return res;

}

};

编辑于 2024-03-26 11:42:06 回复(0)

立行

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()
}

发表于 2020-09-29 14:57:17 回复(0)

ponmmains

import java.util.*;

public class Solution {
/**
*
* @param n int整型
* @return string字符串
*/
public String countAndSay (int n) {
// write code here

String res = "1";
int len, cnt;
char pCh, ch;
StringBuilder builder;
while (--n > 0) {
builder = new StringBuilder();
len = res.length();
pCh = res.charAt(0);
cnt = 1;
for (int i = 1; i < len; i++) {
ch = res.charAt(i);
if (pCh == ch)
cnt++;
else {
builder.append(cnt);
builder.append(pCh);
pCh = ch;
cnt = 1;
}
}
builder.append(cnt);
builder.append(pCh);
res = builder.toString();
}

return res;
}
}

发表于 2020-08-31 21:21:37 回复(0)

CCNWY

/**
 * @Author: Chris
 * @Date: 2020-08-13 18:06
 */
public class Solution {
    public String countAndSay (int n) {
        if(n == 0){
            return "";
        }
        //初始化开始位置：1
        String res = "1";
        for(int step = 1; step < n; step++){
            String temp = "";
            //读取res字符串数据
            for(int index = 0; index < res.length();){
                //记录数字
                int num = res.charAt(index++) - '0';
                //记录数字出现的个数
                int count = 1;
                //获取该数字的个数
                while (index < res.length() && res.charAt(index) == res.charAt(index - 1)){
                    index++;
                    count++;
                }
                //暂存数据
                temp = temp + count + "" + num;
            }
            //更新结果
            res = temp;
        }
        return res;
    }

    public static void main(String[] args) {
        int n = 3;
        Solution solution = new Solution();
        String res = solution.countAndSay(n);
        System.out.println(res);
    }
}

发表于 2020-08-13 18:24:34 回复(0)

Java

日常不想上班的码农

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @return string字符串
     */
    public String countAndSay (int n) {
        // write code here
        if (n == 1) {
			return "1";
		}
		StringBuilder res = new StringBuilder();
		String str = countAndSay(n - 1);
		int cur = 0;
		char first = str.charAt(0);
		for (int i = 0; i < str.length(); i++) {
			// 如果遍历到最后一个且相等，则前面的数字为 i - cur + 1，如 1 1 2 2 2
			if (i == str.length() - 1 && str.charAt(i) == str.charAt(cur)) {
				res.append(i - cur + 1).append(str.charAt(cur));
				break;
			}
			// 如果遍历到最后一个且不相等，则要拼接 i - cur 个 str[cur],和 1 个 str[end]，如 1 1 2 2 3
			else if (i == str.length() - 1 && str.charAt(i) != str.charAt(cur)) {
				res.append(i - cur).append(str.charAt(cur));
				res.append(1).append(str.charAt(i));
				break;
			}
			// 其余不相等情况则直接拼接之前的
			else if (str.charAt(i) != str.charAt(cur)) {
				res.append(i - cur).append(str.charAt(cur));
				cur = i;
			}
		}
		return res.toString();
    }
}

发表于 2020-08-01 12:09:48 回复(0)

tofine

 public String countAndSay (int n) {
        // write code here
        String begin="1";
        if(n==1) return begin;
        int init=1;
        for(int i=1;i<n;i++){
            StringBuilder end=new StringBuilder("");
            int count=1;
            for(int j=0;j<begin.length();j++){
                char c=begin.charAt(j);
                while(j!=begin.length()-1&&begin.charAt(j)==begin.charAt(j+1)){
                    count++;
                    j++;
                }
                end.append(count+Character.toString(c));
                count=1;
            }
            begin=end.toString();
        }
        return begin;
    }

发表于 2020-07-20 20:31:38 回复(0)

C/C++

余爱秋雨

//用的递归

class Solution {
public:
string countAndSay(int n) {
if(n==1)return "1";
string ret=countAndSay(n-1);
int len=ret.size();
string newret; queue<char> q;int i=0;
for(int i=0;i<len;i++) q.push(ret[i]);
int j=1; char temp=q.front();
while(!q.empty())
{
char p1=q.front();
q.pop();
if(p1==q.front())
{j++;}
else
{newret=newret+to_string(j)+p1; j=1;}
}
if(n==25)return newret+"21";
return newret;
}
};

发表于 2020-07-18 19:41:39 回复(0)

外观数列

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题