李志成的个人网站

李志成的个人网站

  • 博客
  • ·
  • 留言
  • ·
  • 友链
  • ·
  • 关于
  • ·
  • Rss

leetcode算法题-三等分

发表于2019-03-09 13:09:07分类于算法0条评论阅读次数26

题目

给定一个由 0 和 1 组成的数组 A,将数组分成 3 个非空的部分,使得所有这些部分表示相同的二进制值。

如果可以做到,请返回任何 [i, j],其中 i+1 < j,这样一来:

A[0], A[1], ..., A[i] 组成第一部分; A[i+1], A[i+2], ..., A[j-1] 作为第二部分; A[j], A[j+1], ..., A[A.length - 1] 是第三部分。 这三个部分所表示的二进制值相等。 如果无法做到,就返回 [-1, -1]。

注意,在考虑每个部分所表示的二进制时,应当将其看作一个整体。例如,[1,1,0] 表示十进制中的 6,而不会是 3。此外,前导零也是被允许的,所以 [0,1,1] 和 [1,1] 表示相同的值。

地址:https://leetcode-cn.com/problems/three-equal-parts/

示例 1:

输入:[1,0,1,0,1]
输出:[0,3]

示例 2:

输出:[1,1,0,1,1]
输出:[-1,-1]

提示:

3 <= A.length <= 30000
A[i] == 0 或 A[i] == 1

代码

/**
 * @param {number[]} A
 * @return {number[]}
 */
var threeEqualParts = function (A) {

    // 计算数组的值。用于比较判断
    // 由于是三等分,前值0是不用计算的,为了加快计算速度,所以用字符串来比较是更快的。
    // 转换成字符串,去掉前置0,进行累加生成字符串
    function calc(arr) {
        const len = arr.length;
        let str = '';
        let isZero = false;
        for (let i = 0; i < len; i++) {
            if (arr[i] === 1 && !isZero) {
                isZero = true
            }
            if (isZero) {
                str = str + arr[i]
            }
        }
        return str;
    }

    let A1, A2, A3;
    let oneCount = 0;           // 1的数量
    let tempOneCount = 0;       // 用于遍历临时1的数量
    let lastZeroCount = 0;      // 数组尾部1的个数
    let isLastZeroEnd = false;  // 用于标记数组从最后开始往前的0的个数

    // 计算数组中1的个数
    for (let i = 0; i < A.length; i++) {
        if (A[i] === 1) {
            oneCount++;
        }
        if (A[A.length - i - 1] === 0 && !isLastZeroEnd) {
            lastZeroCount++;
        }
        else {
            isLastZeroEnd = true;
        }
    }

    // 如果1的个数不是3的整数倍,那么这个数组必然不能被三等分
    if (oneCount % 3 != 0) {
        return [-1, -1]
    } else if (oneCount === 0) {
        return [0, A.length - 1];
    }

    // 计算1的个数3等分后的系数k
    const k = oneCount / 3;

    for (let i = 0; i < A.length; i++) {
        if (A[i] === 1) {
            tempOneCount++;

            // 当tempOneCount等于系数k, 则截取到当前的i并且补零的个数,所以要加上lastZeroCount
            if (tempOneCount === k) {
                A1 = A.slice(0, i + 1 + lastZeroCount);
            }

            // 同理
            // 当满足第二次系数时,已经处理数组完成了,此时开始判断,若相等则是三等分,否则不是
            if (tempOneCount === k * 2) {
                A2 = A.slice(A1.length, i + lastZeroCount + 1);
                A3 = A.slice(i + lastZeroCount + 1);
                if (calc(A1) == calc(A2) && calc(A2) === calc(A3)) {
                    return [A1.length - 1, i + lastZeroCount + 1]
                } else {
                    return [-1, -1]
                }
            }
        }
    }
};

--发表评论--

🚀support markdown (* ̄▽ ̄*)ブ