【读书笔记】剑指offer

导语

所有的编程练习都在牛客网OJ提交，链接: https://www.nowcoder.com/ta/coding-interviews

九章算法的 lintcode 也有这本书的题目。https://www.lintcode.com/ladder/6/

第二章面试需要的基础知识

【面试题3】二维数组中的查找

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

题解：每次删除一行，或者每次删除一列。每次选取数组右上角的数字，如果右上角数字等于target，直接返回true。如果右上角数组小于target，说明这一行都比target小，那么删除这一行。如果右上角数组大于taget，说明这一列都比target大，删除这一列。

 1 class Solution {
 2 public:
 3     bool Find(int target, vector<vector<int> > array) {
 4         int n = array.size();
 5         if (n == 0) {return false;}
 6         int m = array[0].size();
 7         if (m == 0) {return false;}
 8         int right = m - 1,  up = 0;
 9         while (up < n && right >= 0) {
10             if (array[up][right] == target) {
11                 return true;
12             } else if (array[up][right] < target) {
13                 up++;
14             } else if (array[up][right] > target) {
15                 right--;
16             }
17         }
18         return false;
19     }
20 };

View Code

【面试题4】替换空格

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

题解：如果从前往后替换，那么每一段都要往后平移。这样的复杂度是O(n^2)。我们可以优化下这个算法，首先遍历字符串计算出空格的个数。然后新字符串的总长度就是 (原长度 + 2 * 空格数)。用两根指针，一根指向原字符串的末尾，一根指向新字符串的末尾。如果原字符串遇到了空格，新字符串就应该用‘%20’来代替。其他情况一同往前平移。时间复杂度是O(n)

 1 class Solution {
 2 public:
 3     void replaceSpace(char *str,int length) {
 4         if (length == 0) {return;}
 5         //==1.计算空格个数
 6         int cnt = 0;
 7         for (int i = 0; i < length; ++i) {
 8             if (str[i] == ' ') { cnt++; }
 9         }
10         int newLen = length + cnt * 2;
11         //==2.两根指针从右往左
12         int p1 = length - 1, p2 = newLen - 1;
13         while (p1 >= 0 && p2 >= 0) {
14             if (str[p1] == ' ') {
15                 str[p2--] = '0';
16                 str[p2--] = '2';
17                 str[p2--] = '%';
18             } else {
19                 str[p2--] = str[p1];
20             }
21             p1--;
22         }  
23         return ;
24     }
25 };

View Code

【面试题5】从尾到头打印链表

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

题解：我原本以为这个题目用了什么高端技巧，其实不是。我们从头到尾打印链表的值，然后用个vector reverse一下就可以。也可以往数据结构栈上贴，先用个栈保存中间结果，然后在用先进后出的特性存入vector。

 1 /**
 2 *  struct ListNode {
 3 *        int val;
 4 *        struct ListNode *next;
 5 *        ListNode(int x) :
 6 *              val(x), next(NULL) {
 7 *        }
 8 *  };
 9 */
10 class Solution {
11 public:
12     vector<int> printListFromTailToHead(ListNode* head) {
13         vector<int> ans;
14         if (head == 0) {return ans;}
15         ListNode* tail = head;
16         for (; tail; tail = tail->next) {
17             ans.push_back(tail->val);
18         }
19         reverse(ans.begin(), ans.end());
20         return ans;
21     }
22 };

View Code

【面试题6】重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

题解：直接递归重建。

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
13         int r = pre[0];
14         TreeNode* root = new TreeNode(r);
15         auto iter = find(vin.begin(), vin.end(), r);
16         if (iter == vin.end()) {cout << "illegal"; return root; }
17         int k = distance(vin.begin(), iter);
18         int leftSize = k, rightSize = pre.size() - 1 - k;
19         if (leftSize) {
20             vector<int> leftPre(pre.begin()+1, pre.begin()+k+1);
21             vector<int> leftVin(vin.begin(), vin.begin()+k);
22             root->left = reConstructBinaryTree(leftPre, leftVin);
23         }
24         if (rightSize) {
25             vector<int> rightPre(pre.begin()+k+1, pre.end());
26             vector<int> rightVin(iter+1, vin.end());
27             root->right = reConstructBinaryTree(rightPre, rightVin);
28         }
29         return root;
30     }
31 };

View Code

【面试题7】用两个栈实现队列

Leetcode:

https://leetcode.com/problems/implement-queue-using-stacks/

https://leetcode.com/problems/implement-stack-using-queues/ (一个队列可以做，push为 O(n), pop 为O(1))

https://leetcode.com/problems/min-stack/ (两个stack)

用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。

题解：不管是两个栈实现一个队列还是两个队列实现一个栈，看到这题就要知道一定可以做就行了。记忆，push元素的时候我们从第一个栈push，pop元素的时候我们从第二个栈pop。

 1 class Solution
 2 {
 3 public:
 4     void push(int node) {
 5         stack1.push(node);
 6     }
 7 
 8     int pop() {
 9         if (stack2.empty()) {
10             while (!stack1.empty()) {
11                 int node = stack1.top();
12                 stack1.pop();
13                 stack2.push(node);
14             }
15         }
16         if (stack2.empty()) {
17             cout << "err";
18             return -1;
19         }
20         int node = stack2.top();
21         stack2.pop();
22         return node;
23     }
24 
25 private:
26     stack<int> stack1;
27     stack<int> stack2;
28 };

View Code

【面试题8】旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

题解：我知道是二分，但是没法一次AC，有很多边界条件没有考虑。这个题目需要复习review。

 1 class Solution {
 2 public:
 3     int minNumberInRotateArray(vector<int> rotateArray) {
 4         const int n = rotateArray.size();
 5         if (n == 0) {return 0;}
 6         //没有旋转的情况
 7         if (rotateArray[0] < rotateArray[n-1]) {
 8             return rotateArray[0];
 9         }
10         int mid, low = 0, high = n - 1;
11         int ans = INT_MAX;
12         while (rotateArray[low] >= rotateArray[high]) {
13             mid = (low + high) / 2;
14             if ( high - low == 1) {
15                 mid = high;
16                 break;
17             }
18             if (rotateArray[mid] == rotateArray[low] && rotateArray[mid] == rotateArray[high]) {
19                 for (int k = low; k <= high; ++k) {
20                     ans = min(ans, rotateArray[k]);
21                     return ans;
22                 }
23             }
24             if (rotateArray[mid] >= rotateArray[high]) {
25                 low = mid ;
26             } else if (rotateArray[mid] <= rotateArray[low]) {
27                 high = mid ;
28             } 
29         }
30         return rotateArray[mid];
31     }
32 };

View Code

【面试题9】斐波那契数列

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39。

