阵列中的填充停顿（Big Java Ex 7.22）

Question

对于一些背景，这里是问题陈述。

It is a well-researched fact that men in a restroom generally prefer to maximize their distance from already occupied stalls, by occupying the middle of the longest sequence of unoccupied places. For example, consider the situation where ten stalls are empty.

_ _ _ _ _ _ _ _ _ _ The first visitor will occupy a middle position:

_ _ _ _ _ X _ _ _ _ The next visitor will be in the middle of the empty area at the left.

_ _ X _ _ X _ _ _ _

Write a program that reads the number of stalls and then prints out diagrams in the format given above when the stalls become filled, one at a time. Hint: Use an array of boolean values toindicate whether a stall is occupied.

我也找到了我大部分都能理解但有点难以理解的解决方案。在这里

import java.util.Scanner;
class StallLogic
{
    public void printStalls(boolean [] b)
    {
        for(boolean s:b)
        {
            System.out.print((s?"X" : "_") + " ");
        }
        System.out.print("\n");
    }
    
    public boolean giveFlag(boolean [] b)
    {
        for(boolean s : b)
        {
            if(!s) return false;
        }
        return true;
    }
    
    public int getLongest(boolean [] b)
    {
        int length = 0, temp = 0;
        int len = b.length;
        for(int i = 0; i < len ; i++)
        {
            if (b[i] == false)
            {
                temp++;
            }
            else{
                temp = 0;
            }
            if (length < temp)
                length = temp;
        }
        return length;
    }
    
    public int checkIndex(boolean [] b)
    {
        int length = 0 , temp = 0, ind = 0;
        int len = b.length;
        for (int i = 0 ; i < len ; i++)
        {
            if(b[i] == false)
            {
                temp++;
            }
            else{
                temp = 0;
            }
            if (length < temp)
            {
                ind = i -length;
                length = temp;
            }
        }
        return ind;
    }
    
    public void findStalls(boolean [] b)
    {
        int loc = checkIndex(b);
        int len = getLongest(b);
        int ind = loc + len / 2;
        b[ind] = true;
    }
}

public class checkStall
{
    public static void main(String [] args)
    {
    StallLogic stallin = new StallLogic();  
    System.out.print("Enter number of stalls");
    Scanner in = new Scanner(System.in);
    int i = in.nextInt();
    boolean [] stalls = new boolean [i];
    while(!stallin.giveFlag(stalls))    
    {
        stallin.findStalls(stalls);
        stallin.printStalls(stalls);
    }
    
    }

    
}

我的奋斗历程

我无法理解 checkIndex 的真正意义。我明白getLongest，会告诉我们arraylist的哪些部分有最连续的_'s

例如在 _ _ _ _ _ X _ _ _ _ 中，我们检查左侧是否有更多 _ 和 getLongest。现在的问题是我们需要一个实际的索引来放入 X。我们的程序如何知道是将它放在每个预先存在的 X 的左侧还是右侧？这就是我推测 checkIndex 出现的地方。

特别让我感到困惑的是，为什么我要对有多少个 _ 进行最大计数并将其与特定索引相加？即 int ind = loc + len / 2;

checkIndex 和 int ind = loc + len / 2, 到底在做什么？是否有一些我没有意识到的算法？

Answer 1

如果不写出算法，getLongest 似乎是 return 最长空档的长度。

然后，checkIndex 得到同一区域最左边的空摊位。

有了这两个数字，您只需平分差额，然后占据那个摊位 left + (length / 2)。

"scanning" 停顿两次是一种效率较低的方法。 getLongest 和 checkIndex 方法可以合并为两个位置的 return 和 int[]，因为包含 int ind 是这两种方法之间的唯一变化。

阵列中的填充停顿（Big Java Ex 7.22）

Filling stalls within an Array ( Big Java Ex 7.22)

java

divide-and-conquer