解题思路

这是一道数学规律题，主要思路如下：

  1. 问题分析：

    • 对 的序列，每次丢弃奇数位置的数
    • 需要找到最后剩下的数字
    • 例如：对于 ，最后剩下

  2. 解决方案：

    • 观察规律可以发现，最后剩下的数是小于等于 的最大2的幂次数减1
    • 通过位运算可以快速求解：
      1. 找到大于 的最小2的幂
      2. 将该数除以2再减1即为答案

  3. 数学证明：

    • 每次删除奇数位后，剩余数字形成新序列
    • 新序列的规律符合2的幂次数减1的形式

代码

#include <iostream>
using namespace std;

int findLastNumber(int n) {
    // 找到大于n的最小2的幂
    int power = 1;
    while (power <= n + 1) {
        power <<= 1;
    }
    // 返回该2的幂除以2再减1
    return (power >> 1) - 1;
}

int main() {
    int n;
    while (cin >> n) {
        cout << findLastNumber(n) << endl;
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static int findLastNumber(int n) {
        // 找到大于n的最小2的幂
        int power = 1;
        while (power <= n + 1) {
            power <<= 1;
        }
        // 返回该2的幂除以2再减1
        return (power >> 1) - 1;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            System.out.println(findLastNumber(n));
        }
    }
}

def find_last_number(n: int) -> int:
    # 找到大于n的最小2的幂
    power = 1
    while power <= n + 1:
        power <<= 1
    # 返回该2的幂除以2再减1
    return (power >> 1) - 1

# 处理输入
while True:
    try:
        n = int(input())
        print(find_last_number(n))
    except EOFError:
        break

算法及复杂度

  • 算法：位运算
  • 时间复杂度： - 需要循环 次找到合适的2的幂
  • 空间复杂度： - 只需要常数额外空间