BulbSwitcherII [source code]
public class BulbSwitcherII {
static
/******************************************************************************/
class Solution {
public int flipLights(int n, int m) {
Set<Integer> res = new HashSet<> ();
n = Math.min (n, 6);
int offset = 6 - n;
for (int residues = 0; residues < (1 << 4); residues++) {
int res_bit_count = Integer.bitCount (residues);
// ==m also works, don't forget
if (res_bit_count % 2 == m % 2 && res_bit_count <= m) {
int lights = (1 << 6) - 1;
if (((residues >> 0) & 1) > 0)
lights ^= 0b111111 >> offset;
if (((residues >> 1) & 1) > 0)
lights ^= 0b010101 >> offset;
if (((residues >> 2) & 1) > 0)
lights ^= 0b101010 >> offset;
if (((residues >> 3) & 1) > 0)
lights ^= 0b100100 >> offset;
res.add (lights);
}
}
return res.size ();
}
}
/******************************************************************************/
public static void main(String[] args) {
BulbSwitcherII.Solution tester = new BulbSwitcherII.Solution();
int[] inputs = {
1, 1, 2,
2, 1, 3,
3, 1, 4,
};
for (int i = 0; i < inputs.length / 3; i++) {
int n = inputs[3 * i], m = inputs[3 * i + 1], ans = inputs[3 * i + 2];
System.out.println (Printer.separator ());
int output = tester.flipLights (n, m);
System.out.printf ("%d and %d-> %s, expected: %d\n",
n, m, Printer.wrapColor (output + "", output == ans ? "green" : "red"), ans
);
}
}
}
这题被downvote的吓人, 有点慌.
这题看完题目之后一点思路都没有, 难怪被downvote的这么多, 这个看样子是一个纯正的数学题; 当然你也可以用DFS做, 这个也是我们以前总结过的思路, math题如果实在不知道math的解法, 哪怕是写一个搜索解法, 也是可以接受的;
不过我还是有点想找出来这题真正的解题思路. 观察到的一个特点就是, 这四个操作, 操作1其实就是间隔为1的一个循环, 操作2和3是步进为2, 操作3的步进为3; 不知道有没有用;
想了二十分钟, 没有想出来合理的数学方法, 开始写暴力搜;
最后写出来的算法是超时了, 就是上面的这个算法. 本身是暴力搜, 超时也是正常的, 暂时也想不到什么改进的办法了; 上面这个算法的复杂度其实就是N * (select 3 in M), 最后是N*(M^3). 这个复杂度肯定是比不过math算法的; 不过还是有所学习的;
这题之所以一个DFS可以用一个循环来写, 因为这题的这个算法其实是一个加法拆分问题, 但是order does not matter, 这样的一个加法拆分, 用循环写起来更快, 直接找数字就行了;
另外关于这题最后的collect的办法, 还是老生常谈的用string来做一个unique collection的操作了; 注意这里最后用的是StringBuilder, 是为了一定程度上避免string操作带来的cost;
当然, 这种collect的另外一种方法是用一个类似hash的方法, 也就是这里的这个01序列, 你可以组合成一个int, 然后用来作为记录的根据; 这个方法我一开始是这样写的, 不过后来放弃了因为认为这个n可能太大了; 但是后面看editorial发现, 这个方法其实是可行的, 就是你要稍微先加一点优化;
还有一点也是之前看awice的代码学来的一个技巧, 就是多个header的合并; 注意, 如果有这种continuous singleton header, 你想要合并, 最好这样写, 这样省略大括号的时候少危险一点;
决定按照editorial1的做法自己重新写一次, 之前TLE的算法保存在这里:
class Solution {
public int flipLights(int n, int m) {
if (n <= 0)
return 0;
Set<String> set = new HashSet<> ();
StringBuilder sb = new StringBuilder ();
for (int i = 0; i < n; i++)
sb.append ('1');
for (int i1 = 0; i1 <= m; i1++) {
if (i1 % 2 == 1) for (int j = 0; j < n; j++)
sbFlip (sb, j);
for (int i2 = 0; i2 <= m - i1; i2++) {
if (i2 % 2 == 1) for (int j = 0; j < n; j++) if ((j + 1) % 2 == 0)
sbFlip (sb, j);
for (int i3 = 0; i3 <= m - i1 - i2; i3++) {
if (i3 % 2 == 1) for (int j = 0; j < n; j++) if ((j + 1) % 2 == 1)
sbFlip (sb, j);
int i4 = m - i1 - i2 - i3;
if (i4 % 2 == 1) for (int j = 0; j < n; j++) if ((j + 1) % 3 == 1)
sbFlip (sb, j);
set.add (sb.toString ());
if (i4 % 2 == 1) for (int j = 0; j < n; j++) if ((j + 1) % 3 == 1)
sbFlip (sb, j);
if (i3 % 2 == 1) for (int j = 0; j < n; j++) if ((j + 1) % 2 == 1)
sbFlip (sb, j);
}
if (i2 % 2 == 1) for (int j = 0; j < n; j++) if ((j + 1) % 2 == 0)
sbFlip (sb, j);
}
if (i1 % 2 == 1) for (int j = 0; j < n; j++)
sbFlip (sb, j);
}
return set.size ();
}
void sbFlip (StringBuilder sb , int i) {
sb.setCharAt (i, sb.charAt (i) == '1' ? '0' : '1');
}
}
最后这个模仿出来的代码的速度是7ms (19%), 翻篇儿.
editorial
Approach #1: Reduce Search Space [Accepted]
class Solution {
public int flipLights(int n, int m) {
Set<Integer> seen = new HashSet();
n = Math.min(n, 6);
int shift = Math.max(0, 6-n); // can be changed to: int shift = 6 - n;
for (int cand = 0; cand < 16; ++cand) {
int bcount = Integer.bitCount(cand);
if (bcount % 2 == m % 2 && bcount <= m) {
int lights = 0;
if (((cand >> 0) & 1) > 0) lights ^= 0b111111 >> shift;
if (((cand >> 1) & 1) > 0) lights ^= 0b010101 >> shift;
if (((cand >> 2) & 1) > 0) lights ^= 0b101010 >> shift;
if (((cand >> 3) & 1) > 0) lights ^= 0b100100 >> shift;
seen.add(lights);
}
}
return seen.size();
}
}
这个算法最后他给的解释也是比较简单, 最后我花了很多时间才看懂; 主要是awice写这个算法的时候也没有对每一个变量的含义给出明确的说明; 加之他这个算法其实使用了大量的bit操作;
先看一下网页上面他给的解释; 这里他的candidate, 总共有4位, 每一个bit代表每一种操作的residue; 因为总共只有四个操作, 实际上最后总共只有可能有2^4种residue的组合; 他用candidate来枚举所有的residue组合, 然后进行相应的操作; ifheader里面判断的就是legit residues的操作, 这个步骤可以记住以后可能其他地方能用的到;
这个residue的计算我感觉如果给我自己的算法里面, 估计可以时间解决TLE;
总体来说这个还是一个非常聪明的算法, 而且并不是一个math算法, 所以按理来说也是应该能写出来的才对; 不过因为这个算法要求先看到的规律总结比较多, 所以比较难想出来; 需要相当的观察力;
这个题目使用了大量的bit操作, 最后的算法也是非常的精简;
另外, 这个算法的产生, 有几个关键的observation:
- 我一开始看到了几个操作之间的step之间的关系, 但是没有看出来明确的作用; 这里这个做法就看出来了, 所有step的最小公倍数就是一个循环周期, 所以最后实际上只要看一个长度为6的首段就行了;
- 因为这个问题是一个binary flip的问题, 所以他敏锐的看到了number of operation最后有用的只有residue;
- 但是如果给你一个数字, 然后让你枚举所有可能的residue组合其实也不是那么简单的; 如果给我写, 我很可能最后的写法就是还是要枚举m, 然后记录结果; 而他这里的方法是直接从residue结果出发, 然后check这个结果是否满足一个合理的residues of m的条件; 这个思路需要记忆, 其他地方可能能用到: enumerate all combinations of residues.
Approach #2: Mathematical [Accepted]
在这个方法里面, 他认为最后有用的其实只是前3位:
- Light 1 = 1 + a + c + d
- Light 2 = 1 + a + b
- Light 3 = 1 + a + c
- Light 4 = 1 + a + b + d
- Light 5 = 1 + a + c
- Light 6 = 1 + a + b
这个总结规律我其实自己写的时候也发现了, 就是把所有的bit位置进行一个类似分组的操作; 但是我没有发现他这里的这个规律, 尤其是6还可以继续拆分, 1-3和4-6是类似的; 严格来说, 也不是说是类似, 应该说, 如果1-3决定了, 4-6也就对应的决定了;
So that (modulo 2):
- Light 4 = (Light 1) + (Light 2) + (Light 3)
- Light 5 = Light 3
- Light 6 = Light 2
这个是从数学上证明这个对应性;
然后后面基本就是枚举就行了, 毕竟很短;
class Solution {
public int flipLights(int n, int m) {
n = Math.min(n, 3);
if (m == 0) return 1;
if (m == 1) return n == 1 ? 2 : n == 2 ? 3 : 4;
if (m == 2) return n == 1 ? 2 : n == 2 ? 4 : 7;
return n == 1 ? 2 : n == 2 ? 4 : 8;
}
}
最后的算法基本就是各种枚举, 懒得看了;
看了一下后面的discussion的算法, 好像这个小范围的枚举并不是那么trivial; 回头又看了一下editorial上面对于这个的解释, 相比就显得很聪明. awice是外层循环用的m, 然后n怎么办呢? 他一律认为至少是3; 你可能认为如果n小于3怎么办? 没关系, 用一个类似trie操作的思路, 去思考prefix就行了, 比如你在m=2的时候枚举出来多少个(, , _)的state, 然后如果n小于3, 直接考虑有多少种不同的prefix就行了; 这个想法非常的聪明;
这个是discussion最优解:
@woshifumingyuan said in Java O(1):
We only need to consider special cases which n<=2 and m < 3. When n >2 and m >=3, the result is 8.
The four buttons:
- Flip all the lights.
- Flip lights with even numbers.
- Flip lights with odd numbers.
- Flip lights with (3k + 1) numbers, k = 0, 1, 2, ...
If we use button 1 and 2, it equals to use button 3.
Similarly...
1 + 2 --> 3, 1 + 3 --> 2, 2 + 3 --> 1
So, there are only 8 cases.
All_on,1,2,3,4,1+4,2+4,3+4And we can get all the cases, when n>2 and m>=3.
class Solution {
public int flipLights(int n, int m) {
if(m==0) return 1;
if(n==1) return 2;
if(n==2&&m==1) return 3;
if(n==2) return 4;
if(m==1) return 4;
if(m==2) return 7;
if(m>=3) return 8;
return 8;
}
}
然后下面有一个解释:
@lakeshore1986 said in Java O(1):
Thanks for your smart solution! The following is my attempt to understand it.
The four buttons correspond to four kinds of numbers:
x % 2 == 1 && x % 3 == 1, such as x == 1;
x % 2 == 1 && x % 3 != 1, such as x == 3;
x % 2 == 0 && x % 3 == 1, such as x == 4;
x % 2 == 0 && x % 3 != 1, such as x == 2.There are eight independent button operations (suppose the initial status is on, on, on, on) : 1 (off, off, off, off), 2 (on, off, on, off), 3 (off, on, off, on), 4 (off, on, on, off), 1 + 4 (on, off, off, on), 2 + 4 (off, off, on, on), 3 + 4 (on, on, off, off), 1 + 2 + 3 == 3 + 3 (on, on, on, on), because 1 + 2 == 3, 2 + 3 == 1, 1 + 3 == 2, 1 + 2 + 4 == 3 + 4， 2 + 3 + 4 == 1 + 4，1 + 3 + 4 == 2 + 4， 1 + 2 + 3 + 4 == 3 + 3 + 4 == 4. The first operation changes all bulbs simultaneously, the eighth brings no change at all, the rest six operations always flip two bulbs together, so there are only three independent bulbs among the four kinds. We only need analyze cases for n = 1, 2, 3.
When m == 0, nothing happens, there is only one status;
when n == 1, the bulb can be kept "on" as a result of button operation 2, or switched "off" as a result of operation 1 or 3 or 4. Operation 2 equals operation 1 plus operation 3, operation 3 equals the combination of operation 1 and 2, operation 1 is equal to operation 2 plus 3. Therefore we can get the same status after both odd and even operations. Case n == 1 always yields 2;
when n == 2, there are four possible status, "on, off" == operation 2 or 1 + 3, "off, on" == 3 or 1 + 2, "off, off" == 1 or 2 + 3, "on, on" == 1 + 1 == 2 + 3 + 1 == 1 + 3 + 3 + 1 == ... or 2 + 2 or 3 + 3 or 4 + 4. Except status "on, on" which can be reached only after 2 or more operations, all the rest status can be obtained through both odd and even operations;
When n == 3, eight distinct status are possible. Using the same trick, we can find there are only two special cases: m == 1 and m == 2, all the other cases yield the same result 8.
总体来说感觉有点狗尾续貂, editorial里面说了, 最关键的一步是你要看出来前3位决定所有; 这样如果n和m都足够大, 那么结果就肯定是8;
然后在小范围内的枚举, 其实也有点麻烦; editorial里面好像其实并没有给出非常详细的解释;
但是我认为editorial里面的枚举方式更加的合理, 是根据m的主见增长来枚举, 这样更加的有条理; 不过如果根据我的脾气, 直接就枚举就行了; 不过你怎么知道这个"小范围"的范围所在呢?
首先, 什么是足够大? n肯定至少要3, 所以我们的小范围内n = 0..2; m呢? n足够大是不是就一定能保证8? 其实也未必,... 这里好像就看出来外循环用n好像很不方便;
突然发现一个技巧, 在我自己在思考的时候, 是发现了这个类似flag的做法的:
1 2 3 4 5 6 // lights
// relevant operations:
1 1 1 1 1 1
3 2 3 2 3 2
4 4
通过这个方法, 可以很好的帮助分析小范围内的枚举情况;
好像如果不理解上面的讨论方式, 还真的不好说就一定能够把这里的小范围内给处理好; n小的情况其实是比较好处理的, 但是m的小范围怎么定义并不是那么简单;
最后想了半天, 感觉n作为外循环还是太笨重了, 最好的方法还是m作为外循环; 论据呢? 还没有想到;
找规律
这个问题还是暴露出来我找规律能力的不足; 这个也是我向来的问题了, 并不是一天两天的毛病; 如果你看看discussion他们的讨论, 可以看到这个题目大部分人的解答都有大量的找规律的思考过程;
这个题目讲道理, 刚拿到手的时候就感觉笨办法可能行不通, 因为有太多需要枚举的东西了; 这个时候一般的选手一看到可能性太多, 他们立刻就会想到去找规律; 我刚拿到题目看到笨办法行不通的时候, 我是怎么做的呢? 我认为肯定有什么屠龙术, 所以朝这个方向去走, 最后结果也是没有走通;
如果找不到笨办法?
笨办法走不通的情形并不是很rare, 有时候碰到了这种情况, 不要立刻只会去找屠龙术, 还要思考有没有可能是让你简单的观察和总结规律.
这个是discussion里面awice的editorial1下面的一个人的回帖:
@roc571 said in Python, Straightforward with Explanation:
@awice said in Python, Straightforward with Explanation:
A necessary and sufficient condition for cand to be valid is that sum(cand) % 2 == m % 2 and sum(cand) <= m, as only when these conditions are satisfied can we find some f with sum(f) == m and cand[i] = f[i] % 2.
great solution but I feel it's quite difficult to figure out the valid condition tho.
我也是认同这个看法, awice的这个valid residue的判断, 并不是一般人就熟悉的一个东西, 我感觉他数学功底应该还是比较深厚的;
这个是discussion一个AC的暴力搜:
class Solution {
public int flipLights(int n, int m) {
n = n <= 6? n: (n % 6 + 6);
Set<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
int init = (1 << n) - 1;
queue.offer(init);
for (int i=0; i<m; i++) {
int size = queue.size();
visited.clear();
for (int k=0; k<size; k++) {
int s = queue.poll();
int[] next = new int[] {flipAll(s, n),
flipEven(s, n), flipOdd(s, n), flip3k1(s, n)};
for (int s1: next) {
if (!visited.contains(s1)) {
queue.offer(s1);
visited.add(s1);
}
}
}
}
return queue.size();
}
private int flipAll(int s, int n) {
int x = (1 << n) - 1;
return s ^ x;
}
private int flipEven(int s, int n) {
for (int i=0; i<n; i+=2) {
s ^= 1 << i;
}
return s;
}
private int flipOdd(int s, int n) {
for (int i=1; i<n; i+=2) {
s ^= 1 << i;
}
return s;
}
private int flip3k1(int s, int n) {
for (int i=0; i<n; i+=3) {
s ^= 1 << i;
}
return s;
}
}
不知道为什么这个算法能AC但是我的算法就TLE? 应该是因为他用的是integer hash, 而不是string来表达一个lights序列;
他这个写法是不知不觉的利用了这个题目的周期性的性质, 所以最后实际上当他再做1 << n的时候, 其实是利用了shift的一个wrap性质的; 没错, 当你对1的shift位数超过31的时候, 会自从wrap, 而不是直接超界没有人管:
java> 1 << 33
java.lang.Integer res4 = 2
java> 1 << 32
java.lang.Integer res5 = 1
java> (1 << 32 ) - 1
java.lang.Integer res6 = 0
总体来说这个题目是有点讨厌的, 也不知道想考察的到底是什么, 最后除了awice的editorial1, 大部分的答案考察的几乎就是你枚举的能力;
Problem Description
There is a room with n lights which are turned on initially and 4 buttons on the wall. After performing exactly m unknown operations towards buttons, you need to return how many different kinds of status of the n lights could be.
Suppose n lights are labeled as number [1, 2, 3 ..., n], function of these 4 buttons are given below:
- Flip all the lights.
- Flip lights with even numbers.
- Flip lights with odd numbers.
- Flip lights with (3k + 1) numbers, k = 0, 1, 2, ...
Example 1:
Input: n = 1, m = 1.
Output: 2
Explanation: Status can be: [on], [off]
Example 2:
Input: n = 2, m = 1.
Output: 3
Explanation: Status can be: [on, off], [off, on], [off, off]
Example 3:
Input: n = 3, m = 1.
Output: 4
Explanation: Status can be: [off, on, off], [on, off, on], [off, off, off], [off, on, on].
Note:
- n and m both fit in range [0, 1000].
Difficulty:Medium
Total Accepted:4.3K
Total Submissions:8.9K
Contributor:Stomach_ache
Companies
microsoft
Related Topics
math
Similar Questions
Bulb Switcher