程序面试题之我见

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/tkokof1/article/details/101788914

本文简述了自己对于程序面试题的一些看法

前些年程序面试题比较流行,自然也涌现了不少网红试题,这里简单讲解一下,也顺道说说自己的看法~

链表

简单起见,以下讨论的链表都是单链表

  • 如何判断两条(不存在环)链表有交点 ? 如果有交点,如何找出交点 ?

存在交点的两条(不存在环)链表,其尾部节点一定是相同的(这里有些朋友可能会有疑问,相交的链表不能是蝶形的吗(这样两条链表就可能存在不相同的尾部节点)?其实对于相交的链表来说,是不可能存在蝶形的相交方式的,因为对于相交的那个链表节点来说,其只有一个链接指针,不能形成蝶形链接),所以我们直接遍历两条链表至尾部,然后比较各自的尾部节点是否相同就可以了~

至于如何找出链表相交的交点,我们要做的就是首先"对齐"两条链表,然后再同步遍历,遇到的第一个相等节点便是链表的交点.

那么怎么"对齐"两条链表呢?方法就是让长度较长的链表先遍历(ll−lsl_l - l_sll​−ls​)个节点(lll_lll​ 为较长链表的长度, lsl_sls​ 为较短链表的长度),然后再开始遍历较短的链表.

(至于如何获取链表的长度,我们可以通过遍历一遍链表的方式来获取)

  • 如何判断链表中存在环 ? 如果有环,如何找出入环点 ?

如果链表中存在环,那么链表就可以一直遍历下去而不会终止,有一个技巧性比较强的方法来判定链表是否存在环:

我们使用两个指针来遍历链表(慢指针和快指针),慢指针每次步进 111 个节点,快指针每次步进 222 个节点,如果两个指针中途相遇(指向相同的节点),则链表存在环,否则则没有环(两个指针中途没有相遇,意味着快指针首先达到了链表尾部,而既然链表存在尾部,自然也就没有环了)

至于为何慢指针和快指针(慢指针每次步进 111 个节点,快指针每次步进 222 个节点)在链表存在环的情况下一定会相遇,有兴趣的朋友可以自己证明一下.

这里可以引申一个更进一步的问题: 如果快慢指针采取另外的步进速度(譬如慢指针每次步进 111 个节点,快指针每次步进 333 个节点),那么在链表存在环的情况下快慢指针还一定会相遇吗?

(我简单分析了一下上述这个引申问题,如果慢指针每次步进 111 个节点,快指针每次步进 333 个节点的话,快慢指针是 不保证 一定会相遇的,至于更一般的情况,还需要进一步的论证)

那么如何找出链表的入环点呢?方法同样需要技巧性:

首先我们要计算出链表中环的元素个数,方法就是扩展使用上述判断链表有环的方法: 当慢指针和快指针相遇时(此时可以判断链表一定有环),那么相遇的那个链表节点就一定是环中的某一节点,我们从这个节点出发遍历链表,当再次回到这个节点的时候,即可得到链表中环的元素个数(设为 lcl_clc​).

得到了链表中环的元素个数,我们便可以尝试找出入环点了:

我们创建两个指针,并让其中一个指针首先步进 lcl_clc​ 个节点,之后再让两个指针同步遍历,当两个指针相遇时,其共同指向的那个链表节点即为链表的入环点.

有兴趣的朋友可以证明一下上述方法的正确性.

进一步的问题 : 如何判断两条存在环的链表有交点 ? 如果有交点,如何找出交点 ? (有兴趣的朋友可以思考一下~)

关于链表的这几个题目,每一个题目的解法都需要一定的技巧,但朴素的来说,我们都可以通过建立节点缓存的方式来解决,虽然空间复杂度更高一些,但是通用性更高,也更容易理解.

数组

  • 如何找出数组中的主元素 ?

首先要说明下什么是数组的主元素,所谓数组的主元素,是指出现次数大于 n/2n / 2n/2 (nnn 为数组的元素个数)的数组元素,例如数组 [2,1,1,1][2, 1, 1, 1][2,1,1,1], 其中 111 出现了 333 次, 大于 n/2=>4/2=>2n / 2 => 4 / 2 => 2n/2=>4/2=>2 次,所以 111 就是这个数组的主元素;而对于数组 [2,1,1,3][2, 1, 1, 3][2,1,1,3], 其中 111 只出现了 222 次(不大于 n/2=>4/2=>2n / 2 => 4 / 2 => 2n/2=>4/2=>2 次),所以 111 不是这个数组的主元素.

现在我们已知一个数组中存在主元素,问题是如何找出这个主元素?

朴素的方法是将数组排序,然后取中间位置的元素即可(不要忘了前提,我们知道数组一定存在主元素)~

代码大概是这个样子(Lua):

