t*******i
发帖数: 4960 | 1 flip bits。
给定一个bits数组，你可以 flip 从 L 到 R 的值，就是 0 -> 1, 1 -> 0.
找出怎么 flip整个数组的和最大。
比如： 101001
flip 以后最大的和是 5 (110111)，L = 1， R = 4. |
C***U
发帖数: 2406 | 2 没看懂啥意思
【在 t*******i 的大作中提到】
: flip bits。
: 给定一个bits数组，你可以 flip 从 L 到 R 的值，就是 0 -> 1, 1 -> 0.
: 找出怎么 flip整个数组的和最大。
: 比如： 101001
: flip 以后最大的和是 5 (110111)，L = 1， R = 4.
|
d******s
发帖数: 274 | |
l*****a
发帖数: 14598 | 4 把中间一段0->1,1->0
为了最大，显然找最多的0 ->1
其实就是最大子数组和
【在 C***U 的大作中提到】
: 没看懂啥意思
|
t*******i
发帖数: 4960 | 5 75分钟 timed coding。
反正我挂了。 |
t*****s
发帖数: 416 | |
t*******i
发帖数: 4960 | 7 一次。
【在 t*****s 的大作中提到】
: 就是一次flip一个子数组？能flip几次？
|
N****s
发帖数: 267 | 8 L = 4, R = 4 ???
【在 t*******i 的大作中提到】
: flip bits。
: 给定一个bits数组，你可以 flip 从 L 到 R 的值，就是 0 -> 1, 1 -> 0.
: 找出怎么 flip整个数组的和最大。
: 比如： 101001
: flip 以后最大的和是 5 (110111)，L = 1， R = 4.
|
j*a
发帖数: 14423 | 9 把LR当成n1,n2来念
【在 C***U 的大作中提到】
: 没看懂啥意思
|
t*****s
发帖数: 416 | 10 这个应该是O(n)吧？最大子数组和问题的变种啊。白皮书上有。 |
|
|
o***g
发帖数: 2784 | 11 想要整个数组的1最多，那就要尽量多的flip 0.
因为是只能flip连续的一串数，所以当中有1的话，就相当于起了负作用，就是说本来
是1的，flip之后变成0. 最终结果里的1就少了一个。
如果flip一串数，开头的一个是1，是没有必要的。同样，结尾是1也没有必要，所以这
串数肯定是0开始0结束。
中间一串数，比如01，这两个数做flip对结果是没有影响的。
如果一串数00，flip了的结果是2，就是两个都需要flip。
如果这串数再加上1，变成001，根据前面的结论，我们只会flip前两个，最终结果是1+
2，1是原来有一个1,2是flip了之后出现了2个1.
如果再加一个0，变成0010，如果flip整个串，最终结果是1+3-1，最开始有个1，flip
出来3个1，但是中间的1变成0了，所以需要减掉。
再加一个0，变成00100，结果只能flip整个串，答案是1+4-1.
这时会发现，flip的串里有个0就是+1,有个1就是-1。
我们可以从左往右扫描，遇到0就+1，遇到1就-1，然后找最大值，这个点就是要flip的
右边界。
有个特例011111111000，这种情况，算到第一个的地方，结果是1，但是经历过下面一
串1之后，变成很负的一个数了，然后再经历后面的一串0之后也没有>1。但是这个例子
明显答案应该是flip最后3个0。所以之前的算法需要修改一下，就是当结果小于0的时
候，就不继续减了，这样当扫描到这个例子的最后一位的时候，就是3。大于第一位的1。
有了前面这个保证，从最大的值再往回扫，找到0为止。并且这个0是肯定可以找到的。
因为这个最大值是从0加上来的。往回扫算法的不同是，遇到0要-1，遇到1要+1。
下面是代码
true表示1，false表示0
public int[] flipBits(boolean[] bits)
{
int maxIndex = 0;
int max = Integer.MIN_VALUE;
int current = 0;
for (int i=0;i
{
if (bits[i] == true && current > 0)
{
current--;
}
if (bits[i] == false)
{
current ++;
if (current > max)
{
maxIndex = i;
max = current;
}
}
}
if (max == Integer.MIN_VALUE)
{
return null;
}
int minIndex = maxIndex;
current = max-1;
while (current>0)
{
minIndex --;
if (bits[minIndex] == true)
{
current ++;
}
else
{
current --;
}
}
return new int[]{minIndex,maxIndex};
}
做题花了半个小时，发帖又花了半个小时。。。。
【在 t*******i 的大作中提到】
: flip bits。
: 给定一个bits数组，你可以 flip 从 L 到 R 的值，就是 0 -> 1, 1 -> 0.
: 找出怎么 flip整个数组的和最大。
: 比如： 101001
: flip 以后最大的和是 5 (110111)，L = 1， R = 4.
|
b***e
发帖数: 1419 | 12 /*
Transform the array:
1 -> -1
0 -> 1
Then find max sum for substring (consecutive).
Spent 10 min coding and 2 min posting.
*/
var LR = function(a) {
for (var i = 0; i < a.length; i++) {
a[i] = a[i]? -1: 1;
}
console.log(a);
var L = a.length - 1;
var R = L;
var maxL = L;
var maxR = R;
var maxI = a[L];
var max = maxI;
for (var i = a.length - 2; i >= 0; i--) {
L = i;
if (maxI > 0) {
maxI += a[i];
} else {
R = L;
maxI = a[i];
}
if (max <= maxI) {
max = maxI;
maxR = R;
maxL = L;
}
}
return {L: maxL, R: maxR};
};
var a = [1,0,1,0,0,1];
console.log(LR(a));
1+
flip
【在 o***g 的大作中提到】
: 想要整个数组的1最多，那就要尽量多的flip 0.
: 因为是只能flip连续的一串数，所以当中有1的话，就相当于起了负作用，就是说本来
: 是1的，flip之后变成0. 最终结果里的1就少了一个。
: 如果flip一串数，开头的一个是1，是没有必要的。同样，结尾是1也没有必要，所以这
: 串数肯定是0开始0结束。
: 中间一串数，比如01，这两个数做flip对结果是没有影响的。
: 如果一串数00，flip了的结果是2，就是两个都需要flip。
: 如果这串数再加上1，变成001，根据前面的结论，我们只会flip前两个，最终结果是1+
: 2，1是原来有一个1,2是flip了之后出现了2个1.
: 如果再加一个0，变成0010，如果flip整个串，最终结果是1+3-1，最开始有个1，flip
|
i*******n
发帖数: 114 | 13 这个是VMWare的题，我也是前段时间在interviewstreet上做的。做完3周了也没有回复
，应该是挂了，不过我是做出来了（在本机上通过，不过在interviewstreet上过不了
），估计效率不行。
Input Format
An integer N
Next line contains the N bits, separated by spaces: d[0] d[1] ... d[N - 1]
Output:
S
Constraints:
1 <= N <= 100000
d[i] can only be 0 or 1
0 <= L <= R < n
Sample Input:
8
1 0 0 1 0 0 1 0
Sample Output:
6
Explanation:
We can get a maximum of 6 ones in the given binary array by performing
either of the following operations:
Flip [1, 5] ==> 1 1 1 0 1 1 1 0
or
Flip [1, 7] ==> 1 1 1 0 1 1 0 1 |
i*******n
发帖数: 114 | 14 这个用动态规划就可解决。数组的每个位置的bit逐个flip一次，然后再递归去子数组
中flip，最后比较，取最大的那个。
// dynamic programming
public static int getMaxOnes(int[] binaryArray){
int largestCount = 0;
int count = 0;
for(int i = 0; i < binaryArray.length; i++){
for(int j = i; j < binaryArray.length; j++){
count = flipAndGetOnesCount(Arrays.copyOf(binaryArray,
binaryArray.length), i, j);
if(count > largestCount){
largestCount = count;
}
}
}
return largestCount;
} |
w********s
发帖数: 1570 | 15 这个问题就是找到一个区间[i, j]其中的0的个数-1的个数最大，O(n^2)解显然有。
O(n)的话，从前往后扫，每扫到1个0，记录以这个0结尾的最大flip benefit
对下一个0，要么flip这个0，就是1，要么就是merge前面的一个0，前值-(i - prev0的
位置 - 1) + 1, 取两者大的。
【在 t*******i 的大作中提到】
: flip bits。
: 给定一个bits数组，你可以 flip 从 L 到 R 的值，就是 0 -> 1, 1 -> 0.
: 找出怎么 flip整个数组的和最大。
: 比如： 101001
: flip 以后最大的和是 5 (110111)，L = 1， R = 4.
|
p*****e
发帖数: 537 | 16 这题就是那个求max subarray sum的变种，是1就加0，是0就加1，求最大的subarray
sum。 |
m*****n
发帖数: 2152 | 17 有个思路，不知道对不对啊？大家看看。
考虑如下情况，假设边界确定，数组分为3段
(a0....ai)(b0....bj)(c0...ck)
其中(b0...bj)是要flip的segment。
那么ai一定是1，否则，ai要并入b，同理b0一定是0，否则b0要并入a
同理bj是0，c0是1。
左边界的pattern一定是10，（起始点是0的情况，也算入）
右边界的pattern一定是01，（终点是0的情况，也算入）。
确定左边界的条件：
1. (a0...a（i-1） ) 中一定是1的个数大于0的个数，否则左边界可以推到a0。
2. 对于任意(a0...ax) 其中(x <= i-1)中1的个数与0的个数的差一定小于(a0...ai)，
否则左边界可以推到ax。
对于右边界的确定，类似。
对了特殊情况是确定的左边界比右边界更右。比如0000111111000，这种情况比较(0...
R)和(L...n-1)谁0更多吧。
所以O(n)就够了。 |