题解：正常写就ok，可以用滚动数组优化。

 1 class Solution {
 2 public:
 3     int Fibonacci(int n) {
 4         if (n == 0) return 0;
 5         vector<int> f(n + 1, 0);
 6         f[0] = 0, f[1] = 1;
 7         for (int i = 2; i < n + 1; ++i) {
 8             f[i] = f[i-2] + f[i-1];
 9         }
10         return f[n];
11     }
12 };

一般写法

 1 class Solution {
 2 public:
 3     int Fibonacci(int n) {
 4         if (n == 0 || n == 1) return n;
 5         int pre = 0, cur = 1;
 6         int ans = 0;
 7         for (int i = 2; i <= n; ++i) {
 8             ans = pre + cur;
 9             pre = cur;
10             cur = ans;
11         }
12         return ans;
13     }
14 };

滚动数组

【面试题9的拓展题】

【一】跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

题解：和面试题9一模一样。

 1 class Solution {
 2 public:
 3     int jumpFloor(int number) {
 4         vector<int> f(number+1, 0);
 5         f[0] = 0, f[1] = 1, f[2] = 2;
 6         for (int k = 3; k < number+1; ++k) {
 7             f[k] = f[k-1] + f[k-2];
 8         }
 9         return f[number];
10     }
11 };

一般写法

 1 class Solution {
 2 public:
 3     int jumpFloor(int number) {
 4         if (number == 0 || number == 1) {return number;} 
 5         int ans = 0, pre = 1, cur = 1;
 6         for (int k = 2; k <= number; ++k) {
 7             ans = pre + cur;
 8             pre = cur;
 9             cur = ans;
10         }
11         return ans;
12     }
13 };

滚动数组

【二】变态跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

题解：f[n] = f[1] + f[2] + f[3] +...+f[n-1] + 1， f[1] = 1, f[2] = 2, f[3] = 4, f[4] = 8, 我们可以从数学归纳法得到 f[n] = 2 ^ (n-1)

 1 class Solution {
 2 public:
 3     int jumpFloorII(int number) {
 4         if (number == 0) return 0;
 5         int ans = 1;
 6         for (int k = 1; k < number; ++k) {
 7             ans *= 2;
 8         }
 9         return ans;
10     }
11 };

View Code

【三】矩阵覆盖

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

题解：f[n-1] --> f[n], f[n-1] = f[n], f[n] = f[n-2] + 2; f[0] = 0, f[1] = 1, f[2] = 2 (这个想法是错的。我对题目的理解有点问题，题目的大矩形已经设定好了必须是2行N列，我搞成了随意一个大矩形）《剑指offer》 P77

我们把 2 * 8 的覆盖方法记为 f(8)，当用第一个 1 * 2 的小矩形去覆盖最左边的时候有两个选择，横着放或者竖着放。当竖着放的时候，右边还剩下 2 * 7的区域，这种情况下的覆盖方法数我们记为 f(7)。接下来考虑横着放的情况，当横着放的时候，下面也必须横着放一个小矩形，所以剩下区域的覆盖方法我们记为 f(6)。所以 f(8) = f(7) + f(6)。这个和斐波那契数列一样的。

 1 class Solution {
 2 public:
 3     int rectCover(int number) {
 4         if (number == 0 || number == 1) {return number;}
 5         int ans, pre = 1, cur = 1;
 6         for (int i = 2; i <= number; ++i) {
 7             ans = pre + cur;
 8             pre = cur;
 9             cur = ans;
10         }
11         return ans;
12     }
13 };

View Code

【面试题10】二进制中1的个数

输入一个整数n，输出该数二进制表示中1的个数。其中负数用补码表示。

题解：书上提出了一种错误的做法是每次把n右移一位，然后和1相&，这种做法是错的，当n是负数的时候，比如 0x80000000，把它右移一位的时候，并不是变成0x40000000，而是0xc00000000。因为移位前是个负数，移位后也依然是个负数，所以移位后最高位会设置成1。如果一直右移，那么最终这个数会变成0xFFFFFFFF。

为了避免右移n，我们可以左移flag。依次判断n的最低位是不是1，次低位是不是1...(这个是常规做法)。

 1 class Solution {
 2 public:
 3      int  NumberOf1(int n) {
 4          unsigned int flag = 1;
 5          int cnt = 0;
 6          while (flag) {
 7              if (flag & n) {
 8                  cnt++;
 9              }
10              flag <<= 1;
11          }
12          return cnt;
13      }
14 };

flag左移方法

还有一种位运算的做法。我们先来分析把一个数减去1的情况。如果一个数不等于0，那么它的二进制表示中起码有一个1。假设这个数的最右边一位是1，那么减去1的时候，最后一位变成0而其他所有位都保持不变。也就是最后移位相当于做了取反操作，由1变成了0。再来谈谈如果最右一位不是1而是0的话，假如这个数的二进制表示最右边的第一个1位于第m位，那么减去1的时候，第m位从1变成了0，m位之后的所有的0都变成了1，而m位之前的所有位保持不变。eg， 1100，它的第二位是从最右边数的第一个1，减去1之后，第二位变成0，的后面的两位变成1，而前面的1保持不变，得到的结果是1011。综合以上两种情况，我们发现把一个数减去1，都是相当于把最右边的1变成了0。如果它右边还有0的话，所有的0都变成了1，而它左边所有位都保持不变。接下来我们把这个整数和它减去1之后的数做与运算，相当于把最右边的1变成了0。eg， n=1100， n-1=1011，n&(n-1) = 1000。我们把上面的分析总结起来就是，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0。那么一个整数的二进制表示中有多少个1，就可以进行多少次这样的操作。

 1 class Solution {
 2 public:
 3      int  NumberOf1(int n) {
 4          int cnt = 0;
 5          while (n) {
 6              cnt++;
 7              n = n & (n - 1);
 8          }
 9          return cnt;
10      }
11 };

位运算解法

【面试题10的拓展题】 p82

第三章高质量的代码

【面试题11】数值的整数次方

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

题解：这个题目的难点在于很多情况，需要分类讨论。如果base为0，或者exponent为正数，负数，或者零的情况。具体的明天再补充，今天累了先休息。

 1 class Solution {
 2 public:
 3     double Power(double base, int exponent) {
 4         if (exponent == 0) {return 1;}
 5         if (equal(base, 0.0)) {
 6             return base;
 7         }
 8         int absExp = exponent;
 9         if (exponent < 0) { absExp = -absExp; }
10         double ans = PowerWithAbsExp(base, absExp);
11         if (exponent < 0) { ans = 1/ans; }
12         return ans;
13     }
14     bool equal(double num1, double num2) {
15         if (num1 - num2 < 0.000000001 && num1 - num2 > -0.000000001) {
16             return true;
17         }
18         return false;
19     }
20     double PowerWithAbsExp(double base, int absExp) {
21         if (absExp == 0) {return 1;}
22         if (absExp == 1) {return base;}
23         double res = PowerWithAbsExp(base, absExp >> 1);
24         res = res * res;
25         if (absExp & 0x1 == 1) {
26             res *= base;
27         }
28         return res;
29     }
30 };

View Code

【面试题12】打印 1 到最大的 n 位数

【面试题13】在 O(1) 时间删除链表节点

【面试题14】调整数组顺序使奇数位于偶数前面（leetcode 905这题没有要求相对位置不变）

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

书上也没有要求交换后的数组相对位置不变。所以这题提供两种思路。

(1) 按照牛客网的题目，要求交换前后相对位置不变的情况下，有点类似与冒泡排序。每一趟都把不符合「前奇后偶」性质的相邻元素交换位置，做n-1趟就可以了。时间复杂度是 O(n^2)

 1 class Solution {
 2 public:
 3     void reOrderArray(vector<int> &array) {
 4         const int n = array.size();
 5         for (int i = 1; i <= n-1; ++i) {
 6             for (int j = 0; j < n - 1; ++j) {
 7                 if (array[j] % 2 == 0 && array[j+1] % 2 == 1) {
 8                     swap(array[j], array[j+1]);
 9                 }
10             }
11         }
12         return;
13     }
14 };

View Code

(2) 按照剑指offer书上和leetcode的题意，没有要求奇数和奇数，偶数和偶数相对位置不变的情况下，我们可以用two pointers扫描一遍就可以解决问题。时间复杂度是 O(n)。

 1 class Solution {
 2 public:
 3     vector<int> sortArrayByParity(vector<int>& A) {
 4         const int n = A.size();
 5         int begin = 0, end = n - 1;
 6         while (begin < end) {
 7             if (begin < n && end >= 0 && A[begin] % 2 == 1 && A[end] % 2 == 0) {
 8                 swap(A[begin], A[end]);
 9                 begin++, end--;
10             }
11             while (begin < n && A[begin] % 2 == 0) { begin++; }
12             while (end >= 0 && A[end] % 2 == 1) { end--; }
13             //printf("begin = %d, end = %d 
", begin, end);
14         }
15         return A;
16     }
17 };

leetcode 905

(3) 除此之外，剑指offer提出了一种工程性拓展的方式，把模式通用化，听说可以秒杀offer。细节等待补充， P104.

【面试题15】链表中倒数第k个结点

输入一个链表，输出该链表中倒数第k个结点。

题解：这个题目其实一开始大家的想法都是先遍历一次链表，数出一共有n个节点，然后倒数第k个节点其实就是从前往后数第 n-(k-1) 个节点（一共遍历两次）。但是，面试官会说我想要一种方法只需要遍历一次链表。blablabla...

我们可以用 two pointers 的解法，第一根指针先走 k-1 步，从第k步开始，两根指针一起往前走，他们的距离保持在 k-1步，当第一根指针指向最后一个节点的时候，第二根指针正好是倒数第k个节点。

注意判头（头节点是空），判尾（第一根指针是否超过了最后一个节点，踩内存），判空（链表为空，或者k大于链表长度n）。

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6             val(x), next(NULL) {
 7     }
 8 };*/
 9 class Solution {
10 public:
11     ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
12         if (!pListHead || k == 0) {return NULL;}
13         ListNode* p1 = pListHead, *p2 = pListHead;
14         for (int i = 0; i < k - 1; ++i) {
15             if (p1->next) {
16                 p1 = p1->next;
17             } else {
18                 return NULL;
19             }
20         }
21         while (p1->next) {
22             p1 = p1->next;
23             p2 = p2->next;
24         }
25         return p2;
26     }
27 };

