首页Computer-ScienceCoding-Interviews

# 面试题 58：翻转字符串

# 题目一：翻转单词顺序

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串 I am a student. ，则输出 student. a am I 。

# 思路

第一步翻转句子中所有的字符。比如翻转 I am a student. 中所有的字符得到 .tneduts a ma I ，此时不但翻转了句子中单词的顺序，连单词内的字符顺序也被翻转了。第二步再翻转每个单词中字符的顺序，就得到了 student. a am I 。

# 代码

#include <iostream>
#include <string>
using namespace std;
void reverse(string &str, int begin, int end) {
    if (begin >= str.size() || end >= str.size() || begin > end) {
        return;
    }
    while (begin < end) {
        swap(str[begin], str[end]);
        ++begin;
        --end;
    }
}
void reverse_word(string &str) {
    if (str.empty()) {
        return;
    }
    int begin = 0;
    int end = str.size() - 1;
    reverse(str, begin, end);
    begin = end = 0;
    while (begin < str.size()) {
        if (str[begin] == ' ') {
            ++begin;
            ++end;
        } else if (end == str.size() || str[end] == ' ') {
            reverse(str, begin, --end);
            begin = ++end;
        } else {
            ++end;
        }
    }
}
# 题目二：左旋转字符串


字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串  abcdefg  和数字 22，该函数将返回左旋转两位得到的结果  cdefgab 。


# 思路


以  abcdefg  为例，可以把它分为两部分。把前两个字符分到第一部分，把后面的所有字符分到第二部分。先分别翻转这两部分，于是就得到  bagfedc 。接下来翻转整个字符串，得到的  cdefgab  刚好就是把原始字符串左旋转两位的结果。通过前面的分析，可以发现只需耍调用 33 次前面的  reverse  函数就可以实现字符串的左旋转功能。


# 代码


#include <iostream>
#include <string>
using namespace std;
void reverse(string &str, int begin, int end) {
    if (begin >= str.size() || end >= str.size() || begin > end) {
        return;
    }
    while (begin < end) {
        swap(str[begin], str[end]);
        ++begin;
        --end;
    }
}
void left_rotate_string(string &str, int n) {
    if (str.empty()) {
        return;
    }
    int len = str.size();
    if (len > 0 && n > 0 && n < len) {
        int first_start = 0;
        int first_end = n - 1;
        int second_start = n;
        int second_end = len - 1;
        reverse(str, first_start, first_end);
        reverse(str, second_start, second_end);
        reverse(str, first_start, second_end);
    }
}
# 面试题 59：队列的最大值


# 题目一：滑动窗口的最大值


给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。例如，如果输入数组 {2,3,4,2,6,2,5,1}\{2,3,4,2,6,2,5,1\} 及滑动窗口的大小 33，那么一共存在 66 个滑动窗口，它们的最大值分别为 {4,4,6,6,6,5}\{4,4,6,6,6,5\}。


# 思路


使用单调队列 QQ 存储当前窗口的最大值的下标，QQ 使用双端队列  deque  实现。每次移动窗口时，判断当前队首的元素的下标是否仍在当前窗口的范围内。如果不在范围内，则需要将该元素从队首端移除。


对于新添加的元素，将其和队尾元素进行比较，如果小于队尾元素，则将其直接存储到队列中；如果大于队尾元素，则将队尾元素从队尾端移除，并继续进行比较，直到某个元素比新添加的元素更大，或者队列中无其他元素。


# 代码


#include <iostream>
#include <deque>
#include <vector>
using namespace std;
vector<int> max_in_windows(const vector<int> &numbers, unsigned int size) {
    vector<int> max_in_windows;
    if (numbers.size() >= size && size >= 1) {
        deque<int> index;
        for (unsigned int i = 0; i < size; ++i) {
            while (!index.empty() && numbers[i] >= numbers[index.back()]) {
                index.pop_back();
            }
            index.push_back(i);
        }
        for (unsigned int i = size; i < numbers.size(); ++i) {
            max_in_windows.push_back(numbers[index.front()]);
            while (!index.empty() && numbers[i] >= numbers[index.back()]) {
                index.pop_back();
            }
            if (!index.empty() && index.front() <= (int)(i - size)) {
                index.pop_front();
            }
            index.push_back(i);
        }
        max_in_windows.push_back(numbers[index.front()]);
    }
    return max_in_windows;
}
# 题目二：队列的最大值


请定义一个队列并实现函数  max  得到队列里的最大值，要求函数  max 、 push_back  和  pop_front  的时间复杂度都是 O(1)O(1)。


# 思路


滑动窗口可以看成一个队列。因此和上一题的思路类似。


# 代码


