首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >程序面试题之我见

程序面试题之我见

作者头像
用户2615200
发布2019-10-22 19:51:40
3880
发布2019-10-22 19:51:40
举报

版权声明:本文为博主原创文章,遵循 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

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

后记

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

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019-09-30 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

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

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 链表
  • 数组
  • 后记
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档