首页 Computer-Science Coding-Interviews

# 面试题 39：数组中出现次数超过一半的数字

# 题目

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如，输入一个长度为 99 的数组 {1,2,3,2,2,2,5,4,2}\{1,2,3,2,2,2,5,4,2\}。由于数字 22 在数组中出现了 55 次，超过数组长度的一半，因此输出 22。

# 思路

# 解法一：基于 Partition 函数的时间复杂度为 O(n)O(n) 的算法

对于一个出现次数超过数组长度一半的数字，如果把数组排序，那么排序之后位于数组中间的数字一定就是所求的目标数字。即长度为 nn 的数组中第 n/2n/2 大的数字。对于数组中任意第 kk 大的数字，有时间复杂度为 O(n)O(n) 的算法可以求得。

这种算法受快速排序算法的启发。在随机快速排序算法中，先在数组中随机选择一个数字，然后调整数组中数字的顺序，使得比选中的数字小的数字都排在它的左边，比选中的数字大的数字都排在它的右边。如果这个选中的数字的下标刚好是 n/2n/2，那么这个数字就是数组的中位数；如果它的下标大于 n/2n/2，那么中位数位于它的左边，可以接着在它的左边部分的数组中查找；如果它的下标小于 n/2n/2，那么中位数位于它的右边，可以接着在它的右边部分的数组中查找。

# 解法二：基于数组特点的时间复杂度为 O(n)O(n) 的算法

数组中有一个数字出现的次数超过数组长度的一半，也就是说它出现的次数比其他所有数字出现次数的和还要多。因此，可以考虑在遍历数组的时候保存两个值：一个是数组中的一个数字；另一个是该数字出现的次数。当遍历到下一个数字的时候，如果下一个数字和之前保存的数字相同，则次数加 11；如果和之前保存的数字不同，则次数减 11。如果次数为零，那么需要保存下一个数字，并把次数设为 11。由于要找的数字出现的次数比其他所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把次数设为 11 时对应的数字。

# 代码

# 解法一

#include <iostream>
#include <vector>
using namespace std;
int partition(vector<int> &numbers, int start, int end) {
    if (start == end) {
        return start;
    }
    int pivot = numbers[start];
    int left = start, right = end;
    while (left < right) {
        while (numbers[right] >= pivot) {
            --right;
        }
        numbers[left] = numbers[right];
        while (numbers[left] <= pivot) {
            ++left;
        }
        numbers[right] = numbers[left];
    }
    numbers[left] = pivot;
    return left;
}
int more_than_half_number(vector<int> &numbers) {
    if (numbers.empty()) {
        return 0;
    }
    int mid = numbers.size() >> 2;
    int start = 0;
    int end = numbers.size() - 1;
    int index = partition(numbers, start, end);
    while (index != mid) {
        if (index > mid) {
            end = index - 1;
            index = partition(numbers, start, end);
        } else {
            start = index + 1;
            index = partition(numbers, start, end);
        }
    }
    int result = numbers[mid];
    return result;
}
# 解法二


int more_than_half_numbers(vector<int> &numbers) {
    if (numbers.empty()) {
        return 0;
    }
    int result = numbers[0];
    int times = 1;
    for (int i = 1; i < numbers.size(); ++i) {
        if (times == 0) {
            result = numbers[i];
            times = 1;
        } else if (numbers[i] == result) {
            ++times;
        } else {
            --times;
        }
    }
    return result;
}
# 面试题 40：最小的 kk 个数


# 题目


输入 nn 个整数，找出其中最小的 kk 个数。例如，输入 44、55、11、66、22、77、33、88 这 88 个数字，则最小的 44 个数字是 11、22、33、44。


# 思路


# 解法一：时间复杂度为 O(n)O(n) 的算法，需要修改输入的数组


可以基于  partition  函数来解决这个问题。如果基于数组的第 kk 个数字来调整，则使得比第 kk 个数字小的所有数字都位于数组的左边，比第 kk 个数字大的所有数字都位于数组的右边。这样调整之后，位于数组中左边的 kk 个数字就是最小的 kk 个数字（这 kk 个数字不一定是有序的）。


# 解法二：时间复杂度为 O(nlog⁡k)O(n\log k) 的算法，适合处理海量数据


可以选择用最大堆来实现存储这 kk 个数据。在最大堆中，根节点的值总是大于它的子树中任意节点的值，可以在 O(1)O(1) 时间内得到己有的 kk 个数字中的最大值，但需要 O(log⁡k)O(\log k) 时间完成删除及插入操作。


