本系列文章是《剑指 Offer(第二版)》的个人笔记。主要是对作者的思路讲解在个人理解的基础上进行精炼,并且将其中的代码用更加偏 C++
的风格进行改写。
# 面试题 3:数组中重复的数字
# 题目一:找出数组中重复的数字
在一个长度为 的数组里的所有数字都在 ~ 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意个重复的数字。例如,如果输入长度为 的数组 ,那么对应的输出是重复的数字 或者 。
# 思路
题目给定的数字都在 ~ 的范围内,如果假定数组内的数字有序,并且数组中没有重复的数字,那么数字 应该出现在下标 对应的位置。
现在,由于数组中可能有重复的数字,那么可能存在下标 ,不与数字 对应,数字 可能缺失,也有可能因为在前面位置的数字重复而导致位置在下标 之后。
我们从头到尾依次遍历数组中的每个数字,当遍历到下标为 的数字时,首先比较该位置的数字 是否等于 。如果相等,那么继续遍历;如果不相等,那么将其与第 个数字进行比较。如果其与第 个数字相等,就找到了一个重复的数字(出现在位置 和位置 );如果不相等,那么将第 个数字和第 个数字进行交换。接下来重复比较、交换的过程,直到发现一个重复的数字。
# 代码
#include<vector> | |
using namespace std; | |
bool duplicate(vector<int> &numbers, int *duplication) { | |
if (numbers.size() == 0) { | |
return false; | |
} | |
for (int i = 0; i < numbers.size(); ++i) { | |
if (numbers[i] < 0 || numbers[i] > numbers.size()) { | |
return false; | |
} | |
} | |
for (int i = 0; i < numbers.size(); ++i) { | |
while(numbers[i] != i) { | |
if (numbers[i] == numbers[numbers[i]]) { | |
*duplication = numbers[i]; | |
return true; | |
} | |
// swap numbers[i] and numbers[numbers[i]] | |
swap(numbers[i], numbers[numbers[i]]); | |
} | |
} | |
return false; | |
} |
# 题目二:不修改数组找出重复的数字
在一个长度为 的数组里的所有数字都在 ~ 的范围内,所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字,但不能修改输入的数组。例如,如果输入长为 的数组 ,那么对应的输出是重复的数字 或者 。
# 思路
这一题和上一题有些类似,但是不同点在于不能修改输入的数组。由于数组中的数字都属于 ~,而数组的长度又为 ,那么必然有一个重复的数字。
我们把 ~ 的数字以中间的数字 为界,将数组分为两个部分,前一半的数字为 ~,后一半的数字为 ~。如果 ~ 的数字的数目超过了 ,那么可以确定这一半之中必定包含重复的数字;否则在另一半中必定包含重复的数字。重复这一过程,将数组继续一分为二,直到找到一个重复的数字。
# 代码
#include <iostream> | |
#include <vector> | |
using namespace std; | |
int count_range(vector<int> &numbers, int lower, int upper) { | |
if (lower > upper) { | |
return 0; | |
} | |
int count = 0; | |
for (int i = 0; i < numbers.size(); ++i) { | |
if (numbers[i] >= lower && numbers[i] <= upper) { | |
++count; | |
} | |
} | |
return count; | |
} | |
int get_duplicate(vector<int> &numbers) { | |
if (numbers.size() <= 0) { | |
return -1; | |
} | |
int lower = 1; | |
int upper = numbers.size() - 1; | |
while (lower <= upper) { | |
int mid = lower + ((upper - lower) >> 1); | |
int count = count_range(numbers, lower, mid); | |
if (lower == upper) { | |
if (count > 1) { | |
return lower; | |
} else { | |
break; | |
} | |
} | |
if (count > (mid - lower + 1)) { | |
upper = mid; | |
} else { | |
lower = mid + 1; | |
} | |
} | |
return -1; | |
} |
# 面试题 4:二维数组中的查找
# 题目
在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
# 思路
对于一维数组而言,可以使用二分查找很快的判断一个数是否在数组中。对于本题的数组而言,也可以使用二分法进行查找,关键点在于如何选取初始查找的位置。
假如我们从左上角的开始查找,当前所处的位置是 ,以该点所在行和列为界限,将二维数组矩阵划分为四个区域。如果查找的数字大于当前的值,该值可能在右上、右下、左下的区域中,达不到将搜索区域减半的效果。例如上方矩阵中的数字 。同理,从右下角开始,如果查找的数字比当前的值小,那么该值可能在左上、左下、右上三个区域,也无法决定接下来该选择哪个方向继续搜索。
我们不妨换个思路,将二维数组看成是由多个一维数组组合而成。例如上方的矩阵,我们可以看成是 组成的,它们都是有序的一维数组。
对于一维数组,我们很容易知道是从其中点位置可是查找。因此第一个搜索的位置可以定在右上角的 ;接着回忆,当目标值和当前值进行比较之后,我们可以将数组中一半的值丢弃。假如我们的查找值为 ,那么 这一数组中我们需要将后一半的数字丢弃。而在二维矩阵中,这一操作可以通过行号或者列号的变化来实现。比如说在上方矩阵中,丢弃 这一操作对应列号的减少。
经过这一操作之后,我们可以发现,新的矩阵可以视作 组成的。接下来我们可以进一步执行上述的操作,直到找到对应的数值,或者所有数值都查找完毕。
# 代码
#include <iostream> | |
#include <vector> | |
using namespace std; | |
bool find(vector<vector<int>> matrix, int number) { | |
bool is_found = false; | |
if (!matrix.empty()) { | |
int row = matrix.size(); | |
int col = matrix[0].size(); | |
int i = 0, j = col - 1; | |
while (i < row && col >= 0) { | |
if (matrix[i][j] == number) { | |
is_found = true; | |
break; | |
} else if (matrix[i][j] > number) { | |
--j; | |
} else { | |
++i; | |
} | |
} | |
} | |
return is_found; | |
} |
# 面试题 5:替换空格
# 题目
请实现一个函数,把字符串中的每个空格替换成 "%20"。例如输入 “We are happy.”,则输出 “We%20are%20happy.”。
# 思路
如果不限制返回的字符串是在原字符串的基础上修改的话,那么可以很容易地分配一个新的字符串,然后遍历原字符串并替换空格,将结果写入到新的字符串中。
如果限制返回的字符串是在原址上进行修改的,那么对于长度固定的字符串,我们可以通过遍历一遍字符串,统计出其中空格的数量,然后计算出替换之后的新的字符串的长度。之后在原址上通过倒序的方式进行替换。
# 代码
#include <iostream> | |
using namespace std; | |
void replace_blank(char *str, int length) { | |
if (str == nullptr || length <= 0) { | |
return; | |
} | |
int original_len = 0; | |
int num_of_blank = 0; | |
int i = 0; | |
while (str[i] != '\0') { | |
++original_len; | |
if (str[i] == ' ') { | |
++num_of_blank; | |
} | |
++i; | |
} | |
int new_len = original_len + num_of_blank * 2; | |
if (new_len > length) { | |
return; | |
} | |
int index_of_origin = original_len; | |
int index_of_new = new_len; | |
while (index_of_origin >= 0 && index_of_new > index_of_origin) { | |
if (str[index_of_origin] == ' ') { | |
str[index_of_new--] = '0'; | |
str[index_of_new--] = '2'; | |
str[index_of_new--] = '%'; | |
} else { | |
str[index_of_new--] = str[index_of_origin]; | |
} | |
--index_of_origin; | |
} | |
} |
# 面试题 6:从尾到头打印链表
# 题目
输入一个链表的头节点,从尾到头反过来打印出每个节点的值。链表节点定义如下
struct ListNode { | |
int m_key; | |
ListNode *m_next; | |
} |
# 思路
如果将链表逆序,可以很容易实现。如果不能改变链表的结构,那么可以利用栈的先进后出的性质,将值存储到栈中,然后输出其中的值。而递归本质上就是一个栈结构,也可以利用其实现。
# 代码
#include <iostream> | |
#include <stack> | |
using namespace std; | |
struct ListNode { | |
int m_key; | |
ListNode *m_next; | |
}; | |
void print_list_reversely_iteratively(ListNode *head) { | |
stack<ListNode*> nodes; | |
ListNode *node = head; | |
while (node != nullptr) { | |
nodes.push(node); | |
node = node->m_next; | |
} | |
while (!nodes.empty()) { | |
node = nodes.top(); | |
cout << node->m_key << "\t"; | |
nodes.pop(); | |
} | |
} | |
void print_list_reversely_recursively(ListNode *head) { | |
if (head != nullptr) { | |
if (head->m_next != nullptr) { | |
print_list_reversely_recursively(head->m_next); | |
} | |
cout << head->m_key << "\t"; | |
} | |
} |