程序员面试题精选100题完整版(4)

class A;

A* Array[2];

class A

{

public:

};

class B: public A virtual int Sum (int n) { return 0; }

很全面,很经典的程序员面试题精选100题,包括网络编程,socket编程,c++/c编程程序员面试题,linux/windows网络编程面试必备。

{

public:

};

int solution2_Sum(int n)

{

} return value; int value = Array[1]->Sum(n); A a; B b; Array[0] = &a; Array[1] = &b; virtual int Sum (int n) { return Array[!!n]->Sum(n-1)+n; }

这种方法是用虚函数来实现函数的选择。当n不为零时，执行函数B::Sum；当n为0时，执行A::Sum。我们也可以直接用函数指针数组，这样可能还更直接一些：

typedef int (*fun)(int);

int solution3_f1(int i)

{

}

int solution3_f2(int i)

{

}

另外我们还可以让编译器帮我们来完成类似于递归的运算，比如如下代码：

template <int n> struct solution4_Sum

{

};

template <> struct solution4_Sum<1>

{

};

solution4_Sum<100>::N就是1+2+...+100的结果。当编译器看到solution4_Sum<100>enum Value { N = 1}; enum Value { N = solution4_Sum<n - 1>::N + n}; fun f[2]={solution3_f1, solution3_f2}; return i+f[!!i](i-1); return 0; 时，就是为模板类solution4_Sum以参数100生成该类型的代码。但以100为参数的类型需要得到以99为参数的类型，因为solution4_Sum<100>::N=solution4_Sum<99>::N+100。这个过程会递归一直到参数为1的类型，由于该类型已经显式定义，编译器无需生成，递归编译到此结束。由于这个过

很全面,很经典的程序员面试题精选100题,包括网络编程,socket编程,c++/c编程程序员面试题,linux/windows网络编程面试必备。

程是在编译过程中完成的，因此要求输入n必须是在编译期间就能确定，不能动态输入。这是该方法最大的缺点。而且编译器对递归编译代码的递归深度是有限制的，也就是要求n不能太大。

大家还有更多、更巧妙的思路吗？欢迎讨论^_^

(09)－查找链表中倒数第k个结点

题目：输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表

的尾指针。链表结点定义如下：

struct ListNode

{

}; int m_nKey; ListNode* m_pNext;

分析：为了得到倒数第k个结点，很自然的想法是先走到链表的尾端，再从尾端回溯k步。可是输入的是单向链表，只有从前往后的指针而没有从后往前的指针。因此我们需要打开我们的思路。

既然不能从尾结点开始遍历这个链表，我们还是把思路回到头结点上来。假设整个链表有n个结点，那么倒数第k个结点是从头结点开始的第n-k-1个结点（从0开始计数）。如果我们能够得到链表中结点的个数n，那我们只要从头结点开始往后走n-k-1步就可以了。如何得到结点数n？这个不难，只需要从头开始遍历链表，每经过一个结点，计数器加一就行了。 这种思路的时间复杂度是O(n)，但需要遍历链表两次。第一次得到链表中结点个数n，第二次得到从头结点开始的第n-k-1个结点即倒数第k个结点。

如果链表的结点数不多，这是一种很好的方法。但如果输入的链表的结点个数很多，有可能不能一次性把整个链表都从硬盘读入物理内存，那么遍历两遍意味着一个结点需要两次从硬盘读入到物理内存。我们知道把数据从硬盘读入到内存是非常耗时间的操作。我们能不能把链表遍历的次数减少到1？如果可以，将能有效地提高代码执行的时间效率。

如果我们在遍历时维持两个指针，第一个指针从链表的头指针开始遍历，在第k-1步之前，第二个指针保持不动；在第k-1步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1，当第一个（走在前面的）指针到达链表的尾结点时，第二个指针（走在后面的）指针正好是倒数第k个结点。

这种思路只需要遍历链表一次。对于很长的链表，只需要把每个结点从硬盘导入到内存一次。因此这一方法的时间效率前面的方法要高。

思路一的参考代码：

///////////////////////////////////////////////////////////////////////

// Find the kth node from the tail of a list

// Input: pListHead - the head of list

// k - the distance to the tail

// Output: the kth node from the tail of a list

///////////////////////////////////////////////////////////////////////

ListNode* FindKthToTail_Solution1(ListNode* pListHead, unsigned int k) {

很全面,很经典的程序员面试题精选100题,包括网络编程,socket编程,c++/c编程程序员面试题,linux/windows网络编程面试必备。

return NULL; // count the nodes number in the list ListNode *pCur = pListHead; unsigned int nNum = 0; while(pCur->m_pNext != NULL) { } // if the number of nodes in the list is less than k // do nothing if(nNum < k) return NULL; pCur = pCur->m_pNext; nNum ++; // the kth node from the tail of a list // is the (n - k)th node from the head pCur = pListHead; for(unsigned int i = 0; i < nNum - k; ++ i) pCur = pCur->m_pNext;

return pCur;

}

思路二的参考代码：

///////////////////////////////////////////////////////////////////////

// Find the kth node from the tail of a list

// Input: pListHead - the head of list

// k - the distance to the tail

// Output: the kth node from the tail of a list

///////////////////////////////////////////////////////////////////////

ListNode* FindKthToTail_Solution2(ListNode* pListHead, unsigned int k) {

for(unsigned int i = 0; i < k; ++ i) { ListNode *pAhead = pListHead; ListNode *pBehind = NULL; if(pListHead == NULL) return NULL;