FilesExpand file tree

 master

/

countAndSay.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

88 lines (78 loc) · 1.81 KB

 master

/

countAndSay.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

88 lines (78 loc) · 1.81 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

// Source : https://oj.leetcode.com/problems/count-and-say/

// Author : Hao Chen

// Date : 2014-07-03

/**********************************************************************************

*

* 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.

*

*

**********************************************************************************/

#include <stdlib.h>

#include <iostream>

#include <sstream>

#include <string>

#include <vector>

using namespace std;

string vecToStr(vector<int> v) {

stringstream ss;

for (int i=0; i<v.size(); i++) {

ss << v[i];

}

return ss.str();

}

vector<int> getNext(vector<int>& v) {

int cnt=0;

int val=0;

vector<int> ret;

for(int i=0; i<v.size(); i++){

if (i==0){

val = v[i];

cnt = 1;

continue;

}

if (v[i] == val){

cnt++;

}else{

ret.push_back(cnt);

ret.push_back(val);

val = v[i];

cnt = 1;

}

}

if (cnt>0 && val>0){

ret.push_back(cnt);

ret.push_back(val);

}

return ret;

}

string countAndSay(int n) {

if (n<=0) return "";

if (n==1) return "1";

string s;

vector<int> v;

v.push_back(1);

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

v = getNext(v);

//s = s + ", " +vecToStr(v);

}

s = vecToStr(v);

return s;

}

int main(int argc, char** argv)

{

int n = 4;

if (argc>1){

n = atoi(argv[1]);

}

cout << countAndSay(n) << endl;

return 0;

}