Python技术迷

女朋友要求我把所有的钱都给她管,合理吗?

“把工资卡交出来”这事,谈恋爱里一旦说成默认操作,味儿就有点不对了。网友吐槽女朋友要求他把所有钱都给她管,我第一反应不是浪漫,是警报。谈对象不是入职财务外包,工资一发先全额上交,谁听了不皱眉。

Image

评论区也挺真实。有人说,愿意给是一回事,被要求全给是另一回事。还有人更直接:你这不是找对象,是找了个移动版出纳。话糙,理还真差不多。

钱这东西,最能测边界感。你主动承担开销、一起做规划、甚至拿一部分出来共同管理,都正常。可上来就“全部给我管”,还带点理所当然,那就不是信任,是控制欲在试水。

算法题:分隔链表

链表题里,“分隔链表”算不上难,真写起来却很容易把指针绕乱。尤其是你一边遍历,一边往原链表里插来插去,最后不是丢节点,就是整出环。这个题我一般不碰花活,老老实实拆成两条链表:一条放小于 x 的,一条放大于等于 x 的。最后一拼,稳得很。

题目要求还有个细节,很多人第一眼没太在意:分隔之后,原来的相对顺序不能乱。这就意味着你不能排序,也别想着把节点往头上插。谁先来,谁就老老实实排前面。

比如这组数据:

1 -> 4 -> 3 -> 2 -> 5 -> 2, x = 3

处理完应该是:

1 -> 2 -> 2 -> 4 -> 3 -> 5

注意,两个 2 的先后顺序不能变,4、3、5 的顺序也不能变。

这题最顺手的写法,就是准备两个哑节点。一个管“小链表”,一个管“大链表”。遍历原链表时,看当前节点值和 x 的关系,挂到对应链表尾巴上。遍历结束后,把大链表尾巴置空,再把小链表和大链表接起来。

代码我按平时写法来,不整那些花里胡哨的:

classListNode:
def__init__(self, val=0, next=None):
        self.val = val
        self.next = next


classSolution:
defpartition(self, head: ListNode, x: int) -> ListNode:
        small_dummy = ListNode()
        large_dummy = ListNode()

        small_tail = small_dummy
        large_tail = large_dummy

        cur = head
while cur:
            nxt = cur.next
            cur.next = None

if cur.val < x:
                small_tail.next = cur
                small_tail = cur
else:
                large_tail.next = cur
                large_tail = cur

            cur = nxt

        small_tail.next = large_dummy.next
return small_dummy.next

这里我专门留了两行:

nxt = cur.next
cur.next = None

这不是多余,是真能少踩坑。因为节点是从原链表里“摘”出来的,你不先断开,后面一接,很容易把旧指针关系带过去。链表题里这种 bug 最烦,代码看着没毛病,打印出来一串死循环。

再说下复杂度。这个做法只遍历一遍链表,时间复杂度是 O(n),额外用了几个指针,空间复杂度算 O(1)。面试里这就够了,别自己给自己加戏。

这题本身没什么深奥算法,核心就两个字:稳住。链表题很多时候不是比谁想法多,而是比谁下手不乱。能拆开就拆开,能分桶就分桶,别在原链表上来回折腾。写到这一步,基本就不会翻车了。