View Code

PS：书后练习题目有两个相关题目，这两个还没看 P111

【面试题16】反转链表

输入一个链表，反转链表后，输出新链表的表头。

题解：扫描一遍反转链表。3根指针。（这个题目太久没写了，WA了两次，都是在多节点的情况下，eg = {1, 2, 3, 4 ,5}）

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6             val(x), next(NULL) {
 7     }
 8 };*/
 9 class Solution {
10 public:
11     ListNode* ReverseList(ListNode* pHead) {
12         if (!pHead) {return pHead;}
13         ListNode *pre = NULL, *cur = NULL, *ne = pHead;
14         while (ne) {
15             pre = cur;
16             cur = ne;
17             ne = cur->next;
18             cur->next = pre;
19         }
20         return cur;
21     }
22 };

View Code

【面试题17】合并两个排序的链表

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

题解：链表版本的归并排序。（一次过了）

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6             val(x), next(NULL) {
 7     }
 8 };*/
 9 class Solution {
10 public:
11     ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
12     {
13         if (!pHead1) {return pHead2;}
14         if (!pHead2) {return pHead1;}
15         ListNode *p1 = pHead1, *p2 = pHead2, *head = NULL, *tail = NULL;
16         while (p1 && p2) {
17             if (p1->val <= p2->val) {
18                 if (!head) {
19                     tail = head = p1;
20                 } else {
21                     tail = tail->next = p1;
22                 }
23                 p1 = p1->next;
24             } else {
25                 if (!head) {
26                     tail = head = p2;
27                 } else {
28                     tail = tail->next = p2;
29                 }
30                 p2 = p2->next;
31             }
32         }
33         while (p1) {
34             tail = tail->next = p1;
35             p1 = p1->next;
36         }
37         while (p2) {
38             tail = tail->next = p2;
39             p2 = p2->next;
40         }
41         return head;
42     }
43 };

View Code

【面试题18】树的子结构

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

题解：递归查找判断，先在A中找一个和B的根节点值相同的节点，然后递归判断。不行的话换下一个A的节点。

我第一次写理解上有点问题，我认为 B 是 A 的子结构的时候，当B的叶子节点没有子节点的时候，A也必须没有子节点。其实不是这样的。如果在A中找到了B的叶子节点，那么A的这个节点下面可以有别的节点。可以参考P118的例子。

 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };*/
10 class Solution {
11 public:
12     bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
13     {
14         if (!pRoot1 || !pRoot2) {return false;}
15         bool res = false;
16         if (pRoot1->val == pRoot2->val) {
17             res = JudgeSame(pRoot1, pRoot2);
18         }
19         if (!res) {
20             res = HasSubtree(pRoot1->left, pRoot2);
21         }
22         if (!res) {
23             res = HasSubtree(pRoot1->right, pRoot2);
24         }
25         return res;
26     }
27     bool JudgeSame(TreeNode* pRoot1, TreeNode* pRoot2) {
28         if (pRoot2 == NULL) {return true;}
29         if (pRoot1 == NULL) {return false;}
30         if (pRoot1->val != pRoot2->val) {return false;}
31         return JudgeSame(pRoot1->left, pRoot2->left) && JudgeSame(pRoot1->right, pRoot2->right);
32     }
33 };

View Code

第四章解决面试题的思路

【面试题19】二叉树的镜像

