ITKeyword,专注技术干货聚合推荐

注册 | 登录

[leetcode] 248. Strobogrammatic Number III 解题报告

qq508618087 分享于 2016-06-21

推荐:[LeetCode] Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements

2019阿里云全部产品优惠券(新购或升级都可以使用,强烈推荐)
领取地址https://promotion.aliyun.com/ntms/yunparter/invite.html

题目链接: https://leetcode.com/problems/strobogrammatic-number-iii/

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

Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.

For example,
Given low = "50", high = "100", return 3. Because 69, 88, and 96 are three strobogrammatic numbers.

推荐:[leetcode] 305. Number of Islands II 解题报告

题目链接: https://leetcode.com/problems/number-of-islands-ii/ A 2d grid map of m rows and n columns is initially filled with water. We may perform an 

Note:
Because the range might be a large number, the low and high numbers are represented as string.


思路: 和之前的II一样, 在上一题中让求固定长度的答案, 而这题给了一个范围, 这个范围可能包含了几个长度, 所以只要枚举一样不同长度的答案并且在最后的时候判断一下是否在给定的范围内即可. 需要注意的是可能会整型溢出, 所以在判断答案范围的时候要用long类型.

代码如下:

class Solution {
public:
    void DFS(string& low, string& high, int n, string str)
    {
        if(n==0 && stol(str)>=stol(low) && stol(str)<=stol(high)) {Max++; return;}
        if(n%2==1) for(auto val: same) DFS(low, high, n-1, val);
        if(n==0 || n%2==1) return;
        for(int i = (n==2?1:0); i< two.size(); i++)
            DFS(low, high, n-2, two[i].first+str+two[i].second);
    }
    
    int strobogrammaticInRange(string low, string high) {
        int n1 = low.size(), n2 = high.size();
        for(int i = n1; i <= n2; i++) DFS(low, high, i, "");
        return Max;
    }
private:
    int Max = 0;
    vector<string> same{"0", "1", "8"};
    vector<pair<char,char>> two{{'0','0'},{'1','1'},{'6','9'},{'8','8'},{'9','6'}};
};


推荐:[leetcode] 321. Create Maximum Number 解题报告

题目链接: https://leetcode.com/problems/create-maximum-number/ Given two arrays of length m and n with digits 0-9 representing two numbers. Create the

题目链接: https://leetcode.com/problems/strobogrammatic-number-iii/ A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Write

相关阅读排行


用户评论

游客

相关内容推荐

最新文章

×

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品,请激活账号。

您的注册邮箱: 修改

重新发送激活邮件 进入我的邮箱

如果您没有收到激活邮件,请注意检查垃圾箱。