程序員進(jìn)階之算法練習(xí)：LeetCode專場

Leo_chen 發(fā)布于2019-08-16 13:51 / 3512人閱讀

摘要：例如題目解析題目的意思很明顯，就是把兩個數(shù)字加起來，需要考慮進(jìn)位的情況。總結(jié)這個題目如果都能獨(dú)立完成，那么水平已經(jīng)可以足以應(yīng)付國內(nèi)各大企業(yè)的算法面。

歡迎大家前往騰訊云+社區(qū)，獲取更多騰訊海量技術(shù)實(shí)踐干貨哦~

本文由落影發(fā)表

前言

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)槭菃蜗虻逆湵?，遍歷后很難回溯，所以先把數(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 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 &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)計(jì)每個數(shù)字的出現(xiàn)次數(shù)； 2、從中選擇k個次數(shù)最多的數(shù)字；

一個簡單的做法：用哈希表統(tǒng)計(jì)每個數(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 topKFrequent(vector& nums, int k) {
        unordered_map numsHash;
        for (int i = 0; i < nums.size(); ++i) {
            ++numsHash[nums[i]];
        }
        priority_queue> 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 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

class Solution {
public:
    vector maxNumber(vector& nums1, vector& nums2, int k) {
        int n = (int)nums1.size(), m = (int)nums2.size();
        vector ret(k, 0);
        for (int i = max(0, k - m); i <= k && i <= n; ++i) {
            vector tmp1 = maxArray(nums1, i);
            vector tmp2 = maxArray(nums2, k - i);
            vector tmp = merge(tmp1, tmp2, k);
            if (greater(tmp, 0, ret, 0)) {
                ret = tmp;
            }
        }
        return ret;
    }
    
    vector maxArray(vector &nums, int k) {
        int n = (int)nums.size();
        vector 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 merge(vector& nums1, vector& nums2, int k) {
        vector 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 &nums1, int i, vector &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ī)返回?cái)?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 >; first存val，second存出現(xiàn)次數(shù)；再用一個哈希map，unordered_map> 里面存對應(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> hashMap;
    vector> 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 keys;
};

class AllOne {
public:
    list buckets;
    unordered_map::iterator> bucketOfKey;
    /** Initialize your data structure here. */
    AllOne() {
        
    }
    /** Inserts a new 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é)

這5個題目如果都能獨(dú)立完成，那么水平已經(jīng)可以足以應(yīng)付國內(nèi)各大企業(yè)的算法面。算法重在勤思多練，埋怨公司出算法題是沒用的，多花時間準(zhǔn)備才是正道。

此文已由作者授權(quán)騰訊云+社區(qū)發(fā)布，更多原文請點(diǎn)擊

搜索關(guān)注公眾號「云加社區(qū)」，第一時間獲取技術(shù)干貨，關(guān)注后回復(fù)1024 送你一份技術(shù)課程大禮包！

GPU云服務(wù)器云服務(wù)器 php程序員如何進(jìn)階匯編語言程序設(shè)計(jì)練習(xí)題 webrtc之vad算法看動畫學(xué)算法之:hashtable

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/72447.html

發(fā)表評論

登陸后可評論

0條評論

Leo_chen

男|高級講師

我要關(guān)注我要私信

TA的文章

#11.11# 華納云：全場3折起，美國/香港云服務(wù)器 5M CN2低至24元/月，物理服務(wù)器終身

閱讀 3022·2021-10-27 14:15
阿里云，輕量云服務(wù)器，60元/年，2核/2G/5M帶寬/60GB ESSD/1T流量

閱讀 3014·2021-09-07 10:18
黑科技：CSS定制多行省略

閱讀 1332·2019-08-30 15:53
對象的解構(gòu)賦值

閱讀 1584·2019-08-26 18:18
javascript表格的一些便捷操作

閱讀 3385·2019-08-26 12:15
首屏渲染優(yōu)化策略

閱讀 3468·2019-08-26 10:43
輪播圖js

閱讀 662·2019-08-23 16:43
webpack4 高手之路第三天

閱讀 2218·2019-08-23 15:27

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

程序員進(jìn)階之算法練習(xí)：LeetCode專場

相關(guān)文章