分而治之——在数组中填充摊位(大Java Ex 7.22)

Question

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

这是一个经过充分研究的事实，男人在厕所里通常更喜欢为了最大限度地与已被占用的摊位保持距离，通过占领最长的空位置序列的中间。例如,假设有十个隔间是空的。

_ _ _ _ _ _ _ _ _ _第一个访问者将占据中间位置:

_ _ _ _ _ X _ _ _ _下一个访问者将位于左侧空白区域的中间。

_ _ _ X _ _ X _ _ _ _

编写一个程序，读取摊位的数量，然后在摊位填满时以上面给出的格式打印图表，一次一个。提示:使用布尔值数组来指示摊位是否被占用。

我也找到了解决方案，我理解的大部分，但我有困难理解一点。在这里

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);
    }
    
    }
    
}

<<p> 我斗争/strong>

我很难理解checkIndex的真正意义。我知道getLongest会告诉我们数组列表的哪些部分具有最连续的_

例如在_ _ _ _ _ X _ _ _ _中，我们检查左侧有更多的_和getLongest。现在的问题是我们需要一个实际的索引来放置X。我们的程序如何知道应该把它放在每个已经存在的X的左边还是右边呢?这就是我认为checkIndex的用武之地。

我特别困惑的是，为什么我要取最大计数有多少_'s，并将其与特定索引相加?即int ind = loc + len / 2;

checkIndex和int ind = loc + len / 2,到底在这里做什么?有没有什么我没意识到的算法?

Answer 1

在不写出算法的情况下，看起来getLongest返回的是摊位最长的空区域的长度。

然后，checkIndex获得同一路段最左边的空摊位。

对于这两个数字，您只需平分差额，并占用该摊位left + (length / 2)。

---

通过两次"扫描"摊位是一种效率较低的方法。getLongest和checkIndex方法可以组合起来返回两个位置的int[]，因为包含int ind是两个方法之间唯一的变化。