微软经典部分面试题

NullPointer · 发表于 2016-12-8 13:43

  1. 把二元查找树转变成排序的双向链表
题目：
输入一棵二元查找树，将该转换成个排序的双向链表。
要求不能创建任何新的结点，只调整指针向。
  10
/       \
6    14
/  \ / \
4 8 12  16
转换成双向链表
4=6=8=10=12=14=16
首先我们定义的二元查找树节点的数据结构如下：

[cpp] view plain copy

struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};

解答：

这是一个可以使用递归的传统问题。显然可以使用中序遍历（左－根－右）。按照这个方式遍历树，比较小的结点先访问。如果我们每访问一个结点，假设之前访问过的结点已经调整成一个排序双向链表，我们再把调整当前结点的指针将其链接到链表的末尾。当所有结点都访问过之后，整棵树也就转换成一个排序双向链表了。

[cpp] view plain copy

BSTreeNode *pHead=NULL;
BSTreeNode *pListIndex=NULL;
// 遍历二元查找树中序
void ergodicBSTree(BSTreeNode * pCurrent)
{
if (NULL == pCurrent) {
return;
}
if (NULL != pCurrent->m_pLeft) {
ergodicBSTree(pCurrent->m_pLeft);
}
// 节点接到链表尾部
convertToDoubleList(pCurrent);
// 右子树为空
if (NULL != pCurrent->m_pRight) {
ergodicBSTree(pCurrent->m_pRight);
}
}
// 二叉树转换成list
void convertToDoubleList(BSTreeNode * pCurrent)
{
pCurrent->m_pLeft = pListIndex;
if (NULL != pListIndex) {
pListIndex->m_pRight = pCurrent;
} else {
pHead = pCurrent;
}
pListIndex = pCurrent;
cout<<pCurrent->m_nValue<<endl;
}

2.设计包含min 函数的栈。定义栈的数据结构，要求添加一个min 函数，能够得到栈的最小元素。要求函数min、push 以及pop 的时间复杂度都是O(1)。

ANSWER:

Stack is a LIFO data structure. When some element is popped from the stack, the status will recover to the original status as before that element was pushed. So we can recover the minimum element, too.

[cpp] view plain copy

#define STACK_LEN 50
typedef struct
{
int val;
int min;
} stack_item;
typedef struct
{
stack_item data[STACK_LEN];
int top;
} stack;
void push(stack *stk, int val)
{
stk->data[++stk->top].val = val;
if (stk->top > 0)
{
if (val < stk->data[stk->top - 1].min)
//如果当前push进的元素小于栈中最小元素
stk->data[stk->top].min = val; //把当前元素置为栈中最小元素
else
//否则，不更新
stk->data[stk->top].min = stk->data[stk->top - 1].min;
}
else
stk->data[stk->top].min = val;
}
int pop(stack *stk)
{
return stk->data[stk->top--].val;
}
int min(stack *stk)
{
return stk->data[stk->top].min;
}

3.求子数组的最大和
题目：
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18。
ANSWER:
A traditional greedy approach.
Keep current sum, slide from left to right, when sum < 0, reset sum to 0.
[cpp] view plain copy

int maxSubarray(int a[], int size) {
if (size<=0) error(“error array size”);
int sum = 0;
int max = - (1 << 31);
int cur = 0;
while (cur < size) {
sum += a[cur++];
if (sum > max) {
max = sum;
} else if (sum < 0) {
sum = 0;
}
}
return max;
}

4.在二元树中找出和为某一值的所有路径
题目：输入一个整数和一棵二元树。
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出和与输入整数相等的所有路径。
例如输入整数22 和如下二元树
10
/ \
5 12
/ \
4 7
则打印出两条路径：10, 12 和10, 5, 7。
二元树节点的数据结构定义为：
[cpp] view plain copy

struct BinaryTreeNode // a node in the binary tree
{
int m_nValue; // value of node
BinaryTreeNode *m_pLeft; // left child of node
BinaryTreeNode *m_pRight; // right child of node
};

ANSWER:
对树进行深度优先遍历，Use backtracking and recurison. We need a stack to help backtracking the path.
[cpp] view plain copy

struct TreeNode {
int data;
TreeNode * left;
TreeNode * right;
};
void printPaths(TreeNode * root, int sum) {
int path[MAX_HEIGHT];
helper(root, sum, path, 0);
}
void helper(TreeNode * root, int sum, int path[], int top) {
path[top++] = root.data;
sum -= root.data;
if (root->left == NULL && root->right==NULL) {
if (sum == 0) printPath(path, top);
} else {
if (root->left != NULL) helper(root->left, sum, path, top);
if (root->right!=NULL) helper(root->right, sum, path, top);
}
top --;
sum -= root.data;
}

5.查找最小的k 个元素
题目：输入n 个整数，输出其中最小的k 个。
例如输入1，2，3，4，5，6，7 和8 这8 个数字，则最小的4 个数字为1，2，3 和4。
ANSWER:
This is a very traditional question...
O(nlogn): cat I_FILE | sort -n | head -n K
O(kn): do insertion sort until k elements are retrieved.
O(n+klogn): Take O(n) time to bottom-up build a min-heap. Then sift-down k-1 times.
So traditional that I don’t want to write the codes...
Only gives the siftup and siftdown function.

参考我的文章“堆结构的运用”：http://blog.csdn.net/zhoudaxia/article/details/5669914
插入排序参考我的文章“排序算法的实现”：http://blog.csdn.net/zhoudaxia/article/details/4586285
第6 题
腾讯面试题：
给你10 分钟时间，根据上排给出十个数，在其下排填出对应的十个数
要求下排每个数都是先前上排那十个数在下排出现的次数。
上排的十个数如下：
【0，1，2，3，4，5，6，7，8，9】
举一个例子，
数值: 0,1,2,3,4,5,6,7,8,9
分配: 6,2,1,0,0,0,1,0,0,0
0 在下排出现了6 次，1 在下排出现了2 次，
2 在下排出现了1 次，3 在下排出现了0 次....
以此类推..

说实话，这题除了一次次迭代尝试外，我没想到什么好的处理办法。假设上排的数组为a，下排对应的数组为b，元素个数为n，按照题目的意思可以得到以下公式：
b1+b2+...+bn=na1*b1+a2*b2+...+an*bn=nb
中的元素来源于a这种一次多项表达式的求解我不会。

我觉得这题比实际上还要复杂，以下情况是必须要考虑的：
1、上排的数据元素并不一定是排序的。
2、上排的数据元素并不一定就有0，可能还有负数。
3、上排的数据元素可能会有重复的。
4、未必有对应的下排数据。

[cpp] view plain copy

#include <iostream.h>
#define len 10
class NumberTB
{
private:
int top[len];
int bottom[len];
bool success;
public:
NumberTB();
int* getBottom();
void setNextBottom();
int getFrequecy(int num);
};
NumberTB::NumberTB()
{
success = false;
//format top
for(int i=0;i<len;i++)
{
top = i;
}
}
int* NumberTB::getBottom()
{
int i = 0;
while(!success)
{
i++;
setNextBottom();
}
return bottom;
}
//set next bottom
void NumberTB::setNextBottom()
{
bool reB = true;
for(int i=0;i<len;i++)
{
int frequecy = getFrequecy(i);
if(bottom != frequecy)
{
bottom = frequecy;
reB = false;
}
}
success = reB;
}
//get frequency in bottom
int NumberTB::getFrequecy(int num) //此处的num即指上排的数 i
{
int count = 0;
for(int i=0;i<len;i++)
{
if(bottom == num)
count++;
}
return count; //cout即对应 frequecy
}
int main()
{
NumberTB nTB;
int* result= nTB.getBottom();
for(int i=0;i<len;i++)
{
cout<<*result++<<endl;
}
return 0;
}