#include <iostream>
#include <deque>
using namespace std;
template<typename T>
class QueueWithMax {
public:
    QueueWithMax() : current_index(0) {}
    void push_back(T number) {
        while (!maximums.empty() && number >= maximums.back().number) {
            maximums.pop_back();
        }
        InternalData internal_data = {number, current_index};
        data.push_back(internal_data);
        maximums.push_back(internal_data);
        ++current_index;
    }
    void pop_front() {
        if (maximums.empty()) {
            throw "Queue is empty.";
        }
        if (maximums.front().index == data.front().index) {
            maximums.pop_front();
        }
        data.pop_front();
    }
    T max() const {
        if (maximums.empty()) {
            throw "Queue is empty.";
        }
        return maximums.front().number;
    }
private:
    struct InternalData {
        T number;
        int index;
    };
    deque<InternalData> data;
    deque<InternalData> maximums;
    int current_index;
};
# 面试题 60：nn 个骰子的点数


# 题目


把 nn 个骰子扔在地上，所有骰子朝上一面的点数之和为 ss。输入 nn，打印出 ss 的所有可能的值出现的概率。


# 思路


考虑用两个数组来存储每种骰子点数的总和出现的次数。


在一轮循环中，第一个数组中的第 nn 个数字表示骰子和为 nn 出现的次数。在下一轮循环中，加上一个新的骰子，此时和为 nn 的骰子出现的次数应该等于上一轮循环中骰子点数和为 n−1n-1、n−2n-2、n−3n-3、n−4n-4、n−5n-5 与 n−6n-6 的次数的总和，所以把另一个数组的第 nn 个数字设为前一个数组对应的第 n−1n-1、n−2n-2、n−3n-3、n−4n-4、n−5n-5 与 n−6n-6 这 66 项之和。


# 代码


#include <vector>
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
const int MAX_VALUE = 6;
void print_probability(int number) {
    if (number < 1) {
        return;
    }
    vector<vector<int>> probabilities(2, vector<int>(MAX_VALUE * number + 1, 0));
    int flag = 0;
    for (int i = 1; i < MAX_VALUE; ++i) {
        probabilities[flag][i] = 1;
    }
    for (int k = 2; k <= number; ++k) {
        for (int i = 0; i < k; ++i) {
            probabilities[1 - flag][i] = 0; // 小于 k 点的骰子点数总和不存在
        }
        for (int i = k; i <= MAX_VALUE * k; ++i) {
            probabilities[1 - flag][i] = 0;
            for (int j = 1; j <= i && j <= MAX_VALUE; ++j) {
                probabilities[1 - flag][i] += probabilities[flag][i - j];
            }
        }
        flag = 1 - flag;
    }
    double total = pow(MAX_VALUE, number);
    for (int i = number; i <= MAX_VALUE * number; ++i) {
        double ratio = (double)probabilities[flag][i] / total;
        printf("%d:%e\n", i, ratio);
    }
}
# 面试题 61：扑克牌的顺子


# 题目


从扑克牌中随机抽 55 张牌，判断是不是一个顺子，即这 55 张牌、是不是连续的。22~1010 为数字本身， A  为 11， J  为 1111， Q  为 1212， K  为 1313，而大、小王可以看成任意数字。


# 思路


不妨把大小王视为 00。如何判断 55 个数字是不是连续的，最直观的方法是把数组排序。值得注意的是，由于 00 可以当成任意数字，可以用 00 去补满数组中的空缺。


如果排序之后的数组不是连续的，即相邻的两个数字相隔若干个数字，那么只要我们有足够的 00 可以补满这两个数字的空缺，这个数组实际上还是连续的。


于是我们需要做 33 件事情：首先把数组排序；其次统计数组中 00 的个数；最后统计排序之后的数组中相邻数字之间的空缺总数。如果空缺的总数小于或者等于 00 的个数，那么这个数组就是连续的；反之则不连续。


# 代码


#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
bool is_continuous(vector<int> &numbers) {
    if (numbers.empty()) {
        return false;
    }
    sort(numbers.begin(), numbers.end());
    int num_of_zero = 0;
    int num_of_gap = 0;
    for (int i = 0; i < numbers.size() && numbers[i] == 0; ++i) {
        ++num_of_zero;
    }
    int small = num_of_zero;
    int large = num_of_zero + 1;
    while (large < numbers.size()) {
        if (numbers[small] == numbers[large]) {
            return false;   // 有对子出现
        }
        num_of_gap += numbers[large] - numbers[small] - 1;
        small = large;
        ++large;
    }
    return num_of_gap <= num_of_zero;
}
# 面试题 62：圆圈中最后剩下的数字


# 题目


00，11，……，n−1n-1 这 nn 个数字排成一个圆圈，从数字 00 开始，每次从这个圆圈里删除第 mm 个数字。求出这个圆圈里剩下的最后一个数字。


# 思路


本题是著名的约瑟夫环（Josephuse) 问题。有两种解题方法。


第一种是用链表模拟圆圈。这里略过。


第二种是分析被删除数字的规律并直接计算出圆圈中最后剩下的数字。这里详细描述这种解决方法。


