C++ 中的翻转字符串数字

2025年5月22日 | 阅读 14 分钟

在数学和计算机科学中，镜像数（strobogrammatic number）是一个非常有趣的数字，因为它在旋转180度（上下颠倒）后仍然保持不变。这样的数字在结构上是对称的，通常用于涉及回文、旋转和模式识别的问题。例如，个位数如 0、1 和 8，以及多位数如 69、96 和 818。

这涉及到了解180°的旋转如何影响每个数字，以及哪些数字组合构成了镜像数。有些数字根本不具备这种对称性。例如：

旋转后不变的数字是 0、1 和 8。6 和 9 是一个特殊的镜像数字对，当它们被翻转时会变成对方。
事实证明，其他数字，如 2、3、4、5 和 7，不具备这种属性，因此不能构成镜像数的一部分。

确定一个数字是否是镜像数，最常通过字符串操作在计算上完成。如果我们把数字表示为一个字符串，我们可以使用双指针方法来比较来自两端的相同位置的数字。为了使数字成为镜像数，它的每个数字都需要与一个镜像数字配对。

实际上，镜像数在许多不同领域都有应用，例如密码学、数字时钟显示和视觉艺术中的美学设计。另一方面，在编程挑战中，它们出现在处理字符串、旋转对称和模式匹配的任务中。例如，为了在 C++ 中查找镜像数，会使用一个无序映射来存储有效的数字对，然后程序会检查字符串是否能正确地旋转到其镜像等效形式。

方法一：双指针法

通过双指针法，通过比较镜像位置上的数字来测试一个数是否为镜像数。这涉及在数字字符串表示的开头（左）和结尾（右）放置两个指针：

关键在于，左指针指向的数字必须是右指针指向数字的镜像配对。有效的配对包括 0 ↔ 0、1 ↔ 1、8 ↔ 8、6 ↔ 9、9 ↔ 6 等。如果左边的数字是 6，那么右边的数字必须是 9，这个数才是镜像数。

然而，这个过程会继续，两个指针会向内移动（left++ 和 right--），直到它们相遇或交叉。我们通过检查是否存在任何不匹配（无效数字或配对不匹配）来确定该数字是否为镜像数。如果所有配对都匹配，则该数字是镜像数。

示例

让我们举一个例子来说明使用双指针法在 C++ 中判断镜像数。

