剑指offer题目（所有题目解答）

面试题63：股票的最大利润

暴力搜索复杂度O(N^2)，换个思路，遍历到某点，只需要记录改点之前最小的点即可，二者之差即为当前最大利润，时间复杂度O(N)

 1 int MaxDiff(vector<int> numbers)
 2 {
 3     int len = numbers.size();
 4     if (len < 2)
 5         return 0;
 6     int min = numbers[0];
 7     int maxDiff = numbers[1] - min;
 8 
 9     for (int i = 2; i < len; i++)
10     {
11         if (numbers[i - 1] < min)
12             min = numbers[i - 1];
13         int currentDiff = numbers[i] - min;
14         if (currentDiff > maxDiff)
15             maxDiff = currentDiff;
16     }
17     return maxDiff;
18 }

View Code

面试题62：圆圈中最后剩下的数字

典型的约瑟夫环的问题，但是需要注意到达链表末尾时需要把指针移到头部

 1 class Solution {
 2 public:
 3     int LastRemaining_Solution(int n, int m)
 4     {
 5        if(n < 1 || m < 1)
 6         return -1;
 7 
 8     unsigned int i = 0;
 9 
10     list<int> numbers;
11     for(i = 0; i < n; ++ i)
12         numbers.push_back(i);
13 
14   auto current = numbers.begin();
15     while(numbers.size() > 1)
16     {
17         for(int i = 1; i < m; ++ i)
18         {
19             current ++;
20             if(current == numbers.end())
21                 current = numbers.begin();
22         }
23 
24        auto next = ++ current;
25         if(next == numbers.end())
26             next = numbers.begin();
27 
28         -- current;
29         numbers.erase(current);
30         current = next;
31     }
32 
33     return *current;
34     }
35 };

View Code

面试题61：扑克牌中的顺子

三步走：排序；统计大小王数量；统计gap数量如果后者小于前者，则可以凑成顺子，反之不行

 1 class Solution {
 2 public:
 3     bool IsContinuous(vector<int> numbers) {
 4         int len = numbers.size();
 5         if (len < 1)
 6             return false;
 7         sort(numbers.begin(), numbers.end());
 8         int numberOfZero = 0;
 9         int numberOfGap = 0;
10         //统计数组中0 的个数
11         for (int i = 0; i < len && numbers[i] == 0; i++)
12             numberOfZero++;
13         int small = numberOfZero;
14         int big = small + 1;
15         while (big < len)
16         {
17             //如果有对子，肯定不是顺子
18             if (numbers[small] == numbers[big])
19                 return false;
20             numberOfGap += numbers[big] - numbers[small] - 1;
21             small = big;
22             big++;
23         }
24         return numberOfZero >= numberOfGap ? true : false;
25     }
26 };

View Code

面试题57-2：和为s的连续正数序列

方法与1类似，遍历然后根据数字求和之后的大小和sum大小之间的关系来确定指针的移动方向，注意while循环的边界条件，while中必须为small<middle，而不能是<=

 1 class Solution {
 2 public:
 3     vector<vector<int> > FindContinuousSequence(int sum) {
 4         vector<vector<int> > res;
 5         if (sum < 3)
 6             return res;
 7         int small = 1;
 8         int big = 2;
 9         int middle = (sum + 1) / 2;
10         int curSum = small + big;
11         while (small < middle)  // 这里千万不要写成 <=,否则在最后一次循环执行过程中，会陷入死循环
12         {
13             if (curSum == sum)
14             {
15                 vector<int> temp;
16                 for (int i = small; i <= big; i++)
17                     temp.push_back(i);
18                 res.push_back(temp);
19             }
20         //解释一下这里为何要将small往前而不是big往后，因为big往后的验证过了
21 
22             while (curSum > sum &&small < middle)  //这里需要注意，两处while条件中 small middle中的符号必须一致，都是<
23             {
24                 curSum -= small;
25                 small++;
26                 if (curSum == sum)
27                 {
28                     vector<int> temp;
29                     for (int i = small; i <= big; i++)
30                         temp.push_back(i);
31                     res.push_back(temp);
32                 }
33             }
34             big++;
35             curSum += big;
36         }
37         return res;
38             
39     }
40 };
41 
42 int main() {
43     Solution A;
44     vector<vector<int> > v;
45     v = A.FindContinuousSequence(3);
46     for (int i = 0; i < v.size(); i++)
47     {
48         for (int j = 0; j < v[i].size(); j++)
49             cout << v[i][j] << " ";
50         cout << endl;
51 
52     }
53     //cout << "hhh" << endl;
54     system("pause");
55     return 0;
56 }

View Code

面试题57：和为s的两个数字

经典的双指针为题，首尾开始往中间遍历

 1 class Solution {
 2 public:
 3     vector<int> FindNumbersWithSum(vector<int> array, int sum) {
 4         vector<int> res;
 5         int ahead = 0;
 6         int behind = array.size() - 1;
 7         while (ahead < behind)
 8         {
 9             if (array[ahead] + array[behind] == sum)
10             {
11                 res.push_back(array[ahead]);
12                 res.push_back(array[behind]);
13                 break;
14             }
15             else if (array[ahead] + array[behind] < sum)
16                 ahead++;
17             else
18                 behind--;
19         }
20         return res;
21     }
22 };

View Code

面试题56-1：数组中数字出现的次数

可以直接排序然后遍历搜索，时间复杂度O(nlogn)

 1 class Solution {
 2 public:
 3     void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
 4         sort(data.begin(),data.end());
 5         int count = 0;
 6         for (int i = 0; i < data.size();)
 7         {
 8             if (data[i] == data[i+1])
 9                  i = i+2;
10             else
11             {
12                 if (count == 0)
13                 {
14                      *num1 = data[i];
15                     count++;
16                     i++;
17                 }
18                 else
19                 {
20                     *num2 = data[i];
21                     break;
22                 }
23             }
24         }
25     }
26 };

View Code

更好的方式是利用数位的异或运算，详细内容请参考书本

面试题55：二叉树的深度

递归的典型应用

 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)
15             return 0;
16         return 1 + max(TreeDepth(pRoot->left),TreeDepth(pRoot->right));
17     }
18 };

View Code

面试题55-2：平衡二叉树

和1挺像，如果调用1中的求深度的函数来构造递归，可以运行，但是会多次重复遍历节点，会存在问题，会有节点多次重复调用

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

View Code

