Leetcode 927 的疑问

来源:1-5 大厂面试为什么总考算法?

甲骨文_0001

2022-10-06

图片描述

老师,国庆快乐哈:)下面我求解first, second的方式是有问题的,leetcode上我跑了,在如上的用例中执行下来的结果我的逻辑是[-1, -1], 但其实是有解的,刚好是3对 [1, 0], 然后您的github上的逻辑我看了,没看懂,这块切分这块的逻辑老师指点下哈。。。

/**
 * @param {number[]} arr
 * @return {number[]}
 */
var threeEqualParts = function(arr) {
    let sum = 0;
    for( let i = 0; i < arr.length; i ++ ){
        sum += arr[i];
    } // for i
    // 和能否被3整除
    if( sum % 3 != 0 ){
        return [-1, -1];
    }

    const numsOne = sum / 3; // 每份中1的数量

    let first = -1, second = -1; // 数组分成3份, 切割点是first, second, [0, first), [first, second), [second, 结尾+1)
    let count = 0;
    // 接下来求解 first, second
    for( let i = 0; i < arr.length; i ++ ){
        if( arr[i] == 1 ){
            count ++;
        }

        if( count == numsOne ){
            count = 0;
            if( first == -1 ){
                first = i + 1;
            }else{
                second = i + 1;
                break;
            }
        }

    } // for i

    let arr0 = arr.slice(0, first), arr1 = arr.slice(first, second), arr2 = arr.slice(second);
    // 去除数组前导0
    arr0 = trimArr(arr0)
    arr1 = trimArr(arr1)
    arr2 = trimArr(arr2)

    // 看数组拼接后的字符串是否相等
    if( arr0.join('') == arr1.join('') && arr1.join('') == arr2.join('') ){
        return [first - 1, second]
    }
    return [-1, -1];
};

// 去除数组前导0, [0, 1, 0]=>[1, 0]
function trimArr(arr){
    let i = 0;
    for( i = 0; i < arr.length; i ++ ){
        if( arr[i] != 0 ){
            break;
        }
    } // for i
    
    return arr.slice(i);
}``
写回答

1回答

liuyubobobo

2022-10-06

我看看我能不能说明白...


以下讲解基于我的代码:https://github.com/liuyubobobo/Play-Leetcode/blob/master/0501-1000/0927-Three-Equal-Parts/cpp-0927/main.cpp


==========


基本思想就是,三个相等部分的二进制表示,肯定是 1XXXXXX 的形式,前面有可能有前缀 0,但是把前缀 0 去掉,一定是 1XXXXXX 的形式。比如你的例子中,这个二进制表示就是 10。10010000010 的结果也是 10:[10, 010, 000010],只不过在第二个数字和第三个数字前面有前缀 0.


首先数整个字符串的 1 的个数,这些 1 肯定被平均分到三部分中。如果 1 的个数不能被 3 整除,就无解,否则每部分假设有 k 个 1(即总共有 3k 个 1)。(23-28 行)


从后向前先数 k 个 1,数到第 k 个 1 的位置,假设在 j 的位置,那么 A[j... n-1] 的表示,一定是我上面说的 1XXXXXX 的形式。只不过可能还有前缀 0 没考虑。(30-36 行)


现在把整个 A 的前缀 0 扔掉(这些 0 是第一部分的前缀 0),从 A 的第一个 1 开始,看能不能匹配上刚才找到 1XXXXX 的形式,如果能找到,第一部分的结尾就找到了(是 i - 1),否则无解。(38-44 行)


从第一部分结尾的下一个字符开始(从 i 开始),去掉前缀 0(这些 0 是第二部分的前缀 0),从第一个 1 开始(设为 k),看能不能匹配上刚才找到 1XXXXX 的形式,如果能匹配上,第二部分的结尾就找到了(循环结束后的 k - 1)。(46-51 行)


后面可能还有一些 0,这些 0 是第三部分的前缀 0。最终解是 {i - 1, k}。


继续加油!:)

0
1
甲骨文_0001
谢谢老师,理解了。
2022-10-06
共1条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7408 学习 · 1150 问题

查看课程