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回答
-
我看看我能不能说明白...
==========
基本思想就是,三个相等部分的二进制表示,肯定是 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}。
继续加油!:)
012022-10-06
相似问题