剑指offer算法题1-10
数组中重复的数字-03
题目1
找到数组中重复的数字
一个数组存放n个数字，所有数字在[0, n-1]范围内。某些数字是随机重复的。请找出任意一个重复的数字。例如[2,3,1,0,2,5,3]，输出2或3
思路1
对数组进行排序，然后可以找出重复的数字。但是排序的时间复杂度是O(nlogn)
思路2
使用哈希表，每次存放的时候检查是否在哈希表中，如果已经存在，那么就重复了。时间复杂度O(n)，空间复杂度O(n)
最优思路
利用下标和值的关系，从头到尾依次扫描这个数组。扫描到下标为i，值为m。尽量把m放到a[m]的位置上。修改了原来的数组。
1
2
3
4
5
6
7
8
9
10
| while (a[i] != i)
if m == i:
else:
if m == a[m]:
else:
m <--> a[m]
|
尽管有两重循环，但每个数字最多交换两次就能找到自己的位置，所以总的时间复杂度是O(n)，空间复杂度为O(1)
关键代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
bool duplicate(int a[], int alen, int *dup) {
for (int i = 0; i < alen; i++) {
while (a[i] != i) {
int m = a[i];
if (a[m] == m) {
*dup = m;
return true;
} else {
int t = a[m];
a[m] = m;
a[i] = t;
}
}
}
return false;
}
|
题目2
不修改数组找出重复的数字
数组，长度为n+1，数字范围[1, n]，数组中至少有一个是重复的，找出任意一个重复的数字，但是不能修改数组
思路1
创建一个新数组b存放原数组a。遍历原数组，当前是m，如果b[m]已经没有值，则存放；如果有值，则重复。但是需要O(n)的辅助空间
最优思路
见二分查重描述清晰版
把\(a[1, n]\)的个数字，分为两部分。\(a[1, m]\)和\(a[m+1, n]\)。
在\(a[1, m]\)中，统计数字\(1,2\cdots, m\)在\(a[1,m]\)中出现的次数count
- 如果是m次，则\(a[1,m]\)每个数字独一无二，重复的区间在a[m+1, n]中。则\(\rm{start}=m+1\)，继续查找。
- 否则不独一无二，则重复在\(a[1, m]\)中 。则\(\rm{end}=m\)， 继续查找。
- 直到\(\rm{start} == \rm{end}\) 。count > 1，则start重复，否则没有重复的。
关键代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
int get_duplication(const int *a, int alen) {
if (a == nullptr || alen <= 0) {
return -1;
}
int start = 1;
int end = alen - 1;
while (start <= end) {
int m = ((end - start) >> 1) + start;
int count = count_range(a, alen, start, m);
if (start == end) {
if (count > 1) {
return start;
} else {
break;
}
}
if (count == m - start + 1) {
start = m + 1;
} else {
end = m;
}
}
return 0;
}
|
二维数组查找-04
一个二维数组，每一行从左到右递增，每一列，从上到下递增。输入一个整数，判断二维数组中是否有这个数字
错误思路
全盘扫描肯定不行，从左上角最小的开始也不行，应该从最大角的地方开始
思路
一行的最大元素在最右边，一列的最小元素在上边。所以从右上角开始查找最好。即向左查、向下查，这样每次都能够剔除一行或者一列。
1
2
3
4
5
6
7
8
9
10
11
| while
if t == a[i,j]:
done
else if t > a[i,j]:
m = a[i+1, j]
else if t < a[i, j]:
m = a[i, j-1]
|
关键代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
bool find(int target, std::vector<std::vector<int>> array) {
int col = array.size();
int row = array[0].size();
bool exist = false;
int i = 0;
int j = col - 1;
while (exist == false && (i < row && i >= 0 && j < col && j >= 0)) {
int t = array[i][j];
if (target == t) {
exist = true;
break;
} else if (target < t) {
--j;
} else if(target > t) {
++i;
}
}
return exist;
}
|
字符串替换空格-05
把字符串中的每个空格替换成"%20"
- 如果在原来的字符串上修改，则会覆盖原来字符串后面的内存
- 如果创建新的字符串，则要分配足够的内存
- C/C++中字符串最后一个字符是
\0
不好思路
从前向后扫描，遇到一个空格替换一个。但是每次都需要大量移动后面的元素，所以时间复杂度是\(O(n^2)\)
最优思路
从后向前替换。使用两个指针p1和p2。先计算出替换后的长度，p2指向替换后的长度的末尾指针。p1指向之前的字符串的指针。
- 从p1开始向前移动
- 当前是普通字符，则复制到p2，p2向前移动
- 当前是空格，则在p2加入“%20”，p2向前移动
- 如果p1==p2，那么移动完毕
总的来说，先找到最终的长度，从后向后拉。时间复杂度是\(O(n)\)
技巧
合并两个数组/字符串，如果从前往后，则需要移动多次。从后向前，能够减少移动次数，提高效率
关键代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
void replace_space(char *str, int len) {
int count = 0;
for (int i = 0; i < len; i++)
if (str[i] == ' ')
++count;
int newlen = (len - count) + count * 3;
int i = len - 1, j = newlen - 1;
while (i >= 0 && j >= 0) {
if (str[i] == ' ') {
str[j--] = '0';
str[j--] = '2';
str[j--] = '%';
--i;
} else {
str[j--] = str[i--];
}
}
str[newlen] = '0';
}
|
逆序打印链表-06
链表基础考点
链表是面试中最频繁的数据结构。动态结构很灵活，考指针、考编程功底。
链表创建 ：链表插入： 为新节点分配内存，调整指针的指向。删除链表中的节点从尾到头打印链表链表中倒数第k个节点反转链表合并两个排序的链表两个链表的第一个公共节点环形链表 ：尾节点指针指向头结点。题目62：圆圈中最后剩下的数字双向链表 ：题目36，二叉搜索树与双向链表复杂链表 ：指向下一个，指向任意节点的指针
从尾到头打印链表
本质上是先进后出， 可以用栈和递归。显然，栈的效率高。
关键代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
vector<int> get_reverse_by_stack(ListNode *head) {
ListNode* pnode = head;
stack<int> st;
int count = 0;
while (pnode != nullptr) {
st.push(pnode->val);
pnode = pnode->next;
count++;
}
vector<int> res(count);
for (int i = 0; i < count && st.empty() == false; i++) {
res[i] = st.top();
st.pop();
}
return res;
}
|
重建二叉树-07
树的考点
树的遍历
叉树涉及指针，比较难。最常问遍历。需要对下面7种了如指掌。
考题
- 题26，树的子结构
- 题34，二叉树中和为某一值的路径
- 题55，二叉树的深度
- 题7，重建二叉树
- 题33，二叉搜索树的后序遍历序列
- 题32，从上到下打印二叉树（层次遍历）
特别的二叉树
二叉搜索树 ：左节点小于根节点，根节点小于右节点。查找搜索时间复杂度\(O(\log n)\)。 题36，二叉搜索树与双向链表；题68：树中两个节点的最低公共祖先。
堆 ：最大堆和最小堆。找最大值和最小值。
红黑树 ： 节点定义为红黑两种颜色。根节点到叶节点的最长路径不超过最短路径的两倍。
前序中序建立二叉树
前序序列：1, 2, 4, 7, 3, 5, 6, 8。 根 左 右。
中序序列：4, 7, 2, 1, 5, 3, 8, 6。 左 根 右。
使用递归，先找到根节点，找到左右子树，为左右子树分别创建各自的前序和中序序列，再进行递归创建左右子树。
关键是要构建下面的序列，注意下标值。
| 左子树 |
2, 4, 7 |
4, 7, 2 |
| 右子树 |
3, 5, 6, 8 |
5, 3, 8, 6 |
关键代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
TreeNode * reconstruct_binary_tree(vector<int>vpre, vector<int> vin) {
if (vpre.size() == 0 || vin.size() == 0) {
return NULL;
}
TreeNode *root = new TreeNode(vpre[0]);
int root_index = -1;
for (int i = 0; i < vin.size(); i++) {
if (vin[i] == vpre[0]) {
root_index = i;
break;
}
}
if (root_index == -1) {
cout << "root_index is -1" << endl;
return NULL;
}
int leftlen = root_index;
int rightlen = vin.size() - leftlen - 1;
vector<int> leftvpre(leftlen), leftvin(leftlen);
vector<int> rightvpre(rightlen), rightvin(rightlen);
for (int i = 0; i < vin.size(); i++) {
if (i < root_index) {
leftvin[i] = vin[i];
leftvpre[i] = vpre[i+1];
} else if (i > root_index){
int right_idx = i - root_index - 1;
rightvin[right_idx] = vin[i];
rightvpre[right_idx] = vpre[leftlen + 1 + right_idx];
}
}
root->left = reconstruct_binary_tree(leftvpre, leftvin);
root->right = reconstruct_binary_tree(rightvpre, rightvin);
return root;
}
|
二叉树的下一个节点-08
二叉树：值，左孩子，右孩子，父亲节点指针。
给一个节点，找出中序序列的该节点的下一个节点。重在分析中序序列。
1
2
3
4
5
6
7
8
9
10
| if "有右子树":
while ("p有左孩子")
p = "左孩子"
t = p
else:
while ("p有父节点 && p是父节点的右节点"):
p = "父节点"
t = p
|
关键代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
TreeNode* get_next_inorder(TreeNode* pnode) {
if (pnode == nullptr) {
return nullptr;
}
TreeNode* pnext = nullptr;
if (pnode->right != nullptr) {
TreeNode* p = pnode->right;
while (p->left != nullptr) {
p = p->left;
}
pnext = p;
} else {
TreeNode* p = pnode;
while (p->parent != nullptr && p == p->parent->right) {
p = p->parent;
}
if (p->parent != nullptr) {
pnext = p->parent;
}
}
return pnext;
}
|
两个栈实现队列-09
栈和队列
栈 ：后进先出
- 题31：
栈的压入、弹出序列
- \(O(n)\) 找到最大最小元素。若\(O(1)\) ，则题30：
包含min函数的栈
队列 ：先进先出
用两个栈实现队列
分为入栈（栈A）和出栈（栈B）。
- 入队时：直接进入入栈
- 出队时：若出栈为空，则把入栈里的内容放入出栈；再从出栈里面出一个元素。
[关键代码]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class Solution {
private:
stack<int> stackIn;
stack<int> stackOut;
public:
void push(int node) {
stackIn.push(node);
}
int pop() {
if (this->empty()) {
cout << "empty queue" << endl;
return -1;
}
int node = -1;
if (stackOut.empty() == true) {
while (stackIn.empty() == false) {
node = stackIn.top();
stackIn.pop();
stackOut.push(node);
}
}
node = stackOut.top();
stackOut.pop();
return node;
}
bool empty() {
return stackIn.empty() == true && stackOut.empty() == true;
}
};
|
两个队列实现栈
分为空队列和非空队列
- 入栈：进入非空队列
- 出栈：非空队列中中前n-1个进入空队列，出非空队列最后一个元素（最新进来的）
关键代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| int pop() {
if (this->empty()) {
return -1;
}
queue<int>* qout;
queue<int>* qin;
if (q1.empty() == true) {
qout = &q2;
qin = &q1;
} else {
qout = &q1;
qin = &q2;
}
while (qout->size() > 1) {
qin->push(qout->front());
qout->pop();
}
int res = qout->back();
qout->pop();
return res;
}
|
算法和数据操作
总览
| 递归和循环 |
树的遍历 |
递归简介，循环效率高 |
| 排序和查找 |
二分查找、归并排序、快速排序 |
正确、完整写出代码 |
| 二维数组 |
迷宫、棋盘 |
回溯法；栈模拟递归 |
| 最优解 |
动态规划，问题分解为多个子问题 |
自上而下递归分析；自下而上循环代码实现，数组保存 |
| 最优解 |
贪心算法 |
分解时是否存在某个特殊选择：贪心得到最优解 |
|
与、或、异或、左移、右移 |
|
递归效率低的原因：函数调用自身，函数调用是由时间和空间的消耗；会在内存栈中分配空间以保存参数，返回地址和临时变量，往栈里弹入和弹出都需要时间。
递归和循环：题10，斐波那契数列；题60，n个骰子的点数。
动态规划
递归思路分析，递归分解的子问题中存在着大量的重复。用自下而上的循环来实现代码。题14 剪绳子， 题47礼物的最大价值 ， 题48最长不含重复字符的子字符串
斐波那契数列-递归循环-10
斐波那契数列
数列定义 \[
f(n) =
\begin{cases}
&0 & n=0 \\
&1 & n=1 \\
&f(n-1) + f(n-2) & n \ge 1
\end{cases}
\] 递归和循环两种实现策略
关键代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| long long fibonacci_recursion(unsigned int n) {
if (n <= 0) return 0;
if (n == 1) return 1;
return fibonacci_recursion(n-1) + fibonacci_recursion(n-2);
}
long long fibonacci_loop(unsigned int n) {
if (n <= 0) return 0;
if (n == 1) return 1;
long long f1 = 0;
long long f2 = 1;
long long fn = 0;
for (unsigned int i = 2; i <= n; i++) {
fn = f1 + f2;
f1 = f2;
f2 = fn;
}
return fn;
}
|
青蛙跳台阶
青蛙可以一次跳1个台阶，一次跳2个台阶。问青蛙跳n个台阶有多少种跳法。
青蛙跳到第n个台阶有两种跳法：跳1个和2个。所以\(f(n)=f(n-1)+f(n-2)\) 。是斐波那契数列。
扩展
青蛙一次可以跳1个台阶、2个台阶、n个台阶。问有多少种跳法？
数学归纳法证得：\(f(n) = 2^{n-1}\)
矩阵覆盖问题
\(2\times1\)矩阵去覆盖\(2 \times 8\) 矩阵，可以横着竖着覆盖，问多少种覆盖方法？
同理，最后一个横着放或者竖着放。\(f(8)=f(7)+f(6)\)