除了上面提到的，就楼主的程序而言，个人觉得有以下几个改进建议：
1、类中success是个多余的东西，如果设置这么一个成员变量，就不应该在函数setNextBottom中再无谓多一个reB变量。
2、由于未必有解，getBottom可能限于死循环。
3、getBottom中变量i完全是多余的。
4、getFrequecy中判断有些是多余的，可以考虑把我上面提到的公司考虑进去。
等有时间了，我再好好考虑如何写个比较好的程序。

第7 题
微软亚院之编程判断俩个链表是否相交。给出俩个单向链表的头指针，比如h1，h2，判断这俩个链表是否相交。为了简化问题，我们假设俩个链表均不带环。
问题扩展：
1.如果链表可能有环列?
2.如果需要求出俩个链表相交的第一个节点列?
ANSWER:
该问题的分析可参考本博客的文章“判断单链表是否存在环以及两个链表是否相交 ”：http://blog.csdn.net/zhoudaxia/article/details/8884402

[cpp] view plain copy

struct Node {
  int data;
  int Node *next;
};
// if there is no cycle.
int isJoinedSimple(Node * h1, Node * h2) {
  while (h1->next != NULL) {
h1 = h1->next;
  }
  while (h2->next != NULL) {
h2 = h2-> next;
  }
  return h1 == h2;
}

// if there could exist cycle
int isJoined(Node *h1, Node * h2) {
  Node* cylic1 = testCylic(h1);
  Node* cylic2 = testCylic(h2);
  if (cylic1+cylic2==0) return isJoinedSimple(h1, h2);
  if (cylic1==0 && cylic2!=0 || cylic1!=0 &&cylic2==0) return 0;
  Node *p = cylic1;
  while (1) {
if (p==cylic2 || p->next == cylic2) return 1;
p=p->next->next;
cylic1 = cylic1->next;
if (p==cylic1) return 0;
  }
}

Node* testCylic(Node * h1) {
  Node * p1 = h1, *p2 = h1;
  while (p2!=NULL && p2->next!=NULL) {
p1 = p1->next;
p2 = p2->next->next;
if (p1 == p2) {
   return p1;
}
  }
  return NULL;
}

   第8 题
此贴选一些比较怪的题，由于其中题目本身与算法关系不大，仅考考思维。特此并作一题。
★有两个房间，一间房里有三盏灯，另一间房有控制着三盏灯的三个开关，这两个房间是分割开的，从一间里不能看到另一间的情况。现在要求受训者分别进这两房间一次，然后判断出这三盏灯分别是由哪个开关控制的。有什么办法呢？
ANSWER:
Skip.
★你让一些人为你工作了七天，你要用一根金条作为报酬。金条被分成七小块，每天给出一块。如果你只能将金条切割两次，你怎样分给这些工人?
ANSWER:
1+2+4;
★用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍。
ANSWER:

[cpp] view plain copy

Node * reverse(Node * head) {
  if (head == NULL) return head;
  if (head->next == NULL) return head;
  Node * ph = reverse(head->next);
  head->next->next = head;
  head->next = NULL;
  return ph;
}
Node * reverseNonrecurisve(Node * head) {
  if (head == NULL) return head;
  Node * p = head;
  Node * previous = NULL;
  while (p->next != NULL) {
p->next = previous;
previous = p;
p = p->next;
  }
  p->next = previous;
  return p;
}

★用一种算法在一个循环的链接表里插入一个节点，但不得穿越链接表。
ANSWER:
I don’t understand what is “Chuanyue”.
★用一种算法整理一个数组。你为什么选择这种方法?
ANSWER:
What is “Zhengli?”
★用一种算法使通用字符串相匹配。
ANSWER:
What is “Tongyongzifuchuan”... a string with “*” and “?”? If so, here is the code.
[cpp] view plain copy

int match(char * str, char * ptn) {
  if (*ptn == ‘\0’) return 1;
  if (*ptn == ‘*’) {
do {
   if (match(str++, ptn+1)) return 1;
} while (*str != ‘\0’);
return 0;
  }
  if (*str == ‘\0’) return 0;
  if (*str == *ptn || *ptn == ‘?’) {
return match(str+1, ptn+1);
  }
  return 0;
}

★颠倒一个字符串。优化速度。优化空间。
[cpp] view plain copy

void reverse(char *str) {
  reverseFixlen(str, strlen(str));
}
void reverseFixlen(char *str, int n) {
  char* p = str+n-1;
  while (str < p) {
char c = *str;
*str = *p; *p=c;
  }
}

★颠倒一个句子中的词的顺序，比如将“我叫克丽丝”转换为“克丽丝叫我”，
实现速度最快，移动最少。
ANSWER:
Reverse the whole string, then reverse each word. Using the reverseFixlen() above.

[cpp] view plain copy

void reverseWordsInSentence(char * sen) {
  int len = strlen(sen);
  reverseFixlen(sen, len);
  char * p = str;
  while (*p!=’\0’) {
while (*p == ‘ ‘ && *p!=’\0’) p++;
str = p;
while (p!= ‘ ‘ && *p!=’\0’) p++;
reverseFixlen(str, p-str);
  }
}

★找到一个子字符串。优化速度。优化空间。
ANSWER:
KMP? BM? Sunday? Using BM or sunday, if it’s ASCII string, then it’s easy to fast access the auxiliary array. Otherwise an hashmap or bst may be needed. Lets assume it’s an ASCII string.

[cpp] view plain copy