其实可以有改进，做到每个节点只访问一次，也就是后序遍历二叉树时，遍历到某个节点之后记录下来它的深度，就可以一边遍历一遍判断每个节点是否平衡。注意：递归时一定要要传递指针（或者引用）而不是数值

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

View Code

面试题54：二叉搜索树的第K大节点

就是个中序遍历，但是书上代码不是很好理解，其实可以中序遍历所有节点然后读取第k个就可以

 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     TreeNode* KthNode(TreeNode* pRoot, int k)
14     {
15         if (pRoot == nullptr || k == 0)
16             return nullptr;
17         return KthNodeCore(pRoot,k);
18     }
19     TreeNode* KthNodeCore(TreeNode* pRoot, int &k)
20     {
21         TreeNode* temp = nullptr;
22         if (pRoot->left != nullptr)
23             temp = KthNodeCore(pRoot->left, k);
24         if (temp == nullptr)
25         {
26             if (k==1)
27                 temp = pRoot;
28             k--;
29         }
30         if (temp == nullptr && pRoot->right != nullptr)
31             temp = KthNodeCore(pRoot->right, k);
32         return temp;
33     }
34  
35      
36 };

View Code

面试题53-3：数组中数值和下标相等的元素

思路与53-2类似，二分查找

 1 int GetNumberSameAsIndex(vector<int> data)
 2 {
 3     if (data.empty())
 4         return -1;
 5     int lo = 0, hi = data.size() - 1;
 6     while (lo <= hi)
 7     {
 8         int mid = (lo + hi) >> 1;
 9         if (data[mid] > mid)
10             hi = mid - 1;
11         else if (data[mid] < mid)
12             lo = mid + 1;
13         else
14             return mid;
15     }
16     if (lo == data.size())
17         return data.size();
18     return -1;
19     //return data.size();
20 }

View Code

面试题53-2：0~n-1中缺失的数字

可以顺序遍历，但不是最优解法，没有利用数组递增特性，思路与53-1相似，寻找第一个数字与对应下标不一样的元素即可

我自己写的

 1 //这种情我自己写的，也算是做出来了，但是感觉讨论的情况太多，而且很容易出现遗漏或者说数组访问越界
 2 //还是应该学习《剑指offer》的思路
 3 int GetMissingNumber(vector<int> data)
 4 {
 5     int lo = 0, hi = data.size() - 1;
 6     while (lo <= hi)
 7     {
 8         if (data[0] != 0)
 9             return 0;
10         if (data[data.size() - 1] == data.size() - 1)
11             return data.size();
12         int mid = (lo + hi) / 2;
13         if (data[mid] != mid && data[mid - 1] == mid - 1)
14             return mid;
15         else if (data[mid] == mid && data[mid + 1] != mid + 1)
16             return mid + 1;
17         else if (data[mid] == mid && data[mid + 1] == mid + 1)
18             lo = mid + 1;
19         else if (data[mid] != mid && data[mid - 1] != mid - 1)
20             hi = mid - 1;
21     }
22     //return data.size();
23 }

View Code

书上的

 1 int GetMissingNumber(vector<int> data)
 2 {
 3     if (data.empty())
 4         return -1;
 5     int lo = 0, hi = data.size() - 1;
 6     while (lo <= hi)
 7     {
 8         int mid = (lo + hi) >> 1;
 9         if (data[mid] != mid)
10         {
11             if (mid == 0 || data[mid - 1] == mid - 1)
12                 return mid;
13             hi = mid - 1;
14         }
15         else
16             lo = mid + 1;
17     }
18     if (lo == data.size())
19         return data.size();
20     return -1;
21     //return data.size();
22 }

View Code

面试题53-1：在排序数组中查找数字

可以从头到尾数，时间复杂度O(n)

 1 class Solution {
 2 public:
 3     int GetNumberOfK(vector<int> data ,int k) {
 4         int res = 0;
 5         for (int i = 0; i < data.size(); i++)
 6             if (data[i] == k)
 7                 res++;
 8         return res;
 9     }
10 };

View Code

但是没有利用排序特性，一般看见“排序”二字，就应该想到，二分查找，最后可以得到log（n）的复杂度，这道题的关键在于如何寻找第一个该数字和最后一个该数字的位置(牛客网上折腾至少一个半小时，自己写的死活过不去，还是粘贴官方代码然后修改，mmp！！！！)

 1 class Solution {
 2 public:
 3     int GetNumberOfK(vector<int> data ,int k) {
 4         int number = 0;
 5 
 6     if(data.size() > 0)
 7     {
 8         int first = GetFirstK(data, k, 0, data.size() - 1);
 9         int last = GetLastK(data, k, 0, data.size() - 1);
10         
11         if(first > -1 && last > -1)
12             number = last - first + 1;
13     }
14     return number;
15     }
16     
17     int GetFirstK(vector<int> data, int k, int start, int end)
18 {
19     if(start > end)
20         return -1;
21 
22     int middleIndex = (start + end) / 2;
23     int middleData = data[middleIndex];
24 
25     if(middleData == k)
26     {
27         if((middleIndex > 0 && data[middleIndex - 1] != k) 
28             || middleIndex == 0)
29             return middleIndex;
30         else
31             end  = middleIndex - 1;
32     }
33     else if(middleData > k)
34         end = middleIndex - 1;
35     else
36         start = middleIndex + 1;
37 
38     return GetFirstK(data, k, start, end);
39 }
40 
41 // 找到数组中最后一个k的下标。如果数组中不存在k，返回-1
42 int GetLastK(vector<int> data, int k, int start, int end)
43 {
44     if(start > end)
45         return -1;
46 
47     int middleIndex = (start + end) / 2;
48     int middleData = data[middleIndex];
49 
50     if(middleData == k)
51     {
52         if((middleIndex < data.size() - 1 && data[middleIndex + 1] != k) 
53             || middleIndex == data.size() - 1)
54             return middleIndex;
55         else
56             start  = middleIndex + 1;
57     }
58     else if(middleData < k)
59         start = middleIndex + 1;
60     else
61         end = middleIndex - 1;
62 
63     return GetLastK(data, k, start, end);
64 }
65 };

View Code

