[LeetCode] 248. Strobogrammatic Number III

yzd 发布于2019-08-16 13:50 / 3096人阅读

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 of low <= num <= high.

Example:

Input: low = "50", high = "100"
Output: 3
Explanation: 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.

Solution

class Solution {
    int count = 0;
    public int strobogrammaticInRange(String low, String high) {
        Map map = new HashMap<>();
        map.put("0", "0");
        map.put("1", "1");
        map.put("6", "9");
        map.put("8", "8");
        map.put("9", "6");
        List res = new ArrayList<>();
        for (int len = low.length(); len <= high.length(); len++) {
            dfs(map, low, high, new char[len], 0, len-1, res);
        }
        System.out.println(res);
        return count;
        
    }
    
    private void dfs(Map map, String low, String high, char[] buffer, int left, int right, List res) {
        if (left > right) {
            String num = new String(buffer);
            if ((num.length() == low.length() && num.compareTo(low) < 0) ||
               (num.length() == high.length() && num.compareTo(high) > 0)) {
                return;
            }
            count++;
            res.add(num);
            return;
        }
        
        for (char ch: map.keySet()) {
            if (buffer.length != 1 && left == 0 && ch == "0") continue;
            if (left == right && ch != map.get(ch)) continue;
            buffer[left] = ch;
            buffer[right] = map.get(ch);
            dfs(map, low, high, buffer, left+1, right-1, res);
        }
    }
}

海外云主机私有云 Strobogrammatic III LeetCode ucos-iii 消息队列

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

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

246. 247. 248. Strobogrammatic Number I II II

摘要：题目解答题目解答先考虑最底层的两种情况，当和当的时候，就是最中间的数为空还是存在唯一的一个数。然后我们在这个基础上，用循环两个数两个数地一起向外扩张。扩张后的结果存在里，作为再服务于上一层的扩张，得到最终结果。 246.Strobogrammatic NumberI题目：A strobogrammatic number is a number that looks the same w...

Fundebug 2019-08-14 16:31 评论0 收藏0
[Leetcode] Strobogrammatic Number 对称数

摘要：比如，先判断和是有映射的，然后和自己又是映射，所以是对称数。这样每次从中间插入两个对称的字符，之前插入的就被挤到两边去了。只插入一个字符时不能插入和插入字符和它的对应字符 Strobogrammatic Number I A strobogrammatic number is a number that looks the same when rotated 180 degrees ...

wendux 2019-08-14 12:34 评论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 2019-08-19 11:14 评论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 2019-08-16 13:50 评论0 收藏0
247. Strobogrammatic Number II

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

cnTomato 2019-08-14 17:29 评论0 收藏0