int bm_strstr(char *str, char *sub) {
  int len = strlen(sub);
  int i;
  int aux[256];
  memset(aux, sizeof(int), 256, len+1);
  for (i=0; i<len; i++) {
aux[sub = len - i;
  }
  int n = strlen(str);
  i=len-1;
  while (i<n) {
int j=i, k=len-1;
while (k>=0 && str[j--] == sub[k--])
   ;
if (k<0) return j+1;
if (i+1<n)
   i+=aux[str[i+1];
else
   return -1;
  }
}

However, this algorithm, as well as BM, KMP algorithms use O(|sub|) space. If this is not acceptable, Rabin-carp algorithm can do it. Using hashing to fast filter out most false matchings.

[cpp] view plain copy

#define HBASE 127
int rc_strstr(char * str, char * sub) {
  int dest= 0;
  char * p = sub;
  int len = 0;
  int TO_REDUCE = 1;
  while (*p!=’\0’) {
dest = HBASE * dest + (int)(*p);
TO_REDUCE *= HBASE;
len ++;
  }
  int hash = 0;
  p = str;
  int i=0;
  while (*p != ‘\0’) {
if (i++<len) hash = HBASE * dest + (int)(*p);
else hash = (hash - (TO_REDUCE * (int)(*(p-len))))*HBASE + (int)(*p);
if (hash == dest && i>=len && strncmp(sub, p-len+1, len) == 0) return i-len;
p++;
  }
  return -1;
}

★比较两个字符串，用O(n)时间和恒量空间。
ANSWER:
What is “comparing two strings”? Just normal string comparison? The natural way use O(n) time and O(1) space.
[cpp] view plain copy

int strcmp(char * p1, char * p2) {
  while (*p1 != ‘\0’ && *p2 != ‘\0’ && *p1 == *p2) {
p1++, p2++;
  }
  if (*p1 == ‘\0’ && *p2 == ‘\0’) return 0;
  if (*p1 == ‘\0’) return -1;
  if (*p2 == ‘\0’) return 1;
  return (*p1 - *p2); // it can be negotiated whether the above 3 if’s are necessary, I don’t like to omit them.
}

★ 假设你有一个用1001 个整数组成的数组，这些整数是任意排列的，但是你知道所有的整数都在1 到1000(包括1000)之间。此外，除一个数字出现两次外，其他所有数字只出现一次。假设你只能对这个数组做一次处理，用一种算法找出重复的那个数字。如果你在运算中使用了辅助的存储方式，那么你能找到不用这种方式的算法吗?
ANSWER:
方法1：将数据组中的所有元素相加，然后减去1+2+3+...+1000=1000*1001/2；
方法2：使用性质A XOR A XOR B = B。可将这1001个整数与1到1000中的所有数异或，最后必得到这个出现两次的数。

[cpp] view plain copy

int findX(int a[]) {
  int k = a[0];
  for (int i=1; i<=1000;i++)
k ~= a~i;
  }
  return k;
}

★不用乘法或加法增加8 倍。现在用同样的方法增加7 倍。
ANSWER:
n<<3;
(n<<3)-n;

第9 题
判断整数序列是不是二元查找树的后序遍历结果
题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。
如果是返回true，否则返回false。
例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：
8
/ \
6 10
/ \ / \
5 7 9 11
因此返回true。
如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。
ANSWER:
传统问题。根据遍历结果（后序/中序/前序）来构造二叉查找树，涉及二叉树递归是首选。对后序遍历，最后一个元素就是树的根，然后通过根把数组分割成左子树和右子树两部分，分割点在数组第一个大于根的元素处（因为左子树所有元素小于根，右子树所有元素大于根），然后对左右子树进行递归遍历。其实，就是一个后序遍历二叉树的算法。

[cpp] view plain copy

bool verifySquenceOfBST(int squence[], int length)
{
   if(squence == NULL || length <= 0)
         return false;

   // root of a BST is at the end of post order traversal squence
   int root = squence[length - 1];

   // the nodes in left sub-tree are less than the root
   int i = 0;
   for(; i < length - 1; ++ i)
   {
         if(squence > root)
               break;
   }

   // the nodes in the right sub-tree are greater than the root
   int j = i;
   for(; j < length - 1; ++ j)
   {
         if(squence[j] < root)
               return false;
   }

   // verify whether the left sub-tree is a BST
   bool left = true;
   if(i > 0)
         left = verifySquenceOfBST(squence, i);

   // verify whether the right sub-tree is a BST
   bool right = true;
   if(i < length - 1)
         right = verifySquenceOfBST(squence + i, length - i - 1);

   return (left && right);
}

第10 题
翻转句子中单词的顺序。
题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。
句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。
例如输入“I am a student.”，则输出“student. a am I”。

ANSWER:
可以利用堆栈后进先出的特性，把输入先push到堆栈中，然后再pop出来，即反序。

[cpp] view plain copy

#include<iostream>
#include<string>
using namespace std;

class ReverseWords{
public:
ReverseWords(string* wo):words(wo){}
void reverse_()
{
      int length=words->size();
      int begin=-1,end=-1;
      for(int i=0;i<length;++i){
         if(begin==-1&&words->at(i)==' ')
            continue;
         if(begin==-1)
         {
            begin=i;
            continue;
         }
         if(words->at(i)==' ')
            end=i-1;
         else if(i==length-1)
            end=i;
         else
      continue;
         reverse__(begin,end); //1.字母翻转
         begin=-1,end=-1;
      }
      reverse__(0,length-1);    //2.单词翻转
}

private:
void reverse__(int begin,int end) //
{
      while(begin<end)
{
         char t=words->at(begin);
         words->at(begin)=words->at(end);
         words->at(end)=t;
         ++begin;
         --end;
      }
}
string* words;
};


int main(){
string s="I  am a student.";
ReverseWords r(&s);
r.reverse_();
cout<<s<<endl;

return 0;
}

运行结果：
student. a am I

第11题

求二叉树中节点的最大距离...
如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义"距离"为两节点之间边的个数。写一个程序，求一棵二叉树中相距最远的两个节点之间的距离。
ANSWER:
This is interesting... Also recursively, the longest distance between two nodes must be either from root to one leaf, or between two leafs. For the former case, it’s the tree height. For the latter case, it should be the sum of the heights of left and right subtrees of the two leaves’ most least ancestor.
The first case is also the sum the heights of subtrees, just the height + 0.

[cpp] view plain copy

int maxDistance(Node * root) {
  int depth;
  return helper(root, depth);
}
int helper(Node * root, int &depth) {
  if (root == NULL) {
depth = 0; return 0;
  }
  int ld, rd;
  int maxleft = helper(root->left, ld);
  int maxright = helper(root->right, rd);
  depth = max(ld, rd)+1;
  return max(maxleft, max(maxright, ld+rd));
}

第12 题
题目：求1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句（A?B:C）。

方案1：
1+..+n=n*(n+1)/2=(n^2+n)/2
it is easy to get x/2, so the problem is to get n^2
though no if/else is allowed, we can easilly Go around using short-pass. using macro to make it fancier:

[cpp] view plain copy

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

int foo(int n){
  int r=n;
  T(r, n, 0); T(r, n,1); T(r, n, 2); … T(r, n, 31);
  return r >> 1;
}

方案2：

循环只是让相同的代码执行n遍而已，我们完全可以不用for和while达到这个效果。比如定义一个类，我们new一个含有n个这种类型元素的数组，那么该类的构造函数将确定会被调用n次。我们可以将需要执行的代码放到构造函数里。

[cpp] view plain copy

#include <iostream.h>

class Temp
{
public:
   Temp()
   {
      ++N;
      Sum += N;
   }
   static void Reset() { N = 0; Sum = 0; }
   static int GetSum() { return Sum; }

private:
   static int N;
   static int Sum;
};

int Temp::N = 0;
int Temp::Sum = 0;

int solution1_Sum(int n)
{
   Temp::Reset();

   Temp *a = new Temp[n]; //就是这个意思，new出n个数组。
   delete []a;
   a = 0;

   return Temp::GetSum();
}

int main()
{
cout<<solution1_Sum(100)<<endl;
return 0;
}

运行结果：
5050

方案3：
用递归，结合C++的虚函数调用来实现递归终止。既然不能判断是不是应该终止递归，我们不妨定义两个函数。一个函数充当递归函数的角色，另一个函数处理终止递归的情况，我们需要做的就是在两个函数里二选一。从二选一我们很自然的想到布尔变量，比如ture/(1)的时候调用第一个函数，false/(0)的时候调用第二个函数。那现在的问题是如和把数值变量n转换成布尔值。如果对n连续做两次反运算，即!!n，那么非零的n转换为true，0转换为false。

[cpp] view plain copy

#include <iostream.h>

class A;
A* Array[2];

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

class B: public A
{
public:
virtual int Sum (int n) { return Array[!!n]->Sum(n-1)+n; }
};

int solution2_Sum(int n)
{
A a;
B b;
Array[0] = &a;
Array[1] = &b;

int value = Array[1]->Sum(n);
//利用虚函数的特性，当Array[1]为0时，即Array[0] = &a; 执行A::Sum，
//当Array[1]不为0时，             即Array[1] = &b; 执行B::Sum。

return value;
}

int main()
{
cout<<solution2_Sum(100)<<endl;
return 0;
}

方案4：

刚看到这个题目，我的第一想法就是多半用递规解决，接下来难点就是递规如何结束。题目的要求是比较苛刻的，楼主答案里面用的两种方法确实挺巧妙的，但我不会C++，因此只能另外想办法。下面是我写的代码：

[cpp] view plain copy

int sum(int n)
{
      int val = 0;

      n > 0 && (val = n + sum(n - 1));

      return val;
}

虽然功能是实现了，但这个代码编译时是有警告的，当然这个警告不重要。但我总觉得有更加合适的方法。

方案5：
模板元编程，最快捷的计算方式，编译期完成计算。

[cpp] view plain copy

#include <iostream>
using namespace std;

template<int N>
struct CalCls
{
enum {sum = CalCls<N-1>::sum + N};
};

//模板特化，用于终止递归
template<>
struct CalCls<0>
{
enum {sum = 0};
};

int main()
{
cout<<"1+2+3+...+100 = "<<CalCls<100>::sum<<endl;
return 0;
}

第13 题：
题目：输入一个单向链表，输出该链表中倒数第k 个结点。链表的倒数第0 个结点为链表的尾指针。
链表结点定义如下：
[cpp] view plain copy

struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};

