使用有限的位数查找最大的奇数-Java 学习之路

我试图解决这个问题，但自动判断返回“超出时间限制”（TLE） .

在情人节之际，亚当和夏娃继续参加比赛 . 他们全面清理并进入决赛 . 在最后一轮中，给予偶数N和整数K，并且他必须找到小于N的最大奇数M，使得M的二进制表示中的数字之和最多为K.

输入格式：

对于每个测试用例，您将获得偶数N和整数K.

输出格式：

对于每个测试用例，输出整数M（如果存在），否则输出-1

约束：

1≤T≤104
2≤N≤109
0≤K≤30

样本输入：

2  
10 2  
6 1

样本输出：

9 
1

这是我到目前为止所做的 .

static long play(long n, int k){
      if(k==0) return -1;
      if(k==1) return 1;
      long m=n-1;      
      while(m>0){                      
              long value=Long.bitCount(m); //built in function to count bits
              if(value<=k ){                  
                  return m;
              }
              m=m-2;          
      }     
        return -1;
    }

    public void solve(InputReader in, OutputWriter out) {
       long start=System.currentTimeMillis(); 
       int t=in.readInt();
       while(t-->0){                
          long n=in.readLong();         
          int k=in.readInt();
          long result=play(n,k);         
          out.printLine(result);
       }
       long end=System.currentTimeMillis();
       out.printLine((end-start)/1000d+"ms");       
    } 
 }

3 回答

答案很奇怪，

让ans = 1，这里我们使用1位，所以k = k - 1;

现在ans的二进制表示

ans(binary) = 00000000000000000000000000000001

while(k > 0):

     make 30th position set
     ans(binary) = 01000000000000000000000000000001
     if(ans(decimal) < N):
          k -= 1
     else:
          reset 30th position
          ans(binary) = 00000000000000000000000000000001
 Do the same from 29th to 1st position

回复于 2024-04-29T04:21:54+08:00

0
您必须执行按位运算才能快速计算答案 . 让我给你一些提示 .

数字1的二进制和十进制表示法相同：12 = 110

要使数字102 = 210，将 1 向左移动一个位置 . 在Java和许多其他语言中，我们可以这样写：
```
(1 << 1) == 2
```
要使二进制数1002 = 410，请将 1 向左移动两个位置：
```
(1 << 2) == 4
```
要使二进制数10002 = 810向左移动 1 三个位置：
```
(1 << 3) == 8
```
你明白了 .

要查看某个位置的位是1还是0，请使用按位AND运算符 & . 例如，我们可以确定510 = 1012在第三个最高有效位为1，在第二个最高有效位为0，在最低有效位为1：
```
5 & (1 << 2) != 0
5 & (1 << 1) == 0
5 & (1 << 0) != 0
```
要将位设置为0，请使用 ^ （按位XOR运算符） . 例如，我们可以将710 = 1112的第二个最高有效位设置为0，从而获得510 = 1012：
```
7 ^ (1 << 1) == 5
```
回复于 2024-04-29T04:21:54+08:00
4

根据更新的问题 N 可以在2到10 ^ 9之间 . 你从 N-1 开始并向下循环2，所以你得到了循环的大约 10^9 / 2 次迭代 . 不好 .

从 M = N - 1 开始很好 . 使用 bitCount(M) 很好，开始使用 . 如果最初的bitcount是 <= K 你已经完成了 .

但如果不是，请不要使用步骤 -2 循环 .

请将您的数字看作二进制，例如 110101011 . 位数为6.假设K为4，这意味着您必须删除2位 . 最右边的位必须保持打开，并且您想要最大的数字，因此要清除两个倒数第二个1位 . 结果： 110100001 .

现在，你弄清楚如何写它 . 并且无需转换为文本即可完成 .

Note: 使用 N <= 10^9 ，它将适合 int . 不需要 long .

回复于 2024-04-29T04:21:54+08:00

使用有限的位数查找最大的奇数

3 回答

相关问题