次日早上重新学习之后自己编写完成上面的程序，一个循环，一个递归，调试一下居然通过了，开心，编程序就是这样，很多技巧书本无法交给我们，只能依靠自己一次次碰壁来获得，加油，希望这是一个好的开始，然后有一个坚持，就酱紫！——2018.06.16

 1 class Solution {
 2 public:
 3     int GetNumberOfK(vector<int> data ,int k) {
 4         int res = 0;
 5         if (data.empty())
 6             return res;
 7         int first = getFirstK(data,k,0,data.size()-1);
 8         int last = getLastK(data,k,0,data.size()-1);
 9         if (first != -1 && last != -1)
10             return last - first + 1;
11         return res;
12         
13     }
14     //递归写法
15     int getFirstK(vector<int> data, int k, int lo, int hi)
16     {
17         if (lo > hi)   //这里很重要，是递归的终止条件
18             return -1;
19         int mid = (lo + hi )/ 2;
20         if (data[mid] > k)
21             return getFirstK(data,k,lo,mid - 1);
22            // hi = mid - 1;
23         else if (data[mid] < k)
24             return getFirstK(data,k,mid+1,hi);
25             // lo = mid + 1;
26         else //if (data[mid] == k)
27         {
28             if (mid == 0 || data[mid - 1] != k)
29                 return mid;
30             else
31                 return getFirstK(data,k,lo,mid - 1);
32         }
33         return -1;
34     }
35     
36     //循环写法
37     int getLastK(vector<int> data, int k, int lo, int hi)
38     {
39         int mid = (lo + hi) / 2;
40         while (lo <= hi)
41         {
42             if (data[mid] > k)
43                 hi = mid - 1;
44             else if (data[mid] < k)
45                 lo = mid + 1;
46             else //if (data[mid] == k)
47         {
48             if (mid == data.size()-1 || data[mid + 1] != k)
49                 return mid;
50             else
51                 lo = mid + 1;
52         }
53             mid = (lo + hi)/2;
54         }
55         return -1;
56     }
57 };

View Code

牛客评论区看见的更巧的解法，寻找k-0.5和k+0.5这俩数字的位置，然后相减即可

 1 class Solution {
 2 public:
 3     int GetNumberOfK(vector<int> data ,int k) {
 4         return biSearch(data, k+0.5) - biSearch(data, k-0.5) ;
 5     }
 6 private:
 7     int biSearch(const vector<int> & data, double num){
 8         int s = 0, e = data.size()-1;     
 9         while(s <= e){
10             int mid = (e - s)/2 + s;
11             if(data[mid] < num)
12                 s = mid + 1;
13             else if(data[mid] > num)
14                 e = mid - 1;
15         }
16         return s;
17     }
18 };

View Code

牛客网，循环与递归的写法

 1 public class Solution {
 2     public int GetNumberOfK(int [] array , int k) {
 3         int length = array.length;
 4         if(length == 0){
 5             return 0;
 6         }
 7         int firstK = getFirstK(array, k, 0, length-1);
 8         int lastK = getLastK(array, k, 0, length-1);
 9         if(firstK != -1 && lastK != -1){
10              return lastK - firstK + 1;
11         }
12         return 0;
13     }
14     //递归写法
15     private int getFirstK(int [] array , int k, int start, int end){
16         if(start > end){
17             return -1;
18         }
19         int mid = (start + end) >> 1;
20         if(array[mid] > k){
21             return getFirstK(array, k, start, mid-1);
22         }else if (array[mid] < k){
23             return getFirstK(array, k, mid+1, end);
24         }else if(mid-1 >=0 && array[mid-1] == k){
25             return getFirstK(array, k, start, mid-1);
26         }else{
27             return mid;
28         }
29     }
30     //循环写法
31     private int getLastK(int [] array , int k, int start, int end){
32         int length = array.length;
33         int mid = (start + end) >> 1;
34         while(start <= end){
35             if(array[mid] > k){
36                 end = mid-1;
37             }else if(array[mid] < k){
38                 start = mid+1;
39             }else if(mid+1 < length && array[mid+1] == k){
40                 start = mid+1;
41             }else{
42                 return mid;
43             }
44             mid = (start + end) >> 1;
45         }
46         return -1;
47     }
48 }

View Code

面试题42：连续子数组最大和

动态规划的思想，线性复杂度，数组中某个数字之前的所有数字的和如果小于0，那就不用再考虑了，加上只有比本身还小，无意义

 1 class Solution {
 2 public:
 3     int FindGreatestSumOfSubArray(vector<int> array) {
 4         if (array.size() < 1)
 5             return 0;
 6         int nCurSum = 0;
 7         int nGreatestSum = INT_MIN;
 8         for (int i = 0; i < array.size(); i++)
 9         {
10             if (nCurSum <= 0)
11                 nCurSum = array[i];
12             else
13                 nCurSum += array[i];
14             if (nCurSum > nGreatestSum)
15                 nGreatestSum = nCurSum;
16         }
17         return nGreatestSum;
18 
19     }
20     };

View Code

二刷：AC

面试题36：二叉搜索树与双向链表

这道题主要涉及中序遍历，以及指针方向的调整，难点在于递归的过程，个人认为递归并不需要知道细节，只需要卡准更简单的递归形式和递归的终止条件即可，根本不需要单步调试，详细过程参看书本

代码如下：

 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     TreeNode* Convert(TreeNode* pRootOfTree)
14     {
15         TreeNode *pLastNodeInList = nullptr;
16         ConvertCore(pRootOfTree,&pLastNodeInList);
17         TreeNode *head = pLastNodeInList;
18         while (head != nullptr && head->left != nullptr)
19             head = head->left;
20         return head;
21     }
22      
23     void ConvertCore(TreeNode *pNode, TreeNode **pLastNodeInList)
24     {
25         if (pNode == nullptr)
26             return;
27         TreeNode *cur = pNode;
28         if (pNode->left != nullptr)
29             ConvertCore(pNode->left,pLastNodeInList);
30         cur->left = *pLastNodeInList;
31         if (*pLastNodeInList != nullptr)
32             (*pLastNodeInList)->right = cur;
33         *pLastNodeInList = cur;
34         if (cur->right != nullptr)
35             ConvertCore(cur->right,pLastNodeInList);
36     }
37 };

View Code

面试题35：复杂链表的赋值

思路很直接，三步走：1、赋值节点并连接在原节点后方；2、还原新节点的random指针；3、拆分链表

代码如下：

 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)
