中心对称数 II

1.题目描述

中心对称数是指一个数字在旋转了 180 度之后看起来依旧相同的数字（或者上下颠倒地看）。

找到所有长度为 n 的中心对称数。

示例 :

输入:  n = 2

输出: ["11","69","88","96"]

2.解题思路

（1）如果n == 0，那么返回“” (空字符串)

（2）如果n == 1, 那么返回“0”， “1”， ”8“

（3）如果n == 2，那么返回 “11” ， “69”， “88”， “96”（这里不包含”00“的情况）

（4）如果n == 3, 那么返回（这里包含”00“的情况,例如"1001"）

　　“1” + s + “1”

　　“6” + s + “9”

　　“8” + s + “8”

　　“9" + s + “6”

最外围是对称数，那么s呢，就等于n==1的时候的取值，满足n-2.

add1 = {"0","1","8"}，add2 = {"00","11","69","88","96"}

i 是奇数，我们在 i-1 偶数的基础上每个数中间位置 add1

i 是偶数，我们在 i-2 偶数的基础上每个数中间位置 add2

class Solution {

public:

    vector<string> findStrobogrammatic(int n) {

        if(n <= 0) return {""};

        if(n==1) return {"0","1","8"};

        vector<vector<string>> dp(n+1);

        dp[1] = {"0","1","8"};

        dp[2] = {"11","69","88","96"};

        vector<string> add1 = {"0","1","8"};

        vector<string> add2 = {"00","11","69","88","96"};

        string num;

        for(int i = 3, j,k,h; i <= n; ++i)

        {

            if(i&1)//奇数,我们在i-1偶数的基础上每个数中间位置add1

            {

                for(j = 0; j < dp[i-1].size(); j++)

                {

                    num = dp[i-1][j];

                    h = num.size()/2;

                    for(k = 0; k < 3; k++)

                    {

                        dp[i].push_back(num.substr(0,h)+add1[k]+num.substr(h));

                    }

                }

            }

            else//i是偶数，我们在i-2偶数基础上每个数中间位置add2

            {

                for(j = 0; j < dp[i-2].size(); j++)

                {

                    num = dp[i-2][j];

                    h = num.size()/2;

                    for(k = 0; k < 5; k++)

                    {

                        dp[i].push_back(num.substr(0,h)+add2[k]+num.substr(h));

                    }

                }

            }

        }

        return dp[n];

    }

};

巴特西

中心对称数 II

中心对称数 II

1.题目描述

2.解题思路

最新文章

热门文章