程序面试题之我见

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

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

链表

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

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

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

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

那么怎么"对齐"两条链表呢?方法就是让长度较长的链表先遍历( $l_l - l_s$)个节点( $l_l$ 为较长链表的长度, $l_s$ 为较短链表的长度),然后再开始遍历较短的链表.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

数组

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

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

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

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

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

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

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

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

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

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

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

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

假设数组 $A$ 存在主元素,并且其包含的元素分别为 $a_0, a_1, ... a_n$,假设 $a_i \neq a_j$,将 $a_i$ 和 $a_j$ 从数组 $A$ 中去除后得到数组 $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

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

后记

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

转载：https://blog.csdn.net/tkokof1/article/details/101788914