15             return nullptr;
16         RandomListNode *pNode = pHead;
17         while (pNode)
18         {
19             RandomListNode *pCloned = new RandomListNode(pNode->label);
20             pCloned->next = pNode->next;
21             pNode->next = pCloned;
22             pNode = pCloned->next;
23         }
24         pNode = pHead;
25         while (pNode)
26         {
27             if (pNode->random)
28                 pNode->next->random = pNode->random->next;
29             pNode = pNode->next->next;
30         }
31         RandomListNode *newHead = pHead->next;
32         pNode = pHead;
33        while (pNode)
34         {
35             RandomListNode *l1 = pNode->next;
36             pNode->next = l1->next;
37            pNode = pNode->next;
38            if (l1->next)
39             l1->next = l1->next->next;
40         }
41          /*for (l1 = pHead; l1 != nullptr; l1 = l1->next)
42         {
43             l2 = l1->next;
44             l1->next = l2->next;
45             if (l2->next != nullptr)
46             l2->next = l2->next->next;
47         }*/
48         return newHead;
49     }
50 };

View Code

2018-03-22二刷：前两步没问题，最后一步折腾我很久，最后才知道是处理最后一个节点的null时出问题了，我不小心修改了原链表末尾的null。链表类题目一定要小心头和尾部；另外，用while循环自己一定要处理好循环变量的增加与范围。

面试题33：二叉搜索树的后序遍历序列

书上的思路不难理解，利用递归进行，但是把书上的内容生搬硬套使用向量这让我很不爽，郁闷中……

代码如下：

 1 class Solution {
 2 public:
 3     bool VerifySquenceOfBST(vector<int> sequence) {
 4         int len = sequence.size();
 5         if (len == 0)
 6             return false;
 7         int* array = new int[len];
 8         for (int i = 0; i < len; i++)
 9             array[i] = sequence[i];
10         return  myVerifySquenceOfBST(array,len);
11     }
12     bool myVerifySquenceOfBST(int sequence[], int length)
13     {
14         if (sequence == nullptr || length <= 0)
15             return false;
16         int root = sequence[length - 1];
17         //二叉搜索树中左子树节点值小于根节点的值
18         int i = 0;
19         for (; i < length - 1; i++)
20             if (sequence[i]>root)
21                 break;
22         int j = i;
23         for (; j < length - 1; j++)
24             if (sequence[j] < root)
25                 return false;
26         //判断左子树是否为二叉树；
27         bool left = true;
28         if (i > 0)
29             left = myVerifySquenceOfBST(sequence, i);
30         //判断右子树是否为二叉树；
31         bool right = true;
32         if (i < length - 1)
33             right = myVerifySquenceOfBST(sequence + i, length - 1 - i);
34         return left&&right;
35 
36         
37     }
38     
39 };

View Code

面试题32-3：之字形打印二叉树

与32-1类似，可以看做是层序遍历的变种，牛客网上的解答仍然是利用层序遍历，只是在偶数层的vector需要调用reverse函数进行翻转；《剑指offer》书上提供的解法则是是用来两个栈

代码如下：

 1 struct TreeNode {
 2 int val;
 3 struct TreeNode *left;
 4 struct TreeNode *right;
 5 TreeNode(int x) :
 6 val(x), left(NULL), right(NULL) {
 7 }
 8 };
 9 
10 //这道题本质上也是一个层序遍历,只是偶数层需要反序；书上给的方法是两个栈
11 //我个人觉得有点绕，牛客网上的解答有的是用层序遍历，调用reverse函数反转偶数层
12 //但是有人说自己面试时用reverse被面试官批评，海量数据用这个会很慢
13 //我最开始的思路是用双端队列来做，因为双端队列本身就兼具队列和栈的特性
14 //实践之后证明双端队列并不好用，尽量少用，不伦不类，容易混乱
15 //这里队列存的是指针而非数值，涉及到访问左右子节点的问题，必须仔细，这也是用双端队列不方便的地方
16 class Solution
17 {
18 public:
19     vector<vector<int> > Print(TreeNode* pRoot)
20     {
21         vector<vector<int>> res;
22         if (pRoot == nullptr)
23             return res;
24         queue<TreeNode*> nodes;
25         bool even = false;
26         nodes.push(pRoot);
27         while (!nodes.empty())
28         {
29             vector<int> vec;
30             int size = nodes.size();
31             for (int i = 0; i < size; i++)
32             {
33                 TreeNode* pNode = nodes.front();
34                 nodes.pop();
35                 vec.push_back(pNode->val);
36                 if (pNode->left != nullptr)
37                     nodes.push(pNode->left);
38                 if (pNode->right != nullptr)
39                     nodes.push(pNode->right);
40             }
41             if (even)
42                 reverse(vec.begin(), vec.end());
43             even = !even;
44             res.push_back(vec);
45         }
46         return res;
47     }
48 
49 };

View Code

面试题32-2：分行从上到下方打印二叉树（层序遍历/广度优先遍历）

与32-1类似，但是细节方面略有差异，实现上是用的向量的向量

代码如下：

 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> > result;  //类似于二维数组
15         if (pRoot == nullptr)
16             return  result;
17         queue<TreeNode*> nodes;  //建立一个队列，存放层序遍历的节点
18         nodes.push(pRoot);
19         while (!nodes.empty())
20         {
21             vector<int> nodesInLevel; //存放每一层的节点，其实是局部变量，每次循环结束之后会自动释放的
22             int lo = 0, hi = nodes.size();//队列中元素始末位置，要求队列中元素是二叉树中一层的元素
23             while (lo < hi)
24             {
25                 TreeNode* temp = nodes.front();  //这里其实应该考虑要不要释放的
26                 nodesInLevel.push_back(temp->val);
27                 nodes.pop();
28                 if (temp->left) nodes.push(temp->left);
29                 if (temp->right) nodes.push(temp->right);
30                 lo++;
31             }
32             result.push_back(nodesInLevel);
33         }
34         return result;
35     }
36 
37 };

View Code

面试题32-1：从上到下方打印二叉树（层序遍历/广度优先遍历）

先访问的节点其子节点也会被先访问，符合队列的特征

代码如下：

 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<int> PrintFromTopToBottom(TreeNode* root) {
14         vector<int> result;
15         if (root == nullptr)   //这里必须加上对空指针的处理，否则牛客网会报“段错误”
16             return result;
17         deque<TreeNode*> dequeTreeNode;//利用队列来实现；
18         dequeTreeNode.push_back(root);
19         while (dequeTreeNode.size())
20         {
21             TreeNode* pNode = dequeTreeNode.front();
22             result.push_back(pNode->val);
23             dequeTreeNode.pop_front();
24             if (pNode->left)
25                 dequeTreeNode.push_back(pNode->left);
26             if (pNode->right)
27                 dequeTreeNode.push_back(pNode->right);
28         }
29         return result;
30     }
31 };

