SplitArrayIntoConsecutiveSubsequences [source code]
public class SplitArrayIntoConsecutiveSubsequences {
static
/****************************************************************************/
class Solution {
public boolean isPossible(int[] nums) {
Map<Integer, Integer> counts = new HashMap<> (), subseqs = new HashMap<> ();
for (int num : nums)
counts.put (num, counts.getOrDefault (num, 0) + 1);
for (int num : nums) {
if (counts.get (num) == 0)
continue;
else if (subseqs.containsKey (num) && subseqs.get (num) > 0) {
subseqs.put (num, subseqs.get (num) - 1);
subseqs.put (num + 1, subseqs.getOrDefault (num + 1, 0) + 1);
counts.put (num, counts.get (num) - 1);
} else if (counts.containsKey (num + 1) && counts.get (num + 1) > 0 &&
counts.containsKey (num + 2) && counts.get (num + 2) > 0) {
counts.put (num + 1, counts.get (num + 1) - 1);
counts.put (num + 2, counts.get (num + 2) - 1);
subseqs.put (num + 3, subseqs.getOrDefault (num + 3, 0) + 1);
counts.put (num, counts.get (num) - 1);
} else {
return false;
}
}
return true;
}
}
/****************************************************************************/
public static void main(String[] args) {
SplitArrayIntoConsecutiveSubsequences.Solution tester = new SplitArrayIntoConsecutiveSubsequences.Solution();
int[][] inputs = {
{1,2,3,3,4,5}, {1},
{1,2,3,3,4,4,5,5}, {1},
{1,2,3,4,4,5}, {0},
{1,2,3}, {1},
{1,2,3,3,4,4,5,5,9}, {0},
{1,2,3,3,4,4,5,5,6}, {1},
{1,2,3,5,7,8}, {0},
};
for (int i = 0; i < inputs.length / 2; i++) {
System.out.println (Printer.separator ());
int[] nums = inputs[2 * i];
boolean ans = inputs[2 * i + 1][0] != 0, output = tester.isPossible (nums);
System.out.printf ("%s\n%s\n%s\n",
Printer.array (nums), Printer.wrap (output + "", output == ans ? 92 : 91), ans
);
}
}
}
题目意思倒是很清楚, 不过看完是一点思路都没有, 有点难啊;
毕竟Google家的题目, 题目读完了之后, 一点思路都没有;
这题tag给的提示是greedy, 那么自己想怎么想到呢?
我之前看地里的面经, 好多他们编程高手, 如果一点办法都没有的时候, 一般两种思路:
- DFS暴搜
- greedy瞎写
尤其是针对greedy, 这个第二条路这里, 很多时候他们就是感觉好像一个greedy可能做, 跟面试官讨论一下, 就开始写了, 毕竟面试嘛, 就算greedy不对, 有一个代码也比什么都没有要好; 而且一般大部分不算太坏的面试官, 如果他知道greedy对于这题不适用, 他们一般是会告诉你的;
大概想了一下, 人逻辑都想不出来; 主要问题是感觉有太多的uncertainty;
那么下面的思路, 可以是:
- 枚举: 来消除uncertainty
- 观察简化uncertainty
不过这两个principle其实都是说起来简单, 真正实现起来并没有什么很好的思路;
仔细重新阅读一下题目, 题目要求的其实是, 一个array给你, 你分成(没有残留的)若干个subSequence, 然后每一个都要至少包含一个长度为3的连续的run; 比如给的例子:
尤其是第二个例子, 虽然第一个subSequence可以一直走12345长度为5, 但是实际上我们最终需要的, 只有红色标出来的这两段就行了; 把两个红色部分的挑出来, 分别分配到一个subSequence里面, 然后所有剩余的数字, 直接随便丢就行了;
是这样吗? 如果是分成三个的情况呢?
我认为, 如果一个array可以分成三个subSequence, 每一个至少含有一个3run, 那么其实他是不是也可以分成两个subSequence呢? 反正我们最后要决定的就是能不能分就行了; 能分成三个subSequence的肯定也能分成两个subSequence; 所以最后所有的情况, 我们就只判断能不能分成两个subSequence就算了;
感觉有点像打麻将的时候的捋牌的;
等于说, 只要是能挑3run就行, 如果能找到两个disjoint的3run, 那么就能说是成功;
第三个例子:
之所以失败, 就是因为没有办法分出两个3run来;
行, 就当成是找两个3run这样来写, 你怎么找呢?
估计就是tag对应的那个greedy的意思了; 先捋一遍, 能够找到一个3run(先用三个数字维护, 暂时还不从原来的string里面deduct掉, 成功之后再一起deduct掉, 有点类似进行时技巧), deduct掉, 然后重新再走一遍;
感觉好像我是不是对题目的意思理解有点跑偏了? 不管了, 先写写看;
题目给的限制是length有限制, 但是里面的value是没有给限制的, 所以要小心一点;
说起来是捋两遍拉倒, 但是好像实际上也没那么简单? 因为假如第一个3run成功, 然后第二个3run失败, 那么最后第一个3run的deduct是要undo掉的;
然后写了一个简单的代码:
class Solution {
public boolean isPossible(int[] nums) {
int min = nums[0], max = nums[nums.length - 1];
int[] counts = new int[max - min + 1];
for (int num : nums)
counts[num - min]++;
for (int i = min; i <= max - 2; i++) {
if (counts[i - min] > 0 && counts[i + 1 - min] > 0 && counts[i + 2 - min] > 0) {
counts[i - min]--;
counts[i + 1 - min]--;
counts[i + 2 - min]--;
for (int j = min; j <= max - 2; j++) {
if (counts[j - min] > 0 && counts[j + 1 - min] > 0 && counts[j + 2 - min] > 0) {
return true;
}
}
counts[i - min]++;
counts[i + 1 - min]++;
counts[i + 2 - min]++;
}
}
return false;
}
}
居然被test4给break了: 这个为什么是true?
然后自己编了一个test5, 居然也是错的; 这个test是根据test2, 也就是我的主要的example来改动的, 就是故意考察一下, 是不是每一个subSequence都包含三个连续的数字就行了, 但是这里看来, 是不行的, 否则的话, 直接9随便扔给谁都可以;
但是感觉题目就是这个意思啊;
再稍微改了一下, 改成test6, 这个应该是true; 所以我感觉题目的意思应该是, 每一个subSequence应该全都是连续的; 然后长度至少是3; 哎, 感觉题目表达不清楚啊; 这种如果面试碰到只能希望自己多交流了;
那么如果这样, 思路也要完全不同了; 不能有剩的, 要完整无缺的分割, 所有的subSequence都是连续的, 然后都是至少是长度是3, 题目应该就是这个意思; 这个也是为什么1,2,3是true, 因为就是一点儿剩的都没有;
这样理解之后感觉其实题目的意图更加清晰, 虽然暂时还是没有思路;
一个很naive的做法, 还是之前的那个例子, 当我第一个循环找到123之后, 我应该继续找, 能找多长就找多长, 然后记录长度m, 然后第二个循环(内部循环)找剩下的, 只要剩下的内容是完全连续的就行, 记录长度是n; 然后最后...好像不行; 我一开始的想法是假如m很长, 那么m可以贴一点给n, 但是有那么容易吗? 未必接的上啊;
干脆一次找3个一次找3个这样无限找, 行不行? 不行, 因为最后这个subSequence可能是比如1234和789组成的, 这个你怎么找啊; 不是可以用若干个3run组合得到的;
这个题目思考的时候感觉重点应该放在最后分成的几个subSequence之间有什么可以分析的特征, 而少去纠结原来的数组nums本身是什么样的;
感觉好像有点什么东西在里面, 毕竟看起来感觉是一个完全正常的算法问题, 但是就是想不到; 看答案了;
参考editorial实现了一下;
实现的时候, 还是提醒一下自己, 你看他第三个branch, 这个create new chain的时候, 是一个eager或者说pre的过程: 立刻就要判断, 我当前num作为开头的话, 后面至少要足够长度是3;
所以如果与editorial1进行对比, 这个实际上差别还是很明显的;
editorial1实际上是eager的维护连续性constraint, 然后再连续性被破坏, 需要确实去分段subSequence的时候, 再来检查长度;
但是editorial2这个方法, 是先eager维护长度constraint; 至于连续性...好像其实也是implicit的eager维护的: 对于concate to old chain和create new chain两种情况的分开处理实际上就是在respect continuity constraint;
自己写的过程当中, 一开始第二branch(concatenate的)当中没有加count(num)--这个操作; 但是出了bug:
counts: {1=1, 2=1, 3=2, 4=2, 5=2}
num:(1)
num:(1)
counts: {1=0, 2=0, 3=1, 4=2, 5=2}
subseqs: {4=1}
num:(2)
num:(3)
num:(3)
counts: {1=0, 2=0, 3=0, 4=1, 5=1}
subseqs: {4=1, 6=1}
num:(3)
num:(4)
num:(4)
counts: {1=0, 2=0, 3=0, 4=1, 5=1}
subseqs: {4=0, 5=1, 6=1}
num:(4)
1 2 3 3 4 4 5 5
false
true
第一个4出现的时候, 延长了1 2 3这个chain, 然后我没有--他的count, 这个是有问题的; 这么说吧, 你这里这个concatenate操作, 就是确实是消耗了一个4, 为什么不--?
当然, 这个是intuitive的角度来理解这个;
这个count--的操作实际上就是与第一个branch的判断对应的: 没有count的就不应该管了;
为什么要这样维护这个count, 就是因为第三个branch(create的这个)当中, 有一个向后eager peek的操作, 所以比如你在3的时候, 你把4和5都peek了, 然后他们的count--, 这样才能让后面真正走到这两个位置的时候, 不会重复处理;
最后AC, 速度是101(35);
editorial1倒是快很多, 24(81). 不知道为什么差这么多; 是因为editorial2这个需要2pass的原因吗? 当然还用了Map以及Map的新API, 可能也是一个原因;
没什么好纠结的, 毕竟editorial2这个算法面试当中好解释的多了;
UNFINISHED
看了一下代码篇幅, 感觉是有点技巧在里面的, 不是那种抖机灵的题目;
评论好几个在喷awice写的读不懂, 所以, 有点慌;
editorial
Approach #1: Opening and Closing Events [Accepted]
Intuition
We can think of the problem as drawing intervals on a number line. This gives us the idea of opening and closing events.
这个想法还是有点敏锐的; 至于这个所谓的events思路, 估计是一个他认为已经总结的很成熟的编程套路了; 不过想到interval这个确实有点意思;
To illustrate this concept, say we have nums = [10, 10, 11, 11, 11, 11, 12, 12, 12, 12, 13], with no 9s and no 14s. We must have two sequences start at 10, two sequences start at 11, and 3 sequences end at 12.
这个不是特别难理解, 实际上是一个有点greedy的思路; 你最后分出来的subSequence, 要把所有的数字都消耗掉; 那么从最小的开始, 两个10要消耗掉, 他们只能做开头; 然后后面4个11, 其中有两个肯定被前面两个10给承包了, 另外两个11只能作为start, 然后依次类推;
In general, when considering a chain of consecutive integers x, we must have C = count[x+1] - count[x] sequences start at x+1 when C > 0, and -C sequences end at x if C < 0. Even if there are more endpoints on the intervals we draw, there must be at least this many endpoints.
With the above example, count[11] - count[10] = 2 and count[13] - count[12] = -3 show that two sequences start at 11, and three sequences end at 12.
这个例子看起来好像是这么一回事, 不过一个medium题目居然也要这么复杂的observation吗;
Also, if for example we know some sequences must start at time 1 and 4 and some sequences end at 5 and 7, to maximize the smallest length sequence, we should pair the events together in the order they occur: ie., 1 with 5 and 4 with 7.
这个是什么意思呢?
首先, 这个maximize the shortest subseq的概念是能理解的, 因为我们是要决定这个数组能不能分成合理的subSequence; 我们手上的限制有两个(在保证原来的array被分完的情况下): 一个是, 所有的subSequence都是连续递增, 另外一个是, 所有的subSequence长度都至少应该达到3;
同时考虑满足这两个subSequence有点复杂, 所以他这里的做法其实是, 先只考虑完整分成所有的连续subSequence, 这个总是可以完成的(在不考虑长度限制的情况下);
然后我们再来考虑怎么照顾长度要求; 一个简单的思路就是, 我们尽可能保证最短的这个subSequence最长, 只要他足够长, 最后所有的subSequence也就足够长了; 这个也是好像见过的一种思路;
again, 这题真的要这么复杂的思考吗;
然后这里说的这个pairing, 大概是这个意思:
代表的是什么意思? 为什么一定要顺序的来? 哦, 好像也没问题; 这样是尽可能的让min最大; 不难理解;
Algorithm
For each group of numbers, say the number is x and there are count of them. Furthermore, say prev, prev_count is the previous integer encountered and it's count.
Then, in general there are abs(count - prev_count) events that will happen: if count > prev_count then we will add this many t's to starts; and if count < prev_count then we will attempt to pair starts.popleft() with t-1.
又开始直接讲代码了, 开始看不懂了;
More specifically, when we have finished a consecutive group, we will have prev_count endings; and when we are in a consecutive group, we may have count - prev_count starts or prev_count - count endings.
For example, when nums = [1,2,3,3,4,5], then the starts are at [1, 3] and the endings are at [3, 5]. As our algorithm progresses:
- When t = 1, count = 1: starts = [1]
- When t = 2, count = 1: starts = [1]
- When t = 3, count = 2: starts = [1, 3]
- When t = 4, count = 1: starts = [3], since prev_count - count = 1 we process one closing event, which is accepted as t-1 >= starts.popleft() + 2.
- When t = 5, count = 1: starts = [3]
And at the end, we process prev_count more closing events nums[-1].
前几个iteration好像还可以, 讲到后面t=4和5这两个iteration就有点想不通了; 先看代码;
class Solution {
public boolean isPossible(int[] nums) {
Integer prev = null;
int prevCount = 0;
Queue<Integer> starts = new LinkedList();
int anchor = 0;
for (int i = 0; i < nums.length; ++i) {
int t = nums[i];
if (i == nums.length - 1 || nums[i+1] != t) {
int count = i - anchor + 1;
if (prev != null && t - prev != 1) {
while (prevCount-- > 0)
if (prev < starts.poll() + 2) return false;
prev = null;
}
if (prev == null || t - prev == 1) {
while (prevCount > count) {
prevCount--;
if (t-1 < starts.poll() + 2)
return false;
}
while (prevCount++ < count)
starts.add(t);
}
prev = t;
prevCount = count;
anchor = i+1;
}
}
while (prevCount-- > 0)
if (nums[nums.length - 1] < starts.poll() + 2)
return false;
return true;
}
}
分段的写法还是熟悉的: if (prev == null || t - prev == 1), 把最后一个下降沿和前面的下降沿合并在一起写, 是awice的风格;
普通下降沿的是用i+1这样的peek ahead来完成的;
难怪被人骂, 这代码写的实在是太乱了..
一层一层的看, 看他一个block是干什么的; 有点类似一个Top-Down的过程, node是block, 从大block向更小的block一点一点的收缩梳理;
可以用一个手算的例子来帮助理解, 不要搞太fancy的, 就一个简单的小例子甚至就是题目给的这个例子都可以; 有trace过一个不完整例子, 好过一个例子也都没有trace过;
if (prev != null && t - prev != 1): 这个看起来很隐晦, 实际上, 不等于1, 意思就是至少是2的意思啊, 不是嘛; 反正0肯定是不可能的, prev的更新法则就限定了, 肯定不会是0; 那么这里1也让, 意思其实就是判断我们跟anchor的距离是否已经超过2? 不对啊, t和prev是value啊, 你判断这个超过2有什么用?
不对, 这个是跟下面的if (prev == null || t - prev == 1)形成对应的两个branch; 为什么不用else? 我感觉差不多啊, 这两个if的header完全就是反命题. 可能他是故意写成这样, 把else对应的condition特意explicit的写出来, 让你看的更加明显?
哦我知道了, 为什么要判断t-prev是不是1? 因为如果不是1, 连续就断了啊, 很简单的事情, 我们最后必须要分成完全连续的; 他这里的做法是非常greedy的, 如果碰到连不上, 就给你分成两段, 多大事儿嘛; 先不管长度, 长度自然有办法判断;
所以这两个if, 第一个对应的是不能连续, 第二个对应的是可以连续;
代码的重复性总之还是太高了; 自己跑一个例子看看, 到底是在干什么好了;
二话不说先打trace(全都是after iteration的);
i:(0), nums:(1), anchor: (1), prev:(1), prevCount:(1), starts: [1]
i:(1), nums:(2), anchor: (2), prev:(2), prevCount:(1), starts: [1]
i:(2), nums:(3), anchor: (2), prev:(2), prevCount:(1), starts: [1]
i:(3), nums:(3), anchor: (4), prev:(3), prevCount:(2), starts: [1, 3]
i:(4), nums:(4), anchor: (5), prev:(4), prevCount:(1), starts: [3]
i:(5), nums:(5), anchor: (6), prev:(5), prevCount:(1), starts: [3]
1 2 3 3 4 5
true
true
快速定位index
这个图很不陌生了:
以前只是用来帮助理解length和index之间的转换; 最近还想到了一个新的用途, 就是可以快速定位一个index; 比如你要找4这个index, 你直接找到钱4个数字, 然后下一个就是index是4的; 这个比自己从0开始数到4, 要快的多; 当然, 不同的人快速找index肯定有自己总结的方法, 我认为这个方法还是比较适合我的;
这个方法可以很轻松的拓展到2D的情形, 比如找row4, 那么一眼望到前4行, 然后下一行就是row3.
这个方法比普通的自己数要快的原因是, 人本身的直觉对于length数量是更为敏感的, 比如让你找一个长度是多少的subarray, 立刻一眼就能扫出来了;
回到正题;
他的anchor定义的其实是当前段的开头, 然后prev的两个变量就是维护之前段的完整信息;
确实也足够维护所有的分段信息了;
回头重新看他的逻辑, 这个简单的例子感觉并不能完整解释他代码背后的逻辑;
看看starts在哪些位置可以Poll? 一种是不能连续的情况下, 这个时候要把prev的所有的东西都处理掉, 所以我们需要从starts里面Poll出来prevCount数量的start; 一种情况是能够连续, 但是当前的count数量比prevcount数量更少, 这个时候还是要把prevCount多余出来的部分解决掉, 因为他们肯定不能跟curCount在一个sequence里面;
感觉讲的还是不够详细;
他代码实际上是用了很多tricky的优化的, 比如你看他第二个if的第二while, 这里把prevCount对齐到count, 你可能会觉得这个有什么用呢? 这个实际上他是为了能够让最后大while结尾的那个advance里面的prevCount = count能够对所有的情况进行统一的处理;
如果是我自己实现这个算法的话, 我就先用一个快慢指针的方法, 把这个数组压缩, 然后记录count; 或者直接用bucket的方法, 来计算count, 就跟我之前的失败做法一样; 这样分段count和主干逻辑同时进行简直是搞自己, 最少是不适合面试的写法;
两个小while可以写在一起, 因为无所谓, 两个没有重叠; 这个好像也是以前见过的while处理的一个小技巧, 其实是有点像conditional的思路的;
回头重新看看, 感觉他这个一遍头, 不去专门走一遍搞bucket的, 好像也不错? 逻辑刚开始看确实有点绕, 不过好像本质上应该是还能接受的;
举例来说, 比如这个:
while (prevCount-- > 0)
if (prev < starts.poll() + 2) return false;
关键还是要理解他背后的意图; again, 他这里的思路是, 你看他代码的思路, 首先是判断能不能连续, 如果不能连续, 立刻分subSequence, 或者如果能连续, 但是要处理多余的不匹配的count, 这个就是两个forifif处理的东西;
这样我们subSequence分段这个事情, 其实就是已经确定下来的了, 这个uncertainty就已经消除了; 整个问题的所有uncertainty都被压到了下一层, 也就是当你这么greedy的完成subSequence分段之后, 长度是否满足要求呢? 然后这几个for-if-if-while就是做这个工作;
第一个for-if-if-while处理的是不能连续的时候, 消除所有prev信息的操作; 第二和第三个for-if-if-while, 处理的都是prevCount和当前count不匹配的问题; 因为是while, 所以两个方向分别进行一下就行了;
一个遗留问题就是, 这个思路的正确性你能够证明吗? 重新回顾一下, 当我们看到连续性被破坏之后, 立刻就分subSequence, 然后再判断获得的subSequence长度是否满足要求, 来完成最后一道关卡的检验;
这样一个思路得到的检查结果就能一定保证是题目要求的结果吗? 感觉有待推敲?
你认为这个思路有可能不对, 那我们能不能消除这个uncertainty? 比如, 什么样的情况下, 这个思路可能会错误? 你按照连续性严格分段之后, 检查所有得到的分段的长度, 如果是true, 也就是都够长, 那么这个没问题, 这个true是没毛病的: 一种方法subSequence分段成功了, 整个问题就是true的;
但是假如你按照这个思路得到一个FALSE, 这个FALSE是不是可靠的呢? 你严格维护连续性得到的一个分段, 然后其中有一个不够长度3, 然后你说false, 这个false有没有可能是错的? 也就是说, 有没有可能有其他的一种分法, 能够保证最后实际上最小subSequence的长度是满足3的? 当然是想证明不可能的, but how? 关键要证明的是, 比如这个得到的2run, 无论你最后怎么分, 都会存在;
想不到什么好的严格证明办法; 好像可以反证法? 但是没思路;
但是我认为这个是一个证明这个方法正确性难以逃脱的核心问题.
这个是我在下面问的问题:
In your approach 1, I think your thinking is, whenever you find that there are more
prevCountofprev, you have to give them closure by choosing onestartfor each of them, implicitly meaning putting them into a finished subsequence.
Then you examine, in the same time as you finish their subsequence building, the length of such subsequences, to validate at least 3.Can you prove the correctness of this approach? I mean, this approach does have some eagerness in it: first respect the continuity constraint for the subsequence greedily, then check the resultant subsequence lengths. This is of course one way of splitting. But when this approach returns
false, can you prove that there is no other way that might split the array successfully?
我觉得我这个问题的提问方式还是可以的; 这个其实就有点像比如最大化问题的时候, 一种方法是可以比如有两个参数x和y, 你可以分别对x和y求偏导, 然后解出来, 而且是独立有顺序的互相解出来; 但是这样得到的结果就真的一定是对的吗? 不一定吧, 有时候还是得用gradient办法不是吗; 所以这里我现在也不知道怎么证明这个东西;
回到正题:
我重新想了一下怎么理解这个算法, 这个算法其实是两个分段算法并行的一个问题; 第一个分段就是我们最熟悉的简单的分段, 类似bucket的操作, 这个主要依赖于anchor这个东西;
然后第二个分段, 是建立在第一个分段基础上面的分段, 实际上就是一个针对subSequence的分段: 这个分段的维护方法, 是用starts来维护: starts里面维护的是所有目前正在build过程当中的subSequence的head;
比如1 2 3 3 4 5, 当我们一开始在[0]的时候, 我们的starts就是1, 放进去了, 然后走到[1], 这个时候2, 一看, 和前一个数字, 也就是1, 能够接上, 那么我们目前还不需要对subSequence分段做什么额外的操作; 因为prevcount和当前count也相等, 二三两个for-if-if-while也不需要执行;
假设[2]是5, 比如, 那么我们走到这里的时候, 一看, 这个5跟前一个数字, 2, 接不上了, 那么这个时候subSequence分段必须立刻分段, 这个是无条件的(减少uncertainty, 反正只要一断连续了, 就立刻分subSequence), 然后检查长度: 直接从starts里面按照FIFO顺序取出对应数量的start, 同时获得每一个完成的subSequence的长度, 然后检查, 失败就立刻退出;
一个需要理解的核心概念就是, 每一个start维护的实际上是一个building的subSequence; 如果是2这种, count也跟1的count对应, 然后数值也连续, 他基本最后实际上就是什么也没做: implicit的就直接加入到1这个start的subSequence里面去了: 这个start, 其实有点类似于是subSequence的anchor!!!
为什么用queue? 这个其实是上面解释过的, 那个区间重叠的那张图上面有; 那里awice解释的时候就是后面来的人, 想要取start的时候,应该按照最开始的从小到大的顺序来取, 一个FIFO的顺序, 实际上就是对应于他最后实现的时候选择了一个queue;
总体上来说这个算法应该是理解了的, 两层分段这个真的是第一次见, 有点懵逼, 了解一下;
唯一剩下的问题就是上面这个缺失的证明; 或许其实就是我自己没有理解? 反正count的上升沿, 应该add start, 然后count的下降沿, 应该消费start, 这个应该是理解的;
感觉这个算法还是需要多一点时间消化看看;
上面讨论的那个例子有点小, 不过还是可以参考看一下;
可以看到, 2和第一个3, 都是直接加入之前的start=1的这个subSequence里面, 然后走到4的时候, count有一个下降沿, 这个时候知道要收尾, 这个时候starts代表的是两个subSequence, 1 2 3和3, 然后按照FIFO的顺序, 收的是第一个, 也就是1 2 3这个subSequence, 检查长度, 合格, 直接扔掉不管; 然后后面4和5加入3的这个subSequence, 也就是红色;
这个图应该还是能比较好的解释问题的; 不过没有展示断连的情况; 其实断连的情况跟count下降沿应该差不多的, 不过是下降到直接是0而已; 或许可以统一起来处理? 没有什么必要, 这个题目已经够难的了, 不要急着去Premature Optmization;
注意一下他最后时间复杂度分析那里, 他的分析实际上是aggregate, 而且是data-structure-based的分析, 也就是分析这个array占用了多少时间复杂度, 这个queue会贡献多少时间复杂度; 这个技巧好像以前也大概见过;
Approach #2: Greedy [Accepted]
Intuition
Call a chain a sequence of 3 or more consecutive numbers.
Considering numbers x from left to right, if x can be added to a current chain, it's at least as good to add x to that chain first, rather than to start a new chain.
这个就是一个典型的简化观察, 来消除uncertainty; 虽然我暂时还不理解这个观察是用来干什么的;
Why? If we started with numbers x and greater from the beginning, the shorter chains starting from x could be concatenated with the chains ending before x, possibly helping us if there was a "chain" from x that was only length 1 or 2.
好像不是很难理解;
讲代码的他lei了;
Algorithm
Say we have a count of each number, and let tails[x] be the number of chains ending right before x.
Now let's process each number. If there's a chain ending before x, then add it to that chain. Otherwise, if we can start a new chain, do so.
It's worth noting that our solution can be amended to take only O(1) additional space, since we could do our counts similar to Approach #1, and we only need to know the last 3 counts at a time.
果然他editorial1里面, 不单独走一个bucket过程是故意的, 意思是为了节省空间; 能省多少呢, 就那么多字母而已;
看完这个结果感觉还是有点类似方法1, 都是维护building subseq这样的思路; 事实上, 他方法1的时候, 也是有一个greedy的: 来了一个新的数字, 可以连到之前的subSequence里面去, 直接就连进去, 只不过是一个implicit的过程;
说起来, 方法1是怎么判断can concatenate的? 他比较的实际上是当前的t和prev的关系: 如果是+1关系, 就是连续, 也就是能够concatenate; 这个跟这里的这个方法有区别吗? 这里的方法看上面描述估计是一个跟每一个chain的尾巴进行比较的过程;
为什么方法1的时候, 直接t跟prev假如超过+1, 就可以确定肯定是断连? 好像没有那么trivial的, 比如之前那个1 2 3 3 4 5的例子, 不对, 这个例子没有断连. 反正方法1当时判断断连, 是没有跟某一个特定的*subSequence或者说chain的end进行比较的;
感觉是一个invariant的角度: 如果之前保证starts里面维护的都是连续性成立的chain, 那么当你出现一个新的t的时候, 如果他跟自己的prev不能连续, 那么他跟任何一个starts里面的chain也肯定不能连续;
为什么? 因为prev已经被处理过了, 如果prev当时是维持连续性, 他就已经被implicit的加到starts里面去了;
如果prev当时是破坏了连续性, 那么肯定也从starts里面消费掉一个甚至多个start, 然后走了; so what?
不是很好理解, 举一个简单的例子: 1 2 3 5 7 8, 那么这里5肯定是断连, 把之前维护的1 2 3直接从starts里面给消费掉了; 然后5变成prev, 然后我们走到t=7; 这个时候7和5一比, 还是断连, 然后这里按照代码的操作, 直接是继续消费start? 但是这个时候starts是空的啊? 算了, 打trace看一下;
i:(0), nums:(1), anchor: (1), prev:(1), prevCount:(1), starts: [1]
i:(1), nums:(2), anchor: (2), prev:(2), prevCount:(1), starts: [1]
i:(2), nums:(3), anchor: (3), prev:(3), prevCount:(1), starts: [1]
i:(3), nums:(5), anchor: (4), prev:(5), prevCount:(1), starts: [5, 5]
1 2 3 5 7 8
false
false
这个trace跟我预想的不一样, 我才发现方法1 awice实际上还藏了更多的坑: 第一个FII和第二个FII之间, 不是互斥的关系!!! 也就是不是一个else的关系;
第一个FII如果执行, 那么执行结束之后, prev会自动变成Null, 然后prevCount是0; 然后第二个FII可以自然的执行...
这个时候我们还在t=5, 因为这个时候prevCount被第一个FII搞成了0, 但是我们的count还是1, 所以第二个FII的第二个while会执行; 这个会把5给扔到starts里面去;
结束的时候为什么starts里面有两个5啊?
把第一个FII结束的时候的prevCount也打印出来了:
prevCount:(0)
i:(0), nums:(1), anchor: (1), prev:(1), prevCount:(1), starts: [1]
prevCount:(1)
i:(1), nums:(2), anchor: (2), prev:(2), prevCount:(1), starts: [1]
prevCount:(1)
i:(2), nums:(3), anchor: (3), prev:(3), prevCount:(1), starts: [1]
prevCount:(-1)
i:(3), nums:(5), anchor: (4), prev:(5), prevCount:(1), starts: [5, 5]
1 2 3 5 7 8
可以看到, 跟第一个FII里面那个while的写法有关系, 断连退出之后, 给的prevCount是-1, 而不是0, 实际上我认为应该是0比较好; 不过这个就导致了后面5被add了两次;
awice真的是...到处挖坑.
回到之前, 看到了t=7会发生什么; 这个时候7和之前的5继续断连, 然后触发Poll, 然后5 < 5+2, 然后这里这个false直接就触发了; 好像也没毛病; 也就是回到我们之前讨论的话题, 当前的t跟prev是断连的, 然后prev本身还跟之前的prevprev也是断连的, 已经在starts里面消费过一波了, 那么这个时候的t, 怎么处理? 这里看来, 因为prev也就是5是在...
感觉断连的时候发生的故事比我想象的要复杂很多啊;
我觉得有一个claim, 就是一旦比如5这样, 跟前面断连了, 他肯定能把starts里面所有的chain, 都清干净. 因为starts里面这些chain, end其实肯定全都是5的prev, 不然早就被消费了; 然后5在这儿消费一波, 其实就是把他们全都清了; 然后5自己进去starts里面;
然后到了7, 7这个时候一来, 一看跟5断连, 也说, 我也要把starts都清干净, 然后他就清了. 每一个从starts里面清出来的chain(他们肯定是chain, 因为讲过了, 连续性是在starts里面是被维护的), 都同时检查长度;
因为这个时候, starts里面就一个5自己, 所以一检查长度就露馅, 然后就可以false了;
大概是能理解这个逻辑了, 不过这么一看, awice这个方法一背后tricky的东西实在是太多了;
两个FII之间的巧妙组合(断连之后可以重新进入第一个FII然后add到starts里面去), 实际上用else结构是可以弥补的, 就是有点重复代码;
不过用t跟prev的比较来直接判断断连, 这个就真的很tricky; 面试的时候很难解释清楚; 当然了, 是对的, 可是你要怎么让面试官认为你能够在段时间内想到一个灵活性这么高的设计?
有点坑.
回到正题:
class Solution {
public boolean isPossible(int[] nums) {
Counter count = new Counter();
Counter tails = new Counter();
for (int x: nums) count.add(x, 1);
for (int x: nums) {
if (count.get(x) == 0) {
continue;
} else if (tails.get(x) > 0) {
tails.add(x, -1);
tails.add(x+1, 1);
} else if (count.get(x+1) > 0 && count.get(x+2) > 0) {
count.add(x+1, -1);
count.add(x+2, -1);
tails.add(x+3, 1);
} else {
return false;
}
count.add(x, -1);
}
return true;
}
}
class Counter extends HashMap<Integer, Integer> {
public int get(int k) {
return containsKey(k) ? super.get(k) : 0;
}
public void add(int k, int v) {
put(k, get(k) + v);
}
}
counter这个设计我可能还不太熟悉; awice好喜欢用这种继承的设计;
因为是继承Map, 所以默认的, containskey, put, get这些函数都是可以直接用的, 尤其是在Counter的定义里面, 可以直接不用object就直接调用;
然后他override了get;
注意get这个override里面要用super.get来调用默认实现, 而不是直接写get: 当前class的get已经被你给override了, 没了, 所以你只能去super里面拿备用的copy;
他没有override put, 而是直接自己重新加了一个add方法; 也可以吧; add实际上是一个increment的操作;
感觉这个封装其实挺没有必要的, Map实现counter用getOrDefault之类的新API写起来本身就很方便;
当然, 或许这个是awice自己的代码库?
ok, 看代码, 记得counter就是一个变形的Map而已, 不要搞混淆;
...完全看不懂;
and let tails[x] be the number of chains ending right before x.
这个是什么意思, 也就是tails[3]=2实际上代表的就是, 现在有2个chain, 都是end at 2, and waiting for 3的意思? 字面意思好像是这样, 不过这个定义看起来有点奇怪就是了;
Now let's process each number. If there's a chain ending before x, then add it to that chain. Otherwise, if we can start a new chain, do so.
好像这样定义就是有点类似2sum的那种, 你站在3的时候, 你就知道我的complement是谁? 我的天, 又回到2sum问题了? 牛欢喜;
这么一看, 代码结构也很类似2sum啊, 就是一个很单纯的循环;
最简单的这个trace:
count: {1=1, 2=1, 3=2, 4=1, 5=1}
x:(1)
count: {1=0, 2=0, 3=1, 4=1, 5=1}
tails: {4=1}
x:(3)
count: {1=0, 2=0, 3=0, 4=0, 5=0}
tails: {4=1, 6=1}
1 2 3 3 4 5
true
true
好像这个trace来看, 没有特别复杂的? 看看失败的trace:
count: {1=1, 2=1, 3=1, 5=1, 7=1, 8=1}
x:(1)
x:(1)
count: {1=0, 2=0, 3=0, 5=1, 7=1, 8=1}
tails: {4=1}
x:(2)
x:(3)
x:(5)
1 2 3 5 7 8
false
false
所以是在5的时候失败的, 2和3被跳过是理解范围内的;
5进来, 第一个branch, count(5)>0, 无法continue; 第二个branch, 有没有wait for 5的chain? 没有; 第三个branch: 5能不能开头一个new chain? 不能
然后直接就挂掉了;
这个逻辑好像真的是非常的简单啊;
而且算上前面讲过的, 他的这个counter class实际上也没有必要; 这题最后整个就是一个复杂版本的2sum的样子; 重新捋一下逻辑, 看看是不是这么回事;
最后的这个count.add(x, -1);有没有必要这样写?
只对二三两个branch有影响; 第三个branch的话, 这个count--可以直接写在branch里面; 如果是针对第二个branch, 我感觉这个其实是无所谓的? 因为所有的对count的查询, 都是不向前的, 所以如果你进入第二个branch, 然后讲一个chain延长之后, 不更新这个x的count, 其实也是无所谓的;
这个算法好实现多了, 我尝试实现一下这个算法;
感觉只要在理解了intuition的正确性的情况下, 这个算法本身的正确性应该是没有什么需要专门单独证明的, 整体的思路就是, 我们每一个数字, 如果可以接到一个旧的chain上面, 就接上去, 如果不行, 就开一个新的chain; 这里的concatenate的做法比approach1的那个要简单和直接的多;
这个做法应该算是这题的钦定做法了;
submission也是一个很快的, 21(86)左右的:
class Solution {
public boolean isPossible(int[] nums) {
int pre = Integer.MIN_VALUE, p1 = 0, p2 = 0, p3 = 0;
int cur = 0, cnt = 0, c1 = 0, c2 = 0, c3 = 0;
for (int i = 0; i < nums.length; pre = cur, p1 = c1, p2 = c2, p3 = c3) {
for (cur = nums[i], cnt = 0; i < nums.length && cur == nums[i]; cnt++, i++);
if (cur != pre + 1) {
if (p1 != 0 || p2 != 0) return false;
c1 = cnt; c2 = 0; c3 = 0;
} else {
if (cnt < p1 + p2) return false;
c1 = Math.max(0, cnt - (p1 + p2 + p3));
c2 = p1;
c3 = p2 + Math.min(p3, cnt - (p1 + p2));
}
}
return (p1 == 0 && p2 == 0);
}
}
没有仔细看了, 暂时没时间; 而且这个也是一点解释都没有的, 全都是蛇皮变量名称; 循环也全都用的复合写法, 懒得浪费时间了;
Problem Description
You are given an integer array sorted in ascending order (may contain duplicates), you need to split them into several subsequences, where each subsequences consist of at least 3 consecutive integers. Return whether you can make such a split.
Example 1:
Input: [1,2,3,3,4,5]
Output: True
Explanation:
You can split them into two consecutive subsequences :
1, 2, 3
3, 4, 5
Example 2:
Input: [1,2,3,3,4,4,5,5]
Output: True
Explanation:
You can split them into two consecutive subsequences :
1, 2, 3, 4, 5
3, 4, 5
Example 3:
Input: [1,2,3,4,4,5]
Output: False
Note:
- The length of the input is in range of [1, 10000]
Difficulty:Medium
Total Accepted:8.7K
Total Submissions:23.6K
Contributor:fallcreek
Companies
google
Related Topics
heapgreedy
Similar Questions
Top K Frequent Elements