247. Strobogrammatic Number II (Medium)

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Find all strobogrammatic numbers that are of length = n.

For example,

Given n = 2, return ["11","69","88","96"].

Hint:

  1. Try to use recursion and notice that it should recurse with n - 2 instead of n - 1.

Solution 1: Recursion 23ms

class Solution {
public:
    vector<string> findStrobogrammatic(int n) {
        return dfs(n,n);
    }

    vector<string> dfs(int n, int size) {
        if (n == 0) return {""};
        if (n == 1) return {"0","1","8"};
        vector<string> res;
        for (auto& a: dfs(n-2,size)) {
            if (n < size) res.push_back('0'+a+'0');
            res.push_back('1'+a+'1');
            res.push_back('8'+a+'8');
            res.push_back('6'+a+'9');
            res.push_back('9'+a+'6');
        }
        return res;
    }
};

Solution 2: Iterative 32ms

这道题还有迭代的解法,感觉也相当的巧妙,需要从奇偶来考虑,奇数赋为0,1,8,偶数赋为空,如果是奇数,就从i=3开始搭建,因为计算i=3需要i=1,而我们已经初始化了i=1的情况,如果是偶数,我们从i=2开始搭建,我们也已经初始化了i=0的情况,所以我们可以用for循环来搭建到i=n的情况,思路和递归一样,写法不同而已,参见代码如下:

vector<string> findStrobogrammatic(int n) {
    vector<string> one{"0","1","8"}, zero{""}, res = zero;
    if (n%2) res = one;
    // i start from 3(1) or 2(0)
    for (int i = (n%2)+2; i <= n; i+=2) {
        vector<string> t;
        for (auto a: res) {
            if (i < n) t.push_back('0'+a+'0');
            t.push_back('1'+a+'1');
            t.push_back('8'+a+'8');
            t.push_back('6'+a+'9');
            t.push_back('9'+a+'6');
        }
        res = t;
    }
    return res;
}

results matching ""

    No results matching ""