[Leetcode] Strobogrammatic Number 對稱數

wendux 發布于2019-08-14 12:34 / 3416人閱讀

摘要：比如，先判斷和是有映射的，然后和自己又是映射，所以是對稱數。這樣每次從中間插入兩個對稱的字符，之前插入的就被擠到兩邊去了。只插入一個字符時不能插入和插入字符和它的對應字符

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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