Strobogrammatic Number III

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

Return the number of all strobogrammatic numbers that are of length from 1 to n.

For example, Given n = 2, return 7, because ["0", "1", "8", "11","69","88","96"].

Thoughts

排列问题. 对于长度为n的, 如果是偶数, 那么左半边可以为[0, 1, 8, 6, 9]四个数的任意组合, 但0不能排在左半边的最外面的, 因此除最外层有5 ^ (n / 2 - 1) 排列方式, 再乘以除0外剩余4个. 奇数的话在此基础上*3, 因为能取[0 , 1, 8].

Code

int res = 1;
        for (int i = 1; i <= n; i++) {
            int tmp = 4 * Math.pow(5, n / 2 - 1);
            if (n % 2 == 1) {
                tmp *= 3;
            }
            res += tmp;
        }
        return res;

Analysis

时间复杂度O(N).