【读书笔记】剑指offer

时间：2018-10-08 14:44:21 阅读：188 评论：0 收藏：0 [点我收藏+]

第二章

【面试题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】用两个栈实现队列

用两个栈来实现一个队列，完成队列的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的个数

【读书笔记】剑指offer

原文：https://www.cnblogs.com/zhangwanying/p/9752845.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)