View Code

面试题31：栈的压入、弹出序列

利用辅助栈，重现栈的压入弹出操作。

代码如下：

 1 class Solution {
 2 public:
 3     bool IsPopOrder(vector<int> pushV, vector<int> popV) 
 4     {
 5         if (pushV.empty() || popV.empty() || pushV.size() != popV.size())
 6             return false;
 7         std::stack<int> sta;    //辅助栈
 8         int pPop = 0;//用来记录弹出序列的读取位置
 9         //读取栈的压入序列，压入sta，当读到的数字与弹出序列pPop对应
10         //的数字相同，弹出该数字，pPop+1
11         //重复以上过程，若sta最后为空，则该序列是压栈序列的弹出序列，否则不是
12         for (int i = 0; i < pushV.size(); i++)
13         {
14             sta.push(pushV[i]);
15             while (!sta.empty() && sta.top() == popV[pPop])
16             {
17                 sta.pop();
18                 pPop++;
19             }
20         }
21         if (sta.empty())
22             return true;
23         return false;
24     }
25 };

View Code

面试题30：包含min函数的栈

这道题应当学会把抽象问题具体化。可以画图分析。关键点在于利用辅助栈处理，辅助栈中包含的是当前情况下的最小的元素

代码如下：

 1 class Solution {
 2 public:
 3     void push(int value) {
 4         m_data.push(value);
 5         if (m_min.empty() || value < m_min.top())
 6             m_min.push(value);
 7         else
 8             m_min.push(m_min.top());
 9 
10     }
11     void pop() {
12         m_data.pop();
13         m_min.pop();
14     }
15     int top() {
16         return m_data.top();
17     }
18     int min() {
19         return m_min.top();
20     }
21 private:
22     std::stack<int> m_data;
23     std::stack<int> m_min;
24 };

View Code

面试题29：顺时针打印矩阵

主要是两部分，一是确定打印的圈数，二是确定打印一圈的操作，注意打印一圈时，需要判断什么情况下需要打印第二、第三、第四步

一刷：没控制好打印一圈的条件，测试用例显示出现重复打印

代码如下：

 1 //牛客网
 2 class Solution {
 3 public:
 4     vector<int> printMatrix(vector<vector<int> > matrix) {
 5         int rows = matrix.size();   //矩阵行数
 6         int cols = matrix[0].size(); //矩阵列数
 7         int start = 0; //左上角的起始标号（start，start）
 8         vector<int> result;
 9         //打印一圈的操作
10         while (rows > start * 2 && cols > start * 2)
11         {
12             int endX = cols - 1 - start;  //终止行号
13             int endY = rows - 1 - start;   //终止列号
14             
15             //第一次写这部分代码连续写了4个for循环，最后只通过了部分测试用例
16             //原因在于第一步是所有的矩阵都需要的，但是后面三步却未必，需要判断是否需要打印，否则会有重复
17             //从左到右打印一行
18             for (int i = start; i <= endX; i++)
19                 result.push_back(matrix[start][i]);  //像访问数组一样访问向量的向量
20             //从上到下打印一列
21             if (start < endY)
22             {
23                 for (int i = start + 1; i <= endY; i++)
24                     result.push_back(matrix[i][endX]);
25             }
26             //从右到左打印一行
27             if (start < endX&&start < endY)
28             {
29                 for (int i = endX - 1; i >= start; i--)
30                     result.push_back(matrix[endY][i]);
31             }
32             //从下到上打印一列
33             if (start < endX&&start < endY - 1)
34             {
35                 for (int i = endY - 1; i >= start + 1; i--)
36                     result.push_back(matrix[i][start]);
37             }
38             ++start;
39         }
40         return result;
41     }
42 };

View Code

面试题26：树的子结构

递归思想，主要是确定递归终止情况，并且确定具有更简单参数的递归调用

一刷：DoesTree1HaveTree2函数中return后面是递归函数，参数写错了，应该是左右子树分别匹配；

代码如下：

 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         //由于val是int类型的，所以可以用“==”直接判断是否相等
15         //否则就需要去写个equal函数来判断double或者float是否相等
16         
17         bool result = false;
18         //初次运行HasSubtree函数，两个指针必须都是非空,否则直接返回false
19         if (pRoot1 != nullptr&&pRoot2 != nullptr)
20         {
21             //若根节点相同，继续判断树1中以R为根节点的子树是否包含树2
22             if (pRoot1->val == pRoot2->val)
23                 result = DoesTree1HaveTree2(pRoot1, pRoot2);
24             //当以R为根节点的树1不包含树2时，继续从R的左子树寻找
25             if (!result)
26                 result = HasSubtree(pRoot1->left, pRoot2);
27             //如果仍然找不到，从R的右子树寻找
28             if (!result)
29                 result = HasSubtree(pRoot1->right, pRoot2);
30         }
31         //返回结果
32         return result;
33     }
34     //该函数的作用是判断以pRoot1为根节点的树是否包含以pRoot2为根节点的树
35     bool DoesTree1HaveTree2(TreeNode* pRoot1, TreeNode *pRoot2)
36     {
37         //如果tree2遍历完，所有节点在tree1中都找得到，返回true
38         if (pRoot2 == nullptr)
39             return true;
40         //如果tree2没遍历完但是tree1遍历完了，返回false
41         if (pRoot1 == nullptr)
42             return false;
43         //如果根节点数值不相等，返回false
44         if (pRoot1->val != pRoot2->val)
45             return false;
46         //若根节点相等了，那么左右子树也必须都相等才可以，所以用&&
47         return DoesTree1HaveTree2(pRoot1->left, pRoot2->left) &&
48             DoesTree1HaveTree2(pRoot1->right, pRoot2->right);
49     }
50 };

View Code

面试题25：合并两个排序链表

递归思路，每次两个链表头部数值较小的就是新链表的头

一刷：if判决语句中pMergedHead的next指向错了，一定注意处理好链表结构体中next指针的指向

代码如下：

 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 == nullptr)
14             return pHead2;
15         else if (pHead2 == nullptr)
16             return pHead1;
17 
18         ListNode *pMergedHead = nullptr;
19         if (pHead1->val < pHead2->val)
20         {
21             pMergedHead = pHead1;                  
22             pMergedHead->next = Merge(pHead1->next, pHead2);  //MD错了，应该是pMerged->next
23         }
24         else
25         {
26             pMergedHead = pHead2;
27             pMergedHead->next = Merge(pHead1, pHead2->next);
28         }
29         return pMergedHead;
30     }
31 };

