This is the 27th day of my participation in the August Genwen Challenge.More challenges in August
It’s Friday again, and it’s time to take stock of the week. At this point, there’s always the question: What did I do this week? I feel very busy every day, but I feel that there is no special progress in my hands after a week. At the beginning of this week, I made a plan and listed 5 to-do items. After a week of hard work, although these 5 items were almost handled, the to-do items were changed from 5 to 10. But this week is not all bad. I have done more exercises and won the table tennis team competition. Let’s keep doing exercises next week.
The text challenge is now in its 27th day, and so far this month has been good, maintaining 1 question per day and more text per day. Today we will continue to do question 38 of Leetcode.
The title
Given a positive integer n, prints the NTH term of the appearance sequence. An “appearance sequence” is a sequence of integers, starting with the number 1, and each item in the sequence is a description of the previous item. You can think of it as a sequence of numeric strings defined by a recursive formula: countAndSay(1) = “1” countAndSay(n) is a description of countAndSay(n-1), which is then converted to another numeric string. The first five are as follows: 1.1 2.11 3.21 4.1211 5.111221 The first term is the number 1 that describes the previous term. This number is 1, which is “one 1”, called “11”, which describes the previous term. This number is 11, which is” two ones “, called “21”, which describes the previous term. So this number right here is 21 which is “one two plus one one”, which is called “1211” to describe the previous term, this number right here is 1211 which is “one one plus one two plus two ones”, which is called “111221” to describe a string of numbers, The first step is to split the string into a minimum number of groups, each consisting of at most consecutive identical characters. Then for each group, the number of characters is described first, and then the characters are described, forming a description group. To convert the description to a numeric string, replace the number of characters in each group with a number, and then concatenate all the description groups. For example, the numeric string “3322251” is described as follows:
Train of thought
There is no special algorithm, just like Fibonacci sequence, start from scratch one by one to calculate back bai, understand the meaning of the question. When calculating f(n) according to f(n-1), we can use the fast and slow pointer, which is also a classic algorithm: First define two Pointers fast and slow to point to subindexes 1 and 0 respectively, and then compare whether the values of fast and slow are the same. If they are the same, move fast backward by 1 bit and continue to compare until they are different. In this case, the number is the number pointing to slow and the number is fast-slow. Note that the last data is not included in the loop, because fast will exceed len at the end, so don’t forget the final concatenation, which is len-slow.
Java version code
class Solution { public String countAndSay(int n) { if (n == 1) { return "1"; } else { String pre = countAndSay(n - 1); int len = pre.length(); StringBuilder ans = new StringBuilder(); int slow = 0; int fast = 1; while (fast < len) { if (pre.charAt(slow) ! = pre.charAt(fast)) { ans.append(fast-slow).append(pre.charAt(slow)); slow = fast; fast++; } else { fast++; }} // Add ans.append(len-slow).append(pre-charat (slow)); return ans.toString(); }}}Copy the code