【JAVA】每日两道算法题0925_双指针+递归

浅浅的花香味﹌ 2021-09-24 18:02 333阅读 0赞

### 算法 ###

*  LeetCode38 外观数列

# LeetCode38 外观数列 #

题目：给定一个正整数 n（1 ≤ n ≤ 30），输出外观数列的第 n 项。整数序列中的每一项将表示为一个字符串。  
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：

1.     1
    2.     11
    3.     21
    4.     1211
    5.     111221

标签：`字符串`、`递归`、`双指针`  
思路：  
1.第n项是对第n-1项的描述。故先获取第n-1项。（递归法）  
2.描述方法：

*  使用双指针通过指针距离统计次数。
 *  i初始化为0; j遍历数组(1-> n)
 *  比较下标为i和j 的数组值,如果一致，j+1继续遍历。如果不一致，输出有j-i个a\[i\],直到最后一个j = n，直接拼接。

情况一：最后一位与倒数第二位不一样  
![在这里插入图片描述][20200925150918377.png_pic_center]  
情况二：最后一位与相邻位一致  
![在这里插入图片描述][20200925150852567.png_pic_center]

代码实现：

class Solution { 
        public String countAndSay(int n) {    
            if(n == 1) { return "1";}
            StringBuffer sb = new StringBuffer();
            String str = countAndSay(n-1);
            int len = str.length();
            int i = 0;   //开始指针指向字符串的第一位
            for(int j = 1; j < len + 1 ; j++) {     //j从字符串的第二位开始遍历，遍历长度为数组长度
                if (j == len) {      //下标j等于数组长度，sb[j]会越界，但此处不影响，加了j之后，才可以正确拼接最后一位i
                    sb.append(j-i).append(str.charAt(i));
                }
                else if (str.charAt(j) != str.charAt(i)){ 
                    sb.append(j-i).append(str.charAt(i));
                    i = j;
                } 
            }
            return sb.toString();
        }
    }

[20200925150918377.png_pic_center]: /images/20210923/5e4e2f2f3e8d4bddb9be21fa3769bb6b.png
[20200925150852567.png_pic_center]: /images/20210923/86a1c2e299054310abd574cb75baa685.png