[Leetcode] Strobogrammatic Number 對稱數(shù)

wendux 發(fā)布于2019-08-14 12:34 / 3407人閱讀

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

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.

雙指針法 復(fù)雜度

時間 O(N) 空間 O(1)

思路

翻轉(zhuǎn)后對稱的數(shù)就那么幾個，我們可以根據(jù)這個建立一個映射關(guān)系：8->8, 0->0, 1->1, 6->9, 9->6，然后從兩邊向中間檢查對應(yīng)位置的兩個字母是否有映射關(guān)系就行了。比如619，先判斷6和9是有映射的，然后1和自己又是映射，所以是對稱數(shù)。

注意

while循環(huán)的條件是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"].

中間插入法 復(fù)雜度

時間 O(N) 空間 O(1)

思路

找出所有的可能，必然是深度優(yōu)先搜索。但是每輪搜索如何建立臨時的字符串呢？因為數(shù)是“對稱”的，我們插入一個字母就知道對應(yīng)位置的另一個字母是什么，所以我們可以從中間插入來建立這個臨時的字符串。這樣每次從中間插入兩個“對稱”的字符，之前插入的就被擠到兩邊去了。這里有幾個邊界條件要考慮：

如果是第一個字符，即臨時字符串為空時進行插入時，不能插入"0"，因為沒有0開頭的數(shù)字

如果n=1的話，第一個字符則可以是"0"

如果只剩下一個帶插入的字符，這時候不能插入"6"或"9"，因為他們不能和自己產(chǎn)生映射，翻轉(zhuǎn)后就不是自己了

這樣，當(dāng)深度優(yōu)先搜索時遇到這些情況，則要相應(yīng)的跳過

注意

為了實現(xiàn)從中間插入，我們用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和它的對應(yīng)字符
            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);
        }
    }
}