答案：

思路1：遍历一次记录链表长度n，然后重新再遍历n-k步。
思路2：稍微有点经验的同志都会想到一种典型的套路。构造两个步长差为k的指针，然后同时移动。设置两个指针p1,p2，首先p1和p2都指向head，p2向前走k步，这样p1和p2之间就间隔k个节点，然后p1和p2同时移动，p2到尾部时，p1到达目标节点。
两种思路的时间复杂度完全相等。

[cpp] view plain copy

Node * lastK(Node * head, int k) {
  if (k<0) error(“k < 0”);
  Node *p=head, *pk=head;
  for (;k>0;k--) {
if (pk->next!=NULL) pk = pk->next;
else return NULL;
  }
  while (pk->next!=NULL) {
p=p->next, pk=pk->next;
  }
  return p;
}

第14 题
题目：输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。
例如输入数组1、2、4、7、11、15 和数字15。由于4+11=15，因此输出4 和11。
ANSWER:
Use two cursors. One at front and the other at the end. Keep track of the sum by moving the cursors.
[cpp] view plain copy

void find2Number(int a[], int n, int dest) {
  int *f = a, *e=a+n-1;
  int sum = *f + *e;
  while (sum != dest && f < e) {
if (sum < dest) sum = *(++f);
else sum = *(--e);
  }
  if (sum == dest) printf(“%d, %d\n”, *f, *e);
}

第15 题：对树做镜像翻转
题目：输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。
例如输入：
8
/ \
6 10
/\ /\
5 7 9 11
输出：
8
/ \
10 6
/\ /\
11 9 7 5
定义二元查找树的结点为：
[cpp] view plain copy

struct BSTreeNode // a node in the binary search tree (BST)
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};

ANSWER:
递归实现：这是递归的基本应用。就是递归翻转树，有子树则递归翻转子树。
非递归实现：由于递归的本质是编译器生成了一个函数调用的栈，因此用循环来完成同样任务时最简单的办法就是用一个辅助栈来模拟递归。首先我们把树的头结点放入栈中。在循环中，只要栈不为空，弹出栈的栈顶结点，交换它的左右子树。如果它有左子树，把它的左子树压入栈中；如果它有右子树，把它的右子树压入栈中。这样在下次循环中就能交换它儿子结点的左右子树了。

[cpp] view plain copy

void swap(Node ** l, Node ** r) {
  Node * p = *l;
  *l = *r;
  *r = p;
}

void mirror(Node * root) {
  if (root == NULL) return;
  swap(&(root->left), &(root->right));
  mirror(root->left);
  mirror(root->right);
}

void mirrorIteratively(Node * root) {
  if (root == NULL) return;
  stack<Node*> buf;
  buf.push(root);
  while (!stack.empty()) {
Node * n = stack.pop();
swap(&(root->left), &(root->right));
if (root->left != NULL) buf.push(root->left);
if (root->right != NULL) buf.push(root->right);
  }
}

第16 题：
题目（微软）：
输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。
例如输入
7
8
/ \
6 10
/ \ / \
5 7 9 11
输出8 6 10 5 7 9 11。
ANSWER:

利用队列做层次遍历，树的层次遍历实际上是广度优先遍历。
由于STL已经为我们实现了一个很好的deque（两端都可以进出的队列），我们只需要拿过来用就可以了。
我们知道树是图的一种特殊退化形式。同时如果对图的深度优先遍历和广度优先遍历有比较深刻的理解，将不难看出这种遍历方式实际上是一种广度优先遍历。因此这道题的本质是在二元树上实现广度优先遍历。

[cpp] view plain copy

#include <deque>
#include <iostream>
using namespace std;

struct BTreeNode // a node in the binary tree
{
   int       m_nValue; // value of node
   BTreeNode  *m_pLeft;  // left child of node
   BTreeNode  *m_pRight; // right child of node
};
BTreeNode* pListIndex;
BTreeNode* pHead;

void PrintFromTopToBottom(BTreeNode *pTreeRoot)
{
   if(!pTreeRoot)
         return;

   // get a empty queue
   deque<BTreeNode *> dequeTreeNode;

   // insert the root at the tail of queue
   dequeTreeNode.push_back(pTreeRoot);

   while(dequeTreeNode.size())
   {
         // get a node from the head of queue
         BTreeNode *pNode = dequeTreeNode.front();
         dequeTreeNode.pop_front();

         // print the node
         cout << pNode->m_nValue << ' ';

         // print its left child sub-tree if it has
         if(pNode->m_pLeft)
               dequeTreeNode.push_back(pNode->m_pLeft);
         // print its right child sub-tree if it has
         if(pNode->m_pRight)
               dequeTreeNode.push_back(pNode->m_pRight);
   }
}

// 创建二元查找树
void addBTreeNode(BTreeNode * & pCurrent, int value)
{
if (NULL == pCurrent)
{
      BTreeNode * pBTree = new BTreeNode();
      pBTree->m_pLeft = NULL;
      pBTree->m_pRight = NULL;
      pBTree->m_nValue = value;
      pCurrent = pBTree;

}
else
{
      if ((pCurrent->m_nValue) > value)
      {
         addBTreeNode(pCurrent->m_pLeft, value);
      }
      else if ((pCurrent->m_nValue) < value)
      {
         addBTreeNode(pCurrent->m_pRight, value);
      }
}
}

int main()
{
BTreeNode * pRoot = NULL;
pListIndex = NULL;
pHead = NULL;
addBTreeNode(pRoot, 8);
addBTreeNode(pRoot, 6);
addBTreeNode(pRoot, 5);
addBTreeNode(pRoot, 7);
addBTreeNode(pRoot, 10);
addBTreeNode(pRoot, 9);
addBTreeNode(pRoot, 11);
PrintFromTopToBottom(pRoot);
return 0;
}

第17 题：
题目：在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。
分析：这道题是2006 年google 的一道笔试题。

