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

程序员进阶之算法练习(三十二)LeetCode专场

正文

Copy List with Random Pointer

题目链接 题目大意: 给出一个链表RandomListNode *next, *random; 每个节点有int值,有两个指针,一个指向下一个节点,一个指向链表的任意节点; 现在实现一个深度复制,复制节点的next、random、还有int值;

题目解析: 要求的是复制所有的值,其中的next、int是常规值,遍历一遍赋值即可; 较为复杂的是random指针的复制,random指针有可能指向上一个节点,也可能指向下一个节点,在赋值的时候要保持对应的关系; 这里可以用hash解决,我们把旧链表和新链表的节点一一对应,比如说oldList[i]=>newList[i]; 那么如果random指针指向oldList[i],相当于新链表指向newList[i];

class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        RandomListNode *ret = NULL;
        RandomListNode *p = head;
        unordered_map<RandomListNode *, RandomListNode *> hashMap;
        while (p) {
            RandomListNode *node = new RandomListNode(p->label);
            hashMap[p] = node;
            if (ret) {
                ret->next = node;
            }
            ret = node;
            p = p->next;
        }
        p = head;
        ret = hashMap[head];
        while (p) {
            if (p->random) {
                ret->random = hashMap[p->random];
            }
            p = p->next;
            ret = ret->next;
        }
        return hashMap[head];;
    }
};

复杂度解析: 时间复杂度是O(N) 空间复杂度是O(N)

Insert Interval

题目链接 题目大意: 给出n个不重叠的区间[x, y],并且按照起始坐标x进行从小到大的排序; 现在新增一个区间[a, b],为了保持区间不重叠,对区间进行merge,问剩下的区间有哪些;

Example: **Input: **intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] Output: [[1,2],[3,10],[12,16]] Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

题目解析: 最直接的做法是对所有区间进行处理,分情况讨论: 1、区间[x, y]与[a, b] 无重叠,则不变换; 2、区间[x, y]与[a, b] 有部分重叠,则拿出来特殊处理; 最后从情况2的所有区间和[a, b]中找到一个区间的起始最小值、结束最大值,作为新的区间。

但是这样的代码复杂度比较高,更简洁的做法可以是: 1、把区间[a, b]放入n个区间中,按起始和结束位置从小到大排序; 2、如果区间i的起始位置<=区间i-1的结束位置,则认为是一个区间;

bool cmp(Interval a, Interval b) {
   if (a.start != b.start) {
       return a.start < b.start;
   }
   else {
       return b.end < a.end;
   }
}
class Solution {
public:
   vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
       intervals.push_back(newInterval);
       if (intervals.empty()) return vector<Interval>{};
       vector<Interval> ret;
       sort(intervals.begin(), intervals.end(), cmp);
       ret.push_back(intervals[0]);
       for (int i = 1; i < intervals.size(); ++i) {
           if (ret.back().end < intervals[i].start) { // 新的段
               ret.push_back(intervals[i]);
           }
           else {
               ret.back().end = max(ret.back().end, intervals[i].end);
           }
       }
       return ret;
   }
}leetcode;

复杂度解析: 方法1 时间复杂度是O(N) 空间复杂度是O(N)

方法2 时间复杂度是O(NLogN) 空间复杂度是O(N)

Word Break

题目链接 题目大意: 给出原串s,字符串数组dict,要求: 1、把s分成多个连续的子串; 2、每个子串都在dict里面; 问,是否有解。

s = "leetcode", dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

题目解析: 把一个串分成2个串的可能性有n种可能,n是字符串长度。 那么对于串[l, r] 如果[l, k] 和 [k+1, r]是合法的,那么[l, r]也是合法的。 故而用动态规划: dp[i][j] 表示字符串[i, j]是否为合法的子串; 枚举k∈[i, j] 来判断分割字符串的位置; 转移转移是O(N),因为需要判断区间[i, k]和[k+1, j]是否合法(用字典数配合); 最后判断dp[1, n]是否合法。

class Solution {
public:
    bool dp[N];
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet;
        for (int i = 0; i < wordDict.size(); ++i) {
            wordSet.insert(wordDict[i]);
        }
        memset(dp, 0, sizeof(dp));
        dp[0] = true;
        for (int i = 1; i <= s.length(); ++i) {
            for (int j = i - 1; j >= 0; --j) {
                if (dp[j]) {
                    string substr = string(s.begin() + j, s.begin() + i);
                    if (wordSet.find(substr) != wordSet.end()) {
                        dp[i] = true;
                        break;
                    }
                }
            }
        }
        return dp[s.size()];
    }
}leetcode;

复杂度解析: 时间复杂度 O(N^3) N^2的状态* N的字典数判断。 空间复杂度 O(N^2+M) N^2是状态数量,M是字典数;

优化方案: 1、dp用1维表示;dp[i] 表示前i个是否合理,转移的时候dp[i]=dp[k] && substr(k+1, i) 2、判断substr是否存在时,可以用字典数;

Word Break II

题目链接 在前文Word Break的基础上,输出所有的解。

Input: s = "catsanddog" wordDict = ["cat", "cats", "and", "sand", "dog"] Output: [ "cats and dog", "cat sand dog" ]

题目解析: 用vector来存可能的解,然后用dfs来输出即可。

