资讯专栏INFORMATION COLUMN

246. 247. 248. Strobogrammatic Number I II II

Fundebug / 1150人阅读

摘要:题目解答题目解答先考虑最底层的两种情况,当和当的时候,就是最中间的数为空还是存在唯一的一个数。然后我们在这个基础上,用循环两个数两个数地一起向外扩张。扩张后的结果存在里,作为再服务于上一层的扩张,得到最终结果。

246.Strobogrammatic NumberI
题目:
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.

解答:

public class Solution {
    //1, 6, 8, 9, 0
    public boolean isStrobogrammatic(String num) {
        Map map = new HashMap<>();
        map.put(1, 1); map.put(6, 9); map.put(8, 8); map.put(9, 6); map.put(0, 0);
        
        int len = num.length();
        for (int i = 0; i < len; i++) {
            int c1 = num.charAt(i) - "0", c2 = num.charAt(len - 1 - i) - "0";
            if (!map.containsKey(c1) || !map.containsKey(c2) || c1 != map.get(c2)) {
                return false;
            }
        }
        return true;
    }
}

247.StroboGrammatic NumberII
题目:
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"].

解答:
先考虑最底层的两种情况,当n == 0和当n == 1的时候,就是最中间的数为空还是存在唯一的一个数。然后我们在这个基础上,用循环两个数两个数地一起向外扩张。扩张后的结果存在result里,作为base再服务于上一层的扩张,得到最终结果。

public class Solution {
    public List helper(int n, int m) {
        if (n == 0) return new ArrayList(Arrays.asList(""));
        if (n == 1) return new ArrayList(Arrays.asList("0", "1", "8"));
        
        List list = helper(n - 2, m);
        List result = new ArrayList();
        for (int i = 0; i < list.size(); i++) {
            String s = list.get(i);
            
            if (n != m) result.add("0" + s + "0");
            result.add("1" + s + "1");
            result.add("8" + s + "8");
            result.add("6" + s + "9");
            result.add("9" + s + "6");
        }
        
        return result;
    }
    
    public List findStrobogrammatic(int n) {
        return helper(n, n);
    }
}

248.Strobogrammatic NumberIII
题目:
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.

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

解答:
有了上一题作基础,这里我们可以先求出所有长度满足的数,再通过与low,high的compare比较,选出最终的结果并count。

public class Solution {
    public List helper(int n, int max) {
        if (n == 0) return new ArrayList(Arrays.asList(""));
        if (n == 1) return new ArrayList(Arrays.asList("1", "8", "0"));
        
        List list = helper(n - 2, max);
        List result = new ArrayList();
        for (int i = 0; i < list.size(); i++) {
            String s = list.get(i);
            if (n != max) result.add("0" + s + "0");
            result.add("1" + s + "1");
            result.add("8" + s + "8");
            result.add("6" + s + "9");
            result.add("9" + s + "6");
        }
        return result;
    }
    
    public int strobogrammaticInRange(String low, String high) {
        int count = 0;
        List result = new ArrayList();
        for (int i = low.length(); i <= high.length(); i++) {
            result.addAll(helper(i, i));
        }
        for (String str : result) {
            if (str.length() == low.length() && str.compareTo(low) < 0 || str.length() == high.length() && str.compareTo(high) > 0) continue;
            count++;
        }
        return count;
    }
}

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/66216.html

相关文章

  • 247. Strobogrammatic Number II

    摘要:题目链接这题和都可以做,一种思路就是从中间开始往两边延伸,每次有种可能性和,其中开头处不能是。可以加或者用优化。 247. Strobogrammatic Number II 题目链接:https://leetcode.com/problems... 这题recursion和iteration都可以做,一种思路就是从中间开始往两边延伸,每次c[i-k], c[i+k]有5种可能性: (...

    cnTomato 评论0 收藏0
  • [LeetCode] 247. Strobogrammatic Number II

    Problem 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. Example: Input: n = 2Output...

    GHOST_349178 评论0 收藏0
  • [LeetCode] 246. Strobogrammatic Number

    Problem 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 represent...

    whatsns 评论0 收藏0
  • [LeetCode] 248. Strobogrammatic Number III

    Problem 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 o...

    yzd 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<