题目形容
这是 LeetCode 上的 927. 三等分 ,难度为 艰难。
Tag :「模仿」
给定一个由 0
和 1
组成的数组 arr
,将数组分成 3
个非空的局部,使得所有这些局部示意雷同的二进制值。
如果能够做到,请返回任何 [i, j]
,其中 i+1 < j
,这样一来:
arr[0], arr[1], ..., arr[i]
为第一局部;arr[i + 1], arr[i + 2], ..., arr[j - 1]
为第二局部;arr[j], arr[j + 1], ..., arr[arr.length - 1]
为第三局部。- 这三个局部所示意的二进制值相等。
如果无奈做到,就返回 [-1, -1]
。
留神,在思考每个局部所示意的二进制时,该当将其看作一个整体。例如,[1,1,0]
示意十进制中的 6
,而不会是 3
。此外,前导零也是被容许的,所以 [0,1,1]
和 [1,1]
示意雷同的值。
示例 1:
输出:arr = [1,0,1,0,1]
输入:[0,3]
示例 2:
输出:arr = [1,1,0,1,1]
输入:[-1,-1]
示例 3:
输出:arr = [1,1,0,0,1]
输入:[0,2]
提醒:
- $3 <= arr.length <= 3 \times 10^4$
arr[i]
是0
或1
模仿
情绪不好,写的代码也不好。
就大略讲讲啥意思吧:
- 先统计
1
的个数cnt
,若cnt = 0
代表可能任意划分,间接返回[0, 2]
; - 若
cnt
不为 $3$ 的倍数,必然不能失常划分,返回无解[-1, -1]
,否则可知三段中必然每一段1
的数量均为 $t = \frac{cnt}{3}$ 个; -
最初查看「三段中
1
的距离位是否雷同,后缀0
个数是否雷同」即可:- 创立二维数组
ins
记录三段中,相邻1
之间的距离状况,若存在距离1
不同,返回无解[-1, -1]
; - 预处理四个变量
l1
、l2
、r1
和r2
,别离代表可能划分出最右边t
个1
的左右端点,以及可能划分出最左边t
个1
的左右端点,同时统计最初一段的后缀0
的数量d
,配合四个变量来查看是否划分出具备d
个后缀0
的前两段。
- 创立二维数组
代码:
class Solution {public int[] threeEqualParts(int[] arr) {int[] fail = new int[]{-1, -1};
// 查看总数
int n = arr.length, cnt = 0;
for (int i = 0; i < n; i++) cnt += arr[i];
if (cnt == 0) return new int[]{0, 2};
if (cnt % 3 != 0) return fail;
// 查看距离绝对位
int t = cnt / 3;
int[][] ins = new int[3][t];
for (int i = 0, j = -1, k = 0, p = 0, idx = 0; i < n; i++) {if (arr[i] == 0) continue;
if (j != -1) ins[p][idx++] = i - j;
if (++k == t) {j = -1; k = 0; p++; idx = 0;} else {j = i;}
}
for (int i = 0; i < t; i++) {if (ins[0][i] == ins[1][i] && ins[0][i] == ins[2][i] && ins[1][i] == ins[2][i]) continue;
return fail;
}
// 结构答案(l1 和 l2 别离为可能划分出最右边 t 个 1 的 左右端点;r1 和 r2 别离为可能划分出最左边 t 个 1 的左右端点)int l1 = -1, l2 = -1, r1 = -1, r2 = -1;
for (int i = 0, k = 0; i < n; i++) {k += arr[i];
if (k == t) {if (l1 == -1) l1 = i;
} else if (k == t + 1) {
l2 = i - 1;
break;
}
}
for (int i = n - 1, k = 0; i >= 0; i--) {k += arr[i];
if (k == t) {if (r2 == -1) r2 = i;
} else if (k == t + 1) {
r1 = i + 1;
break;
}
}
int d = 0; // d 为最左边一段的后缀 0 的数量
for (int i = n - 1; i >= 0; i--) {if (arr[i] == 1) break;
d++;
}
if (l1 + d > l2 || r1 + d > r2) return fail;
return new int[]{l1 + d, r1 + d};
}
}
- 工夫复杂度:$O(n)$
- 空间复杂度:$O(n)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.927
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,局部是有锁题,咱们将先把所有不带锁的题目刷完。
在这个系列文章外面,除了解说解题思路以外,还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码,我建设了相干的仓库:https://github.com/SharingSou…。
在仓库地址里,你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布