思路剖析：
由于题目与字符出现的次数相关，我们可以统计每个字符在该字符串中出现的次数。要达到这个目的，需要一个数据容器来存放每个字符的出现次数。在这个数据容器中可以根据字符来查找它出现的次数，也就是说这个容器的作用是把一个字符映射成一个数字。在常用的数据容器中，哈希表正是这个用途。由于本题的特殊性，我们只需要一个非常简单的哈希表就能满足要求。
由于字符（char)是一个长度为8的数据类型，因此总共有可能256 种可能。于是我们创建一个长度为256的数组，每个字母根据其ASCII码值作为数组的下标对应数组的对应项，而数组中存储的是每个字符对应的次数。这样我们就创建了一个大小为256，以字符ASCII码为键值的哈希表。我们第一遍扫描这个数组时，每碰到一个字符，在哈希表中找到对应的项并把出现的次数增加一次。这样在进行第二次扫描时，就能直接从哈希表中得到每个字符出现的次数了。

[cpp] view plain copy

#include <iostream.h>
#include <string.h>

char FirstNotRepeatingChar(char* pString)
{
   if(!pString)
         return 0;

   const int tableSize = 256;
   unsigned int hashTable[tableSize];
   //初始化hash表
   for(unsigned int i = 0; i < tableSize; ++ i)
         hashTable = 0;

   char* pHashKey = pString;
   while(*(pHashKey) != '\0')
         hashTable[*(pHashKey++)] ++;

   pHashKey = pString;
   while(*pHashKey != '\0')
   {
         if(hashTable[*pHashKey] == 1)
               return *pHashKey;

         pHashKey++;
   }

   return *pHashKey;
}

int main()
{
cout<<"请输入一串字符："<<endl;
char s[100];
cin>>s;
char* ps=s;
cout<<FirstNotRepeatingChar(ps)<<endl;
return 0;
}

第18 题：
题目：n 个数字（0,1,…,n-1）形成一个圆圈，从数字0 开始，每次从这个圆圈中删除第m 个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。当一个数字删除后，从被删除数字的下一个继续删除第m 个数字。求出在这个圆圈中剩下的最后一个数字。
July：我想，这个题目，不少人已经见识过了。

简单的约瑟夫循环问题。先看这个题目的简单变形。
n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来第几号的那个人?
ANSWER:
一般的解答：

[cpp] view plain copy

#include <stdio.h>

int main()
{
int i,k,m,n,num[50],*p;
printf("input number of person:n=");
scanf("%d",&n);

printf("input number of the quit:m=");
scanf("%d",&m);

p=num;
for(i=0;i<n;i++)
      *(p+i)=i+1; //给每个人编号
i=0; //报数
k=0; //此处为3

while(m<n-1)
{
      if(*(p+i)!=0)
         k++;
      if(k==3)
      {
         *(p+i)=0; //退出，对应的数组元素置为0
         k=0;
         m++;
      }
      i++;
      if(i==n)
         i=0;
}
while(*p==0)
      p++;
printf("The last one is NO.%d/n",*p);
return 0;
}

另一种更优雅的方案：

The keys are:
1) if we shift the ids by k, namely, start from k instead of 0, we should add the result by k%n
2) after the first round, we start from k+1 ( possibly % n) with n-1 elements, that is equal to an (n-1) problem while start from (k+1)th element instead of 0, so the answer is (f(n-1, m)+k+1)%n
3) k = m-1, so f(n,m)=(f(n-1,m)+m)%n.

finally, f(1, m) = 0;
Now this is a O(n) solution.

[cpp] view plain copy

int joseph(int n, int m) {
  int fn=0;
  for (int i=2; i<=n; i++) {
fn = (fn+m)%i; }
  return fn;
}

第19 题：
题目：定义Fibonacci 数列如下：
/ 0 n=0
f(n)= 1 n=1
\ f(n-1)+f(n-2) n=2
输入n，用最快的方法求该数列的第n 项。
分析：

在很多C 语言教科书中讲到递归函数的时候，都会用Fibonacci 作为例子。因此很多程序员对这道题的递归解法非常熟悉，但这并不能说明递归解法最适合这道题目。更简单的办法是从下往上计算，首先根据f(0)和f(1)算出f(2)，再根据f(1)和f(2)算出f(3)……，依此类推就可以算出第n项了。很容易理解，这种思路的时间复杂度是O(n)。其实，就是转化为非递归程序，用递推。

[cpp] view plain copy

long long Fibonacci_Solution2(unsigned n)
{
   int result[2] = {0, 1};
   if(n < 2)
         return result[n];

   long long  fibNMinusOne = 1;
   long long  fibNMinusTwo = 0;
   long long  fibN = 0;
   for(unsigned int i = 2; i <= n; ++ i)
   {
         fibN = fibNMinusOne + fibNMinusTwo;

         fibNMinusTwo = fibNMinusOne;
         fibNMinusOne = fibN;
   }

   return fibN;
}

很可惜，这还不是最快的方法。还有一种方法，可达到时间复杂度为O(log n)。可以用矩阵连乘得到： a[2][2]={1,1,1,0} a连乘n次，得到的a[0][1]和a[1][0]就是第n项。因为是连乘，所有可以用快速连乘（秦九韶），复杂度就可以是logN了。

let A=
{1 1}
{1 0}
f(n) = A^(n-1)[0,0]

代码如下：

[cpp] view plain copy

int f(int n) {
  int A[4] = {1,1,1,0};
  int result[4];
  power(A, n, result);
  return result[0];
}

void multiply(int[] A, int[] B, int _r) {
  _r[0] = A[0]*B[0] + A[1]*B[2];
  _r[1] = A[0]*B[1] + A[1]*B[3];
  _r[2] = A[2]*B[0] + A[3]*B[2];
  _r[3] = A[2]*B[1] + A[3]*B[3];
}

void power(int[] A, int n, int _r) {
  if (n==1) { memcpy(A, _r, 4*sizeof(int)); return; }
  int tmp[4];
  power(A, n>>1, _r);
  multiply(_r, _r, tmp);
  if (n & 1 == 1) {
multiply(tmp, A, _r);
  } else {
memcpy(_r, tmp, 4*sizeof(int));
  }
}

第20题：
题目：输入一个表示整数的字符串，把该字符串转换成整数并输出。例如输入字符串"345"，则输出整数345。

此题一点也不简单。不信，你就先不看一下的代码，你自己先写一份，然后再对比一下，便知道了。
1. 转换的思路：每扫描到一个字符，我们把在之前得到的数字乘以10再加上当前字符表示的数字。这个思路用循环不难实现。
2. 由于整数可能不仅仅之含有数字，还有可能以'+'或者'-'开头，表示整数的正负。如果第一个字符是'+'号，则不需要做任何操作；如果第一个字符是'-'号，则表明这个整数是个负数，在最后的时候我们要把得到的数值变成负数。
3. 接着我们试着处理非法输入。由于输入的是指针，在使用指针之前，我们要做的第一件是判断这个指针是不是为空。如果试着去访问空指针，将不可避免地导致程序崩溃。
4. 输入的字符串中可能含有不是数字的字符。每当碰到这些非法的字符，我们就没有必要再继续转换。
5. 最后一个需要考虑的问题是溢出问题。由于输入的数字是以字符串的形式输入，因此有可能输入一个很大的数字转换之后会超过能够表示的最大的整数而溢出。

[cpp] view plain copy

enum Status {kValid = 0, kInvalid};
int g_nStatus = kValid;