操作给定的二叉树，将其变换为源二叉树的镜像

二叉树的镜像定义：源二叉树 
    	    8
    	   /  
    	  6   10
    	 /   / 
    	5  7 9 11
    	镜像二叉树
    	    8
    	   /  
    	  10   6
    	 /   / 
    	11 9 7  5

题解：先交换根节点的左右子树，然后再交换左右子树的孩子节点。（注意我这种写法的时候，要传入入指向指针的指针。）

 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };*/
10 class Solution {
11 public:
12     void Mirror(TreeNode *pRoot) {
13         if (!pRoot) { return; }
14         mirror(&(pRoot->left), &(pRoot->right));
15         return;
16     }
17     void mirror(TreeNode **l, TreeNode **r) {
18         if (!*l && !*r) {return;}
19         //swap(l, r);
20         TreeNode *temp = *l;
21         *l = *r;
22         *r = temp;
23         if (*l) {
24             mirror(&((*l)->left), &((*l)->right));
25         }
26         if (*r) {
27             mirror(&((*r)->left), &((*r)->right));
28         }
29         return;
30     }
31 };

View Code

【面试题20】顺时针打印矩阵(打印蛇形矩阵)

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10。

题解：不涉及什么算法，就是循环变量控制好就行。（还是容易写错，多复习。）

 1 class Solution {
 2 public:
 3     vector<int> printMatrix(vector<vector<int> > matrix) {
 4         vector<int> ans;
 5         int x = 0, y = 0;
 6         const int n = matrix.size();
 7         if (n == 0) {return ans;}
 8         const int m = matrix[0].size();
 9         if (m == 0) {return ans;}
10         int tot = n * m, cnt = 0;
11         int beginx = 0, endx = n - 1, beginy = 0, endy = m - 1;
12         while (cnt < tot) {
13             y = beginy;
14             while (cnt < tot&& y <= endy) {
15                 ans.push_back(matrix[beginx][y]);
16                 cnt++, y++;
17             }
18             ++beginx;
19             x = beginx;
20             while (cnt < tot && x <= endx) {
21                 ans.push_back(matrix[x][endy]);
22                 cnt++, x++;
23             }
24             --endy;
25             y = endy;
26             while (cnt < tot && y >= beginy) {
27                 ans.push_back(matrix[endx][y]);
28                 cnt++, y--;
29             }
30             --endx;
31             x = endx;
32             while (cnt < tot && x >= beginx) {
33                 ans.push_back(matrix[x][beginy]);
34                 cnt++, --x;
35             }
36             ++beginy;
37         }
38         return ans;
39     }
40 };

View Code

【面试题21】包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（在该栈中，调用min，push，以及pop的时间复杂度应为O (1)）。

题解：设置一个数据栈，此外，额外设置一个辅助栈，每次把最小元素压入辅助栈。比如，首先往空的数据栈里面压入数字3，现在3是最小值，我们把3压入辅助栈，接下来往数据栈里面压入数字4，由于4大于之前的最小值3，我们依然往辅助栈里面压入数字3 。

 1 class Solution {
 2 public:
 3     void push(int value) {
 4         s1.push(value);
 5         if (!s2.empty()) {
 6             int t = ::min(value, s2.top());
 7             s2.push(t);
 8         } else {
 9             s2.push(value);
10         }
11     }
12     void pop() {
13         //if (s1.empty()) {cerr << "empty"};
14         s1.pop();
15         s2.pop();
16     }
17     int top() {
18         return s1.top();
19     }
20     int min() {
21         return s2.top();
22     }
23     stack<int> s1, s2;
24 };

View Code

【面试题22】栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

题解：就直接用栈模拟，用压入顺序往栈里放，然后发现弹出弹出顺序的当前元素就在栈顶的时候，就把它弹出。

 1 class Solution {
 2 public:
 3     bool IsPopOrder(vector<int> pushV,vector<int> popV) {
 4         if (pushV.empty() || popV.empty()) {return false;}
 5         stack<int> s;
 6         int idx = 0; //popV;
 7         for (int i = 0; i < pushV.size(); ++i) {
 8             s.push(pushV[i]);
 9             while (!s.empty() && s.top() == popV[idx]) {
10                 ++idx;
11                 s.pop();
12             }
13         }
14         return s.empty();
15     }
16 };

View Code

【面试题23】从上往下打印二叉树

从上往下打印出二叉树的每个节点，同层节点从左至右打印。（二叉树的层级遍历）

题解：BFS

 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };*/
10 class Solution {
11 public:
12     vector<int> PrintFromTopToBottom(TreeNode* root) {
13         vector<int> ans;
14         if (!root) { return ans; }
15         queue<TreeNode*> que;
16         que.push(root);
17         while (!que.empty()) {
18             TreeNode* cur = que.front();
19             que.pop();
20             ans.push_back(cur->val);
21             if (cur->left) { que.push(cur->left); }
22             if (cur->right) { que.push(cur->right);}
23         }
24         return ans;
25     }
26 };

View Code

【面试题24】二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

题解：先找到根节点，然后区分左子树和右子树，递归判断。对于左右子树数组中的每个元素应当判断和根节点的大小关系。

 1 class Solution {
 2 public:
 3     bool VerifySquenceOfBST(vector<int> sequence) {
 4         const int n = sequence.size();
 5         if (n == 0) {return false;}
 6         if (n == 1) {return true;}
 7         int root = sequence.back();
 8         int idx = 0;
 9         while (sequence[idx] < root) {
10             ++idx;
11         }
12         // idx = {0, n-1, middle}
13         vector<int> left(sequence.begin(), sequence.begin()+idx), right(sequence.begin()+idx, sequence.end()-1);
14         bool ansLeft = true, ansRight = true;
15         
16         if (!left.empty()) {
17             ansLeft = VerifySquenceOfBST(left);
18         }
19         if (!right.empty()) {
20             //这里必须要判断，不然可能判断成右子树的数组里面有元素比根节点小。
21             for (int i = 0; i < right.size(); ++i) {
22                 if (right[i] < root) {
23                     return false;
24                 }
25             }
26             ansRight = VerifySquenceOfBST(right);
27         }
28         return ansLeft && ansRight;
29     }
30 };

View Code

【面试题25】二叉树中和为某一值的路径

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

题解：直接dfs。注意写法，如果在dfs中开始判断root是否为空再往ans里面加当前路径的时候，当前路径会被加两次，因为我们会调用 dfs(root->left), dfs(root->right) （叶子节点的root->left 和 root->right 都为空）。所以我答案里面的写法是直接在当前层判断是否满足条件而且是否为叶子节点（是否应该被加在答案里面）。

 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };*/
