呃呃呃，一個(gè)愉快的周末過去了枉层，接下來又是愉快的周一泉褐。刷題繼續(xù)。
我這里再解釋一下：任何解題的思路和方法都是多種多樣的鸟蜡！我的習(xí)慣就是一種是自己想出來的膜赃，可能很墨跡，很累贅揉忘，性能又不好跳座！但是完全是自己想的，所以我這里也會(huì)貼出來泣矛，而且附上完整的想法思路啥的疲眷。然后我一般還會(huì)貼一種大神的解法，這個(gè)其實(shí)我是在重多題解中選擇我認(rèn)為比較好的一種來分析您朽，學(xué)習(xí)并分享出狂丝。有的方法可能我沒寫，但是也是對的哗总，然后這個(gè)解析也是我認(rèn)為思路好或者簡潔性能優(yōu)的几颜，不一定就是最好的 ，別杠我讯屈！
回文數(shù)
題目：判斷一個(gè)整數(shù)是否是回文數(shù)蛋哭。回文數(shù)是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數(shù)涮母。
示例 1:
輸入: 121
輸出: true
示例 2:
輸入: -121
輸出: false
解釋: 從左向右讀, 為 -121 谆趾。 從右向左讀, 為 121- 。因此它不是一個(gè)回文數(shù)叛本。
示例 3:
輸入: 10
輸出: false
解釋: 從右向左讀, 為 01 棺妓。因此它不是一個(gè)回文數(shù)。
進(jìn)階:
你能不將整數(shù)轉(zhuǎn)為字符串來解決這個(gè)問題嗎炮赦？
看到這個(gè)題大笑三聲怜跑，秒有思路。感覺LeetCode上的題挺有意思的吠勘，不太相信是故意的性芬，只能說巧的很，上一道題才看了整數(shù)反轉(zhuǎn)剧防，結(jié)果做這個(gè)題怕不是手到擒來呦~植锉！然后因?yàn)楹芎唵嗡灾苯由洗a了：
public boolean isPalindrome(int x) {
//首先我這是做了整數(shù)反轉(zhuǎn)后再做這個(gè)題的。
//整數(shù)分三類峭拘，正整數(shù)俊庇，負(fù)整數(shù)狮暑，0、0天然就是回文數(shù)辉饱，正整數(shù)有可能是回文數(shù)搬男，負(fù)整數(shù)肯定不是回文數(shù)
if(x<0){
return false;
}
if(x==0){
return true;
}
//思路是將這個(gè)數(shù)反轉(zhuǎn)，如果等于原數(shù)則是回文數(shù)
if(x>0){
long result = 0l;
//因?yàn)橄旅娌僮骱髕會(huì)改變彭沼，所以提前保存x的值缔逛，并且為了方便比較，直接設(shè)定為long型姓惑，不要吐槽我命名
long xx = x;
while(x!=0){
result = result*10+x%10;
x=x/10;
}
//原數(shù)是int褐奴。如果反轉(zhuǎn)后溢出了則肯定是不是回文數(shù)
if(result>Integer.MAX_VALUE||result<Integer.MIN_VALUE){
return false;
}
if(result==xx){
return true;
}else{
return false;
}
}
return false;
}
嗯，學(xué)到既得到于毙，感謝上一個(gè)整數(shù)反轉(zhuǎn)的題目敦冬。
羅馬數(shù)字轉(zhuǎn)整數(shù)
羅馬數(shù)字包含以下七種字符: I， V唯沮， X匪补， L，C烂翰，D 和 M。
字符 數(shù)值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如蚤氏， 羅馬數(shù)字 2 寫做 II 甘耿，即為兩個(gè)并列的 1。12 寫做 XII 竿滨，即為 X + II 佳恬。 27 寫做 XXVII, 即為 XX + V + II 。
通常情況下于游，羅馬數(shù)字中小的數(shù)字在大的數(shù)字的右邊毁葱。但也存在特例，例如 4 不寫做 IIII贰剥，而是 IV倾剿。數(shù)字 1 在數(shù)字 5 的左邊，所表示的數(shù)等于大數(shù) 5 減小數(shù) 1 得到的數(shù)值 4 蚌成。同樣地前痘，數(shù)字 9 表示為 IX。這個(gè)特殊的規(guī)則只適用于以下六種情況：
I 可以放在 V (5) 和 X (10) 的左邊担忧，來表示 4 和 9芹缔。
X 可以放在 L (50) 和 C (100) 的左邊，來表示 40 和 90瓶盛。
C 可以放在 D (500) 和 M (1000) 的左邊最欠，來表示 400 和 900示罗。
給定一個(gè)羅馬數(shù)字，將其轉(zhuǎn)換成整數(shù)芝硬。輸入確保在 1 到 3999 的范圍內(nèi)蚜点。
示例 1:
輸入: "III"
輸出: 3
示例 2:
輸入: "IV"
輸出: 4
示例 3:
輸入: "IX"
輸出: 9
示例 4:
輸入: "LVIII"
輸出: 58
解釋: L = 50, V= 5, III = 3.
示例 5:
輸入: "MCMXCIV"
輸出: 1994
解釋: M = 1000, CM = 900, XC = 90, IV = 4.
思路：首先說一下這個(gè)題，仔細(xì)看題思路很簡單３橙 禽额！然后磕磕絆絆做了出來，實(shí)現(xiàn)是實(shí)現(xiàn)了皮官，但是肯定不是優(yōu)解８埂（這個(gè)就很無力了，然后我沒想到捺氢，但是猜都能猜到又是人家?guī)仔械拇a我寫了幾十行）
public int romanToInt(String s) {
int i = 0;
if(s.indexOf("IV")!=-1){
s = s.replace("IV", "");
i += 4;
}
if(s.indexOf("IX")!=-1){
s = s.replace("IX", "");
i += 9;
}
if(s.indexOf("XL")!=-1){
s = s.replace("XL", "");
i += 40;
}
if(s.indexOf("XC")!=-1){
s = s.replace("XC", "");
i += 90;
}
if(s.indexOf("CD")!=-1){
s = s.replace("CD", "");
i += 400;
}
if(s.indexOf("CM")!=-1){
s = s.replace("CM", "");
i += 900;
}
String[] arr = s.split("");
for(String str:arr){
if(str.equals("I")){
i += 1;
}
if(str.equals("V")){
i += 5;
}
if(str.equals("X")){
i += 10;
}
if(str.equals("L")){
i += 50;
}
if(str.equals("C")){
i += 100;
}
if(str.equals("D")){
i += 500;
}
if(str.equals("M")){
i += 1000;
}
}
return i;
}
接下來是看大佬的思路藻丢，怎么說呢，首先我這里的if摄乒，普遍都換成了switch悠反，其次我這里是真的很麻煩的處理，一個(gè)字符串來來回回遍歷好幾遍馍佑，而且最后又是if來回走斋否。而大佬的思路就簡單粗暴的多了，判斷每一個(gè)數(shù)字拭荤，前面的比后面的小則是減茵臭。并且我剛剛測試了，用char類型比用string類型的比較性能好6ms舅世，所以改完后完整版如下：
class Solution {
public int romanToInt(String s) {
int result = 0;
//因?yàn)槔锩嬉玫疆?dāng)前元素的后一個(gè)字符旦委，所以只能遍歷到倒數(shù)第二個(gè)元素。
for(int i=0;i<s.length()-1;i++){
//前一個(gè)數(shù)字大于后一個(gè)數(shù)字則是正常相加
if(getValue(s.charAt(i))>=getValue(s.charAt(i+1))){
result += getValue(s.charAt(i));
}else{
//前一個(gè)小于后一個(gè)則是減法
result -= getValue(s.charAt(i));
}
}
//最后一個(gè)元素一定是要相加的
result += getValue(s.charAt(s.length()-1));
return result;
}
public int getValue(char value){
int result = 0;
switch(value){
case 'I':
result = 1;
break;
case 'V':
result = 5;
break;
case 'X':
result = 10;
break;
case 'L':
result = 50;
break;
case 'C':
result = 100;
break;
case 'D':
result = 500;
break;
case 'M':
result = 1000;
break;
}
return result;
}
}
其實(shí)這個(gè)題目本身沒什么好說的雏亚，但是好多語法上的細(xì)節(jié)可以聊聊缨硝，我提交了很多遍，有的思路差不多罢低，但是一點(diǎn)不起眼的改動(dòng)就讓執(zhí)行速度和性能變了很多查辩。
之前這個(gè)for循環(huán)里的if-else我是用兩個(gè)if來判斷的，結(jié)果速度跑出來在百分之七十幾左右网持，然后我看人家大神代碼宜肉，方法差不多一樣，為什么人家百分之九十九呢翎碑？區(qū)別就在于我這個(gè)兩個(gè)if判斷谬返，人家一個(gè)fi-else選擇，然后我只改了這一塊日杈，再執(zhí)行少了兩秒遣铝，超過了百分之二十多的人佑刷。
其實(shí)是想不明白這樣if-else為什么性能好么？能想明白的酿炸，這樣相當(dāng)于一次只需要一次判斷瘫絮，而我那種寫法每次需要兩次判斷的，但是我為什么還那么寫填硕？沒注意麦萤，沒想到而已。其實(shí)真的一直喊著性能扁眯，時(shí)間復(fù)雜度壮莹，優(yōu)化之類的，但是又有多少落到實(shí)際上了呢姻檀？
很感謝這個(gè)LeetCode平臺(tái)命满，尤其是每次提交都會(huì)彈出那個(gè)執(zhí)行時(shí)間，消耗性能绣版，把一種很抽象的說法量化了起來胶台，也讓我認(rèn)識的更深。
最長公共前綴
題目：編寫一個(gè)函數(shù)來查找字符串?dāng)?shù)組中的最長公共前綴杂抽。如果不存在公共前綴诈唬，返回空字符串 ""。
示例 1:
輸入: ["flower","flow","flight"]
輸出: "fl"
示例 2:
輸入: ["dog","racecar","car"]
輸出: ""
解釋: 輸入不存在公共前綴缩麸。
說明:
所有輸入只包含小寫字母 a-z 铸磅。
思路：這個(gè)題注意審題吧，反正我是做笑了匙睹。然后開始分析思路：一個(gè)string數(shù)組，獲取公共前綴济竹，其實(shí)第一印象感覺應(yīng)該挺好做的痕檬，然后大體就是獲取每一個(gè)字符串的第一位比較，相同往下比較送浊，不相同直接返回梦谜。可是思路是有了袭景，實(shí)踐起來一步一個(gè)問題唁桩。首先空數(shù)組怎么辦？其次每個(gè)字符串長度不同耸棒，怎么獲取最短長度荒澡？最后一步才是雙循環(huán)挨個(gè)對比。我習(xí)慣于在代碼中注解寫的很墨跡与殃，所以沒思路的可以看看注解
public String longestCommonPrefix(String[] strs) {
int i = strs.length;
//如果這是一個(gè)空數(shù)組則直接返回空
if(i==0){
return "";
}
//獲取最短的那個(gè)字符串的長度
int j = strs[0].length();
for(String s:strs) {
if(j>s.length()) {
//如果長度比j短則替換j
j=s.length();
}
}
//結(jié)果集
String result = "";
//遍歷第一層单山，從字符串下表為0的字符開始比對
for(int k=0;k<j;k++) {
//第一個(gè)字符串的第一個(gè)字符碍现，作為參照物
char first = strs[0].charAt(k);
//因?yàn)榈谝粋€(gè)字符串已經(jīng)取出來做參照物了，所以直接從第二個(gè)字符串開始遍歷
for(int l=1;l<i;l++) {
//如果進(jìn)到if里說明已經(jīng)不相等了米奸。所以可以直接返回了昼接。
if(strs[l].charAt(k)!=first) {
return result;
}
}
//能走到這一步說明第K個(gè)字符比對成功，是公共前綴悴晰，所以結(jié)果集中加上該字符
result+=first;
}
//通常情況下在上面for循環(huán)中的return中就返回了慢睡，能走到這步說明其中某個(gè)字符串全部都是公共前綴
return result;
}
做到這里下一步就是看大神的思路和解析：一個(gè)神思維的大佬解析，就是人家?guī)仔形規(guī)资写a的再一次重現(xiàn)铡溪。
我做了這么多亂七八糟的判斷漂辐，人家大神都不用。而且思路簡單佃却，不會(huì)讓人看了覺得迷茫者吁，只會(huì)感嘆我怎么想不出來這種做法？饲帅？复凳？
簡單說一下，就是判斷數(shù)組非空則取第一個(gè)字符串開始與所有剩下的匹配灶泵，匹配不上則把第一個(gè)字符串最后一位截取育八，繼續(xù)匹配，再全匹配不上再截取赦邻。直至匹配上了髓棋，那么就是說這個(gè)前綴就是最長公共前綴了。哪怕沒有最長公共前綴也不過是截取成了“”空串惶洲，并不違反結(jié)果要求的按声。
下面是代碼：
public String longestCommonPrefix(String[] strs) {
if(strs.length==0){
return "";
}
//以第一個(gè)字符串為標(biāo)板
String str = strs[0];
for(int i=1;i<strs.length;i++){
while(strs[i].indexOf(str)!=0){
str = str.substring(0,str.length()-1);
}
}
return str;
}
滿打滿算人家的邏輯代碼也就四行。這就是思路的重要性恬吕。下一題签则！
有效的括號
題目：給定一個(gè)只包括 '('，')'铐料，'{'渐裂，'}'，'['钠惩，']' 的字符串柒凉，判斷字符串是否有效。有效字符串需滿足：1.左括號必須用相同類型的右括號閉合篓跛。2.左括號必須以正確的順序閉合膝捞。3.注意空字符串可被認(rèn)為是有效字符串。
示例 1:
輸入: "()"
輸出: true
示例 2:
輸入: "()[]{}"
輸出: true
示例 3:
輸入: "(]"
輸出: false
示例 4:
輸入: "([)]"
輸出: false
示例 5:
輸入: "{[]}"
輸出: true
這個(gè)題怎么說呢愧沟，想了幾分鐘绑警，做了幾分鐘求泰，做出來一看100多ms，心都碎了计盒，我還自我感覺思路挺好的呢渴频！
然后因?yàn)檫@個(gè)題比較簡單北启，所以我至今不知道大神啥思維卜朗，說說我自己的這個(gè)拿不出手的思路吧。
public boolean isValid(String s) {
int len = 0;
//當(dāng)s.length()等于len咕村，說明這次while中沒有剔除括號场钉，說明剩下的字符串無法簡化了
while(s.length()!=len){
len = s.length();
s = s.replace("[]", "");
s = s.replace("()", "");
s = s.replace("{}", "");
}
return "".equals(s)?true:false;
}
如圖吧，只要是有效的括號懈涛，肯定會(huì)有最內(nèi)層的括號,所以講內(nèi)層的括號直接剔除（也有可能是并列的括號逛万，反正直接剔除），然后再繼續(xù)下一輪再剔除批钠，如果是有效的格式則會(huì)被剔除成“”空串宇植，如果不是有效的格式則會(huì)無可提出而不滿足while的條件，跳出while埋心。結(jié)果集如果是空則ture指郁，不是空則false。
接下來？酱簟Ｏ锌病！大神解析：
看個(gè)屁的大神解析茬斧，看了n久腰懂，性能好的代碼賊麻煩，用的棧项秉，真真正正的做到了幾行代碼寫成幾十行绣溜，我還是就這么性能差著吧。附上大神代碼伙狐，反正我有點(diǎn)沒耐心看了
class Solution {
public boolean isValid(String s) {
if (s.length() == 0)
return true;
if ((s.length() & 1) == 1)
return false;
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
switch (s.charAt(i)) {
case '(':
case '[':
case '{':
stack.push(s.charAt(i));
continue;
case ')':
if (stack.isEmpty() || stack.pop() != '(')
return false;
continue;
case ']':
if (stack.isEmpty() || stack.pop() != '[')
return false;
continue;
case '}':
if (stack.isEmpty() || stack.pop() != '{')
return false;
continue;
}
}
return stack.isEmpty();
}
}
然后今天就這樣吧涮毫，目標(biāo)每日3——5題瞬欧，今天做了四道贷屎。每天進(jìn)步一點(diǎn)點(diǎn)嘛~
如果稍微幫到了你麻煩點(diǎn)個(gè)喜歡點(diǎn)個(gè)關(guān)注啥的，也祝大家工作順順利利艘虎！
