[3097] Shortest Subarray With OR at Least K II

卡在很奇怪的地方Orz ( 倒地）

在 看懂要去算bit 之後 -- (因為Or 的結果要拿掉的時候，會不知道是誰的1 造成它on起來的，所以用算的去把它拿掉）

在while 的地方竟然卡住XD 不知道update currOr 的地方要寫在哪裡！！！真是太慘了Orz

還搞的要peek，但是根本不用啊啊啊啊啊！！！

原始版寫在最下面，我上面要貼精簡版本 XD (對了有一些corner case 還是沒辦法考慮到，慎之啊～～～～TOT）

void addBits(int* count, int num)

{

for (int i=0;i<32; i++)

{

if (num<=0)

return;

if (num%2==1)

count[i]++;

num >>=1;

}

return;

}

int updateOr(int* count, int num)

{

for (int i=0;i<32; i++)

{

if (num<=0)

break;

if (num%2==1)

count[i]--;

num >>=1;

}

int ret =0;

for (int i=0;i<32; i++)

{

if (count[i]>0)

ret |= (1<<i);

}

return ret;

}

int minimumSubarrayLength(int* nums, int numsSize, int k) {

if (k==0)

return 1;

int *count = calloc (32, sizeof(int));

int l=0, r=0;

int currOr=0;;

int len = INT_MAX;

while (r<numsSize)

{

while (r<numsSize && (currOr < k))

{

addBits(count, nums[r]);

currOr |= nums[r++];

}

if (r== numsSize && currOr <k)

break;

while (l<r && ( currOr >=k))

currOr = updateOr(count, nums[l++]);

if (r-l+1 <len)

len = r-l+1;

}

if (len == INT_MAX)

return -1;

return len;

}

/***********************************/

void addBits(int* count, int num)

{

for (int i=0;i<32; i++)

{

if (num<=0)

return;

if (num%2==1)

count[i]++;

num >>=1;

}

return;

}

void removeBits(int* count, int num)

{

for (int i=0;i<32; i++)

{

if (num<=0)

return;

if (num%2==1)

count[i]--;

num >>=1;

}

return;

}

int peek(int* count, int num)

{

int *tmp = calloc (32, sizeof(int));

for (int i=0;i<32; i++)

{

if (num%2==1)

tmp[i]=count[i]-1;

else

tmp[i]= count[i];

num >>=1;

}

int ret =0;

for (int i=0;i<32; i++)

{

if (tmp[i]>0)

ret |= (1<<i);

}

return ret;

}

int updateOr(int* count, int num)

{

for (int i=0;i<32; i++)

{

if (num<=0)

break;

if (num%2==1)

count[i]--;

num >>=1;

}

int ret =0;

for (int i=0;i<32; i++)

{

if (count[i]>0)

ret |= (1<<i);

}

return ret;

}

int minimumSubarrayLength(int* nums, int numsSize, int k) {

if (k==0)

return 1;

int *count = calloc (32, sizeof(int));

int l=0, r=0;

int currOr=0;;

int len = INT_MAX;

while (r<numsSize)

{

while (r<numsSize && (currOr < k))

{

addBits(count, nums[r]);

currOr |= nums[r++];

}

if (r== numsSize && currOr <k)

break;

while (l<r && ( currOr >=k))

{

#if 0

currOr= peek(count, nums[l]);

removeBits(count, nums[l]);

l++;

#else

currOr = updateOr(count, nums[l++]);

#endif

}

if (r-l+1 <len)

len = r-l+1;

}

if (len == INT_MAX)

return -1;

return len;

}