欢迎大家前往腾讯云 + 社区，获取更多腾讯海量技术实践干货哦~
本文由落影发表
前言
LeetCode 上的题目是大公司面试常见的算法题，今天的目标是拿下 5 道算法题：题目 1 是基于链表的大数加法，既考察基本数据结构的了解，又考察在处理加法过程中的边界处理；题目 2 是求数组出现频率前 k 大的数字，考察思维能力，代码很短；题目 3 是给出从两个数组中选择数字，组成一个最大的数字，考察的是贪心的思想；前三个都偏向于考察想法，实现的代码都比较简单；题目 4、5 是数据结构实现题，也是大部分人比较头疼的题目，因为需要较多的数据结构和 STL 实现，并且还有时间和空间的限制。
正文
1、Add Two Numbers II
题目链接 题目大意：
给俩个链表，节点由 0~9 的数字组成，分别表示两个数字；求出两个数字的和，以链表的形式返回。
例如
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
7243 + 564 =7807
Output: 7 -> 8 -> 0 -> 7
题目解析：题目的意思很明显，就是把两个数字加起来，需要考虑进位的情况。因为是单向的链表，遍历后很难回溯，所以先把数字存到 vec 中。并且为了处理方便，vec 的最低位存在 vec 的起始部分。于是从 0 开始遍历两个 vec 即可，注意考虑最后进位的情况。
复杂度解析：时间复杂度是 O(N) 空间复杂度是 O(N)
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *ret = NULL;
vector<int> vec1, vec2;
sum(l1, vec1);
sum(l2, vec2);
int n = vec1.size(), m = vec2.size(), flag = 0;
for (int i = 0; i < n || i < m; ++i) {
int x = 0, y = 0;
if (i < n) {
x = vec1[i];
}
if (i < m) {
y = vec2[i];
}
int s = x + y + flag;
if (s > 9) {
s -= 10;
flag = 1;
}
else {
flag = 0;
}
ListNode *tmp = new ListNode(s);
tmp->next = ret;
ret = tmp;
}
if (flag) {
ListNode *tmp = new ListNode(1);
tmp->next = ret;
ret = tmp;
}
return ret;
}
void sum(ListNode* list, vector<int> &vec) {
if (list->next) {
sum(list->next, vec);
}
vec.push_back(list->val);
}
};
2.Top K Frequent Elements
题目链接 题目大意：
给出一个数组和一个数字 k，返回按数字出现频率的前 k 个的数字；1 <= k <= n, n 是数组大小；
example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].
题目解析：
题目分为两个步骤：1、统计每个数字的出现次数；2、从中选择 k 个次数最多的数字；
一个简单的做法：用哈希表统计每个数字的出现次数；把每个数字的出现次数和数字组成一个 pair，放入优先队列；
这样从优先队列中取出 k 个即可。
复杂度解析：时间复杂度是 O(NlogN)，主要在最后的优先队列。
其他解法：有一个 O(NlogK) 的优化；首先把队列变成最小有限队列，每次 pair 放入优先对时，如果当前的 size 大于 k，那么弹出 top；这样每次的操作从 O(logN) 变成 O(logK)。
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> numsHash;
for (int i = 0; i < nums.size(); ++i) {
++numsHash[nums[i]];
}
priority_queue<pair<int, int>> q;
for (int i = 0; i < nums.size(); ++i) {
if(numsHash[nums[i]]) {
q.push(make_pair(numsHash[nums[i]], nums[i]));
numsHash[nums[i]] = 0;
}
}
vector<int> ret;
for (int i = 0; i < k; ++i) {
ret.push_back(q.top().second);
q.pop();
}
return ret;
}
}leetcode;
3、create-maximum-number
题目链接 题目大意：给出两个数组，数组只包括 0~9 十个数字，长度分别为 n、m；从两个数组中选出 k 个数，组成一个长度为 k 的数字，要求：1、从数组 n、m 选择出来的数字相对位置不变；2、最后的数字最大；输出最后的数字。
Example 1:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
return [9, 8, 6, 5, 3]
Example 2:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
return [6, 7, 6, 0, 4]
题目解析：
要求最后数字最大，那么尽可能把数字大的排在前面；在都合法的前提下，99 肯定比 98 要大；那么可以按照这样的贪心策略：先枚举 t，t 表示从数组 nums1 中选出 t 个数字，那么数组 nums2 中应该选出 k - t 个数字；两个数组的所有数字组成最大的数字，因为两个数组间的数字是可以任意顺序，那么只需每次选择较大的放在前面即可。
问题简化成，O(N) 每次从数组中选出 t 个最大的数字；这个可以用贪心解决：假设数组当前枚举到第 i 个，且 nums[i]=x; 从左到右遍历已经选择的数，当遇到一个数字 t，t<x 时，判断插入 x 后，后续是否存在合法解；如果存在则替换，否则直到最后，插入尾部；
class Solution {
public:
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
int n = (int)nums1.size(), m = (int)nums2.size();
vector<int> ret(k, 0);
for (int i = max(0, k – m); i <= k && i <= n; ++i) {
vector<int> tmp1 = maxArray(nums1, i);
vector<int> tmp2 = maxArray(nums2, k – i);
vector<int> tmp = merge(tmp1, tmp2, k);
if (greater(tmp, 0, ret, 0)) {
ret = tmp;
}
}
return ret;
}
vector<int> maxArray(vector<int> &nums, int k) {
int n = (int)nums.size();
vector<int> ret(k, 0);
for (int i = 0, j = 0; i < n; ++i) {
while (n – i + j > k && j > 0 && ret[j – 1] < nums[i]) {
–j;
}
if (j < k) {
ret[j++] = nums[i];
}
}
return ret;
}
vector<int> merge(vector<int>& nums1, vector<int>& nums2, int k) {
vector<int> ret(k, 0);
for (int i = 0, j = 0, r = 0; r < k; ++r) {
ret[r] = greater(nums1, i, nums2, j) ? nums1[i++] : nums2[j++];
}
return ret;
}
bool greater(vector<int> &nums1, int i, vector<int> &nums2, int j) {
while (i < nums1.size() && j < nums2.size() && nums1[i] == nums2[j]) {
++i;
++j;
}
return j == nums2.size() || (i < nums1.size() && nums1[i] > nums2[j]);
}
};
4、Insert Delete GetRandom O(1) – Duplicates allowed
题目链接 题目大意：实现一个数据结构，包括以下三个方法：1、insert(val): 插入一个数字；2、remove(val): 移除一个数字；3、getRandom: O(1) 随机返回一个数字；
Example
插入数字 1；
collection.insert(1);
插入数字 1：
collection.insert(1);
插入数字 2
collection.insert(2);
随机返回数字，要求 2/ 3 可能返回 1，1/ 3 可能返回 2；
collection.getRandom();
题目解析：
插入和移除数字不麻烦，考虑如何在 O(1) 时间返回一个数字。容易知道，放在数组里面可以，然后随机返回一个位置可以实现。增加可以在数组最末端增加；删除数组中间某个数字时，可以把最末端的数字放到删除的位置上；
现在的问题是，如何快速找到数组中该删除的某个位置；考虑用 hash 来实现。数组就是 vector<pair<int, int> >; first 存 val，second 存出现次数；再用一个哈希 map，unordered_map<int, vector<int>> 里面存对应数字出现的位置；
class RandomizedCollection {
public:
/** Initialize your data structure here. */
RandomizedCollection() {
}
/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
bool insert(int val) {
bool ret = hashMap.find(val) == hashMap.end();
hashMap[val].push_back(randVec.size());
randVec.push_back(make_pair(val, hashMap[val].size() – 1));
return ret;
}
/** Removes a value from the collection. Returns true if the collection contained the specified element. */
bool remove(int val) {
bool ret = hashMap.find(val) != hashMap.end();
if (ret) {
auto last = randVec.back();
hashMap[last.first][last.second] = hashMap[val].back();
randVec[hashMap[val].back()] = last;
hashMap[val].pop_back();
if (hashMap[val].empty()) {
hashMap.erase(val);
}
randVec.pop_back();
}
return ret;
}
/** Get a random element from the collection. */
int getRandom() {
return randVec[rand() % randVec.size()].first;
}
private:
unordered_map<int, vector<int>> hashMap;
vector<pair<int, int>> randVec;
}leetcode;
5、All O`one Data Structure
题目链接 题目大意：
实现一个数据结构，要求：1、Inc(Key) – Inserts a new key with value 1. Or increments an existing key by 1. Key is guaranteed to be a non-empty string. 2、Dec(Key) – If Key’s value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string. 3、GetMaxKey() – Returns one of the keys with maximal value. If no element exists, return an empty string “”. 4、GetMinKey() – Returns one of the keys with minimal value. If no element exists, return an empty string “”.
要求所有的数据结构的时间复杂度是 O(1);
题目解析：
在不考虑复杂度的前提下，朴素做法是遍历，O(N); 简单的优化，用 map 来维护优先队列，操作 1、2 先获取 key 值，更新完重新插入；操作 3、4 直接拿队列 top；每个操作的复杂度是 O(LogN);
题目要求是 O(1)，那么必然不能使用树类型的结构，应该利用题目特性，配合 hash 以及贪心来实现。
假设有一个 key-hash 表，来存 key 的对应值。操作 1、先看 keyHash 里面是否有 key，有则 +1，无则插入；操作 2、先看 keyHash 里面是否有 key，有则 -1，无则 Nothing；
为了维护最值，引入链表 list，里面所有的元素是从小到大；每个元素是一个桶，桶里放着值相同的 key；操作 3、直接获取 list 头元素的值；操作 4、直接获取 list 尾元素的值；
同时，操作 1、2 在操作的过程中，需要把当前 key 值从 list 对应的桶里移除，放到上一个或者下一个桶里，或者丢弃。为了实现 O(1) 获取 key 所在位置，可以用 iter-hash 来维护 key 所对应元素的迭代器。
struct Bucket {
int value;
unordered_set<string> keys;
};
class AllOne {
public:
list<Bucket> buckets;
unordered_map<string, list<Bucket>::iterator> bucketOfKey;
/** Initialize your data structure here. */
AllOne() {
}
/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
void inc(string key) {
if (bucketOfKey.find(key) == bucketOfKey.end()) {
bucketOfKey[key] = buckets.insert(buckets.begin(), {0, {key}});
}
auto next = bucketOfKey[key], bucket = next++;
if (next == buckets.end() || next->value > bucket->value + 1) {
next = buckets.insert(next, {bucket->value+1, {}});
}
next->keys.insert(key);
bucketOfKey[key] = next;
bucket->keys.erase(key);
if (bucket->keys.empty()) {
buckets.erase(bucket);
}
}
/** Decrements an existing key by 1. If Key’s value is 1, remove it from the data structure. */
void dec(string key) {
if (bucketOfKey.find(key) == bucketOfKey.end()) {
return ;
}
auto pre = bucketOfKey[key], bucket = pre;
if (pre != buckets.begin()) {
–pre;
}
bucketOfKey.erase(key);
if (bucket->value > 1) {
if (bucket == buckets.begin() || pre->value < bucket->value – 1) {
pre = buckets.insert(bucket, {bucket->value – 1, {}});
}
pre->keys.insert(key);
bucketOfKey[key] = pre;
}
bucket->keys.erase(key);
if (bucket->keys.empty()) {
buckets.erase(bucket);
}
}
/** Returns one of the keys with maximal value. */
string getMaxKey() {
return buckets.empty() ? “” : *(buckets.rbegin()->keys.begin());
}
/** Returns one of the keys with Minimal value. */
string getMinKey() {
return buckets.empty() ? “” : *(buckets.begin()->keys.begin());
}
}leetcode;
总结
这 5 个题目如果都能独立完成，那么水平已经可以足以应付国内各大企业的算法面。算法重在勤思多练，埋怨公司出算法题是没用的，多花时间准备才是正道。
此文已由作者授权腾讯云 + 社区发布，更多原文请点击
搜索关注公众号「云加社区」，第一时间获取技术干货，关注后回复 1024 送你一份技术课程大礼包！