本系列文章是《剑指 Offer(第二版)》的个人笔记。主要是对作者的思路讲解在个人理解的基础上进行精炼,并且将其中的代码用更加偏 C++ 的风格进行改写。

# 面试题 3:数组中重复的数字

# 题目一:找出数组中重复的数字

在一个长度为 nn 的数组里的所有数字都在 00~n1n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意个重复的数字。例如,如果输入长度为 77 的数组 {2,3,1,0,2,5,3}\{2, 3, 1, 0, 2, 5, 3\},那么对应的输出是重复的数字 22 或者 33

# 思路

题目给定的数字都在 00 ~ n1n-1 的范围内,如果假定数组内的数字有序,并且数组中没有重复的数字,那么数字 ii 应该出现在下标 ii 对应的位置。

现在,由于数组中可能有重复的数字,那么可能存在下标 jj,不与数字 jj 对应,数字 jj 可能缺失,也有可能因为在前面位置的数字重复而导致位置在下标 jj 之后。

我们从头到尾依次遍历数组中的每个数字,当遍历到下标为 ii 的数字时,首先比较该位置的数字 mm 是否等于 ii。如果相等,那么继续遍历;如果不相等,那么将其与第 mm 个数字进行比较。如果其与第 mm 个数字相等,就找到了一个重复的数字(出现在位置 ii 和位置 mm);如果不相等,那么将第 ii 个数字和第 mm 个数字进行交换。接下来重复比较、交换的过程,直到发现一个重复的数字。

# 代码

#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;
}

# 题目二:不修改数组找出重复的数字

在一个长度为 n+1n+1 的数组里的所有数字都在 11~nn 的范围内,所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字,但不能修改输入的数组。例如,如果输入长为 88 的数组 {0,3,5,4,3,2,6,7}\{0, 3, 5, 4, 3, 2, 6, 7\},那么对应的输出是重复的数字 22 或者 33

# 思路

这一题和上一题有些类似,但是不同点在于不能修改输入的数组。由于数组中的数字都属于 11~nn,而数组的长度又为 n+1n+1,那么必然有一个重复的数字。

我们把 11~nn 的数字以中间的数字 mm 为界,将数组分为两个部分,前一半的数字为 11~mm,后一半的数字为 m+1m+1~nn。如果 11~mm 的数字的数目超过了 mm,那么可以确定这一半之中必定包含重复的数字;否则在另一半中必定包含重复的数字。重复这一过程,将数组继续一分为二,直到找到一个重复的数字。

# 代码

#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:二维数组中的查找

# 题目

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

# 思路

对于一维数组而言,可以使用二分查找很快的判断一个数是否在数组中。对于本题的数组而言,也可以使用二分法进行查找,关键点在于如何选取初始查找的位置。

假如我们从左上角的开始查找,当前所处的位置是 {i,j}\{i,j\},以该点所在行和列为界限,将二维数组矩阵划分为四个区域。如果查找的数字大于当前的值,该值可能在右上、右下、左下的区域中,达不到将搜索区域减半的效果。例如上方矩阵中的数字 44。同理,从右下角开始,如果查找的数字比当前的值小,那么该值可能在左上、左下、右上三个区域,也无法决定接下来该选择哪个方向继续搜索。

我们不妨换个思路,将二维数组看成是由多个一维数组组合而成。例如上方的矩阵,我们可以看成是 {1,2,8,9,12,13,15},{2,4,9,10,11},{4,7,8},{6}\{1,2,8,9,12,13,15\}, \{2,4,9,10,11\},\{4,7,8\},\{6\} 组成的,它们都是有序的一维数组。

对于一维数组,我们很容易知道是从其中点位置可是查找。因此第一个搜索的位置可以定在右上角的 99;接着回忆,当目标值和当前值进行比较之后,我们可以将数组中一半的值丢弃。假如我们的查找值为 77,那么 {1,2,8,9,12,13,15}\{1,2,8,9,12,13,15\} 这一数组中我们需要将后一半的数字丢弃。而在二维矩阵中,这一操作可以通过行号或者列号的变化来实现。比如说在上方矩阵中,丢弃 {9,12,13,15}\{9,12,13,15\} 这一操作对应列号的减少。

经过这一操作之后,我们可以发现,新的矩阵可以视作 {1,2,8,9,10,11},{2,4,7,8},{6}\{1,2,8,9,10,11\},\{2,4,7,8\},\{6\} 组成的。接下来我们可以进一步执行上述的操作,直到找到对应的数值,或者所有数值都查找完毕。

2d_matrix_search

# 代码

#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";
    }
}