相关疑难解决方法(0)

我正在准备C中的一些培训材料,我希望我的示例适合典型的堆栈模型.

C堆栈在Linux,Windows,Mac OSX(PPC和x86),Solaris和最新的Unix中的发展方向是什么？

我知道在我个人熟悉的架构(x86,6502等)中,堆栈通常会向下增长(即,每个推入堆栈的项目都会导致SP递减,而不是递增的SP).

我想知道这个的历史原因.我知道在一个统一的地址空间中,在数据段的另一端(例如)开始堆栈很方便,所以如果双方在中间发生碰撞,那么只会出现问题.但是为什么堆栈传统上是最重要的？特别是考虑到这与"概念"模型的对立面如何？

(请注意,在6502架构中,堆栈也向下增长,即使它被限制在一个256字节的页面上,这个方向选择似乎是任意的.)

我很困惑,因为如果我们已经有一个指针,那么我们可以很容易地指向下一条指令,我们可以轻松指向返回上一个函数,那么为什么我们需要另一个堆栈指针寄存器来回到以前的函数或模块？

这是Cracking the Coding Interview ^第 5 版的问题9.5

问题:编写一种方法来计算字符串的所有排列

这是我的解决方案,用Java编码(测试它,它工作:))

public static void generatePerm(String s) {
    Queue<Character> poss = new LinkedList<Character>();
    int len = s.length();
    for(int count=0;count<len;count++)
        poss.add(s.charAt(count));
    generateRecurse(poss, len, "");
}
private static void generateRecurse(Queue<Character> possibles, int n, String word) {
    if(n==0)
        System.out.println(word);
    else {
        for(int count=0;count<n;count++) {
            char first = possibles.remove();
            generateRecurse(possibles, n-1, word+first);
            possibles.add(first);
        }
    }
}

我同意作者的观点,我的解决方案在O(n!)时间复杂度下运行,因为要解决这个问题,你必须考虑阶乘,就像像"top"这样的单词,第一个字母有三种可能性,2为第二等......

然而,她没有提到空间复杂性.我知道面试官喜欢问你解决方案的时间和空间复杂性.这个解决方案的空间复杂性是什么？

我最初的猜测是O(n ²),因为在每个级别n都有n个递归调用.所以你要加n + n - 1 + n - 2 + n - 3 ..... …