View Code

面试题21：调整数组顺序使奇数位于偶数前面

牛客网不仅要求分开奇数偶数，还要求相对位置不变，我新开辟了一个向量，两次扫描原来向量。时间空间复杂度均是O（n）

代码如下：

 1 //原来书上 的解题思路不保证顺序，只是让奇数位于前半部分，偶数位于后半部分
 2 //这里既然要求顺序，可以考虑再开辟一个相同大小的vector
 3 class Solution {
 4 public:
 5     void reOrderArray(vector<int> &array) {
 6         int length = array.size();
 7         //vector<int> result(length, 0);//初始化可以不需要的
 8         vector<int> result;
 9         for (int i = 0; i < length; i++)
10             if ((array[i] & 0x1) != 0)
11                 result.push_back(array[i]);
12         for (int i = 0; i < length; i++)
13             if ((array[i] & 0x1) == 0)
14                 result.push_back(array[i]);
15         array = result;
16     }
17 };

View Code

面试题19：正则表达式匹配

分类讨论的关键点在于——正则表达式中第二个字符是否是“*”。若第二个字符不是*，字符与模式都后移一位；若第二个字符是*，则有一下几种可能：1、字符串后移一位，模式不变（对应于*以及它前面的字符多次出现）；2、字符串后移一个，模式后移两个（对应于*和它前面的字符认为只出现一次）；3、字符串不动，模式后移2个（对应于*前面的字符一次都不出现）

代码如下：

 1 class Solution {
 2 public:
 3     bool match(char* str, char* pattern)
 4     {
 5         if (str == nullptr || pattern == nullptr)
 6             return false;
 7         return matchCore(str, pattern);
 8     }
 9 
10     bool matchCore(char* str, char* pattern)
11     {
12         if (*str == ''&&*pattern == '')
13             return true;
14         if (*str != ''&&*pattern == '')
15             return false;
16         if (*(pattern + 1) == '*')
17         {
18             if (*pattern == *str || (*str != ''&&*pattern == '.'))     //第一个字符匹配上了
19                 return matchCore(str + 1, pattern + 2)
20                 || matchCore(str + 1, pattern)
21                 || matchCore(str, pattern + 2);
22             else                 //第一个字符没对上
23                 return matchCore(str, pattern + 2);
24         }
25         if (*pattern == *str || (*str != ''&&*pattern == '.'))
26             return matchCore(str + 1, pattern + 1);
27         return false;
28     }
29 };

View Code

面试题16：数值的整数次方

难度一般，一遍AC，注意底数和指数为0的特殊情况，同时还要注意题目中是否让调用库函数

 1 class Solution {
 2 public:
 3     double Power(double base, int exponent) {
 4         double epsilon=1e-6;
 5         double result=1.0;
 6         int absExponent;
 7         if(fabs(base-0.0)<epsilon)//认为base为零
 8             return 0.0;
 9         if(exponent==0)
10             return 1;
11         if(exponent<0)
12             absExponent=-exponent;
13         else
14             absExponent=exponent;
15         for(int i=1;i<=absExponent;i++)
16             result*=base;
17         if(exponent<0)
18             return 1.0/result;
19         return result;
20     }
21 };

View Code

按照《剑指offer》上的说法，还是可以做进一步优化的，计算乘方时可以使用递归，将复杂度降为O（logn），代码如下：

 1 bool g_InvalidInput = false;
 2 bool equal(double num1, double num2);
 3 double PowerWithUnsignedExponent(double base, unsigned int exponent);
 4 
 5 double Power(double base, int exponent)
 6 {
 7     g_InvalidInput = false;
 8 
 9     if (equal(base, 0.0) && exponent < 0)
10     {
11         g_InvalidInput = true;
12         return 0.0;
13     }
14 
15     unsigned int absExponent = (unsigned int) (exponent);
16     if (exponent < 0)
17         absExponent = (unsigned int) (-exponent);
18 
19     double result = PowerWithUnsignedExponent(base, absExponent);
20     if (exponent < 0)
21         result = 1.0 / result;
22 
23     return result;
24 }
25 double PowerWithUnsignedExponent(double base, unsigned int exponent)
26 {
27     if (exponent == 0)
28         return 1;
29     if (exponent == 1)
30         return base;
31 
32     double result = PowerWithUnsignedExponent(base, exponent >> 1);
33     result *= result;
34     if ((exponent & 0x1) == 1)
35         result *= base;
36 
37     return result;
38 }
39 
40 bool equal(double num1, double num2)
41 {
42     if ((num1 - num2 > -0.0000001) && (num1 - num2 < 0.0000001))
43         return true;
44     else
45         return false;
46 }

View Code

面试题15：二进制中1的个数

能用移位运算就别用乘除，移位的运算速度更快。

为了避免讨论原理数字是正是负，这里选择用数1与原来数字做位与运算，再将1左移，32位的整数需要移动32次

代码如下：

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

View Code

其实可以做简单的优化，优化之后的可以变为“有几个1，就进行几次循环”，这是根据“把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0”

代码如下：

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

View Code

面试题10：斐波那契数列

使用递归虽然简单，但是会导致栈溢出，循环的代码鲁棒性更好一些。

代码如下：

 1 class Solution {
 2 public:
 3     int Fibonacci(int n) {
 4         
 5         if(n<=0)
 6             return 0;
 7         if(n==1)
 8             return 1;
 9         int f1=0;
10         int f2=1;
11         int f;
12         for(int i=2;i<=n;i++)
13         {
14             f=f1+f2;
15             f1=f2;
16             f2=f;
17         }
18         return f;
19     }
20 };

View Code

青蛙跳台阶问题，青蛙一次只能跳一个或者两个台阶，本质上还是斐波那契数列

补充：变态跳台阶问题，青蛙一次可以调1,2,3，……，n个台阶，经过推导，可以发现通向公式f（n） = 2^（n-1）;

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

View Code

面试题9：两个栈实现一个队列

