阅微客栈

注册或登录 (丢失密码?):

用户名：
密码：

记住我

阅微客栈 » 头脑风暴

1. 

   zhang
   神

   给你一个二进制的n位数，求上一个和下一个数，使得有相同个数的1。

   发布于 1 年 之前 #
2. 

   medie2005
   Member

   考虑组合数。
   5选3的组合有：543，542，541，532，531，521，432，431，421，321。用01串表示，就是：
   11100
   11010
   11001
   10110
   10101
   10011
   01110
   01101
   01011
   00111
   由此，可以知道，若给定一个二进制的n位数a,将a化为对应于其二进制表示的01字符串，利用STL 中的next_permutation()就可以得到满足条件的下一个数的01串表示。
   同样，将a的各位二进制按位取反，得到b，再将b化为对应于其二进制表示的01字符串，利用STL 中的next_permutation()就可以得到一个01串s，将s的各位取反，则得到的01串就是满足条件的上一个数的01串表示。

   发布于 11 月 之前 #
3. 

   BreakDrS
   Member

   当前的组合中，找从右往左第一个“可以左移的1”。
   找到之后，将它左移，并把它右边的1全部放到最右。
   这样的算法是O(n)的。

   发布于 11 月 之前 #
4. 

   Wanting
   Member

   int nextNumber(int input) {
   int count1 = 0;
   int i;
   bool previousDigitIs1 = false;
   for (i = 0; i < 32; i++) {
   int temp = input >> i;
   if ((temp & 1) == 1) {
   count1 ++;
   previousDigitIs1 = true;
   } else {
   if (previousDigitIs1) {
   break;
   } else {
   previousDigitIs1 = false;
   }
   }
   }
   int flag = 1 << i;
   for (int j = 0; j < count1 - 1; j++) {
   flag |= (1 << j);
   }
   return (((input >> i) << i) | flag);
   }

   发布于 7 月 之前 #
5. 

   Wanting
   Member

   没测过哦。。

   int prevNumber(int input) {
   bool previousDigitIs0 = false;
   int result;
   for (int i = 0; i < 32; i++) {
   if ((input>>i) & 1 == 1) {
   if (previousDigitIs0) {
   result = input | (1 << i - 1);
   result &= (~(1 << i));
   return result;
   }
   } else {
   previousDigitIs0 = true;
   }
   }
   throw "No valid previous number";
   }

   发布于 7 月 之前 #

该主题的 RSS Feed

回复

你必须 登录 后发帖。