int StrToInt(const char* str)
{
   g_nStatus = kInvalid;
   long long num = 0;

   if(str != NULL)
   {
         const char* digit = str;

         // the first char in the string maybe '+' or '-'
         bool minus = false;
         if(*digit == '+')
               digit ++;
         else if(*digit == '-')
         {
               digit ++;
               minus = true;
         }

         // the remaining chars in the string
         while(*digit != '\0')
         {
               if(*digit >= '0' && *digit <= '9')
               {
                     num = num * 10 + (*digit - '0');

                     // overflow
                     if(num > std::numeric_limits<int>::max())
                     {
                           num = 0;
                           break;
                     }

                     digit ++;
               }
               // if the char is not a digit, invalid input
               else
               {
                     num = 0;
                     break;
               }
         }

         if(*digit == '\0')
         {
               g_nStatus = kValid;
               if(minus)
                     num = 0 - num;
         }
   }
   return static_cast<int>(num);
}

第21 题
2010 年中兴面试题
编程求解：

输入两个整数n 和m，从数列1，2，3.......n 中随意取几个数，使其和等于m，要求将其中所有的可能组合列出来。
答案：
这是一个组合产生问题。与第14题差不多。可以使用递归。

[cpp] view plain copy

// 递归方法
//这个，没有任何问题
//from yansha
//July、updated。
#include<list>
#include<iostream>
using namespace std;

list<int>list1;
void find_factor(int sum, int n)
{
// 递归出口
if(n <= 0 || sum <= 0)
      return;

// 输出找到的结果
if(sum == n)
{
      // 反转list
      list1.reverse();
      for(list<int>::iterator iter = list1.begin(); iter != list1.end(); iter++)
         cout << *iter << " + ";
      cout << n << endl;
      list1.reverse();
}

list1.push_front(n);    //典型的01背包问题
find_factor(sum-n, n-1); //放n，n-1个数填满sum-n
list1.pop_front();
find_factor(sum, n-1);    //不放n，n-1个数填满sum
}

int main()
{
int sum, n;
cout << "请输入你要等于多少的数值sum:" << endl;
cin >> sum;
cout << "请输入你要从1.....n数列中取值的n：" << endl;
cin >> n;
cout << "所有可能的序列，如下：" << endl;
find_factor(sum,n);
return 0;
}

第22 题：
有4 张红色的牌和4 张蓝色的牌，主持人先拿任意两张，再分别在A、B、C 三人额头上贴任意两张牌，A、B、C 三人都可以看见其余两人额头上的牌，看完后让他们猜自己额头上是什么颜色的牌，A 说不知道，B 说不知道，C 说不知道，然后A 说知道了。
请教如何推理，A 是怎么知道的。如果用程序，又怎么实现呢？

4张r，4张b，有以下3种组合：rr bb rb
1. B，C全是一种颜色
B C A
bb.rr bb.rr
2. B C A
bb rr bb/RR/BR,=>A:BR
   rr bb =>A:BR
3. B C A
BR BB RR/BR, =>A:BR
推出A:BR的原因：如果 A是RR，那么当ABC都说不知道后，B最后应该知道自己是BR了。因为B不可能是RR或BB。
4. B C A
BR BR BB/RR/BR
推出A:BR的原因：
//i、如果A是BB，那么B=>BR/RR，如果B=>RR，那么一开始，C就该知道自己是BR了（A俩蓝，B俩红）。（如果C,A俩蓝，那么B就一开始知道,如果C.B俩红，那么A一开始就知道，所以论证前头，当B=>RR，那么一开始，C就该知道自己是BR）。如果B=>BR，那么同样道理，C一开始也该知道自己是BR了。
//ii、如果A是RR，类似分析。
//iii、最后，也还是推出=>A:BR
至于程序，暂等高人。
第23 题：
用最简单，最快速的方法计算出下面这个圆形是否和正方形相交。"
3D 坐标系原点(0.0,0.0,0.0)
圆形:
半径r = 3.0
圆心o = (*.*, 0.0, *.*)
正方形:
4 个角坐标;
1:(*.*, 0.0, *.*)
2:(*.*, 0.0, *.*)
3:(*.*, 0.0, *.*)
4:(*.*, 0.0, *.*)
ANSWER
Crap... I totally cannot understand this problem... Does the *.* represent any possible number?

第24 题：
链表操作
（1）.单链表就地逆置，
（2）合并链表

ANSWER
Reversing a linked list. Already done.
What do you mean by merge? Are the original lists sorted and need to be kept sorted? If not, are there any special requirements? I will only do the sorted merging.
就地逆转：

[cpp] view plain copy

ListNode* ReverseIteratively(ListNode* pHead)
{
   ListNode* pReversedHead = NULL;
   ListNode* pNode = pHead;
   ListNode* pPrev = NULL;
   while(pNode != NULL)       //pNode<=>m
   {
         ListNode* pNext = pNode->m_pNext;    //n保存在pNext下

         //如果pNext指为空，则当前结点pNode设为头。
         if(pNext == NULL)
               pReversedHead = pNode;

         //reverse the linkage between nodes
         pNode->m_pNext = pPrev;

         //move forward on the the list
         pPrev = pNode;
         pNode = pNext;
   }
   return pReversedHead;
}

合并有序链表：

[cpp] view plain copy

Node * merge(Node * h1, Node * h2) {
  if (h1 == NULL) return h2;
  if (h2 == NULL) return h1;
  Node * head;
  if (h1->data>h2->data) {  //头结点指向小的节点
head = h2; h2=h2->next;
  } else {
head = h1; h1=h1->next;
  }
  Node * current = head;
  while (h1 != NULL && h2 != NULL) { //把小的节点先链入当前链表
if (h1 == NULL || (h2!=NULL && h1->data>h2->data)) {
   current->next = h2; h2=h2->next; current = current->next;
} else {
   current->next = h1; h1=h1->next; current = current->next;
}
  }
  current->next = NULL;
  return head;
}

第25 题：
写一个函数,它的原形是int continumax(char *outputstr,char *intputstr)
功能：
在字符串中找出连续最长的数字串，并把这个串的长度返回，
并把这个最长数字串付给其中一个函数参数outputstr 所指内存。
例如："abcd12345ed125ss123456789"的首地址传给intputstr 后，函数将返回9，
outputstr 所指的值为123456789
ANSWER:
这个相对比较简单，跟在序列中求最小值差不多。用一个自动机扫描过去就OK了，开始状态，字符状态，数字状态，结束状态。

[cpp] view plain copy

int continumax(char *outputstr, char *inputstr) {
  int len = 0;
  char * pstart = NULL;
  int max = 0;
  while (1) {
if (*inputstr >= ‘0’ && *inputstr <=’9’) {
   len ++;
} else {
   if (len > max) pstart = inputstr-len;
   len = 0;
}
if (*inputstr++==’\0’) break;
  }
  for (int i=0; i<len; i++)
*outputstr++ = pstart++;
  *outputstr = ‘\0’;
  return max;
}

26.左旋转字符串
题目：
定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。
如把字符串abcdef 左旋转2 位得到字符串cdefab。请实现字符串左旋转的函数。
要求时间对长度为n 的字符串操作的复杂度为O(n)，辅助内存为O(1)。
分析：