如果容器中己有的数字少于 kk 个，则直接把这次读入的整数放入容器之中；如果容器中己有 kk 个数字了，找出这 kk 个数中的最大值，然后拿这次待插入的整数和最大值进行比较。如果待插入的值比当前己有的最大值小，则用这个数替换当前已有的最大值；如果待插入的值比当前已有的最大值还要大，那么这个数不可能是最小的 kk 个整数之一，于是可以丢弃这个数。


# 代码


# 解法一


#include <iostream>
#include <vector>
using namespace std;
int partition(vector<int> &numbers, int start, int end) {
    if (start == end) {
        return start;
    }
    int pivot = numbers[start];
    int left = start, right = end;
    while (left < right) {
        while (numbers[right] >= pivot) {
            --right;
        }
        numbers[left] = numbers[right];
        while (numbers[left] <= pivot) {
            ++left;
        }
        numbers[right] = numbers[left];
    }
    numbers[left] = pivot;
    return left;
}
vector<int> get_least_k_numbers(vector<int> &numbers, int k) {
    vector<int> ans;
    if (numbers.empty() || k > numbers.size() || k <= 0) {
        return ans;
    }
    int start = 0;
    int end = numbers.size() - 1;
    int index = partition(numbers, start, end);
    while (index != k - 1) {
        if (index > k - 1) {
            end = index - 1;
            index = partition(numbers, start, end);
        } else {
            start = index + 1;
            index = partition(numbers, start, end);
        }
    }
    for (int i = 0; i < k; ++i) {
        ans.push_back(numbers[i]);
    }
    return ans;
}
# 解法二


#include <iostream>
#include <vector>
#include <set>
#include <functional>
using namespace std;
typedef multiset<int, greater<int>> int_set;
typedef multiset<int, greater<int>>::iterator set_iterator;
void get_least_k_numbers(const vector<int> &data, int_set &least_k_numbers, int k) {
    least_k_numbers.clear();
    if (k < 1 || data.size() < k) {
        return;
    }
    vector<int>::const_iterator iter = data.begin();
    for ( ; iter != data.end(); ++iter) {
        if (least_k_numbers.size() < k) {
            least_k_numbers.insert(*iter);
        } else {
            set_iterator iter_greatest = least_k_numbers.begin();
            if (*iter < *(least_k_numbers.begin())) {
                least_k_numbers.erase(iter_greatest);
                least_k_numbers.insert(*iter);
            }
        }
    }
}
# 面试题 42：数据流中的中位数


# 题目


如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。


# 思路


可以用两个容器储存数据流中的数据。左边的容器存储当前已读取数据的较小的一部分，右边的容器存储当前已读取数据的较大的一部分。两个容器存储的数据数量尽可能均分。我们关心的其实是数据流中间的数字。可以用一个最大堆实现左边的数据容器，用一个最小堆实现右边的数据容器。往堆中插入一个数据的时间效率是 O(log⁡n)O(\log n)。只需要 O(1)O(1) 时间就可以得到位于堆顶的数据，因此得到中位数的时间复杂度是 O(1)O(1)。


为了实现平均分配，可以在数据的总数目是偶数时把新数据插入最小堆，否则插入最大堆。还要保证最大堆中的所有数据都要小于最小堆中的数据。当数据的总数目是偶数时，可以先把这个新的数据插入最大堆，接着把最大堆中最大的数字拿出来插入最小堆。


# 代码


#include <iostream>
#include <functional>
#include <vector>
#include <algorithm>
using namespace std;
template<typename T>
class DynamicArray {
public:
    void insert(T num) {
        if (((min.size() + max.size()) & 1) == 0) {
            if (max.size() > 0 && num < max[0]) {
                max.push_back(num);
                push_heap(max.begin(), max.end(), less<T>());
                num = max[0];
                pop_heap(max.begin(), max.end(), less<T>());
                max.pop_back();
            }
            min.push_back(num);
            push_heap(min.begin(), min.end(), greater<T>());
        } else {
            if (min.size() > 0 && min[0] < num) {
                min.push_back(num);
                push_heap(min.begin(), min.end(), greater<T>());
                num = min[0];
                pop_heap(min.begin(), min.end(), greater<T>());
                min.pop_back();
            }
            max.push_back(num);
            push_heap(max.begin(), max.end(), less<T>());
        }
    }
    T get_median() {
        int size = min.size() + max.size();
        if (size == 0) {
            throw "No numbers are available";
        }
        T median = 0;
        if ((size & 1) == 1) {
            median = min[0];
        } else {
            median = (min[0] + max[0]) / 2;
        }
        return median;
    }
private:
    vector<T> min;
    vector<T> max;
};
# 面试题 42：连续子数组的最大和


# 题目


输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n)O(n)。


