java获得幸运数字

Question

幸运数是由筛选算法生成的序列的数字：如果正整数序列中的一个数字在筛选过滤算法中幸存，则它是幸运的并幸存，否则它将从序列中消失

首先，您必须获得一个从1到所需大小的数字数组。 第一个数字是1，它仍然存在：在他旁边有一个数字2，它成为了筛子的过滤器：列表中的每一个数字（从1开始计数）都必须被过滤（比如说每一个偶数）。 在这一步之后，1之后的下一个数字是3：消除列表中的每三个数字（从1开始计数）。 在这一步之后，下一个在3之后存活的数字是7：删除列表中的每七个数字。 在每一步重复增加过滤条件的步骤（比如说，新步骤的过滤条件等于第一个数字大于上一步的最后一个幸运数字），直到列表中没有要消除的数字。 对于给定的大小=25和N=5，请参见下面的示例

步骤1：生成一个从1到大小的列表

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

第2步：第一个筛子过滤器是2：从一开始，每隔一秒就必须消除一次

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

第3步：筛子过滤器现在是3：从一开始每三个数字必须被消除

1,3,5,7,9,11,13,15,17,19,21,23,25 第4步：筛子过滤器现在是7：从一开始每七个数字必须被消除

1,3,7,9,13,15,19,21,25

第5步： 筛子过滤器现在是9：每9个数字必须被删除，但我们的列表现在只包含8个数字，因此算法结束。序列的第n个数字是13

在下面的动画中，您可以看到120个数字列表的渐进筛选过程：紫色填充表示已消除的数字，红色表示幸运的数字

这是我的解决方案（它不起作用），我似乎无法得到数组中的每一个第n个数字

是的，我知道我的代码返回1，我现在只是打印一些东西，试图调试我的代码有什么问题

public static List<Integer> generateLucky(int[] A, int steps)
    {
        List<Integer> lst = new ArrayList<>();
        for(int i = 0; i < A.length; i++)
        {
            if(i % steps == 0)
            {
                lst.add(A[i]);
            }
        }
        return lst;
    }
    public static int getLuckyNumber(int size, int nth) 
    {
        List<Integer> nums = new ArrayList<>();
        for(int i = 1; i <= size; i++)
        {
            nums.add(i);
        }
        int steps = 1;
        int[] A = nums.stream().mapToInt(j->j).toArray();
        for(int i = 0; i < A.length; i++)
        {
            List<Integer> lst = generateLucky(Arrays.copyOfRange(A, 0, A.length), steps);
            System.out.println(lst);
            A = lst.stream().mapToInt(j->j).toArray();
            steps = A[1];

        }
        return 1;
    }

Answer 1

我回答这个问题是为了解释我的推理过程

以下是我编写的代码的测试运行结果

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
listFilter: 2
1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25
listFilter: 3
1, 3, 7, 9, 13, 15, 19, 21, 25
listFilter: 7
1, 3, 7, 9, 13, 15, 21, 25
13

该测试运行的输入大小为25，第n个为5

当我写代码时，我是分步骤写的。我检查了每一步，以确保输出符合我的预期

首先，我生成了初始列表。效果很好

接下来，我生成了第一个过滤列表，即被2过滤的列表。在第一个过滤列表正确打印出来之前，我没有编写任何其他代码

接下来，我生成了第二个过滤列表，即被3过滤的列表。同样，在第二个过滤列表正确打印出来之前，我没有编写任何其他代码

接下来，我生成了第三个过滤列表，即被7过滤的列表

在这一点上，我有足够的代码和经验来了解如何推广我称之为ProceeSsieve的方法

最后，打印中间输出有助于调试刚刚编写的代码。代码中的其他每一条语句都应该是系统。出来打印或打印

这是我写的代码。我不认为从长远来看，给你这些代码会帮助你学习。注意代码中嵌入的调试语句

import java.util.ArrayList;
import java.util.List;

public class LuckyNumber {

    public static void main(String[] args) {
        LuckyNumber luckyNumber = new LuckyNumber();
        System.out.println(luckyNumber.getLuckyNumber(25, 5));
    }

    private static boolean DEBUG = true;

    public int getLuckyNumber(int size, int index) {
        List<Integer> numberList = createOriginalList(size);
        if (DEBUG) { 
            printList(numberList);
        }
        numberList = processSieve(numberList);
        return numberList.get(index - 1);
    }

