题解 | #数位重排#

解题思路

这是一个数位统计问题，需要判断一个数字重排后是否可能是原数的倍数：

1. 对于给定数字 ，判断其 倍到 倍是否可能通过重排得到
2. 两个数字是否可以通过重排得到，等价于它们的数位统计相同
3. 使用 map 来统计和比较数位出现次数

解题步骤：

1. 对原数和其倍数分别统计各个数位出现次数
2. 比较两个数字的数位统计是否相同
3. 遍历2到9倍数，只要有一个满足条件即可

代码

#include <iostream>
#include <map>
using namespace std;

bool isSameDigits(int m, int n) {
    map<int, int> count_m, count_n;
    
    // 统计m的数位
    while (m > 0) {
        count_m[m % 10]++;
        m /= 10;
    }
    
    // 统计n的数位
    while (n > 0) {
        count_n[n % 10]++;
        n /= 10;
    }
    
    return count_m == count_n;
}

bool isPossible(int n) {
    // 检查2到9倍
    for (int i = 2; i <= 9; i++) {
        if (isSameDigits(n, n * i)) {
            return true;
        }
    }
    return false;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        cout << (isPossible(n) ? "Possible" : "Impossible") << endl;
    }
    return 0;
}

import java.util.*;

public class Main {
    static boolean isSameDigits(int m, int n) {
        Map<Integer, Integer> countM = new HashMap<>();
        Map<Integer, Integer> countN = new HashMap<>();
        
        // 统计m的数位
        while (m > 0) {
            countM.put(m % 10, countM.getOrDefault(m % 10, 0) + 1);
            m /= 10;
        }
        
        // 统计n的数位
        while (n > 0) {
            countN.put(n % 10, countN.getOrDefault(n % 10, 0) + 1);
            n /= 10;
        }
        
        return countM.equals(countN);
    }
    
    static boolean isPossible(int n) {
        // 检查2到9倍
        for (int i = 2; i <= 9; i++) {
            if (isSameDigits(n, n * i)) {
                return true;
            }
        }
        return false;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            System.out.println(isPossible(n) ? "Possible" : "Impossible");
        }
        sc.close();
    }
}

def is_same_digits(m: int, n: int) -> bool:
    # 统计数位出现次数
    count_m = {}
    count_n = {}
    
    # 统计m的数位
    while m > 0:
        count_m[m % 10] = count_m.get(m % 10, 0) + 1
        m //= 10
    
    # 统计n的数位
    while n > 0:
        count_n[n % 10] = count_n.get(n % 10, 0) + 1
        n //= 10
    
    return count_m == count_n

def is_possible(n: int) -> bool:
    # 检查2到9倍
    for i in range(2, 10):
        if is_same_digits(n, n * i):
            return True
    return False

# 读取输入
t = int(input())
for _ in range(t):
    n = int(input())
    print("Possible" if is_possible(n) else "Impossible")

算法及复杂度

• 算法：哈希表统计
• 时间复杂度：，其中 是测试用例数， 是输入数字
• 空间复杂度：，用于存储数位统计