對稱數II

對稱數是一個旋轉180度後(倒過來)看起來與原數相同的數.找到所有長度為 n 的對稱數.

樣例：

給出 n = 2 傳回 [“11”,”69”,”88”,”96”].

思路：

利用遞歸求解，給出n=1時，結果為{0,1,8}，

n=2時，結果為{11,69,88,96}

計算n時，就先計算n-2（此時的n-2包括以0開頭的字元串）

再将n=2的結果，分别加到n-2結果的兩邊。

#ifndef C776_H
#define C776_H
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
    /**
    * @param n: the length of strobogrammatic number
    * @return: All strobogrammatic numbers
    */
    vector<string> findStrobogrammatic(int n) {
        // write your code here
        vector<string> res;
        if (n <= )
            return{""};
        res = helper(n);
        if (n == )
            return res;
        //去除其中以0開頭的字元串
        sort(res.begin(), res.end());
        int pos = ;
        for (int i = ; i < res.size(); ++i)
        {
            if (res[i][] != '0')
            {
                pos = i;
                break; 
            }
        }
        if (pos != )
            res.erase(res.begin(), res.begin() + pos);
        return res;
    }
    //遞歸求解
    vector<string> helper(int n)
    {
        if (n == )
            return{ "0", "1", "8" };
        else if (n == )
            return{ "00","11", "69", "88", "96" };
        vector<string> res = helper(n - );
        vector<string> tmp = helper();
        vector<string> vec;
        //n的結果就等同于将n=2的每個結果加到n-2每個結果的兩邊
        for (auto c : res)
        {
            for (auto t : tmp)
                vec.push_back(t[] + c + t[]);
        }
        return vec;
    }
};
#endif