V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
longSwordMan
V2EX  ›  LeetCode

微软面试真题+面试官改编 leetcode 思路(链表篇)

  •  
  •   longSwordMan · 2020-06-22 12:16:42 +08:00 · 1474 次点击
    这是一个创建于 1375 天前的主题,其中的信息可能已经有所发展或是发生改变。

    在上一篇文章与大家分享了动态规划篇,今天想继续跟大家探讨一下链表篇。

    链表是一个非常经典的数据结构,但是也非常 tricky,而且常见的是令人虎躯一震的空间 in place 要求,由于链表的一些特殊性质,经常会作为一个面试考察的重点。

    我们先看一个原题: 从已排序的链表中移除重复的单元,如 1->1->2, 返回 1->2. 1->1->2->3->3, 返回 1->2->3

    思路很简单,双指针,指针往后找,碰到相同的数值,继续往后,直到第一个不同的数,讲慢指针的 next 指向快指针,得解。关键在于 one pass,一次过,如果搞个哈希表来做那是画蛇添足,空间上不是最优解,而空间的考察其实是链表的重中之重,所以这就是我一直强调的,哈希虽好,但要慎用。

    改编题 1: 给定有序链表,如果某元素出现三次以上的,删除该元素,1->1->2->3->3->3, 返回 1->1->2 我们仍然可以双指针,如果数值不同,快慢指针各走一步 遇到相同数值,快指针继续走,同时计数,超过三次就接着往后,碰到新数字后修改慢指针的 next 。

    改编题 2: 但如果改成无序的链表呢? 题目变成:给定无序链表,如果某元素出现三次以上的,删除该元素。 这时候我们要头脑冷静地分析,条件虽然变了,但和之前的题目有什么关联和不同? 这时候不是有序数组,因此相同的数不会团在一起,为了能够方便判断是否有 3 个以上的频次,我们需要借助哈希表去统计出现的频次,key 是链表元素的 value,值是频次。那么第二次遍历的时候,我们把链表的 value 当作 key 去哈希表查找,如果对应值大于三,删除元素,问题得解。算法时间复杂度 O ( n ),空间 O ( n )。

    改编题 3: 无序链表,但如果要求重复元素的个数不超过自身的 value 呢,比如:1-> 1-> 2->3->2->2 改成:1 - 2 - 3 - 2 还是用哈希,只不过需要厘清几个值的关系,该 map:key 是链表的 value,value 是链表 value 出现的频次。循环的时候,第一次遍历统计频次,第二次遍历,如果 map ( node.val )> node.val ,删一个节点,并且同时 map 中的 node.val 值减一,算法时间复杂度 O ( n ),空间 O ( n )得解。

    其他推荐原题: 两链表交叉点问题 链表环问题 链表 merge sort 问题

    这几个经典原题原题的改变我之后在我的荔枝微课直播间都会提及。 可以加微信 longswordMAN 进群+听直播,注明 V2EX 的 id 即可。

    目前尚无回复
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1700 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 16:43 · PVG 00:43 · LAX 09:43 · JFK 12:43
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.