如果不考虑时间和空间复杂度的限制，最简单的方法莫过于把这道题看成是把字符串分成前后两部分，通过旋转操作把这两个部分交换位置。于是我们可以新开辟一块长度为n+1的辅助空间，把原字符串后半部分拷贝到新空间的前半部分，在把原字符串的前半部分拷贝到新空间的后半部分。不难看出，这种思路的时间复杂度是O(n)，需要的辅助空间也是O(n)。
把字符串看成有两段组成的，记位XY。左旋转相当于要把字符串XY变成YX。我们先在字符串上定义一种翻转的操作，就是翻转字符串中字符的先后顺序。把X翻转后记为XT。显然有(XT)T=X。我们首先对X和Y两段分别进行翻转操作，这样就能得到XTYT。接着再对XTYT进行翻转操作，得到(XTYT)T=(YT)T(XT)T=YX。正好是我们期待的结果。
分析到这里我们再回到原来的题目。我们要做的仅仅是把字符串分成两段，第一段为前面m个字符，其余的字符分到第二段。再定义一个翻转字符串的函数，按照前面的步骤翻转三次就行了。时间复杂度和空间复杂度都合乎要求。

[cpp] view plain copy

#include "string.h"

// Move the first n chars in a string to its end
char* LeftRotateString(char* pStr, unsigned int n)
{
if(pStr != NULL)
{
      int nLength = static_cast<int>(strlen(pStr));
      if(nLength > 0 || n == 0 || n > nLength)
      {
         char* pFirstStart = pStr;
         char* pFirstEnd = pStr + n - 1;
         char* pSecondStart = pStr + n;
         char* pSecondEnd = pStr + nLength - 1;

         // reverse the first part of the string
         ReverseString(pFirstStart, pFirstEnd);
         // reverse the second part of the strint
         ReverseString(pSecondStart, pSecondEnd);
         // reverse the whole string
         ReverseString(pFirstStart, pSecondEnd);
      }
}

return pStr;
}

// Reverse the string between pStart and pEnd
void ReverseString(char* pStart, char* pEnd)
{
if(pStart == NULL || pEnd == NULL)
{
      while(pStart <= pEnd)
      {
         char temp = *pStart;
         *pStart = *pEnd;
         *pEnd = temp;

         pStart ++;
         pEnd --;
      }
}
}

以abcdef为例
1. ab->ba
2. cdef->fedc
原字符串变为bafedc
3. 最后整个翻转一下得到cdefab
时间复杂度为O（n）

另外一种思路：
abc defghi，要abc移动至最后，可以是这样的过程：abc defghi->def abcghi->def ghiabc
使用俩指针，p1指向ch[0]，p2指向ch[m-1]，p2每次移动m 的距离，p1 也跟着相应移动，
每次移动过后，交换。如上第一步，交换abc 和def ，就变成了 abcdef->defabc
第一步，
abc defghi->def abcghi
第二步，继续交换，
def abcghi->def ghiabc
整个过程，看起来，就是abc 一步一步向后移动
abc defghi
def abcghi
def ghi abc
//最后的复杂度是O（m+n）
再举一个例子，如果123 4567890要变成4567890 123：
123 4567890
1. 456 123 7890
2. 456789 123 0
3. 456789 12 0 3
4. 456789 1 0 23
5. 4567890 123 //最后三步，相当于0前移，p1已经不动。

27.跳台阶问题
题目：一个台阶总共有n 级，如果一次可以跳1 级，也可以跳2 级。求总共有多少总跳法，并分析算法的时间复杂度。
这道题最近经常出现，包括MicroStrategy 等比较重视算法的公司，都曾先后选用过个这道题作为面试题或者笔试题。

分析：
首先我们考虑最简单的情况。如果只有1级台阶，那显然只有一种跳法。如果有2级台阶，那就有两种跳的方法了：一种是分两次跳，每次跳1级；另外一种就是一次跳2级。
现在我们再来讨论一般情况。我们把n级台阶时的跳法看成是n的函数，记为f(n)。当n>2时，第一次跳的时候就有两种不同的选择：一是第一次只跳1级，此时跳法数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1)；另外一种选择是第一次跳2级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即为f(n-2)。因此n级台阶时的不同跳法的总数f(n)=f(n-1)+(f-2)。
我们把上面的分析用一个公式总结如下：
/ 1，n=1
f(n)= 2， n=2
/ f(n-1)+(f-2)，n>2
分析到这里，相信很多人都能看出这就是我们熟悉的Fibonacci序列。

[cpp] view plain copy

int jump_sum(int n)  //递归版本
{
assert(n>0);
if (n == 1 || n == 2) return n;
return jump_sum(n-1)+jump_sum(n-2);
}

int jump_sum(int n) //迭代版本
{
assert(n>0);
if (n == 1 || n == 2) return n;

int an, an_1=2, an_2=1;
for (; n>=3; n--)
{
      an = an_2 + an_1;
      an_2 = an_1;
      an_1 = an;
}
return an;
}

28.整数的二进制表示中1 的个数
题目：输入一个整数，求该整数的二进制表达中有多少个1。
例如输入10，由于其二进制表示为1010，有两个1，因此输出2。
分析：
这是一道很基本的考查位运算的面试题。包括微软在内的很多公司都曾采用过这道题。
方案1：使用x&(x-1)技巧，每一次都清除最右边的1，直到x变成0。注意对x为负数此方法仍然适用。

Traditional question. Use the equation xxxxxx10000 & (xxxxxx10000-1) = xxxxxx00000
Note: for negative numbers, this also hold, even with 100000000 where the “-1” leading to an underflow.

[cpp] view plain copy

int countOf1(int n) {
  int c=0;
  while (n!=0) {
n=n & (n-1);
c++;
  }
  return c;
}

方案2：

保持x不变，用一个数来探测x的每一位是否为1。这种方法比较通用。首先x和1做与运算，判断i的最低位是不是为1。接着把1左移一位得到2，再和x做与运算，就能判断x的次高位是不是1……，这样反复左移，每次都能判断x的其中一位是不是1。

[cpp] view plain copy

int NumberOf1_Solution2(int i)
{
   int count = 0;
   unsigned int flag = 1;
   while(flag)
   {
         if(i & flag)
               count ++;

         flag = flag << 1;
   }

   return count;
}

可以看出方案1的时间复杂恰好为1的个数，方案2 的时间复杂度为int类型占的位数，即32，方案1的时间复杂度更优越。

29.栈的push、pop 序列
题目：输入两个整数序列。其中一个序列表示栈的push 顺序，
判断另一个序列有没有可能是对应的pop 顺序。
为了简单起见，我们假设push 序列的任意两个整数都是不相等的。
比如输入的push 序列是1、2、3、4、5，那么4、5、3、2、1 就有可能是一个pop 系列。
因为可以有如下的push 和pop 序列：
push 1，push 2，push 3，push 4，pop，push 5，pop，pop，pop，pop，
这样得到的pop 序列就是4、5、3、2、1。
但序列4、3、5、1、2 就不可能是push 序列1、2、3、4、5 的pop 序列。

ANSWER
This seems interesting. However, a quite straightforward and promising way is to actually build the stack and check whether the pop action can be achieved.
如果我们希望pop的数字正好是栈顶数字，直接pop出栈即可；如果希望pop的数字目前不在栈顶，我们就到push序列中还没有被push到栈里的数字中去搜索这个数字，并把在它之前的所有数字都push进栈。如果所有的数字都被push进栈仍然没有找到这个数字，表明该序列不可能是一个pop序列。

[cpp] view plain copy

int isPopSeries(int push[], int pop[], int n) {
  stack<int> helper;
  int i1=0, i2=0;
  while (i2 < n) {
//pop的数字不在栈顶
while (stack.empty() || stack.peek() != pop[i2])
   if (i1<n)  //继续push
      stack.push(push[i1++]);
   else  //所有数字进栈后都没找到，则不是一个pop序列
      return 0;
//在栈顶，直接pop出栈
while (!stack.empty() && stack.peek() == pop[i2]) {
      stack.pop(); i2++;
   }
  }
  return 1;
}

