這是悅樂(lè)書的第316次更新争群，第337篇原創(chuàng)
01 看題和準(zhǔn)備
今天介紹的是LeetCode算法題中Easy級(jí)別的第185題（順位題號(hào)是788）摧茴。如果一個(gè)數(shù)字經(jīng)過(guò)180度旋轉(zhuǎn)后，變成了一個(gè)與原數(shù)字不同的數(shù)，這樣的數(shù)被稱為好數(shù)字鞭衩。數(shù)字中的每一位都必須經(jīng)過(guò)旋轉(zhuǎn)。旋轉(zhuǎn)的規(guī)則是：0,1,8這三個(gè)數(shù)旋轉(zhuǎn)后還是自身娃善，2旋轉(zhuǎn)后變?yōu)?论衍，5旋轉(zhuǎn)后變?yōu)?,6旋轉(zhuǎn)后變?yōu)?，9旋轉(zhuǎn)后變?yōu)?聚磺，剩下的3坯台，4，7旋轉(zhuǎn)后并不能轉(zhuǎn)成其他數(shù)字瘫寝，是無(wú)效的⊙牙伲現(xiàn)在給出正數(shù)N，從1到N的好數(shù)字一共有多少個(gè)焕阿？例如：
輸入：10
輸出：4
說(shuō)明：在[1,10]范圍內(nèi)有四個(gè)好的數(shù)字：2,5,6,9咪啡。請(qǐng)注意，1和10不是好數(shù)字暮屡，因?yàn)樗鼈冊(cè)谛D(zhuǎn)后保持不變撤摸。
?注意：N將在[1,10000]范圍內(nèi)。
本次解題使用的開(kāi)發(fā)工具是eclipse，jdk使用的版本是1.8愁溜，環(huán)境是win7 64位系統(tǒng)疾嗅，使用Java語(yǔ)言編寫和測(cè)試。
02 第一種解法
題目的意思很明確冕象，根據(jù)旋轉(zhuǎn)規(guī)則來(lái)判斷數(shù)字中的每一位數(shù)即可代承。將正整數(shù)轉(zhuǎn)為字符數(shù)組，然后判斷每一個(gè)字符是否符合要求渐扮。我們借助一個(gè)布爾類型的標(biāo)志來(lái)判斷论悴，整個(gè)數(shù)字是否符合要求，對(duì)于3墓律、4膀估、7三個(gè)數(shù)，因?yàn)槭菬o(wú)效數(shù)字耻讽，可以直接將標(biāo)志改為false察纯，并且終止循環(huán)判斷，進(jìn)入下一個(gè)數(shù)针肥。對(duì)于2饼记、5、6慰枕、9四個(gè)數(shù)具则，是有效數(shù)字，可以轉(zhuǎn)換成其他的數(shù)具帮，碰到其中任意一個(gè)博肋，都將標(biāo)志改為true。剩下的0蜂厅、1匪凡、8因?yàn)檗D(zhuǎn)換后還是自身，雖然也是有效數(shù)字葛峻，但是可以直接忽略锹雏。
public int rotatedDigits(int N) {
int count = 0;
for (int i=0; i<= N; i++) {
String s = i+"";
boolean flag = false;
for (char ch : s.toCharArray()) {
if (ch == '3' || ch == '4' || ch == '7') {
flag = false;
break;
}
if (ch == '2' || ch == '5' || ch == '6' || ch == '9') {
flag = true;
}
}
if (flag) {
count++;
}
}
return count;
}
03 第二種解法
因?yàn)榕袛嗍前凑諒男〉酱蟮捻樞蜻M(jìn)行的，所以可以先將前面部分的判斷結(jié)果存起來(lái)术奖，在遇到更大的數(shù)時(shí)礁遵，可以節(jié)省判斷步驟。
使用一個(gè)數(shù)組采记，長(zhǎng)度為N+1佣耐，初始元素值都為0，現(xiàn)在定義數(shù)組元素三種值類型：為0時(shí)唧龄，表示無(wú)效數(shù)字兼砖；為1時(shí)，表示有效數(shù)字，但是轉(zhuǎn)換后不變讽挟；為2時(shí)懒叛，表示有效數(shù)字，且轉(zhuǎn)換后變成了新數(shù)字耽梅。
在N小于10的時(shí)候薛窥，根據(jù)旋轉(zhuǎn)規(guī)則，直接將部分元素的值給定眼姐；當(dāng)N大于10的時(shí)候诅迷，只需要判斷兩部分即可，一是個(gè)位數(shù)之前的數(shù)众旗，二是個(gè)位數(shù)罢杉。比如：當(dāng)判斷11的時(shí)候，先判斷十位數(shù)1贡歧，再判斷個(gè)位數(shù)1滩租，因?yàn)檫€是自身，所以dp[11]=1艘款；當(dāng)判斷112的時(shí)候持际，112除以10等于11，而dp[11]=1哗咆，再判斷個(gè)位數(shù)2，dp[2]=2益眉，2會(huì)轉(zhuǎn)成5晌柬，因此旋轉(zhuǎn)后變成115，符合要求是個(gè)好數(shù)郭脂，因此dp[112]=2年碘。以此類推，再112的基礎(chǔ)上再增加一位時(shí)展鸡，就只需要判斷112和增加的個(gè)位數(shù)了屿衅，而不必像第一種解法那樣，整數(shù)上的每一位都要判斷一遍莹弊。
public int rotatedDigits2(int N) {
int count = 0;
int[] dp = new int[N+1];
for (int i=0; i<= N; i++) {
if (i < 10) {
if (i == 0 || i == 1 || i == 8) {
dp[i] = 1;
} else if (i == 2 || i == 5 || i == 6 || i == 9) {
dp[i] = 2;
count++;
}
} else {
// 判斷前面的幾位數(shù)和個(gè)位數(shù)
int a = dp[i/10], b = dp[i%10];
if (a == 1 && b == 1) {
dp[i] = 1;
} else if (a >= 1 && b >= 1) {
dp[i] = 2;
count++;
}
}
}
return count;
}
04 小結(jié)
算法專題目前已日更超過(guò)五個(gè)月涤久，算法題文章185+篇，公眾號(hào)對(duì)話框回復(fù)【數(shù)據(jù)結(jié)構(gòu)與算法】忍弛、【算法】响迂、【數(shù)據(jù)結(jié)構(gòu)】中的任一關(guān)鍵詞，獲取系列文章合集细疚。
以上就是全部?jī)?nèi)容蔗彤，如果大家有什么好的解法思路、建議或者其他問(wèn)題，可以下方留言交流然遏，點(diǎn)贊贫途、留言、轉(zhuǎn)發(fā)就是對(duì)我最大的回報(bào)和支持待侵！