10 class Solution {
11 public:
12     vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
13         vector<vector<int>> ans;
14         if (!root) {return ans;}
15         vector<int> temp;
16         dfs(root, expectNumber, ans, temp);
17         return ans;
18     }
19     void dfs(TreeNode* root, int leftNumber, vector<vector<int>>& ans, vector<int>& temp) {
20         temp.push_back(root->val);
21         if (!root->left && !root->right && leftNumber - root->val == 0) {
22             ans.push_back(temp);
23         } else {
24             if (root->left) {
25                 dfs(root->left, leftNumber - root->val, ans, temp);
26             }
27             if (root->right) {
28                 dfs(root->right, leftNumber - root->val, ans, temp);
29             }
30         }
31         temp.pop_back();
32         return;
33     }
34 };

View Code

【面试题26】复杂链表的复制

请实现函数 ComplexListNode* Clone(ComplexListNode* pHead) ，复制一个复杂链表。在复杂链表中，每个结点除了有一个 next 指针指向下一个结点之外，还有一个 sibling 指针指向链表的任意结点或者NULL。

牛客网的结点定义如下：

1 struct RandomListNode {
2     int label;
3     struct RandomListNode *next, *random;
4     RandomListNode(int x) :
5             label(x), next(NULL), random(NULL) {
6     }
7 };

题解：这道题有两种解法都还可以。

第一种解法是我们首先复制一个正常链表，先连接next指针，然后每次对于结点N，new出来一个N' 的时候用一个哈希保存 <N, N'>，然后再考虑兄弟结点，直接用map查找对应的结点。这样时间复杂度是O(N), 空间复杂度也是O(N). (leetcode clone graph一样的思路)

 1 /*
 2 struct RandomListNode {
 3     int label;
 4     struct RandomListNode *next, *random;
 5     RandomListNode(int x) :
 6             label(x), next(NULL), random(NULL) {
 7     }
 8 };
 9 */
10 class Solution {
11 public:
12     RandomListNode* Clone(RandomListNode* pHead)
13     {
14         if (!pHead) {return pHead;}
15         unordered_map<RandomListNode*, RandomListNode*> mp;
16         RandomListNode *head = 0, *tail = 0, *cur = pHead;
17         //1.先复制链表
18         while (cur) {
19             if(!head) {
20                 head = tail = new RandomListNode(cur->label);
21                 mp[cur] = tail;
22             } else {
23                 tail = tail->next = new RandomListNode(cur->label);
24                 mp[cur] = tail;
25             }
26             cur = cur->next;
27         }
28         //2. 然后关心一下random指针
29         cur = pHead; tail = head;
30         while (cur) {
31             if (cur->random) {
32                 tail->random = mp[cur->random];
33             }
34             cur = cur->next;
35             tail = tail->next;
36         }
37         return head;
38          
39     }
40 };

View Code

第二种解法是比较惊奇的解法，以前没接触过这种玩法。第一步依旧是根据原始链表的每个结点N创建对应的N'，这一次我们把 N' 链接在 N 后面。

第二步复制 sibling （如果原始链表中的结点N的sibling指向S，那么它的复制结点N' 的sibling指向S的下一个结点S'）。

第三步拆分奇偶链表。

奇怪了，死活过不了。不明觉厉

【面试题27】二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

题解：看到这题完全不会做。抄了答案，一定要复习。

我们在把BST转换成排好序的双向链表的时候，原来指向左儿子的指针调整为链表中指向前一个结点的指针，原来指向右儿子的指针调整成链表中指向后一个结点指针。

 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };*/
10 class Solution {
11 public:
12     TreeNode* Convert(TreeNode* pRootOfTree)
13     {
14         if (!pRootOfTree) { return pRootOfTree; }
15         TreeNode* lastNodeInList = 0;
16         ConvertNode(pRootOfTree, &lastNodeInList);
17         TreeNode* head = lastNodeInList;
18         while (head && head->left) {
19             head = head->left;
20         }
21         return head;
22     }
23     void ConvertNode(TreeNode* pNode, TreeNode** lastNodeInList) {
24         if (!pNode) {
25             return;
26         }
27         if (pNode->left) {
28             ConvertNode(pNode->left, lastNodeInList);
29         }
30         pNode->left = *lastNodeInList;
31         if (*lastNodeInList) {
32             (*lastNodeInList)->right = pNode;
33         }
34         *lastNodeInList = pNode;
35         if (pNode->right) {
36             ConvertNode(pNode->right, lastNodeInList);
37         }
38     }
39 };

View Code

【面试题28】字符串的排列

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

题解：（1）直接用stl的next_permutaion; （2）回溯法(需要复习重新思考为什么这么写就能对。)

 1 class Solution {
 2 public:
 3     vector<string> Permutation(string str) {
 4         const int n = str.size();
 5         vector<string> ans;
 6         if (n == 0) {return ans;}
 7         do {
 8             ans.push_back(str);
 9         } while (next_permutation(str.begin(), str.end()));
10         return ans;
11     }
12 };

next_permutaion

 1 class Solution {
 2 public:
 3     vector<string> Permutation(string str) {
 4         n = str.size();
 5         set<string> ans;
 6         vector<string> ret;
 7         if (n == 0) {return ret;}
 8         backtracking(str, 0, ans, str);
 9         for (auto iter = ans.begin(); iter != ans.end(); ++iter) {
10             ret.push_back(*iter);
11         }
12         return ret;
13     }
14     void backtracking(string& str, int cur, set<string>& ans, string& temp) {
15         if (cur == n) {
16             ans.insert(temp);
17         }
18         for (int i = cur; i < n; ++i) {
19             swap(str[cur], temp[i]);
20             backtracking(str, cur+1, ans, temp);
21             swap(str[cur], temp[i]);
22         }
23     }
24     int n;
25 };

backtracking

【面试题28的拓展题】 P157

【28.1】输入一个含有8个数字的数组，判断有没有可能把这8个数字分别放到正方体的八个顶点上，使得正方体上三组相对的面上的4个顶点的和都相等。

【28.2】八皇后

第五章优化时间和空间效率

【面试题29】数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

题解：本题有两种解法，第一种是基于partition函数的O(n)解法，第二种是「Boyer-Moore Voting」？算法。

第一种解释：基于快速排序的partition. (需要再次理解)

第二种解释：数组中有一个数字出现的次数超过数组的一半，也就是说明它出现的次数比其他所有数字出现的次数之和还多。那么我们遍历数组的时候考虑保存两个值，一个数组中的数字，另外一个是次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1；如果下一个数字和我们之前保存的数字不同，则次数减1。如果次数为零，我们需要保存下一个数字，并且把次数设置为1。我们要找的数字就是最后把次数设置为1的那个数。（但是需要在最后判断这个数字是否真的次数出现超过一半，有可能数组中根本没有次数超过一半的数字。）时间复杂度O(N)，空间复杂度O(1)。

 1 class Solution {
 2 public:
 3     int MoreThanHalfNum_Solution(vector<int> numbers) {
 4         int n = numbers.size();
 5         if (n == 0) {return 0;}
 6         //用一个变量和一个计数器统计
 7         int num = numbers[0], cnt = 1;
 8         for (int i = 1; i < n; ++i) {
 9             if (cnt == 0) {num = numbers[i]; cnt++;}
10             else if (numbers[i] == num) {
11                 cnt++;
12             } else {
13                 cnt--;
14             }
15         }
16         //判断最后的num是否真的超过了数组元素的一半。
17         int times = 0;
18         for (int i = 0; i < n; ++i) {
19            if (numbers[i] == num) {
20                times++;
21            }
22         }
23         return times > n / 2 ? num : 0;
24     }
25 };

