首页 Computer-Science Coding-Interviews

# 面试题 49：丑数

# 题目

我们把只包含因子 22、33 和 55 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 15001500 个丑数。例如，66、88 都是丑数，但 1414 不是，因为它包含因子 77。习惯上把 11 当作第一个丑数。

# 思路

比较直观的做法是从 11 开始，判断一个数是否是丑数，直到找到第 15001500 个丑数，但是这样的做法效率不高。

换一种思路。丑数的因子只有 22、33 和 55 这三种，对于任意一个丑数，可以分解成只包含这些因子的式子。对于每个因子，使用一个计数值来表示该因子的个数。那么对于任意一个丑数，都可以用这样的一个三元组来表示。

不妨设 factor_2 、 factor_3 和 factor_5 表示每个因子的数量。我们需要一种方法来有序的遍历每个丑数。对于一个丑数，将其乘以 22、33 或者 55 中的任意一个因子，都可以得到另一个丑数。我们不妨设当前得到的最大的三个丑数是 M1,M2,M3M_1,M_2,M_3 并且满足 M1<M2<M3M_1 < M_2 < M_3，那么下一个丑数必定是 M1×5,M2×3,M3×2M_1 \times 5, M_2\times 3, M_3\times 2 中的最小值。通过这样的方式，可以有序地遍历丑数，从而找到目标的丑数。

# 代码

#include <vector>
using namespace std;
int get_ugly_number(int n) {
    vector<int> vec = {1};
    int p_2 = 0, p_3 = 0, p_5 = 0;
    for (int i = 1; i < n; ++i) {
        int val = min(2 * vec[p_2], min(3 * vec[p_3], 5 * vec[p_5]));
        if (val == 2 * vec[p_2]) {
            ++p_2;
        }
        if (val == 3 * vec[p_3]) {
            ++p_3;
        }
        if (val == 5 * vec[p_5]) {
            ++p_5;
        }
        vec.push_back(val);
    }
    return vec.back();
}
# 面试题 50：第一个只出现一次的字符


# 题目一：字符串中第一个只出现一次的字符


在字符串中找出第一个只出现一次的字符。如输入  abaccdeff ，则输出  b 。


# 思路


使用一个哈希表，哈希表的键值（Key）定义为字符，值（Value）为该字符出现的次数。


第一次扫描字符串时，每扫描到一个字符，就在哈希表的对应项中把次数加 11。接下来第二次扫描时，每扫描到一个字符，就能从哈希表中得到该字符出现的次数。这样，第一个只出现一次的字符就是符合要求的输出。


# 代码


#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
char first_not_repeating_char(string &str) {
    unordered_map<char, int> table;
    char ans = '0';
    for (char c : str) {
        table[c]++;
    }
    for (char c : str) {
        if (table[c] == 1) {
            ans = c;
            break;
        }
    }
    return ans;
}
# 题目二：字符流中第一个只出现一次的字符


请实现一个函数，用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符  go  时，第一个只出现一次的字符是  g ；当从该字符流中读出前 66 个字符  google  时，第一个只出现一次的字符是  l 。


# 思路


和题目一的思路类似。注意点在于，当一个字符第一次从字符流中读取到时，将其存储到某个容器中；而当该字符再次出现时，将其从容器中删除。需要记录只出现一次的字符的下标。


# 代码


略。


# 面试题 51：数组中的逆序对


# 题目


在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。例如，在数组 {7,5,6,4}\{7,5,6,4\} 中，一共存在 55 个逆序对，分别是 (7,6)(7,6)、(7,5)(7,5)、(7,4)(7,4)、(6,4)(6,4) 和 (5,4)(5,4)。


# 思路


先把数组分隔成子数组，统计出子数组内部的逆序对的数目，然后再统计出两个相邻子数组之间的逆序对的数目。在统计逆序对的过程中，还需要对数组进行排序。整个过程类似于归并排序。


详细解析参考链接。


# 代码


#include <vector>
#include <iostream>
using namespace std;
int inverse_pairs(vector<int> &nums, vector<int> &tmp, int left, int right) {
    if (left >= right) {
        return 0;
    }
    int mid = (left + right) / 2;
    int ans = inverse_pairs(nums, tmp, left, mid) + inverse_pairs(nums, tmp, mid + 1, right);
    // Merge
    int i = left, j = mid + 1;
    for (int k = left; k <= right; ++k) {
        tmp[k] = nums[k];
    }
    for (int k = left; k <= right; ++k) {
        if (i == mid + 1) {
            nums[k] = tmp[j++];
        } else if (j == right + 1 || tmp[i] <= tmp[j]) {
            nums[k] = tmp[i++];
        } else {
            nums[k] = tmp[j++];
            ans += mid - i + 1; // inverse pairs
        }
    }
    return ans;
}
int inverse_pairs(vector<int> &nums) {
    vector<int> tmp(nums.size());
    return inverse_pairs(nums, tmp, 0, nums.size() - 1);
}
# 面试题 52：两个链表的第一个公共节点


# 题目


输入两个链表，找出它们的第一个公共节点。链表节点定义如下：


struct ListNode {
    int m_value;
    ListNode *m_next;
};
# 思路


如果两个单向链表有公共的节点，那么这两个链表从某一节点开始，它们的  m_next  都指向同一个节点。因此从第一个公共节点开始，之后它们所有的节点都是重合的，不可能再出现分叉。所以两个有公共节点而部分重合的链表，其拓扑形状看起来像一个  Y ，而不可能像  X 。我们可以先遍历一次得到两个链表的长度，第二次先在长的链表上走它比短链表多出来的节点数目。接下来两个链表同时遍历，直到找到它们第一个相同的节点，这就是目标节点。


# 代码


#include <iostream>
using namespace std;
struct ListNode {
    int m_value;
    ListNode *m_next;
};
ListNode *find_first_common_node(ListNode *head1, ListNode *head2) {
    int len1 = 0, len2 = 0;
    ListNode *ptr1 = head1;
    ListNode *ptr2 = head2;
    while (ptr1) {
        ++len1;
        ptr1 = ptr1->m_next;
    }
    while (ptr2) {
        ++len2;
        ptr2 = ptr2->m_next;
    }
    if (len2 > len1) {
        swap(head1, head2);
        swap(len1, len2);
    }
    ptr1 = head1;
    ptr2 = head2;
    for (int i = 0; i < len1 - len2; ++i) {
        ptr1 = ptr1->m_next;
    }
    while (ptr1 != nullptr &&
           ptr2 != nullptr &&
           ptr1 != ptr2) {
        ptr1 = ptr1->m_next;
        ptr2 = ptr2->m_next;
    }
    return ptr1;
}