栈1负责进，栈2负责出

 1 class Solution
 2 {
 3 public:
 4     void push(int node) {
 5         stack1.push(node);
 6     }
 7 
 8     int pop() {
 9         if(stack2.size()>0)
10         {
11             int a = stack2.top();
12             stack2.pop();
13             return a;
14         }
15         else        //默认不考虑为负数的的情况，此处只考虑为0的情况
16         {
17             while(stack1.size())
18             {
19                 int temp = stack1.top();
20                 stack1.pop();
21                 stack2.push(temp);
22             }
23             int temp2 = stack2.top();
24             stack2.pop();
25             return temp2;
26         }
27     }
28 
29 private:
30     stack<int> stack1;
31     stack<int> stack2;
32 };
33 
34 /* 一种更高效的解法
35 class Solution
36 {
37 public:
38     void push(int node) {
39         stack1.push(node);
40     }
41  
42     int pop() {
43         int a;
44         if (stack2.empty())
45         {
46             while (!stack1.empty())
47             {
48                 a = stack1.top();
49                 stack1.pop();
50                 stack2.push(a);
51             }
52         }
53         a = stack2.top();
54         stack2.pop();
55         return a;
56     }
57  
58 private:
59     stack<int> stack1;
60     stack<int> stack2;
61 };
62 */

View Code

面试题8：二叉树的下一个节点

思路不难，注意条件的的划分

代码如下：

 1 /*
 2 struct TreeLinkNode {
 3     int val;
 4     struct TreeLinkNode *left;
 5     struct TreeLinkNode *right;
 6     struct TreeLinkNode *next;
 7     TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
 8         
 9     }
10 };
11 */
12 class Solution {
13 public:
14     TreeLinkNode* GetNext(TreeLinkNode* pNode)
15     {
16         //《剑指offer》书本思路,最好还是先按照自己的思路写，然后再去按照书上精简的答案去做
17         if (pNode == nullptr)
18             return nullptr;
19         TreeLinkNode* pNext = nullptr;   //将要作为结果返回的节点
20         if (pNode->right != nullptr)
21         {
22             TreeLinkNode* pRight = pNode->right;
23             while (pRight->left != nullptr)
24                 pRight = pRight->left;
25             pNext = pRight;
26         }
27         else if (pNode->next != nullptr)  //else if 改成else可以吗,可以改，但是运行速度变慢，占用内存增多（牛客测试结果）
28         {
29             TreeLinkNode* pCurrent = pNode;
30             TreeLinkNode* pParent = pNode->next;
31             while (pParent != nullptr&&pCurrent == pParent->right)
32             {
33                 pCurrent = pParent;
34                 pParent = pParent->next;
35             }
36             pNext = pParent;
37         }
38         return pNext;
39     }
40 };

View Code

面试题7：重建二叉树

用递归的方法重建二叉树，凡是递归类的问题，注意三点：1、分析问题；2、找到递归终止条件；3、递归调用函数时，一定要注意参数的取值，否则很容易出错而且错误比较难查找，我第一次做就是参数取值写错，结果函数进入死循环

代码如下：

 1 BinaryTreeNode* ConstructCore(int* startPreorder, int* endPreorder, int* startInorder, int* endInorder);
 2 
 3 BinaryTreeNode* Construct(int* preorder, int* inorder, int length)
 4 {
 5     if(preorder == nullptr || inorder == nullptr || length <= 0)
 6         return nullptr;
 7 
 8     return ConstructCore(preorder, preorder + length - 1,
 9         inorder, inorder + length - 1);
10 }
11 
12 BinaryTreeNode* ConstructCore
13 (
14     int* startPreorder, int* endPreorder, 
15     int* startInorder, int* endInorder
16 )
17 {
18     // 前序遍历序列的第一个数字是根结点的值
19     int rootValue = startPreorder[0];
20     BinaryTreeNode* root = new BinaryTreeNode();
21     root->m_nValue = rootValue;
22     root->m_pLeft = root->m_pRight = nullptr;
23 
24     if(startPreorder == endPreorder)
25     {
26         if(startInorder == endInorder && *startPreorder == *startInorder)
27             return root;
28         else
29             throw std::exception("Invalid input.");
30     }
31 
32     // 在中序遍历中找到根结点的值
33     int* rootInorder = startInorder;
34     while(rootInorder <= endInorder && *rootInorder != rootValue)
35         ++ rootInorder;
36 
37     if(rootInorder == endInorder && *rootInorder != rootValue)
38         throw std::exception("Invalid input.");
39 
40     int leftLength = rootInorder - startInorder;
41     int* leftPreorderEnd = startPreorder + leftLength;
42     if(leftLength > 0)
43     {
44         // 构建左子树
45         root->m_pLeft = ConstructCore(startPreorder + 1, leftPreorderEnd, 
46             startInorder, rootInorder - 1);
47     }
48     if(leftLength < endPreorder - startPreorder)
49     {
50         // 构建右子树
51         root->m_pRight = ConstructCore(leftPreorderEnd + 1, endPreorder,
52             rootInorder + 1, endInorder);
53     }
54 
55     return root;
56 }

View Code

牛客网在线对应题目，注意构建左右子树是，for循环中vector的index，比较容易写错。

代码如下：

 1 class Solution {
 2 public:
 3     TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin) {
 4         int size1 = pre.size();
 5         int size2 = vin.size();
 6         if (size1 <= 0 || size2 <= 0 || size1 != size2)
 7             return nullptr;
 8         vector<int> left_pre,right_pre, left_vin, right_vin;
 9         TreeNode* root = new TreeNode(pre[0]);
10         int pos;
11         for (int i = 0; i < size1;i++)
12             if (vin[i] == pre[0])  
13             {
14                 pos = i;
15                 break;
16             }
17         for (int i = 0; i < pos; i++)
18         {
19             left_pre.push_back(pre[i+1]);  //此处小心
20             left_vin.push_back(vin[i]);
21         }
22         for (int i = pos + 1; i < size1; i++)
23         {
24             right_pre.push_back(pre[i]);
25             right_vin.push_back(vin[i]);
26         }
27         root->left =  reConstructBinaryTree(left_pre, left_vin);
28         root->right=reConstructBinaryTree(right_pre, right_vin);
29         return root;
30     }
31 };

View Code

面试题6：翻转链表

牛客网题目，思路为先将链表顺序压入栈中，在逐个出栈放入另一个vector，完成逆序

代码如下：

 1 class Solution {
 2 public:
 3     vector<int> printListFromTailToHead(ListNode* head) {
 4         vector<int> temp;
 5         stack<int> sta;
 6         ListNode* pNode = head;  //这里注意一定要把头指针赋值，而不要直接去修改头指针，否则会报“段错误”
 7         while(pNode != nullptr)   //只需要判断pNode 而不是它的next
 8           {
 9             sta.push(pNode->val);
10             pNode = pNode->next;
11         }
12         while(!sta.empty())
13             {
14             temp.push_back(sta.top());
15             sta.pop();
16         }
17          return temp;
18     }
19        
20  };

