单向链表逆序排列（单向链表排序最低时间复杂度）



1.把二元查找树转变成排序的双向链表。
题目：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
10
/
6 14
/ /
4 8 12 16
转换成双向链表
4=6=8=10=12=14=16。
首先我们定义的二元查找树节点的数据结构如下：
struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};
ANSWER:
This is a traditional problem that can be solved using recursion.
For each node, connect the double linked lists created from left and right child node to form a full list.

#define T(X, Y, i) (Y & (1<<i)) && X+=(Y<<i)

It seems that a brute-force edge cutting strategy could do. Enumerate all possibilities, then for each guy delete the permutation that could be reduced if failed (for A, B, C at 1st round), Then there should be only one or one group of choices left.

But who uses this as an interview question?

int dij

Time complexity analysis:

2)一串首尾相连的珠子(m 个)，有N 种颜色(N<=10)，
设计一个算法，取出其中一段，要求包含所有N 中颜色，并使长度最短。
并分析时间复杂度与空间复杂度。
ANSWER
Use a sliding window and a counting array, plus a counter which monitors the num of zero slots in counting array. When there is still zero slot(s), advance the window head, until there is no zero slot. Then shrink the window until a slot comes zero. Then one candidate segment of (window_size + 1) is achieved. Repeat this. It is O(n) algorithm since each item is swallowed and left behind only once, and either operation is in constant time.
int shortestFullcolor(int a[], int n, int m) {
int c[m], ctr = m;
int h=0, t=0;
int min=n;
while (1) {
     while (ctr > 0 && h<n) {
       if (c[a[h]] == 0) ctr --;
       c[a[h]] ++;
       h++;
     }
     if (h>=n) return min;
     while (1) {
       c[a[t]] --;
       if (c[a[t]] == 0) break;
       t++;
     }
     if (min > h-t) min = h-t;
     t++; ctr++;
}
}

43.递归和非递归俩种方法实现二叉树的前序遍历。
ANSWER
void preorderRecursive(TreeNode * node) {
if (node == NULL) return;
visit(node);
preorderRecursive(node->left);
preorderRecursive(node->right);
}

For non-recursive traversals, a stack must be adopted to replace the implicit program stack in recursive programs.

2.一个整数数组，长度为n，将其分为m 份，使各份的和相等，求m 的最大值
比如{3，2，4，3，6} 可以分成{3，2，4，3，6} m=1;
{3,6}{2,4,3} m=2
{3,3}{2,4}{6} m=3 所以m 的最大值为3
ANSWER
Two restrictions on m, 1) 1 <= m <= n; 2) Sum(array) mod m = 0
NOTE: no hint that a[i]>0, so m could be larger than sum/max;
So firstly prepare the candidates, then do a brute force search on possible m’s.
In the search , a DP is available, since if f(array, m) = OR_i( f(array-subset(i), m) ), where Sum(subset(i)) = m.

Please do edge cutting yourself, I’m quite enough of this...

…

The trick is like this: take use of the old pSibling, make it points to the new created cloned node, while make the new cloned node’s pNext backup the old pSibling.

Similarly, assume C(M, 2) >= n and C(M-1, 2) < n. Do M rand()’s and get a binary string of M length. Assign 1100...0 to 1, 1010...0 to 2, ...

Also recursive way works. Possible optimizations like Sunday algorithm or Rabin-Karp algorithm will do.

4.删除字符串中的数字并压缩字符串。如字符串”abc123de4fg56”处理后变为”abcdefg”。注意空间和效率。（下面的算法只需要一次遍历，不需要开辟新空间，时间复杂度为O(N)）
ANSWER
Also partition, keep non-digit stable.
char * partition(const char * str) {
char * i = str; // i for cursor, j for the first digit char;
char * j = str;
while (*i != ‘0’) {
    if (*i > ‘9’ || *i < ‘0’) {
      *j++ = *i++;
    } else {
      *i++;
    }
}
*j = ‘0’;
return str;
}

A sub-quadratic solution can be done by DP.

2.在9 个点上画10 条直线，要求每条直线上至少有三个点？（3 分钟-20 分钟）

3.在一天的24 小时之中，时钟的时针、分针和秒针完全重合在一起的时候有几次？都分别是什么时间？你怎样算出来的？（5 分钟-15 分钟）

Pass。ok，微软面试全部100题答案至此完。

附录：

最新整理的全部100题的答案参见如下（重复的，以及一些无关紧要的题目跳过。且因尊重阿财，未作过多修改。因此，有些答案是还有问题的，最靠谱的答案以程序员编程艺术系列为准，亦可参考个人之前整理的前60题的答案：

• 第1题-20题答案：http://blog.csdn.net/v_JULY_v/archive/2011/01/10/.aspx；
• 第21-40题答案：http://blog.csdn.net/v_JULY_v/archive/2011/01/10/.aspx；
• 第41-60题答案：http://blog.csdn.net/v_JULY_v/archive/2011/02/01/.aspx。

参考来源：

http://zhedahht.blog.163.com/

http://blog.csdn.net/v_july_v/article/details/

http://blog.csdn.net/wuzhekai1985/article/details/

http://bylijinnan.iteye.com/category/

http://blog.csdn.net/yysdsyl/article/list/1

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/qkl-jc/25823.html