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

MrZONT 發布于2019-08-23 13:42 / 3077人閱讀

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

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

本文由落影發表

前言

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 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

題目鏈接 題目大意：

給出一個數組和一個數字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 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

題目鏈接 題目大意：給出兩個數組，數組只包括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

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

題目鏈接 題目大意：實現一個數據結構，包括以下三個方法： 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 >; first存val，second存出現次數；再用一個哈希map，unordered_map> 里面存對應數字出現的位置；

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

題目鏈接 題目大意：

實現一個數據結構，要求： 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 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;

總結

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

此文已由作者授權騰訊云+社區發布，更多原文請點擊

搜索關注公眾號「云加社區」，第一時間獲取技術干貨，關注后回復1024 送你一份技術課程大禮包！

GPU云服務器云服務器 php程序員如何進階匯編語言程序設計練習題 webrtc之vad算法看動畫學算法之:hashtable

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/99422.html

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

摘要：例如題目解析題目的意思很明顯，就是把兩個數字加起來，需要考慮進位的情況。總結這個題目如果都能獨立完成，那么水平已經可以足以應付國內各大企業的算法面。歡迎大家前往騰訊云+社區，獲取更多騰訊海量技術實踐干貨哦~ 本文由落影發表前言 LeetCode上的題目是大公司面試常見的算法題，今天的目標是拿下5道算法題：題目1是基于鏈表的大數加法，既考察基本數據結構的了解，又考察在處理加法過程中...

Leo_chen 2019-08-16 13:51 評論0 收藏0
前端該如何準備數據結構和算法？

摘要：很多前端同學在看到數據結構和算法后會有一定的抵觸心理，或者嘗試去練習，但是被難倒，從而放棄。本文選擇的數據結構和算法的類別均是出現頻率最高，以及應用最廣的類別。面試這是非常現實的一點，也是很多前端學習數據結構和算法的原因。一、導讀據我了解，前端程序員有相當一部分對數據結構和算法的基礎概念都不是很清晰，這直接導致很多人在看到有關這部分的內容就會望而卻步。實際上，當你了解了數據結構和...

simon_chen 2019-08-26 14:04 評論0 收藏0
優秀程序員都應該學習的 GitHub 上開源的數據結構與算法項目

摘要：強烈推薦上值得前端學習的數據結構與算法項目，包含圖的演示過程與視頻講解。該倉庫包含了多種基于的算法與數據結構，提供進一步閱讀的解釋和鏈接。數據結構和算法必知必會的個代碼實現。 showImg(https://segmentfault.com/img/bVbvpYZ); 前言算法為王。想學好前端，先練好內功，內功不行，就算招式練的再花哨，終究成不了高手；只有內功深厚者，前端之路才會走得...

cheukyin 2019-08-26 10:17 評論0 收藏0