30.在从1 到n 的正数中1 出现的次数
题目：输入一个整数n，求从1 到n 这n 个整数的十进制表示中1 出现的次数。
例如输入12，从1 到12 这些整数中包含1 的数字有1，10，11 和12，1 一共出现了5 次。
分析：这是一道广为流传的google 面试题。

ANSWER
This is complicated... I hate it...
Suppose we have N=ABCDEFG.
if G<1, # of 1’s in the units digits is ABCDEF, else ABCDEF+1
if F<1, # of 1’s in the digit of tens is (ABCDE)*10, else if F==1: (ABCDE)*10+G+1, else (ABCDE+1)*10
if E<1, # of 1’s in 3rd digit is (ABCD)*100, else if E==1: (ABCD)*100+FG+1, else (ABCD+1)*100
… so on.
if A=1, # of 1 in this digit is BCDEFG+1, else it’s 1*1000000;
so to fast access the digits and helper numbers, we need to build the fast access table of prefixes and suffixes.

[cpp] view plain copy

int countOf1s(int n) {
  int prefix[10], suffix[10], digits[10]; //10 is enough for 32bit integers
  int i=0;
  int base = 1;
  while (base < n) {
suffix = n % base;
digit = (n % (base * 10)) - suffix;
prefix = (n - suffix - digit*base)/10;
i++, base*=10;
  }
  int count = 0;
  base = 1;
  for (int j=0; j<i; j++) {
if (digit[j] < 1) count += prefix;
else if (digit[j]==1) count += prefix + suffix + 1;
else count += prefix+base;
base *= 10;
  }
  return count;
}

方案2：
我们每次判断整数的个位数字是不是1。如果这个数字大于10，除以10之后再判断个位数字是不是1。基于这个思路，不难写出如下的代码：

[cpp] view plain copy

int NumberOf1(unsigned int n);

int NumberOf1BeforeBetween1AndN_Solution1(unsigned int n)
{
   int number = 0;

   // Find the number of 1 in each integer between 1 and n
   for(unsigned int i = 1; i <= n; ++ i)
         number += NumberOf1(i);

   return number;
}

int NumberOf1(unsigned int n)
{
   int number = 0;
   while(n)
   {
         if(n % 10 == 1)
               number ++;

         n = n / 10;
   }

   return number;
}

这个思路比较简单，易于理解。当然有一个非常明显的缺点就是每个数字都要计算1在该数字中出现的次数，因此时间复杂度是O(n)。当输入的n非常大的时候，需要大量的计算，运算效率很低。
31.华为面试题：
一类似于蜂窝的结构的图，进行搜索最短路径（要求5 分钟）
ANSWER
Not clear problem. Skipped. Seems a Dijkstra could do.

32题
有两个序列a,b，大小都为n,序列元素的值任意整数，无序；
要求：通过交换a,b 中的元素，使[序列a 元素的和]与[序列b 元素的和]之间的差最小。
例如:
var a=[100,99,98,1,2, 3];
var b=[1, 2, 3, 4,5,40];

ANSWER
If only one swap can be taken, it is a O(n^2) searching problem, which can be reduced to O(nlogn) by sorting the arrays and doing binary search.
If any times of swaps can be performed, this is a double combinatorial problem.
In the book <<beauty of codes>>, a similar problem splits an array to halves as even as possible. It is possible to take binary search, when SUM of the array is not too high. Else this is a quite time consuming brute force problem. I cannot figure out a reasonable solution.
求解思路2：
当前数组a和数组b的和之差为
A = sum(a) - sum(b)

a的第i个元素和b的第j个元素交换后，a和b的和之差为
A' = sum(a) - a + b[j] - （sum(b) - b[j] + a)
= sum(a) - sum(b) - 2 (a - b[j])
= A - 2 (a - b[j])

设x = a - b[j]
|A| - |A'| = |A| - |A-2x|

假设A > 0,
当x 在 (0,A)之间时，做这样的交换才能使得交换后的a和b的和之差变小，
x越接近A/2效果越好,
如果找不到在(0,A)之间的x，则当前的a和b就是答案。

所以算法大概如下：
在a和b中寻找使得x在(0,A)之间并且最接近A/2的i和j，交换相应的i和j元素，
重新计算A后，重复前面的步骤直至找不到(0,A)之间的x为止。

求解思路3：

[plain] view plain copy

/////////////////////////////////////////
算法
1. 将两序列合并为一个序列，并排序，为序列Source
2. 拿出最大元素Big，次大的元素Small
3. 在余下的序列S[:-2]进行平分，得到序列max，min
4. 将Small加到max序列，将Big加大min序列，重新计算新序列和，和大的为max，小的为min。
////////////////////////////////////////////////

def mean( sorted_list ):
if not sorted_list:
      return (([],[]))

big = sorted_list[-1]
small = sorted_list[-2]
big_list, small_list = mean(sorted_list[:-2])

big_list.append(small)
small_list.append(big)

big_list_sum = sum(big_list)
small_list_sum = sum(small_list)

if big_list_sum > small_list_sum:
      return ( (big_list, small_list))
else:
      return (( small_list, big_list))

tests = [ [1,2,3,4,5,6,700,800],
         [10001,10000,100,90,50,1],
         range(1, 11),
         [12312, 12311, 232, 210, 30, 29, 3, 2, 1, 1]
         ]
for l in tests:
l.sort()
print
print "Source List:/t", l
l1,l2 = mean(l)
print "Result List:/t", l1, l2
print "Distance:/t", abs(sum(l1)-sum(l2))
print '-*'*40

输出结果

[plain] view plain copy

Source List: [1, 2, 3, 4, 5, 6, 700, 800]
Result List: [1, 4, 5, 800] [2, 3, 6, 700]
Distance:    99
-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*

Source List: [1, 50, 90, 100, 10000, 10001]
Result List: [50, 90, 10000] [1, 100, 10001]
Distance:    38
-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*

Source List: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Result List: [2, 3, 6, 7, 10] [1, 4, 5, 8, 9]
Distance:    1
-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*

Source List: [1, 1, 2, 3, 29, 30, 210, 232, 12311, 12312]
Result List: [1, 3, 29, 232, 12311] [1, 2, 30, 210, 12312]
Distance:    21

dxdeng · 发表于 2016-12-8 13:59

好多好不会做

jinguangdi · 发表于 2016-12-8 14:00

看的我睡着了

NullPointer · 发表于 2016-12-8 14:09

dxdeng 发表于 2016-12-8 13:59
好多好不会做

好好学习，业余时间做做，顺便提高下自己，也找到自己的不足

任驰骋 · 发表于 2016-12-8 14:46

直接回复赚个点数，反正我也不懂

hao1234566 · 发表于 2016-12-8 18:13

太难了而且也看不懂。

泽然 · 发表于 2016-12-8 21:13

太长了，看不懂

丶Sasori · 发表于 2016-12-16 10:57

直接回复赚个点数，反正我也不懂

wushaojienigesb · 发表于 2016-12-16 12:56

需要扎实的基础。这是我的感受。。

NullPointer · 发表于 2016-12-16 12:57

wushaojienigesb 发表于 2016-12-16 12:56
需要扎实的基础。这是我的感受。。

确实，我也没几个会的。。。。

帐号		自动登录	找回密码
密码			注册[Register]

[Java 转载] 微软经典部分面试题

个人中心