解题思路

这是一个约瑟夫环变体问题。通过模拟每隔两个数删除一个数的过程，找到最后被删除的数的原始位置。

关键点：

  1. 使用队列模拟循环过程
  2. 计数器记录移动次数
  3. 非删除位置的数移到队尾
  4. 处理循环结束条件

算法步骤：

  1. 初始化数字队列
  2. 循环处理直到只剩一个数
  3. 返回最后剩余的数

代码

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int findLastNumber(int n) {
        if (n <= 1) return 0;
        
        // 使用队列模拟过程
        queue<int> q;
        for (int i = 0; i < n; i++) {
            q.push(i);
        }
        
        int steps = 0;
        while (q.size() > 1) {
            steps++;
            if (steps == 3) {
                // 第三个数删除
                q.pop();
                steps = 0;
            } else {
                // 移动到队尾
                q.push(q.front());
                q.pop();
            }
        }
        
        return q.front();
    }
};

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

import java.util.*;

public class Main {
    static class Solution {
        public int findLastNumber(int n) {
            if (n <= 1) return 0;
            
            // 使用队列模拟过程
            Queue<Integer> queue = new LinkedList<>();
            for (int i = 0; i < n; i++) {
                queue.offer(i);
            }
            
            int steps = 0;
            while (queue.size() > 1) {
                steps++;
                if (steps == 3) {
                    // 第三个数删除
                    queue.poll();
                    steps = 0;
                } else {
                    // 移动到队尾
                    queue.offer(queue.poll());
                }
            }
            
            return queue.peek();
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Solution solution = new Solution();
        
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            System.out.println(solution.findLastNumber(n));
        }
        
        sc.close();
    }
}

from collections import deque

class Solution:
    def findLastNumber(self, n: int) -> int:
        if n <= 1:
            return 0
            
        # 使用双端队列模拟过程
        queue = deque(range(n))
        steps = 0
        
        while len(queue) > 1:
            steps += 1
            if steps == 3:
                # 第三个数删除
                queue.popleft()
                steps = 0
            else:
                # 移动到队尾
                queue.append(queue.popleft())
        
        return queue[0]

if __name__ == "__main__":
    solution = Solution()
    while True:
        try:
            n = int(input().strip())
            print(solution.findLastNumber(n))
        except EOFError:
            break

算法及复杂度

  • 算法：队列模拟
  • 时间复杂度：，每个数字最多被移动 次
  • 空间复杂度：，需要存储 个数字