首页 Computer-Science Coding-Interviews

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

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

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

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

# 思路

题目给定的数字都在 00 ~ n−1n-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";
    }
}