#include <iostream>
#include <unordered_map>
#include <string>
#include <vector>
#include <sstream>
#include <cctype>
#include <iomanip>
// Function to check if a number is strobogrammatic
bool isStrobogrammatic(const std::string& num) {
    std::unordered_map<char, char> strobogrammaticPairs = {
        {'0', '0'}, {'1', '1'}, {'8', '8'}, {'6', '9'}, {'9', '6'}
    };
    int left = 0, right = num.size() - 1;
    while (left <= right) {
        // Check if the current digit has a valid pair
        if (strobogrammaticPairs.find(num[left]) == strobogrammaticPairs.end() ||
            strobogrammaticPairs[num[left]] != num[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}
// Function to validate user input
bool validateInput(const std::string& input) {
    for (char c : input) {
        if (!isdigit(c)) return false;
    }
    return !input.empty();
}

// Function to explain the checking process
std::string explainProcess(const std::string& num) {
    std::unordered_map<char, char> strobogrammaticPairs = {
        {'0', '0'}, {'1', '1'}, {'8', '8'}, {'6', '9'}, {'9', '6'}
    };
    int left = 0, right = num.size() - 1;
    std::stringstream explanation;
    explanation << "Checking process for number: " << num << "\n";
    while (left <= right) {
        char leftChar = num[left];
        char rightChar = num[right];
        explanation << "Comparing '" << leftChar << "' (left) with '" << rightChar
                    << "' (right)... ";
        if (strobogrammaticPairs.find(leftChar) == strobogrammaticPairs.end()) {
            explanation << "Invalid digit '" << leftChar << "' (not strobogrammatic).\n";
            return explanation.str();
        }
        if (strobogrammaticPairs[leftChar] != rightChar) {
            explanation << "Mismatch: '" << leftChar << "' maps to '"
                        << strobogrammaticPairs[leftChar] << "', but '" << rightChar
                        << "' found.\n";
            return explanation.str();
        }
        explanation << "Valid match! '" << leftChar << "' ↔ '" << rightChar << "'\n";
        left++;
        right--;
    }
    explanation << "All pairs are valid! The number is strobogrammatic.\n";
    return explanation.str();
}
// Function to generate some sample numbers for testing
std::vector<std::string> generateSampleNumbers() {
    return {"69", "88", "818", "123", "609", "986", "1", "11", "0", "121","456","737"};
}
// Function to display results in a custom output format
void displayResults(const std::vector<std::string>& numbers) {
    for (const auto& num : numbers) {
        std::cout << "Number: " << num << "\n";
        std::cout << "Result: " 
                  << (isStrobogrammatic(num) ? "Strobogrammatic" : "Not Strobogrammatic") 
                  << "\n";
        std::cout << explainProcess(num) << "\n";
    }
}
// Main function
int main() {
    std::cout << "    Strobogrammatic Number Checker    \n";
    // Step 1: Display some sample results
    std::vector<std::string> sampleNumbers = generateSampleNumbers();
    std::cout << "\nSample Numbers and Results:\n";
    displayResults(sampleNumbers);
    // Step 2: Allow user to input their own numbers
    std::string userInput;
    while (true) {
        std::cout << "\nEnter a number to check (or type 'exit' to quit): ";
        std::cin >> userInput;
        if (userInput == "exit") {
            std::cout << "Exiting the program. Goodbye!\n";
            break;
        }
        if (!validateInput(userInput)) {
            std::cout << "Invalid input! Please enter a non-negative integer.\n";
            continue;
        }
        std::cout << "Number: " << userInput << "\n";
        std::cout << "Result: " 
                  << (isStrobogrammatic(userInput) ? "Strobogrammatic" : "Not Strobogrammatic") 
                  << "\n";
        std::cout << explainProcess(userInput) << "\n";
    }
    return 0;
}   

输出

Strobogrammatic Number Checker    
Sample Numbers and Results:
Number: 69
Result: Strobogrammatic
Checking process for number: 69
Comparing '6' (left) with '9' (right)... Valid match! '6' ↔ '9'
All pairs are valid! The number is strobogrammatic.

Number: 88
Result: Strobogrammatic
Checking process for number: 88
Comparing '8' (left) with '8' (right)... Valid match! '8' ↔ '8'
All pairs are valid! The number is strobogrammatic.
Number: 818
Result: Strobogrammatic
Checking process for number: 818
Comparing '8' (left) with '8' (right)... Valid match! '8' ↔ '8'
Comparing '1' (left) with '1' (right)... Valid match! '1' ↔ '1'
All pairs are valid! The number is strobogrammatic.
Number: 123
Result: Not Strobogrammatic
Checking process for number: 123
Comparing '1' (left) with '3' (right)... Mismatch: '1' maps to '1', but '3' found.
Number: 609
Result: Strobogrammatic
Checking process for number: 609
Comparing '6' (left) with '9' (right)... Valid match! '6' ↔ '9'
Comparing '0' (left) with '0' (right)... Valid match! '0' ↔ '0'
All pairs are valid! The number is strobogrammatic.
Number: 986
Result: Strobogrammatic
Checking process for number: 986
Comparing '9' (left) with '6' (right)... Valid match! '9' ↔ '6'
Comparing '8' (left) with '8' (right)... Valid match! '8' ↔ '8'
All pairs are valid! The number is strobogrammatic.
Number: 1
Result: Strobogrammatic
Checking process for number: 1
Comparing '1' (left) with '1' (right)... Valid match! '1' ↔ '1'
All pairs are valid! The number is strobogrammatic.
Number: 11
Result: Strobogrammatic
Checking process for number: 11
Comparing '1' (left) with '1' (right)... Valid match! '1' ↔ '1'
All pairs are valid! The number is strobogrammatic.
Number: 0
Result: Strobogrammatic
Checking process for number: 0
Comparing '0' (left) with '0' (right)... Valid match! '0' ↔ '0'
All pairs are valid! The number is strobogrammatic.
Number: 121
Result: Not Strobogrammatic
Checking process for number: 121
Comparing '1' (left) with '1' (right)... Valid match! '1' ↔ '1'
Comparing '2' (left) with '2' (right)... Invalid digit '2' (not strobogrammatic).
Number: 456
Result: Not Strobogrammatic
Checking process for number: 456
Comparing '4' (left) with '6' (right)... Invalid digit '4' (not strobogrammatic).
Number: 737
Result: Not Strobogrammatic
Checking process for number: 737
Comparing '7' (left) with '7' (right)... Invalid digit '7' (not strobogrammatic).
Enter a number to check (or type 'exit' to quit): exit
Exiting the program. Goodbye!

说明

1. isStrobogrammatic 函数（镜像数检查函数）

这个函数使用双指针法。

使用无序映射存储有效的镜像数字对（即 0↔0、1↔1、8↔8、6↔9 和 9↔6）。两个指针（左和右）从字符串的两端遍历数字，比较字符。

如果数字不在映射中，或者该数字的镜像配对与该数字不匹配，则函数返回 false。

2. validateInput(input)

确保输入是有效的非负整数。

我们遍历字符串中的每个字符，检查它是否是数字。这确保了输入不是空的。

3. explainProcess（解释函数）

这个函数一步一步地解释镜像数检查过程。

它与 isStrobogrammatic 类似，但为每次比较提供了额外的消息（例如，“有效匹配！”或“不匹配”）。当出现不匹配或无效数字时，它会分解为什么数字不是镜像数。

4. generateSampleNumbers（示例生成）

它列出了一些示例数字，以展示其工作原理（例如，69、818、123）。

5. displayResults（结果显示）

它遍历数字列表：explainProcess 解释每个数字为何是镜像数（或不是），然后打印每个数字是否是镜像数。

6. 用户交互（主函数）

它为预定义的样本数字提供结果。它提示用户输入一个数字并检查输入是否有效。然后运行镜像数检查并打印详细解释。

输出格式

对于每个数字，程序都会分步解释比较过程。

输出显示了匹配的对，例如“6”↔“9”。识别这些匹配或无效数字。该程序采用模块化设计，使其更加健壮、用户友好且文档齐全。

复杂度分析

时间复杂度

1. 镜像数检查（isStrobogrammatic）

该函数使用两个指针（左和右）遍历字符串，每个数字只处理一次。因此，时间复杂度为 O(n)，其中 n 是输入字符串的长度（数字中的位数）。

对每个有效镜像数对的无序映射查找，每个字符的迭代时间为 O(1)。

2. 解释函数（explainProcess）

它像 isStrobogrammatic 一样遍历字符串一次，并进行相同的配对检查和解释。因此，单个数字的时间复杂度也为 O(n)。

3. 验证函数（validateInput）

checkdigit 函数仅遍历字符串中的每个字符以确保它是数字。由于它扫描整个字符串，因此时间复杂度为 O(n)。

4. 样本结果（displayResults）

该函数遍历所有样本数字，并为每个样本调用 isStrobogrammatic 和 explainProcess。

如果我们假设有 m 个样本数字，并且样本数字的平均长度小于 n，则复杂度为 O(m × n)。

空间复杂度

镜像数检查
无序映射的大小是固定的（常数空间，O(1)），指针只使用两个整数变量（left，right）。
解释函数
它使用 stringstream 函数构建解释字符串。对于 n 个数字，它需要 O(n) 的空间来存储解释。总而言之，单个数字的空间复杂度为 O(n)。

方法二：基于哈希的验证

在基于哈希的验证方法中，我们在哈希映射中用其镜像配对替换数字中的每个数字。无序映射存储了有效的镜像数对（例如，0 ↔ 0、1 ↔ 1、6 ↔ 9、9 ↔ 6、8 ↔ 8）。该算法遍历字符串，将一个数字转换为其配对，并构建一个转换后的字符串。

转换完成后，将转换后的字符串反转。如果反转后的字符串等于原始输入，则该数字为镜像数，否则不是。使用这种字符串转换和比较消除了对双指针技术的需求，并检查数字是否满足镜像数条件。

示例

让我们举一个例子来说明使用基于哈希的验证方法在 C++ 中判断镜像数。

#include <iostream>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <sstream>
#include <vector>
// Function to check if a number is strobogrammatic using hash-based transformation
bool isStrobogrammaticHash(const std::string& num) {
    // Define valid strobogrammatic digit pairs
    std::unordered_map<char, char> strobogrammaticPairs = {
        {'0', '0'}, {'1', '1'}, {'8', '8'}, {'6', '9'}, {'9', '6'}
    };
    // Initialize an empty string to store the transformed number
    std::string transformed;
    // Transform each digit to its strobogrammatic pair
    for (char c : num) {
        // If a character is invalid (not in the map), return false immediately
        if (strobogrammaticPairs.find(c) == strobogrammaticPairs.end()) {
            return false;
        }
        transformed += strobogrammaticPairs[c]; // Add the transformed digit
    }
    // Reverse the transformed string
    std::reverse(transformed.begin(), transformed.end());
    // Compare the transformed string with the original number
    return transformed == num;
}

// Function to validate if the input is a valid non-negative integer
bool validateInput(const std::string& input) {
    // Ensure the input is non-empty and contains only digits
    for (char c : input) {
        if (!isdigit(c)) return false;  // If non-digit is found, return false
    }
    return !input.empty();
}
// Function to display the result in a formatted manner
void displayResult(const std::string& num, bool isStrobogrammatic) {
    std::cout << "Number: " << num << "\n";
    std::cout << "Result: " << (isStrobogrammatic ? "Strobogrammatic" : "Not Strobogrammatic") << "\n";
}
// Function to explain the check process
std::string explainProcess(const std::string& num) {
    std::unordered_map<char, char> strobogrammaticPairs = {
        {'0', '0'}, {'1', '1'}, {'8', '8'}, {'6', '9'}, {'9', '6'}
    };
    std::stringstream explanation;
    explanation << "Checking the number: " << num << "\n";
    // Create a transformed string by replacing digits with their strobogrammatic pair
    std::string transformed;
    for (char c : num) {
        if (strobogrammaticPairs.find(c) == strobogrammaticPairs.end()) {
            explanation << "Invalid digit '" << c << "' found.\n";
            return explanation.str(); // Return explanation if invalid digit is found
        }
        transformed += strobogrammaticPairs[c];
    }
    // Reverse the transformed string
    std::reverse(transformed.begin(), transformed.end());
    // Compare the transformed string with the original number
    if (transformed == num) {
        explanation << "The transformed string matches the original number. It's strobogrammatic.\n";
    } else {
        explanation << "The transformed string does not match the original number. It's not strobogrammatic.\n";
    }
    return explanation.str();
}
// Function to generate a few sample numbers for testing
std::vector<std::string> generateSampleNumbers() {
    return {"69", "88", "818", "123", "609", "986", "1", "11", "0", "121"};
}
// Function to display results for a list of sample numbers
void displaySampleResults() {
    std::vector<std::string> sampleNumbers = generateSampleNumbers();
    
    for (const auto& num : sampleNumbers) {
        bool result = isStrobogrammaticHash(num);
        displayResult(num, result);
        std::cout << explainProcess(num) << "\n";
    }
}
// Main function
int main() {
    std::cout << "        Strobogrammatic Number Checker        \n";
    // Step 1: Show sample results
    std::cout << "\nSample Results:\n";
    displaySampleResults();
    // Step 2: Allow user to input numbers and check if they are strobogrammatic
    std::string userInput;
    while (true) {
        std::cout << "\nEnter a number to check (or type 'exit' to quit): ";
        std::cin >> userInput;
        if (userInput == "exit") {
            std::cout << "Exiting the program. Goodbye!\n";
            break;
        }
        // Validate input to ensure it's a valid non-negative integer
        if (!validateInput(userInput)) {
            std::cout << "Invalid input! Please enter a valid non-negative integer.\n";
            continue;
        }
        // Check if the number is strobogrammatic and display the result
        bool isStrobogrammatic = isStrobogrammaticHash(userInput);
        displayResult(userInput, isStrobogrammatic);
        // Display a detailed explanation
        std::cout << explainProcess(userInput) << "\n";
    }
    return 0;
}   

输出

Strobogrammatic Number Checker        

Sample Results:
Number: 69
Result: Strobogrammatic
Checking the number: 69
The transformed string matches the original number. It's strobogrammatic.
Number: 88
Result: Strobogrammatic
Checking the number: 88
The transformed string matches the original number. It's strobogrammatic.
Number: 818
Result: Strobogrammatic
Checking the number: 818
The transformed string matches the original number. It's strobogrammatic.
Number: 123
Result: Not Strobogrammatic
Checking the number: 123
Invalid digit '2' found.
Number: 609
Result: Strobogrammatic
Checking the number: 609
The transformed string matches the original number. It's strobogrammatic.
Number: 986
Result: Strobogrammatic
Checking the number: 986
The transformed string matches the original number. It's strobogrammatic.
Number: 1
Result: Strobogrammatic
Checking the number: 1
The transformed string matches the original number. It's strobogrammatic.

Number: 11
Result: Strobogrammatic
Checking the number: 11
The transformed string matches the original number. It's strobogrammatic.
Number: 0
Result: Strobogrammatic
Checking the number: 0
The transformed string matches the original number. It's strobogrammatic.
Number: 121
Result: Not Strobogrammatic
Checking the number: 121
Invalid digit '2' found.
Enter a number to check (or type 'exit' to quit): exit
Exiting the program. Goodbye!

说明

isStrobogrammaticHash 函数
此函数用于判断给定的数字（字符串）是否为镜像数。它使用无序映射（哈希映射）来定义有效的镜像数字对：“0”↔“0”、“1”↔“1”、“6”↔“9”、“9”↔“6”和“8”↔“8”。
它遍历输入字符串的每个字符，并使用哈希映射进行转换。如果遇到不在映射中的字符，则函数返回 false，因为它是无效字符。
它反转字符串，将其与转换后的数字进行比较，然后将其还原为数字。如果它们匹配，则该数字是镜像数。
validateInput 函数
此函数仅确保输入字符串只包含数字且非空。因此，它会拒绝无效的输入，例如字母或特殊字符。
displayResult 函数
这是一个格式化结果的函数，用于指示数字本身是否为镜像数。
explainProcess 函数
此函数详细说明了检查过程。它将每个数字的转换与原始转换后的字符串进行比较。
generateSampleNumbers 函数
它生成一个样本数字列表，用于展示程序的各项功能。
displaySampleResults 函数
它遍历样本数字，检查每个数字是否为镜像数，并打印带有解释的结果。
主函数
它将显示样本结果并提示用户输入。它会持续验证和检查输入的数字，显示该数字的结果和解释。用户可以通过输入“exit”来退出程序。
程序流程
程序首先显示一些样本数字的结果。然后进入一个循环，在该循环中我们可以输入数字来检查它们是否为镜像数。对于无效输入，程序会要求输入有效的输入。

复杂度分析

时间复杂度分析

isStrobogrammaticHash 函数
遍历字符串：数字是 n 个字符的字符串，函数处理字符串的每个字符。哈希映射（无序映射）的查找操作平均为 O(1)。
第二个步骤是字符串转换步骤，将转换后的数字添加到新字符串（transformed）中。此操作对每个字符的执行时间为 O(1)。
反转转换后的字符串：当所有字符都被转换为字符串后，该字符串会被反转。反转一个长度为 n 的字符串需要 O(n) 的时间。
比较转换后的字符串：最后，将转换后的字符串与原始字符串进行比较。由于它比较两个字符串的每个字符，因此时间复杂度为 O(n)。
因此，isStrobogrammaticHash 的时间复杂度主要由字符串遍历、反转和比较决定，这些都具有 O(n) 的时间复杂度。
此函数的总时间复杂度为：O(n)。
validateInput 函数
此函数遍历每个字符以检查它们是否为数字。由于每个字符循环一次，因此时间复杂度为 O(n)。
displayResult 和 explainProcess
它们都是字符串操作函数，涉及字符串组合、转换和字符串比较。这意味着这些操作需要 O(n) 的时间。
generateSampleNumbers 和 displaySampleResults
由于使用了预定义的样本数字集，因此样本生成和显示操作需要常数时间。因此，它们的时间复杂度为 O(k)，其中 k 是常数个样本数字。

空间复杂度分析

isStrobogrammaticHash
strobogrammaticPairs 无序映射存储 5 对条目，由于条目数量固定，strobogrammaticPairs 无序映射的空间复杂度为 O(1)。
通过存储输入字符串的转换版本来创建转换后的字符串。我们还注意到此字符串的长度与输入字符串成比例，因此需要 O(n) 的空间复杂度。
validateInput, displayResult, explainProcess
这些函数只需要少量固定的空间。因此，它们空间复杂度为 O(1)。
样本数据
样本数字存储在固定大小的向量中（包含 k 个样本数字）。因此，generateSampleNumbers 函数的空间复杂度为 O(k)。

下一个主题Superabundant-numbers-in-cpp

← 上一个下一个 →

C++ 中的翻转字符串数字

方法一：双指针法

示例

说明

复杂度分析

方法二：基于哈希的验证

示例

说明

复杂度分析

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 中的翻转字符串数字

方法一：双指针法

示例

说明

复杂度分析

方法二：基于哈希的验证

示例

说明

复杂度分析

相关帖子

C++ 中的 std::memory_order 枚举

C++ 中每个节点的下一个右侧指针填充

C++ 中异常安全性的不同保证级别

C++ 中的三合数

C++ 中查找旋转排序数组的枢轴

C++ 中检查有效 IMEI 号码的程序

C++ 中打印 V 形和倒 V 形图案的程序

C++ 的不同版本

C++ std::filesystem::hard_link_count

C++ 中的油漆栅栏算法

订阅 Tpoint Tech

联系信息