diff options
-rw-r--r-- | count_and_say.c | 68 | ||||
-rw-r--r-- | count_and_say.py | 35 |
2 files changed, 58 insertions, 45 deletions
diff --git a/count_and_say.c b/count_and_say.c index 8d186fc..95726cd 100644 --- a/count_and_say.c +++ b/count_and_say.c @@ -1,7 +1,5 @@ // 38. Count and Say -#include <stdio.h> -#include <stdlib.h> -#include <string.h> +#include "leetcode.h" /* * the count-and-say sequence is a sequence of digit strings defined by the @@ -16,53 +14,33 @@ * term of the count and say sequence. */ -char *int_to_char(int n) { - char *res = malloc(11); - res[10] = '\0'; - int idx = 9; - while (n) { - res[idx] = '0' + n % 10; - n /= 10; - idx--; - } - return &res[idx + 1]; -} - char *countAndSay(int n) { - char *curr = malloc(5000), *post = malloc(5000); - curr[0] = '1'; - curr[1] = '\0'; if (n == 1) - return curr; - for (int i = 2; i <= n; i++) { - int curr_len = strlen(curr), idx = 0, cnt = 1, pos = 0; - char *tmp; - for (int j = 1; j < curr_len; j++) { - if (curr[j] == curr[j - 1]) - cnt++; - else { - tmp = int_to_char(cnt); - strncpy(&post[pos], tmp, strlen(tmp)); - pos += strlen(tmp); - post[pos] = curr[j - 1]; - pos++; - cnt = 1; - } + return "1"; + char *s = countAndSay(n - 1), curr = *s; + char *ans = (char *)malloc(4463 * sizeof(char)); + int m = strlen(s), idx = 0, cnt = 1; + for (int i = 1; i < m; i++) { + char c = *(s + i); + if (c == curr) + cnt++; + else { + *(ans + idx++) = ('0' + cnt); + *(ans + idx++) = curr; + curr = c; + cnt = 1; } - tmp = int_to_char(cnt); - strncpy(&post[pos], tmp, strlen(tmp)); - pos += strlen(tmp); - post[pos] = curr[curr_len - 1]; - pos++; - post[pos] = '\0'; - tmp = curr; - curr = post; - post = tmp; } - return curr; + *(ans + idx++) = ('0' + cnt); + *(ans + idx++) = curr; + *(ans + idx) = '\0'; + return ans; } int main() { - printf("%s\n", countAndSay(1)); // expect: 1 - printf("%s\n", countAndSay(4)); // expect: 1211 + char *cas1 = countAndSay(4), *cas2 = countAndSay(1); + printf("%s\n", cas1); // expect: 1211 + printf("%s\n", cas2); // expect: 1 + free(cas1); + free(cas2); } diff --git a/count_and_say.py b/count_and_say.py new file mode 100644 index 0000000..e8521b3 --- /dev/null +++ b/count_and_say.py @@ -0,0 +1,35 @@ +# 38. Count and Say +from re import findall + +""" +the count-and-say sequence is a sequence of digit strings defined by the +recursive formula: +- countAndSay(1) = "1" +- countAndSay(n) is the way you would "say" the digit string from +'countAndSay(n - 1)', which is then converted into a different digit string +to determine how you "say" a digit string, split it into minimal number of +substrings such that each substring contains exactly one unique digit. then +for each substring, say the number of digits, then say the digit, finally, +concatenate every said digit. given a positive integer 'n', return the n'th +term of the count and say sequence. +""" + + +class Solution(object): + def countAndSay(self, n): + """ + :type n: int + :rtype: str + """ + ans = "1" + for _ in range(n - 1): + ans = "".join( + str(len(group)) + digit for group, digit in findall(r"((.)\2*)", ans) + ) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.countAndSay(n=4)) + print(obj.countAndSay(n=1)) |