Twitter OA prepare: Flipping a bit - neverlandly - 博客园
Also check: https://github.com/wesleyzh/Algorithm/blob/master/flip.py
Extend:
The element is any number.
--> check flip the element will cause more or less 1 bit.
Read full article from Twitter OA prepare: Flipping a bit - neverlandly - 博客园
You are given a binary array with N elements: d[0], d[1], ... d[N - 1]. You can perform AT MOST one move on the array: choose any two integers [L, R], and flip all the elements between (and including) the L-th and R-th bits. L and R represent the left-most and right-most index of the bits marking the boundaries of the segment which you have decided to flip. What is the maximum number of '1'-bits (indicated by S) which you can obtain in the final bit-string? . more info on 1point3acres.com 'Flipping' a bit means, that a 0 is transformed to a 1 and a 1 is transformed to a 0 (0->1,1->0). 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 can only be 0 or 1f -google 1point3acres 0 <= L <= R < n . 1point3acres.com/bbs Sample Input: 8 1 0 0 1 0 0 1 0 . 1point3acres.com/bbs 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
分析:这道题无非就是在一个数组内,找一个区间,该区间 0的个数 与 1的个数 差值最大。如果我们把这个想成股票的话,0代表+1,1代表-1,那么这道题就转化成了Best Time to Buy and Sell Stock, 找0和1的个数差值最大就变成了找max profit。
因为需要找到这个区间,所以在Stock这道题的基础上还要做一定修改,记录区间边缘移动情况
1 public int flipping(int[] A) { 2 int local = 0; 3 int global = 0; 4 int localL = 0; 5 int localR = 0; 6 int globalL = 0; 7 int globalR = 0; int OnesFlip = 0; 8 int OnesUnFlip = 0; //those # of ones outside the chosen range 9 for (int i=0; i<A.length; i++) { 10 int diff = 0; 11 if (A[i] == 0) diff = 1; 12 else diff = -1; 13 14 if (local + diff >= diff) { 15 local = local + diff; 16 localR = i; 17 } 18 else { 19 local = diff; 20 localL = i; 21 localR = i; 22 } 23 24 if (global < local) { 25 global = local; 26 globalL = localL; 27 globalR = localR; 28 } 29 } 30 for (int i=0; i<globalL; i++) { 31 if (A[i] == 1) 32 OnesUnflip ++; 33 } for (int i=globalL; i<=globalR; i++) { if (A[i] == 0) OnesFlip ++; } 34 for (int i=globalR+1; i<A.length; i++) { 35 if (A[i] == 1) 36 OnesUnflip ++; 37 } 38 return OnesFlip + OnesUnflip; 39 }
Also check: https://github.com/wesleyzh/Algorithm/blob/master/flip.py
Extend:
The element is any number.
--> check flip the element will cause more or less 1 bit.