class Solution {
public:
    vector<int> g[N];
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        vector<string> ret;
        unordered_set<string> wordSet;
        for (int i = 0; i < wordDict.size(); ++i) {
            wordSet.insert(wordDict[i]);
        }
        vector<bool> dp(s.length() + 1, false);
        dp[0] = true;
        for (int i = 1; i <= s.length(); ++i) {
            for (int j = i - 1; j >= 0; --j) {
                if (dp[j]) {
                    string substr = string(s.begin() + j, s.begin() + i);
                    if (wordSet.find(substr) != wordSet.end()) {
                        //                        cout << i << " " << j << " " << substr << endl;
                        dp[i] = true;
                        g[i].push_back(j);
                    }
                }
            }
        }
        vector<string> cur;
        if (dp[s.length()]) {
            dfs(s, ret, cur, s.length());
        }
        return ret;
    }
    
    void dfs(string &s, vector<string> &ret, vector<string> &cur, long n) {
        for (int i = 0; i < g[n].size(); ++i) {
            string str = string(s.begin() + g[n][i], s.begin() + n);
            cur.push_back(str);
            dfs(s, ret, cur, g[n][i]);
            cur.pop_back();
        }
        if (n == 0) {
            string str = cur.back();
            for (int i = cur.size() - 2; i >= 0; --i) {
                str += string(" ");
                str += cur[i];
            }
//            cout << str << endl;
            ret.push_back(str);
        }
    }
}leetcode;

LRU Cache

题目链接 题目大意: 实现一个最近最少使用的缓存算法,要求: get(key) - 返回缓存中key对应的值,如果没有存在缓存,返回-1; set(key, value) - 设置缓存中的key对应的value; 缓存有固定大小。

题目解析: 缓存需要维护两个信息, 1是key和value的对应; 2是value的有效时间; 时间是从小到大,每次会把一个大的值插入(新值),同时可能删掉旧值;(命中) 那么维护一个value的有效时间,优先队列;

这种做法,单次操作的时间复杂度是O(LogN),和题目要求的O(1)有较大的差距;

O(1)表示存储的数据结构只能用数组或者hash加链表的方式。 数组的读取是O(1),但是增删是O(N)的操作; hash+链表的方式较为符合题目的要求,可以实现大致O(1)的查找,也可以实现O(1)的增删操作; 基于此数据结构,我们可以延伸出以下的解法: 1、使用双向链表存储每个key和value; 2、每次get、set已有节点时,把节点放到链表的最前面; 3、每次set的时候如果size已经达到限制,则去掉尾部节点,然后在头部增加节点;

接下来的问题是如何实现O(1)的读取,O(1)的大小判断,以及O(1)的链表移动; O(1)的读取,我们引入unordered_map,然后每次根据key去获取当前节点;(unordered_map 比 map 更快) O(1)的增删操作,我们通过list.splice函数实现;(因为是双向链表,O(1)的增删并不难实现) O(1)的大小判断,list获取size是O(N)的复杂度,所以我们引入一个变量curSize来记录当前节点数量;

总结

从简单的指针复制和区间重叠处理,再到分词、LRU实现,LeetCode的题目更适合面试,这次的题目准备既是为自己练习,也是为了方便后续面试。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode––为求职为生的编程网站

    前言 leetcode是一个在线编程网站,题目源于各大公司的面试、有各种解法、多语言和在线测试支持; 我们扫一眼leetcode上的Company:Googl...

    落影
  • 程序员进阶之算法练习(十七)

    前言 正文6道题目来自leetcode––为求职为生的编程网站,目的是工作闲暇之时锤炼代码功底。 如何从这篇文章受益? 先看题目大意,对照Example的样...

    落影
  • iOS开发笔记(十)— Xcode、UITabbar、特殊机型问题分析

    【问题分析】通过多个文件尝试,发现并非完全不能索引头文件,而是只能索引和当前文件在同级目录的头文件; 有点猜测是Xcode10.1的原因,但是在升级完的半年多...

    落影
  • Deep visual domain adaptation: A survey

    深度视觉域适配作为一个解决大量标注数据缺失的新的学习技巧而出现。与传统的学习共享特征子空间或使用浅层表示重用重要源实例的方法相比,深度域适应方法通过将域适应嵌入...

    于小勇
  • Python有趣时刻,这些代码让你大呼"

    不知道大家第一眼看了这个代码,什么感受?我第一眼的感受是密密麻麻一大堆,读都不想读

    py3study
  • 在Windows商店应用中使用浅色主题

    在开发商店应用时会遇到这样的情况,设计师给我们的设计是浅色背景/深色文本,而商店应用默认是深色背景/浅色文本。那我们需要在每个页面去显式声明背景色和前景色吗,这...

    Shao Meng
  • 【leetcode】String to Integer (atoi)

    Implement atoi to convert a string to an integer.

    阳光岛主
  • 【玩转腾讯云】3分钟打造个人专属云盘,速度吊打某云盘

    ②选择自定义配置——计费模式为“按量付费”——地域选择“北京”——可用区选择“随机可用区”——网络选择“默认”即可

    一只特立独行的兔先生
  • 简单几步,利用Serverless,让COS中文件变更自动刷新CDN

    SCF能实现事件式的触发,让你的一段代码跑在云上,无需自己去搭建服务器。而这里我们要利用能力:COS文件上传/删除的触发器。

    galenye
  • 微信小程序 this.getOpenerEventChannel is not a function

    小程序 添加新的功能, 页面跳转后,通过事件的发布订阅,实现 from => to 或者 to=> from 数据传递

    小蔚

扫码关注云+社区

领取腾讯云代金券