View Code

【面试题30】最小的K个数

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

题解：本题有一个O(N)的解法，只有当我们可以修改输入数组的时候可以用（mark下，有空研究下）

第一种解法：O(N)的算法，只有当我们可以修改输入的数组的时候可以用（P167）

第二种解法：O(nlogk)的解法，特别适合处理海量数据。（适合n比较大，k比较小的实际问题）。我们用一个大根堆维护k个元素，当堆里面的元素个数小于k个的时候，就用数组里面的元素往里加，当堆里面的元素等于k个的时候，取堆里面最大的那个元素，判断它和新元素的大小关系，如果它大于新元素，就把它弹出，把新元素放进去。（假设题目是要求从海量数据里面寻找最小的k个数字，由于内存的大小是有限的，有可能不能把这些海量数据一次性全部载入内存。这个时候我们可以借助从硬盘中每次读取一个数字，然后判断是否需要放进堆里面即可。）

 1 class Solution {
 2 public:
 3     vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
 4         priority_queue<int> pq;
 5         const int n = input.size();
 6         //考虑边界问题（k和n的大小比较）
 7         if (n < k || k < 1) {return vector<int>();}
 8         if (n == k) {return input;}
 9 
10         for (int i = 0; i < n; ++i) {
11             if (pq.size() < k) {
12                 pq.push(input[i]);
13             } else if (pq.size() == k) {
14                 int t = pq.top();
15                 if (t > input[i]) {
16                     pq.pop(); 
17                     pq.push(input[i]);
18                 }
19             } 
20         }
21         vector<int> ans;
22         while (!pq.empty()) {
23             ans.push_back(pq.top());
24             pq.pop();
25         }
26         return ans;
27     }
28 };

View Code

【面试题31】连续子数组的最大和（最大子段和）

输入一个整型数组，数组里面有正数也有负数。数组中一个或者连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(N)。

题解：求当前的累加和，如果累加和是负数的话，直接赋值为0。

 1 class Solution {
 2 public:
 3     int FindGreatestSumOfSubArray(vector<int> array) {
 4         int ans = INT_MIN;
 5         const int n = array.size();
 6         if (n == 0) {return ans;}
 7         int temp = 0;
 8         for (int i = 0; i < n; ++i) {
 9             temp = temp + array[i];
10             ans = max(temp, ans);
11             if (temp < 0) {
12                 temp = 0;
13             }
14         }
15         return ans;
16     }
17 };

View Code

【面试题32】从 1 到 n 整数中 1 出现的次数

输入一个整数n，求从 1 到 n 这 n 个整数的十进制表示中 1 出现的次数。例如输入 12，从 1 到 12 这些整数中包含 1 的数字有 1， 10， 11 和 12， 1 一共出现了5次。

题解：编程之美里面也有这道题。但是多了一个小问题。(这题先留着，还没研究好。。。)

【面试题33】把数组排成最小的数

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

题解：给任意两个数字 m 和 n，给出一个排序规则，使得 mn < nm。根据题目的要求，两个数字 m 和 n 能拼接成数字 mn 和 nm。如果 mn < nm，我们应该打印 mn，也就是 m 排在 n 前面，我们这时定义 m 小于 n。反之，如果 nm < mn 我们定义 n < m。如果 mn = nm，那么 m = n。(注意这题可能用 int 类型的数值计算会导致溢出，所以我们可以改成字符串类型进行大小比较和判断。) 这题可能会要求证明，看看就好，剑指offer P179。

 1 class Solution {
 2 public:
 3     string PrintMinNumber(vector<int> numbers) {
 4         const int n = numbers.size();
 5         if (n == 0) {return "";}
 6         vector<string> strNumbers(n);
 7         for (int i = 0; i < n; ++i) {
 8             strNumbers[i] = to_string(numbers[i]);
 9         }
10         sort(strNumbers.begin(), strNumbers.end(), cmp);
11         string ans = "";
12         for (int i = 0; i < n; ++i) {
13             ans += strNumbers[i];
14         }
15         return ans;
16     }
17     static bool cmp(const string &s1, const string &s2) {
18         string str12 = s1 + s2, str21 = s2 + s1;
19         return str12 < str21;
20     }
21 };

View Code

【面试题34】丑数（leetcode 264）

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

题解：根据丑数的定义，丑数应该是另外一个丑数乘以 2， 3，或者 5的结果（除了1）。那么我们可以创建一个数组，里面的数字是排序好的丑数，每一个丑数都是前面的丑数乘以 2， 3，5得到的。思路的关键在于如何确保数组里面的丑数的排好序的。对于原来要乘以2的丑数而言，肯定有那么一个位置 T2，排在它之前的每一个丑数乘以 2 得到的结果都会小于已有最大的丑数，排在它之后的每个丑数乘以 2 得到的结果都会比较大。我们只需要记录下这个T2 的位置就可以了，然后每次生成新的丑数的时候去更新这个 T2。对于乘以 3 和乘以 5 而言，也同样有这个 T3，和 T5。（注意牛客网的 OJ 里面有个 n = 0的边界）

 1 class Solution {
 2 public:
 3     int GetUglyNumber_Solution(int index) {
 4         if (index == 0) {return 0;} //在leetcode上没有这个用例，写代码的时候因为0没有考虑，一直RE。
 5         vector<int> f(index, 0);
 6         f[0] = 1;
 7         int ptr2 = 0, ptr3 = 0, ptr5 = 0;
 8         int minn = 0;
 9         for (int i = 1; i < index; ++i) {
10             int num2 = f[ptr2] * 2, num3 = f[ptr3] * 3, num5 = f[ptr5] * 5;
11             minn = min(num2, min(num3, num5)); //有可能 num2 和 num3 或者这三个数中的两个数值相等，都是minn，比如6， 这个时候两个指针都要往前移动。
12             if (num2 == minn) {
13                 ptr2++;
14             }
15             if (num3 == minn) {
16                 ptr3++;
17             }
18             if (num5 == minn) {
19                 ptr5++;
20             }
21             f[i] = minn;
22         }
23         return f[index-1];
24     }
25 };

View Code

【面试题35】第一个只出现一次的字符

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.

