[leetcode]38. counting - problem solving (execution time beat 91%, memory consumption beat 97%)

1. Title Description

The number sequence is an integer sequence , Count off in the order of integers , Get the next number . The first five items are as follows ： 1. 1 2. 11 3. 21 4. 1211 5. 111221 1 pronounce as "one 1" , namely 11 11 pronounce as "two 1s", namely 21 21 pronounce as "one 2", "one 1", namely 1211 Given a positive integer n（1 ≤ n ≤ 30）, The number of the output number sequence n term . Be careful ： Integer order will be represented as a string . Example 1: Input : 1 Output : "1" Example 2: Input : 4 Output : "1211"

2. analysis

First, you can see the integer sequence of each message （ character string ） Is in “Count and Say” The integer sequence of the previous number , namely Count the number of times each number appeared in the last counting result . such as n=3 when , The integer sequence is 21, By “1 individual 2 and 1 individual 1” form , So the next count off （n=4）, Integer sequence bits for counting 1211.

therefore , Grasp “ The integer sequence of each message （ character string ） Is in “Count and Say” The integer sequence of the previous number ”, We can use the previous integer sequence to calculate the next integer sequence , The code will always update only the integer sequence of two adjacent numbers , There is no need to save multiple or all . Obvious , We need to calculate from the first teller .

Another question is how "Count and Say":

• Count: Count the number of times each number appears
• Say： Save the current statistics
• Where each new number appears init

such as 1211：

At the beginning, the statistics were 1, Where to start counting init yes 0, Next number 2 It's not equal to 1, therefore count by 1, The integer sequence is 11. here count Zero clearing , Because the next number needs to be counted again . The current statistics are 2, Where to start counting init yes 1, Next number 1 It's not equal to 2, therefore count by 1, The integer sequence is 1112. Again ,count Zero clearing ,init Updated to 2, Because the next new number 1 The place where it appears is 2. According to the above ideas , Until the complete certificate sequence is counted .

3. Code

string countAndSay(int n) {
  if (n == 1){
    return "1";
  }
 
  // Store the result of each count 
  string curRes = "";
  // Store the result of the last count 
  string lastRes = "1";
  // Count variables 
  int i = 1;
  // The count variable of the last count result 
  int j = 0;
  // The position of each new number in the counting result , such as 1211,init Respectively 0,1,2
  int init = 0;
  // The number of each new number , such as 1211,count Respectively 1,1,2
  int count = 0;
  // The length of the last counting result , such as 1211,length by 4
  int length = lastRes.length();
 
  while (i <= n){
    while (j<length){
      if (lastRes[j] == lastRes[init]){
        count++;
        j++;
      }
      else{// New figures appear , Record the statistical results of the last number and the position of the new number init
        curRes.append(1, char(count + '0'));
        curRes.append(1, char(lastRes[j - 1]));
        count = 0;
        init = j;
      }
    }
    curRes.append(1, char(count + '0'));
    curRes.append(1, char(lastRes[j - 1]));
    i++;
    if (i >= n){
      return curRes;
    }
    length = curRes.length();
    lastRes = curRes;
    curRes = "";
    j = 0;
    count = 0;
    init = 0;
  }
  return curRes;
}

Copy

4. Execution results