function major_element(t)
    -- sort first
    table.sort(t)
    -- return center
    return t[math.ceil(#t / 2)]
end

上述代码的时间复杂度一般是 O(nlgn)O(nlgn)O(nlgn),即等于排序的时间复杂度~

进一步的,既然我们排序的目的是获取中间位置的元素,那么有没有可能在不排序数组的情况下获取中间位置的元素呢?

我们可以使用 BFPRT 算法,算法的细节不少,有兴趣的朋友可以深入了解下,这里我们只要知道该算法可以获取指定位置大小(第 kkk 小)的数组元素,并且时间复杂度为 O(n)O(n)O(n).

function major_element(t)
    return BFPRT(t, math.ceil(#t / 2))
end

现在我们代码的时间复杂度变为了 O(n)O(n)O(n) ~

下面讲一下这个问题的"标准答案",技巧性比较强,问题的关键是你要注意到以下等式:

假设数组 AAA 存在主元素,并且其包含的元素分别为 a0,a1,...ana_0, a_1, ... a_na0​,a1​,...an​,假设 ai≠aja_i \neq a_jai​​=aj​,将 aia_iai​ 和 aja_jaj​ 从数组 AAA 中去除后得到数组 A′A'A′,我们有: AAA 的主元素 = A′A'A′ 的主元素

编码实现上也有一定的技巧性,我们采用计数方式来实现上面的等式,方法是遍历数组,对于相等的元素我们增加计数,对于不相等的元素则减少计数,代码如下(Lua):

function major_element(t)
    local element = t[1]
    local count = 1
    
	for i = 2, #t do
        if t[i] == element then
            count = count + 1
		else
            count = count - 1
            if count == 0 then
                count = 1
                element = t[i]
            end
        end
    end
   
    return element
end
  • 如何判断数组中存在主元素 ?

注意这个问题与上面问题的区别,上面的问题有一个已知条件,即数组存在主元素,而这个问题则没有这个前提,即数组可能存在主元素也可能不存在主元素.

上述基于 排序 或者 BFPRT 的方法可以直接沿用,多出的步骤就是需要判断一下获取到的元素是否确实是主元素,示例代码如下(Lua):

function major_element(t)
    -- sort first
    table.sort(t)
    -- check then
    local pending = t[math.ceil(#t / 2)]
    local check_count = math.floor(#t / 2) + 1
    local count = 0
    for i = 1, #t do
        if t[i] == pending then
            count = count + 1
            if count >= check_count then
                return pending
            end
        end
    end
end

至于上述那种技巧性很强的实现方式,这里就不再适用了…

后记

网上看到的不少面试题,很多都是偏于技巧性质的(譬如上面讲述的几道题目),但个人觉得,这些题目除了测试智力之外,其他的作用就比较有限了,甚至从工程角度考虑,偏于技巧性的方法一般都意味着复杂性和不可扩展性,朴素方法虽然在时间或者空间复杂度上更高一些,但是往往比较简单,容易理解,通用性和扩展性也更好,很多时候其实是工程实现中更优的选择~

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 编程小知识之 自增(自减)运算符

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    用户2615200
  • 编程小知识之 Dithering

    图形后处理有一种操作称为 Dithering(抖动),所谓 Dithering,就是一种能够在较小色彩空间上"模拟出"较大色彩空间的图像处理方法,说的有些抽象,...

    用户2615200
  • Sweet Snippet 之 Gram-Schmidt 正交化

    Gram-Schmidt(格拉姆-施密特) 正交化可以正交化一组给定的向量,使这些向量两两垂直,这里列出一份简单的实现(Lua):

    用户2615200
  • 数组和链表总结

    编译自:Difference between Array and Linked List | Array vs. Linked List

    九州暮云
  • 数据算法(内核链表)

    节点既包含了后续节点的指针,也包含了前趋节点的指针,而且一般都设计成循环,这样就可以非常方便地从链表的任意一个位置开始遍历整个链表。

    用户2617681
  • Leetcode打卡 | No.21 合并两个有序链表

    将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

    小小詹同学
  • 链表看这一篇真的就够了!

    有的小伙伴说没有学过数据结构,对链表不是特别了解,所以今天我们就来对链表进行一个系统的总结,另外大家如果想提高算法思想的话,我建议还是要系统的学一下数据结构的。

    公众号袁厨的算法小屋
  • 数据结构--线性表和链表的基础知识

    近期准备重新学习一下常用数据结构和基本算法,并计划将这些内容的只是做一个整理和归类,准备慢慢写一个常用数据结构与基本算法的系列博文,博文列表参见:常用数据结构与...

    mukekeheart
  • 看动画轻松理解「链表」实现「LRU缓存淘汰算法」

    前几节学习了「链表」、「时间与空间复杂度」的概念,本节将结合「循环链表」、「双向链表」与 「用空间换时间的设计思想」来设计一个很有意思的缓存淘汰策略:LRU缓存...

    五分钟学算法
  • 从简单的线性数据结构开始:穿针引线的链表(一)

    在计算机领域离不开算法和数据结构,而在数据结构中我们往往需要一些灵巧的结构去处理一些繁杂的数据,链表 就是这样一种能穿针引线般的帮助我们去解决这种问题的数据结构...

    五分钟学算法

扫码关注云+社区

领取腾讯云代金券