# 思路


动态规划的转移函数：


f(i)={A[i],i=0 or f(i−1)≤0;f(i−1)+A[i],i≠0 and f(i−1)>0f(i) = \begin{cases}
A[i], & i = 0 \text{ or } f(i-1) \le 0;\\
f(i-1) + A[i], & i \ne 0 \text{ and } f(i-1) > 0
\end{cases}



当以第 i−1i - 1 个数字结尾的子数组中所有数字的和小于 00 时，如果把这个负数与第 ii 个数累加，则得到的结果比第 ii 个数字本身还要小，所以这种情况下以第 ii 个数字结尾的子数组就是第 ii 个数字本身。如果以第 i−1i-1 个数字结尾的子数组中所有数字的和大于 00，则与第 ii 个数字累加就得到以第 ii 个数字结尾的子数组中所有数字的和。


# 代码


#include <iostream>
#include <vector>
using namespace std;
int find_greatest_sum_of_subarray(vector<int> &data) {
    if (data.empty()) {
        return 0;
    }
    int current_sum = 0;
    int greatest_sum = 0x80000000;
    for (int i = 0; i < data.size(); ++i) {
        if (current_sum <= 0) {
            current_sum = data[i];
        } else {
            current_sum += data[i];
        }
        if (current_sum > greatest_sum) {
            greatest_sum = current_sum;
        }
    }
    return greatest_sum;
}
# 面试题 43：1 n1~n 整数中 11 出现的次数


# 题目


输入一个整数 nn，求 11~nn 这 nn 个整数的十进制表示中 11 出现的次数。


# 思路


详细思路见链接.


# 代码


#include <iostream>
int counti_digit_one(int n) {
    unsigned int digit = 1;
    int res = 0;
    int high = n / 10, cur = n % 10, low = 0;
    while(high != 0 || cur != 0) {
        if(cur == 0) res += high * digit;
        else if(cur == 1) res += high * digit + low + 1;
        else res += (high + 1) * digit;
        low += cur * digit;
        cur = high % 10;
        high /= 10;
        digit *= 10;
    }
    return res;
}
# 面试题 44：数字序列中某一位的数字


# 题目


数字以  0123456789101112131415...  的格式序列化到一个字符序列中。在这个序列中，第 55 位（从 00 开始计数）是 55，第 1313 位是 11，第 1919 位是 44，等等。请写一个函数，求任意第 nn 位对应的数字。


# 思路


见链接。


# 代码


#include <iostream>
using namespace std;
int find_Nth_digit(int n) {
    int digit = 1;
    long long start = 1;
    long long count = 9;
    while (n > count) { // 1.
        n -= count;
        digit += 1;
        start *= 10;
        count = digit * start * 9;
    }
    long long num = start + (n - 1) / digit; // 2.
    return to_string(num)[(n - 1) % digit] - '0'; // 3.
}
# 面试题 45：把数组排成最小的数


# 题目


输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如，输入数组 {3,32,321}\{3,32,321\}，则打印出这 33 个数字能排成的最小数字 321323321323。


# 思路


根据题目的要求，两个数字 mm 和 nn 能拼接成数字 mnmn 和 nmnm。如果 mn<nmmn < nm，那么应该打印出 mnmn，也就是 mm 应该排在 nn 的前面，我们定义此时 mm 小于 nn。反之，如果 nm<mnnm < mn，则我们定义 nn 小于 mm；如果 mn=nmmn = nm，则 mm 等于 nn。


关于定义的自反性、对称性和传递性的证明，见链接


# 代码


#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
using namespace std;
string minNumber(vector<int>& nums) {
    sort(nums.begin(), nums.end(), [](int a, int b) {
        string a_str = to_string(a);
        string b_str = to_string(b);
        return a_str + b_str < b_str + a_str;
    });
    ostringstream output;
    for (int i = 0; i < nums.size(); ++i) {
        output << to_string(nums[i]);
    }
    return output.str();
}
# 面试题 46：把数字翻译成字符串


# 题目


给定一个数字，我们按照如下规则把它翻译为字符串：00 翻译成  a ，11 翻译成  b ，……，1111 翻译成  11 ，……，2525 翻译成  z 。一个数字可能有多个翻译。例如，1225812258 有 55 种不同的翻译，分别是  bccfi 、 bwfi 、 bczi 、 mcfi  和  mzi 。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。


# 思路


定义函数 f(i)f(i) 表小从第 ii 位数字开始的不同翻译的数目，那么 f(i)=f(i+1)+g(i,i+1)×f(i+2)f(i)=f(i+1)+g(i,i+1)\times f(i+2)。当第 ii 位和第 i+1i+1 位两位数字拼接起来的数字在 1010~2525 的范围内时，函数的值为 11；否则为 00。


# 代码


#include <iostream>
#include <vector>
#include <string>
using namespace std;
int translate_num(int num) {
    string str = to_string(num);
    int len = str.size();
    if(len < 2) return len;
    vector<int> dp(len+1);
    dp[1] = 1;
    dp[0] = 1;
    for(int i = 2;i <= len;i++){
        if(str[i-2] == '1' || (str[i-2] == '2' && str[i-1] <= '5')) dp[i] = dp[i-2]+dp[i-1];
        else dp[i] = dp[i-1];
    }
    return dp[len];
}
# 面试题 47：礼物的最大价值


# 题目


在一个的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 00)。你可以从棋盘的左上角开始拿格子里的礼物，并每次向左或者向下移动一格，直到到达棋盘的右下角。给定一个棋盘及其上面的礼物，请计算你最多能拿到多少价值的礼物？


