程序員進階之算法練習：LeetCode專場

歡迎大家前往騰訊云+社區，獲取更多騰訊海量技術實踐干貨哦~

本文由落影發表

前言

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 =7807Output: 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 = 5return [9, 8, 6, 5, 3]Example 2:nums1 = [6, 7]nums2 = [6, 0, 4]k = 5return [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);插入數字2collection.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> 里面存對應數字出現的位置；

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;