小编Bar*_*234的帖子

在白板考试期间,监考人员要求这个非常常见的算法问题.我的工作是观察,倾听并客观地判断所给出的答案,但我既没有控制这个问题,也没有与回答的人互动.分析问题的时间有五分钟,候选人可以编写子弹笔记,伪代码(这在实际代码编写期间允许,只要明确指出,人们包括伪代码作为注释或TODO任务在搞清楚算法得到奖励积分之前).

• "一个孩子爬上楼梯,有n个台阶,可以一步一跳,两步或三步.实施一种方法来计算孩子跳楼梯的可能方式."

得到这个问题的人无法在现场开始使用递归算法,因此监考人员最终逐件引导他进入HIS解决方案,在我看来这不是最优的(好吧,与我选择的解决方案不同)在代码优化方面很难客观地评价某人.

宝洁:

public class Staircase {

public static int stairs;

public Staircase() {

    int a = counting(stairs);
    System.out.println(a);

}

static int counting(int n) {
    if (n < 0)
        return 0;
    else if (n == 0)
        return 1;
    else
        return counting(n - 1) + counting(n - 2) + counting(n - 3);
}

public static void main(String[] args) {
    Staircase child;
    long t1 = System.nanoTime();
    for (int i = 0; i < 30; i++) {
        stairs = i;
        child = …

首先,我对单链表的基本理解是每个节点只指向下一个后续节点,所以我的问题可能源于我对这种列表的定义不正确.

给定列表设置,到达节点n将需要迭代前面的n-1个节点,因此搜索和访问将是O(n).现在,显然节点插入和删除需要O(1),但除非他们正在谈论第一个项目插入,那么实际上你将在节点n和n +之间插入项目为O(n)+ O(1)1.

现在,索引列表也会有O(n)的复杂性,但显然构建这样的索引是不受欢迎的,我无法理解为什么.我们不能建立一个单链表索引,它允许我们真正的O(1)插入和删除,而不必在列表上执行O(n)迭代来到我们的特定节点？它甚至不需要是所有节点的索引,我们可以指向子索引,即对于1000个项目的列表,第一个索引将指向10个不同的索引,用于1-100,101-200之间的项目等然后这些索引可以指向更小的索引.这样,到达节点543可能只需要3次(索引遍历)迭代,而不是像典型的单链表那样需要543次迭代.

我想,我要问的是为什么通常应该避免这种索引？