[Leetcode] Strobogrammatic Number 对称数

wendux 发布于2019-08-14 12:34 / 3412人阅读

摘要：比如，先判断和是有映射的，然后和自己又是映射，所以是对称数。这样每次从中间插入两个对称的字符，之前插入的就被挤到两边去了。只插入一个字符时不能插入和插入字符和它的对应字符

Strobogrammatic Number I

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.

双指针法 复杂度

时间 O(N) 空间 O(1)

思路

翻转后对称的数就那么几个，我们可以根据这个建立一个映射关系：8->8, 0->0, 1->1, 6->9, 9->6，然后从两边向中间检查对应位置的两个字母是否有映射关系就行了。比如619，先判断6和9是有映射的，然后1和自己又是映射，所以是对称数。

注意

while循环的条件是left<=right

代码

public class Solution {
    public boolean isStrobogrammatic(String num) {
        HashMap map = new HashMap();
        map.put("1","1");
        map.put("0","0");
        map.put("6","9");
        map.put("9","6");
        map.put("8","8");
        int left = 0, right = num.length() - 1;
        while(left <= right){
            // 如果字母不存在映射或映射不对，则返回假
            if(!map.containsKey(num.charAt(right)) || num.charAt(left) != map.get(num.charAt(right))){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

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

中间插入法 复杂度

时间 O(N) 空间 O(1)

思路

找出所有的可能，必然是深度优先搜索。但是每轮搜索如何建立临时的字符串呢？因为数是“对称”的，我们插入一个字母就知道对应位置的另一个字母是什么，所以我们可以从中间插入来建立这个临时的字符串。这样每次从中间插入两个“对称”的字符，之前插入的就被挤到两边去了。这里有几个边界条件要考虑：

如果是第一个字符，即临时字符串为空时进行插入时，不能插入"0"，因为没有0开头的数字

如果n=1的话，第一个字符则可以是"0"

如果只剩下一个带插入的字符，这时候不能插入"6"或"9"，因为他们不能和自己产生映射，翻转后就不是自己了

这样，当深度优先搜索时遇到这些情况，则要相应的跳过

注意

为了实现从中间插入，我们用StringBuilder在length/2的位置insert就行了

代码

public class Solution {
    
    char[] table = {"0", "1", "8", "6", "9"};
    List res;
    
    public List findStrobogrammatic(int n) {
        res = new ArrayList();
        build(n, "");
        return res;
    }
    
    public void build(int n, String tmp){
        if(n == tmp.length()){
            res.add(tmp);
            return;
        }
        boolean last = n - tmp.length() == 1;
        for(int i = 0; i < table.length; i++){
            char c = table[i];
            // 第一个字符不能为"0"，但n=1除外。只插入一个字符时不能插入"6"和"9"
            if((n != 1 && tmp.length() == 0 && c == "0") || (last && (c == "6" || c == "9"))){
                continue;
            }
            StringBuilder newTmp = new StringBuilder(tmp);
            // 插入字符c和它的对应字符
            append(last, c, newTmp);
            build(n, newTmp.toString());
        }
    }
    
    public void append(boolean last, char c, StringBuilder sb){
        if(c == "6"){
            sb.insert(sb.length()/2, "69");
        } else if(c == "9"){
            sb.insert(sb.length()/2, "96");
        } else {
            sb.insert(sb.length()/2, last ? c : ""+c+c);
        }
    }
}

云服务器 GPU云服务器 Strobogrammatic LeetCode LeetCode_String leetcode_35_SearchIn

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

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

[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
[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 2019-08-16 13:50 评论0 收藏0
Strobogrammatic Number 系列 LC解题记录（未完成）

摘要：所以这题先建立一个对应的，然后扫一遍字符串就可以了。复杂度分析第二题题目内容解决思路一看关键词，通常都是，深搜一遍，挖地三尺，雁过拔毛。复杂度分析第三题题目内容解决思路复杂度分析该系列共三道题，Company Tag只有一个Google，那就必须要做了。第一题题目内容 A strobogrammatic number is a number that looks the same ...

王晗 2019-08-14 14:23 评论0 收藏0
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