[Locked] Strobogrammatic Number & Strobogrammatic Number II & Strobogrammatic Number III

Strobogrammatic Number

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Write a function to determine if a number is strobogrammatic. The number is represented as a string.

For example, the numbers "69", "88", and "818" are all strobogrammatic.

分析：

　　找出中心对称的阿拉伯数字串，解释型题目，其中0，1，8本身是中心对称的，69互相中心对称

代码：

bool isStrobogrammatic(string num) {

    int i = , j = int(num.length()) - ;

    while(i < j) {

        if((num[i] == '' && num[j] == '') || (num[i] == '' && num[j] == '') || (num[i] == num[j] && (num[i] == '' || num[i] == '' || num[i] == ''))) {

            i++;

            j--;

        }

        else

            return false;

    }

    //如果i大于j，则为偶数串，直接return true；i等与j，则判断num[i]本身是否是中心对称

    return i > j ? true : (num[i] == '' || num[i] == '' || num[i] == '');

}

Strobogrammatic Number II

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"].

分析：

　　跟I类似，主要问题还是在与代码解释，由于要列出所有可能的答案，递归的复杂度是至少的，所以就用递归吧，DFS, BFS都行

代码：

void dfs(vector<string> &result, string str, int i, int j) {

    if(i == -) {

        result.push_back(str);

        return;

    }

    if(i == j) {

        i--;

        j++;

        dfs(result, str + '', i, j);

        dfs(result, str + '', i, j);

        dfs(result, str + '', i, j);

    }

    else {

        i--;

        j++;

        if(i != -)

            dfs(result, '' + str + '', i, j);

        dfs(result, '' + str + '', i, j);

        dfs(result, '' + str + '', i, j);

        dfs(result, '' + str + '', i, j);

        dfs(result, '' + str + '', i, j);

    }

    return;

}

vector<string> findCertainStrobogrammatic(int num) {

    vector<string> result;

    dfs(result, "", (num - )/, num/);

    return result;

}

Strobogrammatic Number III

The idea is similar to Strobogrammatic Number II: generate all those in-range strobogrammatic numbers and count.

分析：

　　与两个边界中任何一个等长的字符串要进行逐个验证满足要求。最初的想法为了减少时间复杂度，长度n(n > 1)介于两者之间的直接用个数函数计算：n为偶数时，count(n) = 4 * 5^(n/2 -1)；n为奇数时，count(n) = 12 * 5^(n/2 - 1)。但问题在于，n足够大时，O(n * 5^n)与O(5^n)基本没差别，所以如果采用逐个验证的方法，也就不必在乎小于n时的计算量了。

巴特西

[Locked] Strobogrammatic Number & Strobogrammatic Number II & Strobogrammatic Number III

最新文章

热门文章