[LeetCode] 38. Count and Say

轉自LeetCode

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.

<Solution>

這邊再多看一個 output ，會比較知道說什麼

n = 6，"312211"

可以知道，就是去看同樣的字元有幾個，然後把計數加該字元放到下一個string

code 如下

C++

	class Solution {
	public:
	string countAndSay(int n) {
	if(n <= 0) {
	return "";
	}
	else if(n == 1) {
	return "1";
	}
	vector<string> ans(1,"1");
	int num = n - 1;
	while(num--) {
	string prvS = ans.back();
	string tmpS = "";
	for(int i = 0; i < prvS.length(); i++) {
	char ch = prvS[i];
	int cnt = 1;
	//> find the repeat count of the char
	while((i+1) < prvS.length() && prvS[i+1] == ch) {
	++cnt;
	++i;
	}
	//> create string for ans
	tmpS.push_back('0' + cnt);
	tmpS.push_back(ch);
	}
	ans.push_back(tmpS);
	}
	return ans[n-1];
	}
	};

view raw countAndSay.cpp hosted with ❤ by GitHub

Java

	class Solution {
	public String countAndSay(int n) {
	if (n <= 0) {
	return "1";
	}
	StringBuilder sb = new StringBuilder();
	ArrayList<String> table = new ArrayList<>();
	table.add("1");
	char[] chars;
	int anchor, limit;
	for(int i = 1; i < n; i++) {
	chars = table.get(i-1).toCharArray();
	limit = chars.length - 1;
	anchor = 0;
	sb.setLength(0);
	for(int j = 0; j < chars.length; j++) {
	if(j == limit || chars[j] != chars[j+1]) {
	sb.append("" + (j - anchor + 1) + chars[j]);
	anchor = j + 1;
	}
	}
	table.add(sb.toString());
	}
	return table.get(n-1);
	}
	}

view raw countAndSay.java hosted with ❤ by GitHub

Kotlin

	class Solution {
	fun countAndSay(n: Int): String {
	val ans = mutableListOf<String>()
	ans.add("1")
	var str = ""
	var anchor = 0
	var sb = StringBuilder()
	for(i in 2..n) {
	str = ans.last()
	anchor = 0
	sb.clear()
	for(j in str.indices) {
	if (j == str.lastIndex || str[j] != str[j+1]) {
	sb.append(j-anchor+1).append(str[j])
	anchor = j + 1
	}
	}
	ans.add(sb.toString())
	}
	return ans.last()
	}
	}

view raw count_and_say.kt hosted with ❤ by GitHub