前言

LeetCode上的題目是大公司面試常見的算法題揩慕，今天的目標(biāo)是拿下5道算法題：
題目1是基于鏈表的大數(shù)加法妓局，既考察基本數(shù)據(jù)結(jié)構(gòu)的了解冬阳，又考察在處理加法過程中的邊界處理丑掺；
題目2是求數(shù)組出現(xiàn)頻率前k大的數(shù)字猪钮，考察思維能力品山，代碼很短；
題目3是給出從兩個數(shù)組中選擇數(shù)字躬贡，組成一個最大的數(shù)字谆奥，考察的是貪心的思想；
前三個都偏向于考察想法拂玻，實(shí)現(xiàn)的代碼都比較簡單酸些；
題目4、5是數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)題檐蚜，也是大部分人比較頭疼的題目魄懂，因?yàn)樾枰^多的數(shù)據(jù)結(jié)構(gòu)和STL實(shí)現(xiàn)，并且還有時間和空間的限制闯第。

正文

1市栗、Add Two Numbers II

題目鏈接
題目大意：

給倆個鏈表，節(jié)點(diǎn)由0~9的數(shù)字組成咳短，分別表示兩個數(shù)字填帽；
求出兩個數(shù)字的和，以鏈表的形式返回咙好。

例如
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)

7243 + 564 =7807

Output: 7 -> 8 -> 0 -> 7

題目解析：
題目的意思很明顯篡腌，就是把兩個數(shù)字加起來，需要考慮進(jìn)位的情況勾效。
因?yàn)槭菃蜗虻逆湵磬诘浚闅v后很難回溯叛甫，所以先把數(shù)字存到vec中。
并且為了處理方便杨伙，vec的最低位存在vec的起始部分其监。
于是從0開始遍歷兩個vec即可，注意考慮最后進(jìn)位的情況限匣。

復(fù)雜度解析：
時間復(fù)雜度是O(N)
空間復(fù)雜度是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

題目鏈接
題目大意：

給出一個數(shù)組和一個數(shù)字k抖苦，返回按數(shù)字出現(xiàn)頻率的前k個的數(shù)字；
1 <= k <= n, n是數(shù)組大刑鸥睛约；

 example,
 Given [1,1,1,2,2,3] and k = 2, return [1,2].

題目解析：

題目分為兩個步驟：
1、統(tǒng)計每個數(shù)字的出現(xiàn)次數(shù)哲身；
2辩涝、從中選擇k個次數(shù)最多的數(shù)字；

一個簡單的做法：
用哈希表統(tǒng)計每個數(shù)字的出現(xiàn)次數(shù)勘天；
把每個數(shù)字的出現(xiàn)次數(shù)和數(shù)字組成一個pair怔揩，放入優(yōu)先隊(duì)列；

這樣從優(yōu)先隊(duì)列中取出k個即可脯丝。

復(fù)雜度解析：
時間復(fù)雜度是O(NlogN)商膊，主要在最后的優(yōu)先隊(duì)列。

其他解法：
有一個O(NlogK)的優(yōu)化宠进；
首先把隊(duì)列變成最小有限隊(duì)列晕拆，
每次pair放入優(yōu)先對時，如果當(dāng)前的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

題目鏈接
題目大意：
給出兩個數(shù)組昆庇，數(shù)組只包括0~9十個數(shù)字，長度分別為n闸溃、m整吆；
從兩個數(shù)組中選出k個數(shù)，組成一個長度為k的數(shù)字辉川，要求：
1表蝙、從數(shù)組n、m選擇出來的數(shù)字相對位置不變乓旗；
2府蛇、最后的數(shù)字最大；
輸出最后的數(shù)字寸齐。

 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]

題目解析：

要求最后數(shù)字最大欲诺，那么盡可能把數(shù)字大的排在前面；
在都合法的前提下渺鹦，99* 肯定比 98*要大扰法；
那么可以按照這樣的貪心策略：
先枚舉t，t表示從數(shù)組nums1中選出t個數(shù)字毅厚，那么數(shù)組nums2中應(yīng)該選出k-t個數(shù)字塞颁；
兩個數(shù)組的所有數(shù)字組成最大的數(shù)字，因?yàn)閮蓚€數(shù)組間的數(shù)字是可以任意順序吸耿，那么只需每次選擇較大的放在前面即可祠锣。