题解：直接用个map求。这个章节的重点是用空间优化时间效率。

 1 class Solution {
 2 public:
 3     int FirstNotRepeatingChar(string str) {
 4         const int n = str.size();
 5         if (n == 0) {return -1;}
 6         map<char, vector<int>> mp;
 7         for (int i = 0; i < n; ++i) {
 8             char c = str[i];
 9             mp[c].push_back(i);
10         }
11         int minPos = n + 1;
12         for (auto iter = mp.begin(); iter != mp.end(); ++iter) {
13             if (iter->second.size() == 1) {
14                 minPos = min(minPos, iter->second[0]);
15             }
16         }
17         return minPos == n + 1 ? -1 : minPos;
18     }
19 };

View Code

【面试题36】数组中的逆序对（重点题，归并排序找逆序对）

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。即输出P%1000000007

题目保证输入的数组中没有的相同的数字

数据范围：

对于%50的数据,size<=10^4

对于%75的数据,size<=10^5

对于%100的数据,size<=2*10^5

题解：

【面试题37】两个链表的第一个公共结点

输入两个链表，找出它们的第一个公共结点。

题解：本题有两种解法，第一种用两个辅助栈，第二种用 2 pointers。

第一种方法：如果两个链表有公共结点，那么公共结点出现在链表的尾部，如果我们从链表的尾部开始比较，最后一个相同的结点就是我们要找的结点。可是单向链表中我们只能从头结点开始遍历。我们想要从尾部开始依次向前比较，那么这种后进先出的操作可以借助栈来完成。分别把两个链表的结点都放进两个栈里，这样两个链表的尾结点就位于栈顶，接下来比较两个栈顶的结点是否相同。如果相同，就 pop 出去，直到找到最后一个相同的结点。时间复杂度 O(m+n)，空间复杂度 O(m+n)。

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6             val(x), next(NULL) {
 7     }
 8 };*/
 9 class Solution {
10 public:
11     //两个辅助栈
12     ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
13         if (!pHead1 || !pHead2) {return NULL;}
14         ListNode *p1 = pHead1, *p2 = pHead2;
15         stack<ListNode*> stk1, stk2;
16         while (p1) {
17             stk1.push(p1);
18             p1 = p1->next;
19         }
20         while (p2) {
21             stk2.push(p2);
22             p2 = p2->next;
23         }
24         ListNode* ret = NULL;
25         while (!stk1.empty() && !stk2.empty() && stk1.top() == stk2.top()) {
26             ret = stk1.top();
27             stk1.pop(), stk2.pop();
28         }
29         
30         return ret;
31     }
32 
33 };

两个辅助栈

第二种方法：先分别求出两个链表的长度，然后让长的那个链表先走到和短的链表一样长的位置，然后两个链表一起走，一起走的时候第一个相等的结点就是第一个公共结点。

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6             val(x), next(NULL) {
 7     }
 8 };*/
 9 class Solution {
10 public:
11     //思路是分别求出 L1 和 L2 的长度， 然后让比较长的那个先走到和短的那个一样长度，然后一起走，一起走相同的第一个结点就是第一个公共结点。
12     ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
13         if (!pHead1 || !pHead2) {return NULL;}
14         int len1 = getLenOfList(pHead1), len2 = getLenOfList(pHead2);
15         int diff = max(len1, len2) - min(len1, len2);
16         ListNode *p1 = pHead1, *p2 = pHead2;
17         if (len1 > len2) {
18             while (diff-- && p1) {
19                 p1 = p1->next;
20             }
21         } else if (len1 < len2) {
22             while (diff-- && p2) {
23                 p2 = p2->next;
24             }  
25         }
26         if (!p1 || !p2) {return NULL;}
27         while (p1 && p2) {
28             if (p1 == p2) {
29                 return p1;
30             } else {
31                 p1 = p1->next;
32                 p2 = p2->next;
33             }
34         }
35         return NULL;
36     }
37     int getLenOfList(ListNode* head) {
38         if (!head) {return 0;}
39         ListNode* cur = head;
40         int len = 0;
41         while (cur) {
42             len++;
43             cur = cur->next;
44         }
45         return len;
46     }
47 };

2 pointers

第六章面试中的各项能力

【面试题38】数字在排序数组中出现的次数

统计一个数字在排序数组中出现的次数。

题解：用二分查找做，时间复杂度是 O(logN)，我是用 lower_bound(), upper_bound() 做的。也可以自己写二分。

 1 class Solution {
 2 public:
 3     int GetNumberOfK(vector<int> data ,int k) {
 4         const int n = data.size();
 5         if (n == 0) {return 0;}
 6         auto iter1 = lower_bound(data.begin(), data.end(), k);
 7         if (iter1 == data.end() || *iter1 != k) {
 8             return 0;
 9         }
10         auto iter2 = upper_bound(data.begin(), data.end(), k);
11         int dis = distance(iter1, iter2);
12         return dis;
13     }
14 };

View Code

【面试题39】二叉树的深度

输入一棵二叉树的根节点，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成的树的一条路径，最长路径的长度为树的深度。

题解：基础题，直接dfs

 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };*/
10 class Solution {
11 public:
12     int TreeDepth(TreeNode* pRoot)
13     {
14         if (!pRoot) {return 0;}
15         int l = TreeDepth(pRoot->left), r = TreeDepth(pRoot->right);
16         return max(l, r) + 1;
17     }
18 };

View Code

【面试题39拓展题】平衡二叉树

输入一棵二叉树，判断该二叉树是否是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过 1 ，那么它就是一棵平衡二叉树。

题解：递归判断。

 1 class Solution {
 2 public:
 3     bool IsBalanced_Solution(TreeNode* pRoot) {
 4         if (!pRoot) {return true;}
 5         int height = 0;
 6         return isBalanced(pRoot, height);
 7     }
 8     bool isBalanced(TreeNode* pRoot, int& height) {
 9         if (!pRoot) {height = 0; return true;}
10         int leftHeight = 0, rightHeight = 0;
11         if (isBalanced(pRoot->left, leftHeight) && isBalanced(pRoot->right, rightHeight)) {
12             int diff = max(leftHeight, rightHeight) - min(leftHeight, rightHeight);
13             if (diff <= 1) {
14                 height = max(leftHeight, rightHeight) + 1;
15                 return true;
16             }
17         }
18         height = max(leftHeight, rightHeight) + 1;
19         return false;
20     }
21 };

View Code

【面试题40】数组中只出现一次的数字

一个整型数组里除了两个数字之外，其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。

题解：

【面试题41】和为S的两个数字 VS 和为S的连续正数序列

【面试题41.1】输入一个递增的数组和一个数字 S，在数组中查找两个数，使得它们的和正好是 S。如果有多对数字的和为 S，输出任意一对即可。（牛客网要求如果多对结果，返回乘积最小的那对）

