526互联

回文串

发布时间 2023-12-18 14:20:58作者: miyanyan

按顺序生成回文串

vector<int> pal;

auto init = [](int leftBase) {
    // 严格按顺序从小到大生成所有回文数（不用字符串转换）
    for (int base = 1; base <= leftBase; base *= 10) {
        // 生成奇数长度回文数
        for (int i = base; i < base * 10; i++) {
            int x = i;
            for (int t = i / 10; t; t /= 10) {
                x = x * 10 + t % 10;
            }
            pal.push_back(x);
        }
        // 生成偶数长度回文数
        if (base <= leftBase/ 2) {
            for (int i = base; i < base * 10; i++) {
                int x = i;
                for (int t = i; t; t /= 10) {
                    x = x * 10 + t % 10;
                }
                pal.push_back(x);
            }
        }
    }
    return 0;
};

// 生成100000以内的
// 对应回文串范围 [1, 99999]
// 因为是回文串可以翻转, 所以只考虑左半部分，左半部分是999，3位数
init(100);