資訊專(zhuān)欄INFORMATION COLUMN
摘要：比如，先判斷和是有映射的，然后和自己又是映射，所以是對(duì)稱(chēng)數(shù)。這樣每次從中間插入兩個(gè)對(duì)稱(chēng)的字符，之前插入的就被擠到兩邊去了。只插入一個(gè)字符時(shí)不能插入和插入字符和它的對(duì)應(yīng)字符
Strobogrammatic Number I
雙指針?lè)?/b> 復(fù)雜度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.
時(shí)間 O(N) 空間 O(1)
思路翻轉(zhuǎn)后對(duì)稱(chēng)的數(shù)就那么幾個(gè)，我們可以根據(jù)這個(gè)建立一個(gè)映射關(guān)系：8->8, 0->0, 1->1, 6->9, 9->6，然后從兩邊向中間檢查對(duì)應(yīng)位置的兩個(gè)字母是否有映射關(guān)系就行了。比如619，先判斷6和9是有映射的，然后1和自己又是映射，所以是對(duì)稱(chēng)數(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){
// 如果字母不存在映射或映射不對(duì)，則返回假
if(!map.containsKey(num.charAt(right)) || num.charAt(left) != map.get(num.charAt(right))){
return false;
}
left++;
right--;
}
return true;
}
}
Strobogrammatic Number II
中間插入法 復(fù)雜度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"].
時(shí)間 O(N) 空間 O(1)
思路找出所有的可能，必然是深度優(yōu)先搜索。但是每輪搜索如何建立臨時(shí)的字符串呢？因?yàn)閿?shù)是“對(duì)稱(chēng)”的，我們插入一個(gè)字母就知道對(duì)應(yīng)位置的另一個(gè)字母是什么，所以我們可以從中間插入來(lái)建立這個(gè)臨時(shí)的字符串。這樣每次從中間插入兩個(gè)“對(duì)稱(chēng)”的字符，之前插入的就被擠到兩邊去了。這里有幾個(gè)邊界條件要考慮：
如果是第一個(gè)字符，即臨時(shí)字符串為空時(shí)進(jìn)行插入時(shí)，不能插入"0"，因?yàn)闆](méi)有0開(kāi)頭的數(shù)字
如果n=1的話(huà)，第一個(gè)字符則可以是"0"
如果只剩下一個(gè)帶插入的字符，這時(shí)候不能插入"6"或"9"，因?yàn)樗麄儾荒芎妥约寒a(chǎn)生映射，翻轉(zhuǎn)后就不是自己了
這樣，當(dāng)深度優(yōu)先搜索時(shí)遇到這些情況，則要相應(yīng)的跳過(guò)
注意為了實(shí)現(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];
// 第一個(gè)字符不能為"0"，但n=1除外。只插入一個(gè)字符時(shí)不能插入"6"和"9"
if((n != 1 && tmp.length() == 0 && c == "0") || (last && (c == "6" || c == "9"))){
continue;
}
StringBuilder newTmp = new StringBuilder(tmp);
// 插入字符c和它的對(duì)應(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);
}
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/64565.html
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...
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...
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...
摘要：所以這題先建立一個(gè)對(duì)應(yīng)的，然后掃一遍字符串就可以了。復(fù)雜度分析第二題題目?jī)?nèi)容解決思路一看關(guān)鍵詞，通常都是，深搜一遍，挖地三尺，雁過(guò)拔毛。復(fù)雜度分析第三題題目?jī)?nèi)容解決思路復(fù)雜度分析 該系列共三道題，Company Tag只有一個(gè)Google，那就必須要做了。 第一題題目?jī)?nèi)容 A strobogrammatic number is a number that looks the same ...
摘要：題目解答題目解答先考慮最底層的兩種情況，當(dāng)和當(dāng)?shù)臅r(shí)候，就是最中間的數(shù)為空還是存在唯一的一個(gè)數(shù)。然后我們?cè)谶@個(gè)基礎(chǔ)上，用循環(huán)兩個(gè)數(shù)兩個(gè)數(shù)地一起向外擴(kuò)張。擴(kuò)張后的結(jié)果存在里，作為再服務(wù)于上一層的擴(kuò)張，得到最終結(jié)果。 246.Strobogrammatic NumberI題目：A strobogrammatic number is a number that looks the same w...
閱讀 1287·2021-11-22 12:05
閱讀 1415·2021-09-29 09:35
閱讀 701·2019-08-30 15:55
閱讀 3199·2019-08-30 14:12
閱讀 1017·2019-08-30 14:11
閱讀 2939·2019-08-30 13:10
閱讀 2481·2019-08-29 16:33
閱讀 3392·2019-08-29 11:02
