LeetCode_Count_and_say

2017-01-08 留言

LeetCode count and say问题

这个问题，记得高中学习排列组合时候，有同学拿去问数学老师，说是排列组合问题，没想到被老师识破，哈哈哈。。。刚学编程时候想要实现下，但是那时候好弱，写不出来。

问题描述：

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.

其实这个问题就是简单的模拟。

Python实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#condig=utf-8
# https://leetcode.com/problems/count-and-say/
def get_num(start):
    index = 0
    count = 1
    length = len(start)
    temp_list = []
    while True:
        next_one = index + 1
        # 需要将最后一个数字和它的次数存到temp
        if next_one >= length:
            temp = str(count) + start[index]
            break
        else:
            # 计数次数，相同计数加一
            if start[index] == start[next_one]:
                count += 1
            # 不同将当前次数和数字存入temp，加入列表，重置计数
            else:
                temp = str(count) + start[index]
                temp_list.append(temp)
                count = 1
        index += 1
    # 将最后一个temp变量加入列表
    temp_list.append(temp)
    return ''.join(temp_list)
class Solution(object):
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        
        start = '1'
        for i in range(1, n):
            start = get_num(start)
        return start

C语言实现如下，就是再翻译一遍:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#define MAX_LEN 1024
char* next_num(char* num) {
  int count = 1;
  int index = 0, next_index = 0;
  int length = strlen(num);
  char *res = (char*)malloc(sizeof(char*) * (length*2));
  res[0] = '\0';
  char tmp_res[3];
  while (1) {
    next_index = index + 1;
    if (next_index >= length) {
      sprintf(tmp_res, "%d%c", count, num[index]);
      strcat(res, tmp_res);
      break;
    } else {
      if (num[index] == num[next_index]) {
        count++;
      } else {
        sprintf(tmp_res, "%d%c", count, num[index]);
        strcat(res, tmp_res);
        count = 1;
      }
    }
    index++;
  }
  return res;
}
char* countAndSay(int n) {
  char *res = (char*)malloc(sizeof(char*) * MAX_LEN);
  res[0] = '1';
  res[1] = '\0';
  int i;
  for (i = 1; i < n; i++) {
    res = next_num(res);
  }
  return res;
}

不过这样写，没有free掉malloc得到的内存，会出现内存泄漏的，所以，next_num中不使用malloc函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <string.h>
#include <stdio.h>
#define MAX_LEN 5000
void next_num(char* num, int length) {
  int count = 1;
  int index = 0, next_index = 0;
  char res[MAX_LEN];
  res[0] = '\0';
  char tmp_res[3];
  while (1) {
    next_index = index + 1;
    if (next_index == length) {
      sprintf(tmp_res, "%d%c", count, num[index]);
      strcat(res, tmp_res);
      break;
    } else {
      if (num[index] == num[next_index]) {
        count++;
      } else {
        sprintf(tmp_res, "%d%c", count, num[index]);
        strcat(res, tmp_res);
        count = 1;
      }
    }
    index++;
  }
  num[0] = '\0';
  strcat(num, res);
  printf("%d\n", strlen(num));
  num[strlen(num)] = '\0';
}
char* countAndSay(int n) {
  char *res = (char*)malloc(sizeof(char*) * MAX_LEN);
  res[0] = '1';
  res[1] = '\0';
  int i, length = 1;
  for (i = 1; i < n; i++) {
    length = strlen(res);
    next_num(res, length);
  }
  return res;
}

PS:还是Python写起来简单

#LeetCode