卖力OA挂经

第一题中规中矩
"""
Given two strings, one is a subsequence if all of the elements of the first string
occur in the same order within the second string. They do not have to be contiguous
in the second string, but order must be maintained. For example, given the string
'I like cheese', the words ('I', 'cheese') are one possible subsequence of that
string

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式

    best_inv = 1


        if best_len == 0:
            dp.append((1, 0, x))
        else:
            dp.append((best_len, best_inv, x))


    max_len = 0
    for length, _, _ in dp:
        max_len = max(max_len, length)
    return n - max_len

想说这个题 是不是 有点类似于 longest increasing subsequence？找到 LIS 之后 结果 - 1 就行？

User_2026 发表于 2025-3-25 19:08
想说这个题 是不是 有点类似于 longest increasing subsequence？找到 LIS 之后 结果 - 1 就行？

例如数组 [1, 5, 2, 3, 4] 的 LIS 是 [1, 2, 3, 4]，长度为 4。如果按照你的思路，结果应该返回 5 - 4 = 1。但实际上应该返回0，因为原数组只有一个逆序对 5, 2已经满足几乎有序

User_2026 发表于 2025-3-25 19:08
想说这个题 是不是 有点类似于 longest increasing subsequence？找到 LIS 之后 结果 - 1 就行？

我感觉有道理，找到 LIS 之后，原数组的长度减去LIS长度再 -1 就行了，是我没想到。。

谢谢分享！想问一下po是怎么拿到面试的呀，我内推自己海投都被拒了

梨花带雨 发表于 2025-3-25 18:32
谢谢分享！想问一下po是怎么拿到面试的呀，我内推自己海投都被拒了

海投的...u1s1我从没做过这么难的OA

微信用户_a69bb13 发表于 2025-3-25 21:35
海投的...u1s1我从没做过这么难的OA

pat pat 会有更好的公司

我也是...就從來過不了賣力簡歷關

梨花带雨 发表于 2025-3-25 18:36
pat pat 会有更好的公司

谢谢宝！

匿名用户 发表于 2025-3-25 18:37
我也是...就從來過不了賣力簡歷關

我感觉就这个难度，肯定不是认真招人，这根本做不出来，估计HR刷KPI呢

微信用户_a69bb13 发表于 2025-3-25 18:39
我感觉就这个难度，肯定不是认真招人，这根本做不出来，估计HR刷KPI呢

沒事，下一間會更好！

匿名用户 发表于 2025-3-25 18:43
沒事，下一間會更好！

谢谢！！