在一个序列中找到第n项

Question

我有一个序列，想编写一个程序来找到该序列的第n项。

这个序列如下：

1、11、21、1211、111221、312211......

在这个序列中，每一项都描述了前一项。例如，“1211”意味着前一项;前一项是“21” ，其中有一个 2和一个 1（=1211）。要得到第三项“21”，你需要查看第二项：11。有两个 1，这就给了我们“21”。

import java.util.*;
class Main {
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int n = scan.nextInt();
        System.out.println( Main.num(n-1, "1"));
  }
    public static String num(int times, String x){
        if(times == 0){
            return x;
        }else{
            //System.out.println("meow");
            String y = "" + x.charAt(0);
            int counter = 0;
            for(int i = 1; i < x.length(); i++){
                if(x.charAt(i) == x.charAt(i-1)){
                    counter++;
                }else{
                    y += "" + counter + x.charAt(i-1);
                    counter = 0;
                }
            }
            return num(times--, y);
        }
        //return "";
    }
}

我的代码利用递归来寻找第n项。但是，它给我们带来了错误 :(

首先我通过传递项数-1（因为第一项已知）和第一项（1）来启动方法“num”。

在方法num中，我们首先使用条件语句来创建基础情况（当你完成寻找第n项时）。

如果基础情况为false，则寻找序列中的下一项。

- pinkbird

Answer 1

这是一个非常酷的序列！我喜欢它基于英语而不是数学（哈哈）。 （尽管现在我想知道......是否有公式可以用于第n个数字？我很确定这是不可能或使用了一些疯狂的数学，但只是值得思考......）

在你的解决方案中，你的代码递归逻辑是正确的：在找到每个数字后，你重复使用新数字的方法并使用该元素找到下一个数字，并在确定第一个 n 个元素时结束。你的基本情况也是正确的。

然而，你开发用于确定序列中的项的算法存在问题。

为了确定序列中的下一个元素，我们希望：

逻辑错误：

1. 创建一个空变量 y，用于下一个元素。然而，变量 counter 不应该从 0 开始。这是因为每个元素都至少会出现一次，所以我们应该初始化 int counter = 1;

2. 迭代 x 中的字符。（你已经正确执行了这一步）我们从 i=1 开始，因为我们将每个字符与前一个字符进行比较。

3. 如果当前字符等于上一个字符，则将 counter 加 1。

4. 否则，我们将 counter 和正在重复的字符连接起来，赋给 y。记住，要将 counter 重新初始化为 1，而不是 0。

技术错误：

5. 当我们到达迭代 x 的结尾时，我们需要将我们的最终 counter 和字符连接到 y，因为我们的 for 循环中 else 语句不会运行最后一个字符。

可以使用以下代码完成此操作：y += "" + counter + x.charAt(x.length() - 1);

6. 最后，在进行递归调用时，你应该使用 --times 而不是 times--。这两个参数之间的区别在于，使用原始代码时，你正在进行后缀递减。这意味着方法调用后，times 的值会减少，而我们希望减少的值被发送到方法中。为了解决这个问题，我们需要进行前缀递减，即使用 --times。

import java.util.*;
class CoolSequence {
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int n = scan.nextInt();
    System.out.println(num(n, "1"));
  }
    public static String num(int times, String x){
        if(times == 0){
            return x;
        }
        else{
            String y = "";
            int counter = 1;
            for(int i = 1; i < x.length(); i++){
                if(x.charAt(i) == x.charAt(i - 1)){
                    counter++;
                }
                else{
                    y += "" + counter + x.charAt(i - 1);
                    counter = 1;
                }
            }
            y += "" + counter + x.charAt(x.length() - 1);
            return num(--times, y);
        }
    }
}

测试：

6
13112221

另一种方法是使用迭代法：

import java.util.*;
class CoolSequence2 {
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    ArrayList<String> nums = new ArrayList<String>();
    int n = scan.nextInt();
    String val = "1";
    for(int i = 0; i < n; i++){
      String copy = val;
      val = "";
      while(!copy.equals("")){
        char curr = copy.charAt(0);
        int ind = 0;
        int cons = 0;
        while(ind < copy.length() && curr == copy.charAt(ind)){
          cons += 1;
          ind += 1;
        }
        val += String.valueOf(cons) + copy.charAt(cons - 1);
        copy = copy.substring(cons);
      }
      nums.add(val);
    }
    System.out.println(nums.get(nums.size() - 1));
  }
}

6
13112221

在这种方法中，我们使用一个for循环来迭代n个项。为了确定每个元素，我们使用类似于您的逻辑的方法：

1. 我们创建一个空字符串val来保存新元素，并将当前元素存储在复制中。我们还初始化了一个cons，类似于您的计数器。
2. 当复制不为空时，我们遍历复制并增加cons，直到有一个元素不等于下一个元素。
3. 当这种情况发生时，我们将cons和重复的元素连接起来放入val中，就像您的代码一样。然后，我们从复制中剪切出重复的元素并继续这个过程。
4. 我们将val的新值添加到nums中，并继续迭代n个元素。

希望这两种方法能帮助你解决问题！如果您有任何进一步的问题或需要澄清，请告诉我 :)

- Aniketh Malyala

---

@pinkbird 通常来说，递归解决方案会更慢，但是在你的解决方案中，你的递归本质上与O(n)循环相同。然而，在这种情况下，我认为你最初采用的递归方法实际上更快。我编写的迭代方法有更多的嵌套循环。不过，两种方法都可以完美地工作 :) 希望这对你有所帮助！ - Aniketh Malyala

Answer 2

您可以使用带有反向引用的Pattern。

正则表达式"(.)\\1*"匹配任何单个字符("(.)")和零个或多个相同字符序列("\\1*")。"\\1"被称为反向引用，它指的是括号中第一个字符串。

例如，对于111221，它匹配111、22和1。

replaceAll()每次匹配时都会调用由参数指定的lambda表达式。Lambda表达式接收一个MatchResult并返回一个字符串，匹配到的字符串将被替换为结果。

在这种情况下，Lambda表达式连接了匹配字符串的长度(match.group().length())和第一个字符(match.group(1))。

static final Pattern SEQUENCE_OF_SAME_CHARACTER = Pattern.compile("(.)\\1*");

static String num(int times, String x) {
    for (int i = 0; i < times; ++i)
        x = SEQUENCE_OF_SAME_CHARACTER.matcher(x).replaceAll(
            match -> match.group().length() + match.group(1));
    return x;
}

public static void main(String[] args) {
    for (int i = 1; i <= 8; ++i)
        System.out.print(num(i - 1, "1") + " ");
}

输出：

1 11 21 1211 111221 312211 13112221 1113213211

- user17233545

---

哇，我甚至不知道这个方法的存在...非常酷和简化的解决方案 :) - Aniketh Malyala

这很简短！！哇谢谢你 只是一个快速问题，这意味着什么：static final Pattern SEQUENCE_OF_SAME_CHARACTER = Pattern.compile("(.)\1*"); ? - pinkbird