题解：2 pointers。时间复杂度 O(N)，空间复杂度 O(1).

 1 class Solution {
 2 public:
 3     vector<int> FindNumbersWithSum(vector<int> array,int sum) {
 4         const int n = array.size();
 5         vector<int> ans;
 6         if (n < 2) {return ans;}
 7         int p1 = 0, p2 = n - 1;
 8         long long mul = LLONG_MAX;
 9         while (p1 < p2) {
10             int tempSum = array[p1] + array[p2];
11             if (tempSum == sum) {
12                 long long t = array[p1] * array[p2];
13                 if (t < mul) {
14                     mul = t;
15                     ans = vector<int>{array[p1], array[p2]};
16                 }
17                 p1++, p2--;
18             } 
19             if (tempSum < sum) { p1++; }
20             if (tempSum > sum) { p2--; }
21         }
22         return ans;
23     }
24 };

View Code

【面试题41.2】输入一个正数 S，打印出所有和为 S 的连续正数序列（至少含有两个数）。例如输入 15，由于（1 + 2 + 3 + 4 + 5） =（ 4 + 5 + 6） = （7 + 8）= 15 ，所以结果打印出 3 个连续序列 1 ～ 5， 4 ～ 6， 7 ～ 8。

题解：

【面试题42】翻转单词顺序 VS 左旋转字符串

【面试题42.1】翻转单词顺序

输入一个英文句子，翻转句子中的单词顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串 "I am a student."，则输出 "student. a am I"。

题解：先翻转整个句子，再依次翻转每个单词。（有个注意点，句子的分隔符可能不仅仅是一个空格，可能是多个空格，所以不能用getline，要手动用两根指针。）

 1 class Solution {
 2 public:
 3     string ReverseSentence(string str) {
 4         if (str.empty()) { return str; }
 5         const int n = str.size();
 6         reverse(str.begin(), str.end());
 7         stringstream ss;
 8         ss << str;
 9         int p1 = 0, p2= 0;
10         while (p1 < n && p2 < n) {
11             while (p1 < n && str[p1] == ' ') {
12                 ++p1;
13             }
14             p2 = p1;
15             while (p2 < n && str[p2] != ' ') {
16                 ++p2;
17             }
18             reverse(str.begin() + p1, str.begin() + p2);
19             p1 = p2 + 1;
20         }
21         return str;
22     }
23 };

View Code

【面试题42.2】左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如输入字符串 "abcdefg" 和数字 2，该函数将返回左旋转两位得到的结果 "cdefgab"。

题解：先把前 n 位倒序，然后把剩下的字符串倒序，最后整体倒序。

 1 class Solution {
 2 public:
 3     string LeftRotateString(string str, int n) {
 4         const int len = str.size();
 5         if (len < n) { return str; }
 6         reverse(str.begin(), str.begin()+n);
 7         reverse(str.begin()+n, str.end());
 8         reverse(str.begin(), str.end());
 9         return str;
10     }
11 };

View Code

【面试题43】n个骰子的点数

【面试题44】扑克牌的顺子

【面试题45】圆圈中最后剩下的数字（约瑟夫环）

【面试题46】求 1 + 2 + 3 + 4 + .... + n

【面试题47】不用加减乘除做加法

【面试题48】不能被继承的类

第七章两个面试案例

【面试题49】把字符串转换成整数（atoi）

【面试题50】树中两个结点的最低公共祖先

第八章英文版新增面试题

8.1 数组

【面试题51】数组中重复的数字

【面试题52】构建乘积数组

8.2 字符串

【面试题53】正则表达式匹配

【面试题54】表示数值的字符串

【面试题55】字符流中第一个不重复的字符

8.3 链表

【面试题56】链表中环入口的结点

【面试题57】删除链表中重复的结点

8.4 树

【面试题58】二叉树的下一个结点

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

1 struct TreeLinkNode {
2     int val;
3     struct TreeLinkNode *left;
4     struct TreeLinkNode *right;
5     struct TreeLinkNode *next;
6     TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
7     }
8 };

【面试题59】对称二叉树

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

题解：左子树的左儿子和右子树的右儿子比较，左子树的右儿子和右子树的左儿子比较。

 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };
10 */
11 class Solution {
12 public:
13     bool isSymmetrical(TreeNode* pRoot)
14     {
15         if (!pRoot) { return true; }
16         return isSymmetric(pRoot->left, pRoot->right);
17     }
18     bool isSymmetric(TreeNode* l, TreeNode* r) {
19         if (!l && !r) {return true;}
20         if (!l || !r) {return false;}
21         if (l->val != r->val) {return false;}
22         return isSymmetric(l->left, r->right) && isSymmetric(l->right, r->left);
23     }
24 
25 };

View Code

【面试题60】把二叉树打印成多行

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

题解：BFS

 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };
10 */
11 class Solution {
12 public:
13     vector<vector<int> > Print(TreeNode* pRoot) {
14         vector<vector<int>> ret;
15         if (!pRoot) {return ret;}
16         queue<TreeNode*> que, que2;
17         que.push(pRoot);
18         vector<int> temp;
19         while (!que.empty()) {
20             int size = que.size();
21             while (size--) {
22                 TreeNode* cur = que.front();
23                 que.pop();
24                 temp.push_back(cur->val);
25                 if (cur->left) { que2.push(cur->left); }
26                 if (cur->right) { que2.push(cur->right); }
27             }
28             ret.push_back(temp);
29             temp.clear();
30             swap(que, que2);
31         }
32         return ret;
33     }
34 };

View Code

【面试题61】按照之字形打印二叉树

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

题解：用栈的BFS

 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };
10 */
11 class Solution {
12 public:
13     vector<vector<int> > Print(TreeNode* pRoot) {
14         vector<vector<int>> ans;
15         if (!pRoot) {return ans;}
16         stack<TreeNode*> stk, stk2;
17         stk.push(pRoot);
18         int level = 1;
19         vector<int> temp;
20         while (!stk.empty()) {
21             while (!stk.empty()) {
22                 TreeNode * cur = stk.top();
23                 stk.pop();
24                 temp.push_back(cur->val);
25                 if (level & 1) {
26                     if (cur->left) {stk2.push(cur->left);}
27                     if (cur->right) {stk2.push(cur->right);}
28                 } else {
29                     if (cur->right) {stk2.push(cur->right);}
30                     if (cur->left) {stk2.push(cur->left);}
31                 }
32             }
33             ans.push_back(temp);
34             temp.clear();
35             swap(stk, stk2);
36             level++;
37         }
38         return ans;
39     }
40 };

View Code

【面试题62】序列化二叉树

【面试题63】二叉搜索树的第 k 个结点

【面试题64】数据流中的中位数

8.5 栈和队列

【面试题65】滑动窗口的最大值

8.6 回溯

【面试题66】矩阵中的路径

【面试题67】机器人的运动范围