問題簡化成，O(N)每次從數(shù)組中選出t個最大的數(shù)字咽安；
這個可以用貪心解決：
假設(shè)數(shù)組當(dāng)前枚舉到第i個伴网，且nums[i]=x;
從左到右遍歷已經(jīng)選擇的數(shù)，當(dāng)遇到一個數(shù)字t妆棒，t<x時澡腾，判斷插入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

題目鏈接
題目大意：
實(shí)現(xiàn)一個數(shù)據(jù)結(jié)構(gòu)，包括以下三個方法：
1喇肋、insert(val): 插入一個數(shù)字坟乾；
2、remove(val): 移除一個數(shù)字苟蹈；
3糊渊、getRandom: O(1)隨機(jī)返回一個數(shù)字；

 Example
 插入數(shù)字1慧脱；
 collection.insert(1);
 插入數(shù)字1：
 collection.insert(1);
 插入數(shù)字2
 collection.insert(2);
 隨機(jī)返回數(shù)字渺绒，要求 2/3可能返回1， 1/3可能返回2菱鸥；
 collection.getRandom();

題目解析：

插入和移除數(shù)字不麻煩宗兼，考慮如何在O(1)時間返回一個數(shù)字。
容易知道氮采，放在數(shù)組里面可以殷绍，然后隨機(jī)返回一個位置可以實(shí)現(xiàn)。
增加可以在數(shù)組最末端增加鹊漠；
刪除數(shù)組中間某個數(shù)字時主到，可以把最末端的數(shù)字放到刪除的位置上茶行；

現(xiàn)在的問題是，如何快速找到數(shù)組中該刪除的某個位置登钥；
考慮用hash來實(shí)現(xiàn)畔师。
數(shù)組就是vector<pair<int, int> >; first存val，second存出現(xiàn)次數(shù)牧牢；
再用一個哈希map看锉，unordered_map<int, vector<int>> 里面存對應(yīng)數(shù)字出現(xiàn)的位置；

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

題目鏈接
題目大意：

實(shí)現(xiàn)一個數(shù)據(jù)結(jié)構(gòu)伯铣，要求：
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 "".

要求所有的數(shù)據(jù)結(jié)構(gòu)的時間復(fù)雜度是O(1);

題目解析：

在不考慮復(fù)雜度的前提下掌唾，樸素做法是遍歷蹬蚁，O(N);
簡單的優(yōu)化，用map來維護(hù)優(yōu)先隊(duì)列郑兴，操作1犀斋、2先獲取key值，更新完重新插入情连；操作3叽粹、4直接拿隊(duì)列top；每個操作的復(fù)雜度是O(LogN);

題目要求是O(1)却舀，那么必然不能使用樹類型的結(jié)構(gòu)虫几，應(yīng)該利用題目特性，配合hash以及貪心來實(shí)現(xiàn)挽拔。

假設(shè)有一個key-hash表辆脸，來存key的對應(yīng)值。
操作1螃诅、先看keyHash里面是否有key啡氢，有則+1，無則插入术裸；
操作2倘是、先看keyHash里面是否有key，有則-1袭艺，無則Nothing搀崭；

為了維護(hù)最值，引入鏈表list猾编，里面所有的元素是從小到大瘤睹；每個元素是一個桶升敲，桶里放著值相同的key；
操作3轰传、直接獲取list頭元素的值冻晤；
操作4、直接獲取list尾元素的值绸吸；

同時，操作1设江、2在操作的過程中锦茁，需要把當(dāng)前key值從list對應(yīng)的桶里移除蕴茴，放到上一個或者下一個桶里银受，或者丟棄习寸。
為了實(shí)現(xiàn)O(1)獲取key所在位置莲镣，可以用iter-hash來維護(hù)key所對應(yīng)元素的迭代器蚁鳖。

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;

總結(jié)

算法重在勤思多練藻雌，也基本都是面試前才會花很多時間去練習(xí)栅贴。
最近在忙新項(xiàng)目著瓶，積累了很多新的感觸瞳秽，但是還沒時間去整理出來瓣履，只能先更新算法練習(xí)。
每天中午飯后一道m(xù)edium练俐，能堅持一年也會有上百道題袖迎。