V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
techme
V2EX  ›  程序员

笔试挂在这道题上面了,求高效解题思路

  •  
  •   techme ·
    megatontech · 2020-05-14 14:01:39 +08:00 · 5515 次点击
    这是一个创建于 1653 天前的主题,其中的信息可能已经有所发展或是发生改变。

    如题,前两题比较简单,第三题还没有头绪就一不留神超时了 *换算几天后星期几 *x 轴上点之间最大距离 *在数组里面找出 K 个数加起来得到最大的偶数和 答题是在个类似 LeetCode 的网站上,会有跑分,优化会影响得分 这次是因为刷题少吃了亏,凌晨时候一点思路都没得 FireShot Capture 024 -.jpg

    34 条回复    2021-03-18 20:56:39 +08:00
    guyeu
        1
    guyeu  
       2020-05-14 14:07:40 +08:00
    第三个题可以转化为数组内最小的正奇数是几。。。
    techme
        2
    techme  
    OP
       2020-05-14 14:14:15 +08:00
    @guyeu
    是不是这样,如果 K 是 3,那么结果就可能是 (奇+奇+偶)(偶+偶+偶)
    在我排序数组后
    找到最大的两个奇数和最大的一个偶数
    找到最大的三个偶数
    然后比较它们和的大小
    Biggoldfish
        3
    Biggoldfish  
       2020-05-14 14:15:57 +08:00   ❤️ 3
    排个序,把前 K 个加起来得到一个和,和是偶数直接返回;和是奇数的话,把前 K 个中最小的奇数换成后面 N - K 个中最大的偶数 或者 把前 K 个中最小的偶数换成后面 N - K 个中最大的奇数,答案一定是两者中较大的一个,如果两者均为奇数,return -1 。
    guyeu
        4
    guyeu  
       2020-05-14 14:17:33 +08:00
    @techme #2 去掉所有的负数,求和,如果和是奇数,就减去最小的奇数返回,如果和是偶数,就直接返回。
    rabbbit
        5
    rabbbit  
       2020-05-14 14:25:39 +08:00
    function isEven(num) {
    ...return num % 2 === 0;
    }

    function solution(A, K) {
    ...if (K === 0) {
    ......return -1;
    ...}
    ...let maxNum = -1;
    ...function dp(i, sum, remain) {
    ......if (remain === 0) {
    .........if (isEven(sum) && sum > maxNum) {
    ............maxNum = sum;
    .........}
    .........return;
    ......}
    ......for (let j = i + 1; j < A.length; j++) {
    .........dp(j, sum + A[j], remain - 1);
    ......}
    ...}
    ...for (let i = 0; i < A.length; i++) {
    ......dp(i, A[i], K - 1);
    ...}
    ...return maxNum;
    }

    console.log(solution([4, 9, 8, 2, 6], 3));
    console.log(solution([5, 6, 3, 4, 2], 5));
    console.log(solution([7, 7, 7, 7, 7], 1));
    console.log(solution([10000], 2));
    console.log(solution([2, 3, 3, 5, 5], 3));
    Jrue0011
        6
    Jrue0011  
       2020-05-14 14:28:04 +08:00
    @guyeu 不用考虑负数吧,题目说都是正数
    @Biggoldfish 我也是这个想法,不过和是奇数只考虑到了替换掉最小的奇数,忘了还能换偶数这回事。。。
    fancy111
        7
    fancy111  
       2020-05-14 14:34:55 +08:00
    最多中级题。
    先从大到小排序,找出前 K 个偶数,如果有就相加 return 结果,如果没有或者少于 K 个,就把最大的奇数加进来。
    特殊情况返回-1 或者全和。
    如果要其他骚操作,也可以加入数据结构。
    noogler67
        8
    noogler67  
       2020-05-14 14:51:18 +08:00 via iPhone
    定义一种数据结构,要么存一个偶数,要么存两个奇数。然后把奇数从大到小排列转成这种数据结构。然后把所有这种数据结构根据平均数排序。
    然后取前 k 个数,如果第 k 个数只能取到一个奇数,就取下一个偶数。
    techme
        9
    techme  
    OP
       2020-05-14 15:15:06 +08:00
    techme
        10
    techme  
    OP
       2020-05-14 15:28:59 +08:00
    @rabbbit 这个递归解法挺好,学习了,感谢
    lenqu
        11
    lenqu  
       2020-05-14 15:42:51 +08:00
    @Biggoldfish 比动态规划好
    daozhihun
        12
    daozhihun  
       2020-05-14 15:52:30 +08:00
    lz 是面试的 ms 嘛
    cloudzhou
        13
    cloudzhou  
       2020-05-14 16:47:08 +08:00
    最后和是偶数,那么 偶数 = n 个偶数 + m 个奇数 ,其中个数 m 是偶数,m + n = k,k 是总个数。
    要求最大值,将数组分成 偶数数组,奇数数组,从大到小排序。
    如果 k 是奇数,k-1 个最大偶数,1 最大奇数,就是答案。
    如果 k 是偶数,首先选取 n = k,然后记录总和;
    L: 然后 n-2,剔除最后 2 个偶数,加上前 2 个奇数,在算一下总和和之前对比(如果这两奇数和小于提出的两偶数和,直接可以 break);
    重复 L,知道偶数数组或者奇数数组为空,不断比较最大的和
    cloudzhou
        14
    cloudzhou  
       2020-05-14 16:50:25 +08:00
    上面 偶数数组,奇数数组,比较就是两个起始 index i, j,一个左移,一个右移,不断逼近的结果,最后得到 i, j
    nznd
        15
    nznd  
       2020-05-14 16:56:53 +08:00
    楼上那些解法妙啊,学习到了
    islxyqwe
        16
    islxyqwe  
       2020-05-14 17:02:53 +08:00
    按奇偶分组,然后分别排序。如果偶数的前两个和比奇数的前两个和大,从偶数提取两个;否则从奇数提取两个。(有一方个数不足 2 个时,只从另一方提取)
    还需取的数不足两个时如果还需提取 1 个就从偶数提取一个,不能提就返回-1
    islxyqwe
        17
    islxyqwe  
       2020-05-14 17:06:21 +08:00
    不对,不能处理[20,18,5,3] k=3 的情况,不太行
    ncabhd
        18
    ncabhd  
       2020-05-14 17:39:29 +08:00
    @Biggoldfish #3 这个解法是对的,在优化就是分奇偶两数组排序查找,从时间复杂度上来讲,差别不是很大
    @techme 贴的代码有个小问题全选没有验证奇偶;还有个可以优化的地方是数组已经是有序,C#的 Any 的实现不是很清楚,我暂且认为是扫描整个数组,这个是没有必要的。
    @rabbbit #5 @techme 这个应该不能算是 DP,应该是 DFS,将所有情况全部列出来,时间复杂度已经涉及到阶乘了
    @cloudzhou #13 如果 K 是奇数,k-1 最大偶数和 1 最大奇数答案是奇数的。而且这个也要按照 L 去计算。
    rabbbit
        19
    rabbbit  
       2020-05-14 17:44:44 +08:00
    @ncabhd
    嗯,写完了才发现时间复杂度太大了,如果体里的 k 比较小可能还能接受.
    对于这道题来数暴力递归应该是不能接受的.
    rabbbit
        20
    rabbbit  
       2020-05-14 17:45:45 +08:00
    嗯,写完了才发现时间复杂度太大了,如果题里的 k 比较小可能还能接受.
    对于这道题来说暴力递归应该是不能接受的.
    cloudzhou
        21
    cloudzhou  
       2020-05-14 18:26:13 +08:00
    @Biggoldfish 的算法,直观上有问题,但是我验证不出来
    @ncabhd 是的,我后面想到了
    为了确保正确,我写了代码,你们需要的话,我们来验证一下:
    https://gist.github.com/cloudzhou/614d3acf70cbe08a616d0be9888e739e
    cloudzhou
        22
    cloudzhou  
       2020-05-14 18:31:35 +08:00
    里面已经有了测试用例,如果你们有新的测试用例,可以加进去,这样很容易验证是否正确
    复杂度来说,最大在于排序,所以是 lgn,我的代码,以便于阅读理解为主,所以不考虑极致性能
    LYEHIZRF
        23
    LYEHIZRF  
       2020-05-14 18:37:56 +08:00
    top K 问题 一律堆排序
    finalwave
        24
    finalwave  
       2020-05-14 20:40:49 +08:00   ❤️ 1
    分成奇偶两个队列构造最大堆取 pair,K 为奇数时保证偶数堆取走 pair 后还有数就行,O(n+klgn)
    yazoox
        25
    yazoox  
       2020-05-14 21:01:41 +08:00
    @techme 看你的截图,你是用的 vscode? 为什么你右侧的那一栏,看起来和我的不一样?有什么插件加载改造过了么?
    wang247
        26
    wang247  
       2020-05-15 00:09:51 +08:00
    动态规划?
    qwertyegg
        27
    qwertyegg  
       2020-05-15 00:28:04 +08:00
    @techme 不要排序啊,最好都是 O(nlogn)。直接扫一遍,把最大的(奇奇偶)和(偶偶偶)扫出来即可
    Biggoldfish
        28
    Biggoldfish  
       2020-05-15 05:21:06 +08:00
    @ncabhd
    在时间复杂度上想要降低的话,可以不必对整个数组排序,利用 quick select algorithm 可以在平均 O(N) 的时间内找到 top K elements,从而我的整个解法可以在 O(N) 完成。不过个人觉得一般笔试应该没人卡这个 logN 。

    @cloudzhou
    只要证明 1. 如果有偶数和一定可以找到 2. 找到的偶数和一定最大 即可。如果有问题的话找个反例就行。我随便写了一下,LZ 的 test case 都能过 https://leetcode.com/playground/WtagcCkG

    @yazoox
    LZ 那个界面是 Visual Studio
    noxe
        29
    noxe  
       2020-05-15 10:56:09 +08:00
    先排序,找出最大的 k 个值( k<n 时结果为-1 )

    如果和是偶数,那么就取这 k 个值。
    否则只有 2 种情况来改变奇偶性:
    1. 用其它值中最大的奇数,替换当前 k 个值中最小的偶数
    2. 用其它值中最大的偶数,替换当前 k 个值中最小的奇数

    如果无法替换,那么为-1
    noxe
        30
    noxe  
       2020-05-15 11:12:59 +08:00
    才发现前面大牛已经说过这思路了,抱歉抱歉😞
    techme
        31
    techme  
    OP
       2020-05-15 13:48:44 +08:00
    @daozhihun 是 FNC 一家做财务软件的
    @yazoox 我的是 vs2019,vsc 里面也可以打开这个 view 里面有个 showminimap
    MorningStar0
        32
    MorningStar0  
       2020-05-26 21:20:30 +08:00
    写在这了,思路大概是堆排序
    xmoiduts
        34
    xmoiduts  
       2021-03-18 20:56:39 +08:00 via Android
    反馈: 某海外通信公司 机试题。也是这个平台也是第三题。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2732 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 12:40 · PVG 20:40 · LAX 04:40 · JFK 07:40
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.