LeetCode第247题_中心对称数II-CSDN博客

本文链接：https://blog.csdn.net/qq_40263592/article/details/148410585

LeetCode第247题：中心对称数II

问题描述

中心对称数（Strobogrammatic Number）是指在旋转180度后看起来依然相同的数。例如，数字"69"在旋转180度后看起来仍然是"69"，数字"88"旋转后也是"88"。

给定长度为 n 的所有中心对称数的集合。例如，当 n = 2 时，集合包含：“11”，“69”，“88”，“96”。

注意：由于技术限制，我们认为"00"、"10"等不是有效的数字。因此每位数不能以0开头，除非它只有一位且这一位是0。

难度：中等

示例：

示例 1:
输入: n = 2
输出: ["11","69","88","96"]

示例 2:
输入: n = 1
输出: ["0","1","8"]

解题思路

本题需要生成长度为 n 的所有中心对称数。我们先了解一下中心对称数的特性：

数字0、1、8旋转后仍然是自己
数字6旋转后是9，数字9旋转后是6
其他数字旋转后不是有效的数字

我们可以利用递归来解决这个问题。思路如下：

对于长度为n的中心对称数，其第一位和最后一位必须构成一个合法的中心对称对（不能以0开头，除非n=1）
中间部分是长度为n-2的中心对称数
基本情况：
- 当n=0时，返回空字符串（用于构建偶数长度的中心对称数）
- 当n=1时，返回可能的单个数字：“0”、“1”、“8”

递归的实现步骤：

构建长度为n-2的所有中心对称数
在每个结果的前后添加所有合法的中心对称对：(“0”,“0”), (“1”,“1”), (“8”,“8”), (“6”,“9”), (“9”,“6”)
注意：如果是整个数字的外层（即原始调用时的n），则不能添加"0"作为开头（只有n=1的特殊情况除外）

代码实现

C#实现

public class Solution {
    public IList<string> FindStrobogrammatic(int n) {
        return Helper(n, n);
    }
    
    private IList<string> Helper(int n, int originalN) {
        // 基本情况
        if (n == 0) return new List<string> { "" }; // 偶数长度的中心
        if (n == 1) return new List<string> { "0", "1", "8" }; // 奇数长度的中心
        
        // 获取中间部分的所有中心对称数
        IList<string> subResults = Helper(n - 2, originalN);
        IList<string> results = new List<string>();
        
        // 在每个结果的前后添加所有合法的中心对称对
        foreach (string subResult in subResults) {
            // 如果不是最外层，可以添加"0"作为开头和结尾
            if (n != originalN) {
                results.Add("0" + subResult + "0");
            }
            
            results.Add("1" + subResult + "1");
            results.Add("8" + subResult + "8");
            results.Add("6" + subResult + "9");
            results.Add("9" + subResult + "6");
        }
        
        return results;
    }
}

Python实现

class Solution:
    def findStrobogrammatic(self, n: int) -> List[str]:
        return self.helper(n, n)
    
    def helper(self, n: int, original_n: int) -> List[str]:
        # 基本情况
        if n == 0:
            return [""]  # 偶数长度的中心
        if n == 1:
            return ["0", "1", "8"]  # 奇数长度的中心
        
        # 获取中间部分的所有中心对称数
        sub_results = self.helper(n - 2, original_n)
        results = []
        
        # 在每个结果的前后添加所有合法的中心对称对
        for sub in sub_results:
            # 如果不是最外层，可以添加"0"作为开头和结尾
            if n != original_n:
                results.append("0" + sub + "0")
            
            results.append("1" + sub + "1")
            results.append("8" + sub + "8")
            results.append("6" + sub + "9")
            results.append("9" + sub + "6")
        
        return results

C++实现

class Solution {
public:
    vector<string> findStrobogrammatic(int n) {
        return helper(n, n);
    }
    
private:
    vector<string> helper(int n, int originalN) {
        // 基本情况
        if (n == 0) return {""};  // 偶数长度的中心
        if (n == 1) return {"0", "1", "8"};  // 奇数长度的中心
        
        // 获取中间部分的所有中心对称数
        vector<string> subResults = helper(n - 2, originalN);
        vector<string> results;
        
        // 在每个结果的前后添加所有合法的中心对称对
        for (const string& sub : subResults) {
            // 如果不是最外层，可以添加"0"作为开头和结尾
            if (n != originalN) {
                results.push_back("0" + sub + "0");
            }
            
            results.push_back("1" + sub + "1");
            results.push_back("8" + sub + "8");
            results.push_back("6" + sub + "9");
            results.push_back("9" + sub + "6");
        }
        
        return results;
    }
};