View Code

1、一刷失误在while循环中，不应该直接用了头指针，也不应该改变头指针的取值。

《剑指offer》书上提供了两种思路，分别表示如下：

 1 //循环
 2 void PrintListReversingly_Iteratively(ListNode* pHead)
 3 {
 4     std::stack<ListNode*> nodes;
 5 
 6     ListNode* pNode = pHead;
 7     while(pNode != nullptr)
 8     {
 9         nodes.push(pNode);
10         pNode = pNode->m_pNext;
11     }
12     while(!nodes.empty())
13     {
14         pNode = nodes.top();
15         printf("%d	", pNode->m_nValue);
16         nodes.pop();
17     }
18 }
19 
20 //递归
21 void PrintListReversingly_Recursively(ListNode* pHead)
22 {
23     if(pHead != nullptr)
24     {
25         if (pHead->m_pNext != nullptr)
26         {
27             PrintListReversingly_Recursively(pHead->m_pNext);
28         }
29  
30         printf("%d	", pHead->m_nValue);
31     }
32 }

View Code

面试题5：替换空格

从后向前查找，复杂度为O（n）

代码如下：

 1 class Solution {
 2 public:
 3     void replaceSpace(char *str, int length) {
 4         if (str == nullptr || length <= 0)
 5             return;
 6         /*originalLength 为字符串str的实际长度*/
 7         int originalLength = 0;
 8         int numberOfBlank = 0;
 9         int i = 0;
10         while (str[i] != '')
11         {
12             if (str[i]==' ')   //一定注意是单引号而不是双引号
13                 numberOfBlank++;
14             originalLength++;
15             i++;
16         }
17         
18         /*newLenght为把空格替换成%20之后的长度*/
19         int newLength = originalLength + numberOfBlank * 2;
20         if (newLength > length)
21             return;
22         int indexOfOriginal = originalLength;
23         int indexOfNew = newLength;
24         while (indexOfOriginal >= 0 && indexOfNew > indexOfOriginal)
25         {
26             if (str[indexOfOriginal] == ' ')
27             {
28                 str[indexOfNew--] = '0';
29                 str[indexOfNew--] = '2';
30                 str[indexOfNew--] = '%';
31 
32             }
33             else
34                 str[indexOfNew--] = str[indexOfOriginal];
35             indexOfOriginal--;
36         }
37 
38     }
39 };

View Code

面试题4：二维数组的查找

这道题思路是查找时每次要么去除一行，要么去除一列，逐步缩小查找范围。牛客网在线做题函数用的是两重vector传递函数，但是其实我觉得用个一重指针就行

两重vector的初始化方式可以看这个链接：http://blog.csdn.net/oNever_say_love/article/details/50763238

代码如下：

 1 class Solution {
 2 public:
 3     bool Find(int target, vector<vector<int> > array) {   //数据结构为vector的vector，略微有些复杂，访问时和二维数组一样的方式
 4         int row = array.size();        //获得数组的行数
 5         int col = array[0].size();    //获得数组的列数
 6         int rowIndex = 0;             //行索引
 7         int colIndex = col - 1;      //列索引
 8         bool found = false;
 9         if (row > 0 && col > 0)       
10         {
11             while (rowIndex < row&&colIndex >= 0)   //从矩阵的右上角开始遍历，该数字大于target，去掉这一列，否则去掉这一行
12             {                                       //依次往复，每次都可以缩小查找范围
13                 if (array[rowIndex][colIndex] == target)
14                 {
15                     found = true;
16                     break;
17                 }
18                 else if (array[rowIndex][colIndex]>target)
19                     colIndex--;
20                 else
21                     rowIndex++;
22             }
23         }
24         return found;
25     }
26     
27 };

View Code

面试题3：数组中重复的数字

数组中如果有重复的数字，返回true，否则返回false

第一遍：出错，很傻，交换元素时出错了，请小心

class Solution {
public:
    // Parameters:
    //        numbers:     an array of integers
    //        length:      the length of array numbers
    //        duplication: (Output) the duplicated number in the array number
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    bool duplicate(int numbers[], int length, int* duplication)
    {
        if (numbers == nullptr || length <= 0)
            return false;
        for (int i = 0; i < length; i++)
            if (numbers[i]<0 || numbers[i]>length - 1)
                return false;
        for (int i = 0; i < length; i++)
        {
            while (numbers[i] != i)
            {
                if (numbers[i] == numbers[numbers[i]])
                {
                    *duplication = numbers[i];
                    return true;
                }
                int temp = numbers[i];  //交换数字，容易出错
                numbers[i] = numbers[temp];
                numbers[temp] = temp;   //千万别写成  numbers[numbers[i]] = temp;
            }
        }
        return false;

    }


};

View Code

面试题3，题目2：数组中重复的数字（不能改变数组元素的位置）

这道题和上一道题目很像，只是要求不能改动数组，基本思路类似二分查找

 1 class Solution {
 2 public:
 3     // Parameters:
 4     //        numbers:     an array of integers
 5     //        length:      the length of array numbers
 6     //        duplication: (Output) the duplicated number in the array number
 7     // Return value:       the repetitive number    otherwise -1
 8    int countRange(const int* numbers, int length, int start, int end);
 9 
10 // 参数:
11 //        numbers:     一个整数数组
12 //        length:      数组的长度
13 // 返回值:             
14 //        正数  - 输入有效，并且数组中存在重复的数字，返回值为重复的数字
15 //        负数  - 输入无效，或者数组中没有重复的数字
16 int getDuplication(const int* numbers, int length)
17 {
18     if (numbers == nullptr || length <= 0)
19         return -1;
20 
21     int start = 1;
22     int end = length - 1;
23     while (end >= start)
24     {
25         int middle = ((end - start)>>1) + start;
26         int count = countRange(numbers, length, start, middle);
27         if (end == start)
28         {
29             if (count > 1)
30                 return start;
31             else
32                 break;
33         }
34         if (count > (middle - start + 1))
35             end = middle;
36         else
37             start = middle + 1;
38     }
39     return -1;
40 }
41 
42 int countRange(const int* numbers, int length, int start, int end)
43 {
44     if (numbers == nullptr)
45         return 0;
46 
47     int count = 0;
48     for (int i = 0; i < length; i++)
49         if (numbers[i] >= start && numbers[i] <= end)
50             ++count;
51     
52     return count;
53 }
54 };

View Code