程序员进阶之算法练习(三十五)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 =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<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 = 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<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);
 插入数字2
 collection.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<int>> 里面存对应数字出现的位置;

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;

总结

这5个题目如果都能独立完成,那么水平已经可以足以应付国内各大企业的算法面。 算法重在勤思多练,埋怨公司出算法题是没用的,多花时间准备才是正道。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C/C++基础

华为2017校招C++岗笔试题

输入两个字符串M和N,从字符串M中删除字符串N中所有的字符。例如,输入”abcda”和”ac”,则删除之后的第一个字符串变成”bd”。

5591
来自专栏fangyangcoder

算法导论中的四种基本排序

                                                        by方阳

1232
来自专栏软件测试经验与教训

Python学习笔记(十)

3185
来自专栏小詹同学

Leetcode打卡 | No.015 三数之和

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

1332
来自专栏HTML5学堂

原生JS | 当兔子遇到鸡

HTML5学堂-码匠:当兔子遇到鸡,会怎样呢?先别急,看个小视频~ 视频内容 当兔子遇到鸡 —— 不要害怕和别人不一样,在这个世界上,你就是独一无二的自己! 不...

49210
来自专栏专知

关关的刷题日记12——Leetcode 189. Rotate Array 方法1、2、3

关小刷刷题12 – Leetcode 189. Rotate Array 方法1、2、3 题目 Rotate an array of n elements to...

3708
来自专栏木宛城主

从编译原理看一个解释器的实现

『设计模式』中有一个模式可以解释特定的语法规则,它就是解释器模式(Interpreter Pattern)。不同于常见的策略模式或者是工厂模式,解释器模式在....

78810
来自专栏python3

python3--类的组合,初始类的继承

圆环是由两个圆组成的,圆环的面积是外面圆的面积减去内部圆的面积。圆环的周长是内部圆的周长加上外部圆的周长

1562
来自专栏好好学java的技术栈

“365算法每日学计划”:java语言基础题目及解答(11-15打卡)

自从开始做公众号开始,就一直在思考,怎么把算法的训练做好,因为思海同学在算法这方面的掌握确实还不够。因此,我现在想做一个“365算法每日学计划”。

1231
来自专栏Golang语言社区

深入解析快速排序算法的原理及其Go语言版实现

快速排序是一种基于分治技术的重要排序算法。不像归并排序是按照元素在数组中的位置对它们进行划分,快速排序按照元素的值对它们进行划分。具体来说,它对给定数组中的元素...

3525

扫码关注云+社区

领取腾讯云代金券