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

MrZONT 發(fā)布于2019-08-23 13:42 / 3081人閱讀

摘要：例如題目解析題目的意思很明顯，就是把兩個(gè)數(shù)字加起來，需要考慮進(jìn)位的情況?？偨Y(jié)這個(gè)題目如果都能獨(dú)立完成，那么水平已經(jīng)可以足以應(yīng)付國(guó)內(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是給出從兩個(gè)數(shù)組中選擇數(shù)字，組成一個(gè)最大的數(shù)字，考察的是貪心的思想；前三個(gè)都偏向于考察想法，實(shí)現(xiàn)的代碼都比較簡(jiǎn)單；題目4、5是數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)題，也是大部分人比較頭疼的題目，因?yàn)樾枰^多的數(shù)據(jù)結(jié)構(gòu)和STL實(shí)現(xiàn)，并且還有時(shí)間和空間的限制。

正文 1、Add Two Numbers II

題目鏈接 題目大意：

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

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

7243 + 564 =7807

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

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

復(fù)雜度解析：時(shí)間復(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

題目鏈接 題目大意：

給出一個(gè)數(shù)組和一個(gè)數(shù)字k，返回按數(shù)字出現(xiàn)頻率的前k個(gè)的數(shù)字； 1 <= k <= n, n是數(shù)組大?。?/p>

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

題目解析：

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

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

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

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

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

題目鏈接 題目大意：給出兩個(gè)數(shù)組，數(shù)組只包括0~9十個(gè)數(shù)字，長(zhǎng)度分別為n、m；從兩個(gè)數(shù)組中選出k個(gè)數(shù)，組成一個(gè)長(zhǎng)度為k的數(shù)字，要求： 1、從數(shù)組n、m選擇出來的數(shù)字相對(duì)位置不變； 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個(gè)數(shù)字，那么數(shù)組nums2中應(yīng)該選出k-t個(gè)數(shù)字；兩個(gè)數(shù)組的所有數(shù)字組成最大的數(shù)字，因?yàn)閮蓚€(gè)數(shù)組間的數(shù)字是可以任意順序，那么只需每次選擇較大的放在前面即可。

問題簡(jiǎn)化成，O(N)每次從數(shù)組中選出t個(gè)最大的數(shù)字；這個(gè)可以用貪心解決：假設(shè)數(shù)組當(dāng)前枚舉到第i個(gè)，且nums[i]=x; 從左到右遍歷已經(jīng)選擇的數(shù)，當(dāng)遇到一個(gè)數(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)一個(gè)數(shù)據(jù)結(jié)構(gòu)，包括以下三個(gè)方法： 1、insert(val): 插入一個(gè)數(shù)字； 2、remove(val): 移除一個(gè)數(shù)字； 3、getRandom: O(1)隨機(jī)返回一個(gè)數(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í)間返回一個(gè)數(shù)字。容易知道，放在數(shù)組里面可以，然后隨機(jī)返回一個(gè)位置可以實(shí)現(xiàn)。增加可以在數(shù)組最末端增加；刪除數(shù)組中間某個(gè)數(shù)字時(shí)，可以把最末端的數(shù)字放到刪除的位置上；

現(xiàn)在的問題是，如何快速找到數(shù)組中該刪除的某個(gè)位置；考慮用hash來實(shí)現(xiàn)。數(shù)組就是vector >; first存val，second存出現(xiàn)次數(shù)；再用一個(gè)哈希map，unordered_map> 里面存對(duì)應(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)一個(gè)數(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)的時(shí)間復(fù)雜度是O(1);

題目解析：

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

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

假設(shè)有一個(gè)key-hash表，來存key的對(duì)應(yīng)值。操作1、先看keyHash里面是否有key，有則+1，無(wú)則插入；操作2、先看keyHash里面是否有key，有則-1，無(wú)則Nothing；

為了維護(hù)最值，引入鏈表list，里面所有的元素是從小到大；每個(gè)元素是一個(gè)桶，桶里放著值相同的key；操作3、直接獲取list頭元素的值；操作4、直接獲取list尾元素的值；

同時(shí)，操作1、2在操作的過程中，需要把當(dāng)前key值從list對(duì)應(yīng)的桶里移除，放到上一個(gè)或者下一個(gè)桶里，或者丟棄。為了實(shí)現(xiàn)O(1)獲取key所在位置，可以用iter-hash來維護(hù)key所對(duì)應(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個(gè)題目如果都能獨(dú)立完成，那么水平已經(jīng)可以足以應(yīng)付國(guó)內(nèi)各大企業(yè)的算法面。算法重在勤思多練，埋怨公司出算法題是沒用的，多花時(shí)間準(zhǔn)備才是正道。

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

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

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

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

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

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

MrZONT

男|高級(jí)講師

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

TA的文章

imagenet

閱讀 1622·2023-04-26 02:43
自己畫一塊ESP32-C3 的開發(fā)板（第一次使用立創(chuàng)EDA）（更新中...）

閱讀 3040·2021-11-11 16:54
PacificRack中秋閃購(gòu)：2核2G內(nèi)存25G SSD硬盤3.5T月流量@1Gbps帶寬$13.

閱讀 1362·2021-09-23 11:54
前端技術(shù)棧月刊 ???? 2021-08

閱讀 1181·2021-09-23 11:22
Vultr機(jī)房測(cè)評(píng) - Vultr歐洲荷蘭Amsterdam機(jī)房綜合速度和線路去程回程測(cè)試

閱讀 2372·2021-08-23 09:45
CSS魔法堂：更豐富的前端動(dòng)效by CSS Animation

閱讀 855·2019-08-30 15:54
常用跨域方法總結(jié)（2）——CORS

閱讀 3107·2019-08-30 15:53
細(xì)說opacity和層疊上下文

閱讀 3197·2019-08-30 15:53

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

資訊專欄INFORMATION COLUMN

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

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

相關(guān)文章