# 思路


这是一个典型的能用动态规划解决的问题。先用递归的思路来分析。定义第一个函数 f(i,j)f(i,j) 表示到达坐标为 (i,j)(i,j) 的格子时能拿到的礼物总和的最大值。根据题目的要求，有两种可能的途径到达坐标为 (i,j)(i,j) 的格子：通过格子 (i−1,j)(i-1,j) 或者 (i,j−1)(i, j-1)。所以 f(i,j)=max⁡(f(i−1,j),f(i,j−1))+gift[i,j]f(i,j)=\max(f(i-1,j),f(i,j-1)) + \text{gift}[i,j]。gift[i,j]\text{gift}[i,j] 表示坐标为 (i,j)(i,j) 的格子里礼物的价值。


为了缓存中间计算结果，需要一个辅助的二维数组。数组中坐标为 (i,j)(i,j) 的元素表示到达坐标为 (i,j)(i,j) 的格子时能拿到的礼物价值总和的最大值。


# 代码


#include <iostream>
#include <vector>
using namespace std;
int maxValue(vector<vector<int>>& grid) {
    if (grid.empty()) {
        return 0;
    }
    vector<vector<int>> dp(grid.size() + 1, vector<int>(grid[0].size() + 1, 0));
    for (int i = 1; i <= grid.size(); ++i) {
        for (int j = 1; j <= grid[0].size(); ++j) {
            int val = grid[i - 1][j - 1];
            dp[i][j] = val + max(dp[i][j - 1], dp[i - 1][j]);
        }
    }
    return dp[grid.size()][grid[0].size()];
}
# 面试题 48：最长不含重复字符的子字符串


# 题目


请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。假设字符串中只包含  a ~ z  的字符。例如，在字符串  arabcacfr  中，最长的不含重复字符的子字符串是  acfr ，长度为 44。


# 思路


定义函数 f(i)f(i) 表示以第 ii 个字符为结尾的不包含重复字符的子字符串的最长长度。我们从左到右逐一扫描字符串中的每个字符。当我们计算以第 ii 个字符为结尾的不包含重复字符的子字符串的最长长度 f(i)f(i) 时，己经知道 f(i−1)f(i-1) 了。


如果第 ii 个字符之前没有出现过，那么 f(i)=f(i−1)+1f(i) = f(i-1) + 1。


如果第 ii 个字符之前已经出现过，先计算第 ii 个字符和它上次出现在字符串中的位置的距离，并记为 dd。接着分两种情形分析。


第一种情形是 dd 小于或者等于 f(i−1)f(i-1)，此时第 ii 个字符上次出现在 f(i−1)f(i-1) 对应的最长子字符串之中，因此 f(i)=df(i) = d。同时这也意味着在第 ii 个字符出现两次所夹的子字符串中再也没有其他重复的字符了。


第二种情形是 dd 大于此时第 ii 个字符上次出现在 f(i−1)f(i-1) 对应的最长子字符串之前，因此仍然有 f(i)=f(i−1)+1f(i) = f(i-1) + 1。


# 代码


#include <iostream>
#include <string>
#include <vector>
using namespace std;
int longest_substring_without_duplication(string &str) {
    int current_len = 0;
    int max_len = 0;
    vector<int> position(26, -1);
    for (int i = 0; i < str.size(); ++i) {
        int prev_index = position[str[i] - 'a'];
        if (prev_index < 0 || i - prev_index > current_len) {
            ++current_len;
        } else {
            if (current_len > max_len) {
                max_len = current_len;
            }
            current_len = i - prev_index;
        }
        position[str[i] - 'a'] = i;
    }
    if (current_len > max_len) {
        max_len = current_len;
    }
    return max_len;
}