专栏首页落影的专栏程序员进阶之算法练习(三十五)LeetCode专场

程序员进阶之算法练习(三十五)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;

总结

算法重在勤思多练,也基本都是面试前才会花很多时间去练习。 最近在忙新项目,积累了很多新的感触,但是还没时间去整理出来,只能先更新算法练习。 每天中午饭后一道medium,能坚持一年也会有上百道题。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • java简单使用netty

    由于本人的学过的技术太多太乱了,于是决定一个一个的整合到一个springboot项目里面。

    ydymz
  • 美团面试经历,贡献出来一起学习

      晚7点,因为想到下周一才面试,我刚准备出去打个羽毛球,北京的电话就来了。面试官各种抱歉,说开会拖延了。 1、自我介绍 说了很多遍了,很流畅捡重点介绍完。...

    用户2196435
  • Shiro 实战(四) - 过滤器机制1 简介2 过滤器链

    NameableFilter给Filter起个名字,如果没有设置默认就是FilterName 当我们组装拦截器链时会根据这个名字找到相应的拦截器实例

    JavaEdge
  • 分布式系统关键技术之服务调度

    服务关键程度要通过对业务的梳理来发现。服务依赖关系用Spring Cloud的一套方法就能够非常好的解决,但是千万不要出现循环依赖,解决方式是通过第三方的消息队...

    用户1263954
  • day64_SpringMVC学习笔记_02

    注意:springmvc本身就支持xml格式,所以不用导入其他支持的jar包了。

    黑泽君
  • Shiro实战(七) - 环境搭建及使用1 搭建2 连接数据库与配置 mybatis

    JavaEdge
  • Dubbo 源码分析 - 服务导出全过程解析

    本篇文章,我们来研究一下 Dubbo 导出服务的过程。Dubbo 服务导出过程始于 Spring 容器发布刷新事件,Dubbo 在接收到事件后,会立即执行服务导...

    田小波
  • SpringMVC 教程

       Spring 是目前比较流行的MVC框架,让POJO处理起来变的容易,也支持Rest的Url请求。采用松散的耦合可插拔的接口,比其它MVC接口更具有扩展...

    付威
  • Zookeeper实现参数的集中式管理【面试+工作】

    应用项目中都会有一些参数,一般的做法通常可以选择将其存储在本地配置文件或者内存变量中;对于集群机器规模不大、配置变更不是特别频繁的情况下,这两种方式都能很好的解...

    奋斗蒙
  • JMS实现参数的集中式管理【面试+工作】

    JMS的发布订阅机制也能实现类似的功能,集群节点通过订阅指定的节点,同时使用jms对消息的过滤器功能,实现对指定参数的更新,本文将介绍通过JMS实现简单的参数集...

    奋斗蒙

扫码关注云+社区

领取腾讯云代金券