    private List<Integer> createOriginalList(int size) {
        List<Integer> numberList = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            numberList.add(i + 1);
        }
        return numberList;
    }

    private List<Integer> processSieve(List<Integer> numberList) {
        int listIndex = 1;
        int count = 0;
        int listFilter = numberList.get(listIndex);
        while (listFilter <= numberList.size()) {
            if (DEBUG) {
                System.out.println("listFilter: " + listFilter);
            }
            numberList = filterList(numberList, listFilter);
            if (DEBUG) {
                printList(numberList);
            }
            if (count > 0) {
                listIndex++;
            }
            count++;
            listFilter = numberList.get(listIndex);
        }
        return numberList;
    }

    private List<Integer> filterList(List<Integer> list, int listFilter) {
        List<Integer> filterList = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            if ((i + 1) % listFilter == 0) {
                continue;
            } else {
                filterList.add(list.get(i));
            }
        }
        return filterList;
    }

    private void printList(List<Integer> list) {
        for(int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i));
            if (i < (list.size() - 1)) {
                System.out.print(", ");
            }
        }
        System.out.println();
    }

}

Answer 2

第一次运行，在调试之前：

[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]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25]
[1, 7, 13, 19, 25] <  doesn't look good. It's suppose to retain [1, 3, 7, 9, 13,.. 
[1]
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 1 out of bounds for length 1

我删除了导致错误的行：steps = A[1];
然后补充说：

• int stepindex = 1;
• 处理步进的逻辑。似乎那部分不见了。
  • 确保stepindex小于数组的总长度
  • 还要检查数组（stepindex的）中的当前值，看看它是否小于或与前面的steps相同。如果是的话，增加stepindex（1）并重新检查
  • 如果新的步数大于数组的长度，那么就没有什么可删除的了，所以break
• 更改了决定保留哪些数字的声明

我没有将代码更改为只使用数组或列表，因为我试图使它尽可能接近您的原始代码

现在它打印：

steps = 2
stepindex = 1
A = [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]
steps = 3
stepindex = 1
A = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25]
steps = 7
stepindex = 2
A = [1, 3, 7, 9, 13, 15, 19, 21, 25]
steps = 9
stepindex = 3
A = [1, 3, 7, 9, 13, 15, 21, 25]
  getLuckyNumber(25,5): nth = 13
      
steps = 2
stepindex = 1
A = [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]
steps = 3
stepindex = 1
A = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25]
steps = 7
stepindex = 2
A = [1, 3, 7, 9, 13, 15, 19, 21, 25]
steps = 9
stepindex = 3
A = [1, 3, 7, 9, 13, 15, 21, 25]
  getLuckyNumber(25,5000): nth = -2147483648

修改后的代码：

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

public class StackOverflowTest {
  public static void main(String[] args){
    System.out.println("  getLuckyNumber(25,5): nth = " + getLuckyNumber(25,5));
    System.out.println("      ");
    System.out.println("  getLuckyNumber(25,5000): nth = " + getLuckyNumber(25,5000));
  }

  public static List<Integer> generateLucky(int[] A, int steps) {
    List<Integer> lst = new ArrayList<>();
    System.out.println("A = " + Arrays.toString(A));   // debug statement
    for (int i = 0; i < A.length; i++) {
//        if (i % steps == 0) { // not working.. it's only adding the numbers that should be removed
        // decide what numbers to keep
        if ((i+1) % steps != 0) { // arrays are zero-indexed
//            System.out.println("A[" + i + "] = " + A[i]); // intermediate debug statement
            lst.add(A[i]);
        }
    }
    return lst;
  }

  public static int getLuckyNumber(int size, int nth) {
    List<Integer> nums = new ArrayList<>();
    for (int i = 1; i <= size; i++) {
        nums.add(i);
    }

    int steps = 1;
    int stepindex = 1;
    int[] A = nums.stream().mapToInt(j->j).toArray();
    for(int i = 0; i < A.length; i++) {

      // logic to handle stepping:
      while (stepindex < (A.length - 1) && A[stepindex] <= steps) {stepindex++;}
      steps = A[stepindex];
      System.out.println("steps = " + steps);         // debug statement
      System.out.println("stepindex = " + stepindex); // debug statement
      if (steps >= (A.length)) {break;}

      List<Integer> lst = generateLucky(Arrays.copyOfRange(A, 0, A.length), steps);
//      System.out.println(lst);
      A = lst.stream().mapToInt(j->j).toArray();
//      steps = A[1]; // this is the source of the Runtime Error.. 
    }
    System.out.println("A = " + Arrays.toString(A));   // debug statement

    if (nth < A.length) {
      return A[nth-1];
    } else {
      return Integer.MIN_VALUE; // just something to return if nth is too big
    }
  }
}