首先定义一个关于 nn 和 mm 的方程 f(n,m)f(n,m)，表示每次在 nn 个数字 00、11、……、n−1n-1 中删除第 mm 个数字最后剩下的数字。


在这 nn 个数字中，第一个被删除的数字是 (m−1)%n(m-1)\%n，不妨记起为 kk。那么删除 kk 之后剩下的 n−1n-1 个数字为 00、11、……、k−1k-1、k+1k+1、……、n−1n-1，并且下一次删除从数字 k+1k+1 开始计数，从而形成 k+1k+1、……、n−1n-1、00、11、……、k−1k-1 的环，该序列最后剩下的数字也应该是关于 nn 和 mm 的函数，记为 f(n−1,m)f(n-1,m)。最初的序列最后剩下的数字 f(n,m)f(n,m) 一定是删除一个数字之后的序列最后剩下的数字，即 f(n,m)=f(n−1,m)f(n,m)=f(n-1,m)。


把剩下的这 n−1n-1 个数字的序列进行重新映射，形成一个 00~n−2n-2 的序列：


k+1→0k+2→1⋯n−1→n−k−20→n−k−11→n−k⋯k−1→n−2k+1 \rightarrow 0 \\
k+2 \rightarrow 1 \\
\cdots \\
n-1 \rightarrow n-k-2 \\
0 \rightarrow n-k-1 \\
1 \rightarrow n-k \\
\cdots \\
k-1 \rightarrow n-2



将该映射定义为 pp，则 p(x)=(x−k−1)%np(x)=(x-k-1)\%n。该映射的逆映射是 p−1(x)=(x+k+1)%np^{-1}(x)=(x+k+1)\%n。


由于映射之后的序列和最初的序列具有同样的形式，即都是从 00 开始的连续序列，因此仍然可以用函数 ff 来表示，记为 f′(n−1,m)f^\prime(n-1,m)。根据映射规则，映射之前的序列中最后剩下的数字 f(n−1,m)=p−1[f′(n−1,m)+k+1]%nf(n-1,m)=p^{-1}[f^\prime(n-1,m)+k+1]\%n。把 k=(m−1)%nk=(m-1)\%n 代入得到 f(n,m)=f′(n−1,m)=[f(n−1,m)+m]%nf(n,m)=f^\prime(n-1,m)=[f(n-1,m)+m]\%n。


由此可以得到递推公式：


f(n,m)={0,if n=1;[f(n−1,m)+m]%n,if n>1f(n,m) = \begin{cases}
0, & \text{if } n = 1;\\
[f(n-1,m)+m]\%n, & \text{if } n > 1
\end{cases}



# 代码


#include <list>
#include <iostream>
using namespace std;
int simulate(unsigned int n, unsigned int m) {
    if (n < 1 || m < 1) {
        return -1;
    }
    list<int> numbers;
    for (int i = 0; i < n; ++i) {
        numbers.push_back(i);
    }
    list<int>::iterator current = numbers.begin();
    while (numbers.size() > 1) {
        for (int i = 1; i < m; ++i) {
            ++current;
            if (current == numbers.end()) {
                current == numbers.begin();
            }
        }
        list<int>::iterator next = ++current;
        if (next == numbers.end()) {
            next = numbers.begin();
        }
        --current;
        numbers.erase(current);
        current = next;
    }
    return *(current);
}
int analysis(unsigned int n, unsigned int m) {
    if (n < 1 || m < 1) {
        return -1;
    }
    int last = 0;
    for (int i = 2; i <= n; ++i) {
        last = (last + m) % i;
    }
    return last;
}
# 面试题 63：股票的最大利润


# 题目


假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？例如，一只股票在某些时间节点的价格为 {9,11,8,5,7,12,16,14}\{9,11,8,5,7,12,16,14\}。如果我们能在价格为 55 的时候买入并在价格为 1616 时卖出，则能收获最大的利润 11。


# 思路


定义函数 diff(i)\text{diff}(i) 为当卖出价为数组中第 ii 个数字时可能获得的最大利润。显然，在卖出价固定时，买入价越低获得的利润越大。也就是说，如果在扫描到数组中的第 ii 个数字时，只要能够记住之前的 i−1i-1 个数字中的最小值，就能算出在当前价位卖出时可能得到的最大利润。


# 代码


#include <iostream>
#include <vector>
using namespace std;
int max_diff(vector<int> &numbers) {
    if (numbers.size() < 2) {
        return 0;
    }
    int min_val = numbers[0];
    int max_diff = numbers[1] - min_val;
    for (int i = 2; i < numbers.size(); ++i) {
        if (numbers[i - 1] < min_val) {
            min_val = numbers[i - 1];
        }
        int cur_diff = numbers[i] - min_val;
        if (cur_diff > max_diff) {
            max_diff = cur_diff;
        }
    }
    return max_diff;
}