呃呃呃，一个愉快的周末过去了，接下来又是愉快的周一。刷题继续。
我这里再解释一下：任何解题的思路和方法都是多种多样的！我的习惯就是一种是自己想出来的，可能很墨迹，很累赘，性能又不好！但是完全是自己想的，所以我这里也会贴出来，而且附上完整的想法思路啥的。然后我一般还会贴一种大神的解法，这个其实我是在重多题解中选择我认为比较好的一种来分析，学习并分享出。有的方法可能我没写，但是也是对的，然后这个解析也是我认为思路好或者简洁性能优的，不一定就是最好的 ，别杠我！
回文数
题目：判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1:
输入: 121
输出: true
示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
进阶:
你能不将整数转为字符串来解决这个问题吗？
看到这个题大笑三声，秒有思路。感觉LeetCode上的题挺有意思的，不太相信是故意的，只能说巧的很，上一道题才看了整数反转，结果做这个题怕不是手到擒来呦~！然后因为很简单所以直接上代码了：
public boolean isPalindrome(int x) {
//首先我这是做了整数反转后再做这个题的。
//整数分三类，正整数，负整数，0、0天然就是回文数，正整数有可能是回文数，负整数肯定不是回文数
if(x<0){
return false;
}
if(x==0){
return true;
}
//思路是将这个数反转，如果等于原数则是回文数
if(x>0){
long result = 0l;
//因为下面操作后x会改变，所以提前保存x的值，并且为了方便比较，直接设定为long型，不要吐槽我命名
long xx = x;
while(x!=0){
result = result*10+x%10;
x=x/10;
}
//原数是int。如果反转后溢出了则肯定是不是回文数
if(result>Integer.MAX_VALUE||result<Integer.MIN_VALUE){
return false;
}
if(result==xx){
return true;
}else{
return false;
}
}
return false;
}
嗯，学到既得到，感谢上一个整数反转的题目。
罗马数字转整数
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。
示例 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.
思路：首先说一下这个题，仔细看题思路很简单！！然后磕磕绊绊做了出来，实现是实现了，但是肯定不是优解！（这个就很无力了，然后我没想到，但是猜都能猜到又是人家几行的代码我写了几十行）
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，其次我这里是真的很麻烦的处理，一个字符串来来回回遍历好几遍，而且最后又是if来回走。而大佬的思路就简单粗暴的多了，判断每一个数字，前面的比后面的小则是减。并且我刚刚测试了，用char类型比用string类型的比较性能好6ms，所以改完后完整版如下：
class Solution {
public int romanToInt(String s) {
int result = 0;
//因为里面要用到当前元素的后一个字符，所以只能遍历到倒数第二个元素。
for(int i=0;i<s.length()-1;i++){
//前一个数字大于后一个数字则是正常相加
if(getValue(s.charAt(i))>=getValue(s.charAt(i+1))){
result += getValue(s.charAt(i));
}else{
//前一个小于后一个则是减法
result -= getValue(s.charAt(i));
}
}
//最后一个元素一定是要相加的
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;
}
}
其实这个题目本身没什么好说的，但是好多语法上的细节可以聊聊，我提交了很多遍，有的思路差不多，但是一点不起眼的改动就让执行速度和性能变了很多。
之前这个for循环里的if-else我是用两个if来判断的，结果速度跑出来在百分之七十几左右，然后我看人家大神代码，方法差不多一样，为什么人家百分之九十九呢？区别就在于我这个两个if判断，人家一个fi-else选择，然后我只改了这一块，再执行少了两秒，超过了百分之二十多的人。
其实是想不明白这样if-else为什么性能好么？能想明白的，这样相当于一次只需要一次判断，而我那种写法每次需要两次判断的，但是我为什么还那么写？没注意，没想到而已。其实真的一直喊着性能，时间复杂度，优化之类的，但是又有多少落到实际上了呢？
很感谢这个LeetCode平台，尤其是每次提交都会弹出那个执行时间，消耗性能，把一种很抽象的说法量化了起来，也让我认识的更深。
最长公共前缀
题目：编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。
思路：这个题注意审题吧，反正我是做笑了。然后开始分析思路：一个string数组，获取公共前缀，其实第一印象感觉应该挺好做的，然后大体就是获取每一个字符串的第一位比较，相同往下比较，不相同直接返回。可是思路是有了，实践起来一步一个问题。首先空数组怎么办？其次每个字符串长度不同，怎么获取最短长度？最后一步才是双循环挨个对比。我习惯于在代码中注解写的很墨迹，所以没思路的可以看看注解
public String longestCommonPrefix(String[] strs) {
int i = strs.length;
//如果这是一个空数组则直接返回空
if(i==0){
return "";
}
//获取最短的那个字符串的长度
int j = strs[0].length();
for(String s:strs) {
if(j>s.length()) {
//如果长度比j短则替换j
j=s.length();
}
}
//结果集
String result = "";
//遍历第一层，从字符串下表为0的字符开始比对
for(int k=0;k<j;k++) {
//第一个字符串的第一个字符，作为参照物
char first = strs[0].charAt(k);
//因为第一个字符串已经取出来做参照物了，所以直接从第二个字符串开始遍历
for(int l=1;l<i;l++) {
//如果进到if里说明已经不相等了。所以可以直接返回了。
if(strs[l].charAt(k)!=first) {
return result;
}
}
//能走到这一步说明第K个字符比对成功，是公共前缀，所以结果集中加上该字符
result+=first;
}
//通常情况下在上面for循环中的return中就返回了，能走到这步说明其中某个字符串全部都是公共前缀
return result;
}
做到这里下一步就是看大神的思路和解析：一个神思维的大佬解析，就是人家几行我几十行代码的再一次重现。
我做了这么多乱七八糟的判断，人家大神都不用。而且思路简单，不会让人看了觉得迷茫，只会感叹我怎么想不出来这种做法？？？
简单说一下，就是判断数组非空则取第一个字符串开始与所有剩下的匹配，匹配不上则把第一个字符串最后一位截取，继续匹配，再全匹配不上再截取。直至匹配上了，那么就是说这个前缀就是最长公共前缀了。哪怕没有最长公共前缀也不过是截取成了“”空串，并不违反结果要求的。
下面是代码：
public String longestCommonPrefix(String[] strs) {
if(strs.length==0){
return "";
}
//以第一个字符串为标板
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;
}
满打满算人家的逻辑代码也就四行。这就是思路的重要性。下一题！
有效的括号
题目：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。有效字符串需满足：1.左括号必须用相同类型的右括号闭合。2.左括号必须以正确的顺序闭合。3.注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
这个题怎么说呢，想了几分钟，做了几分钟，做出来一看100多ms，心都碎了，我还自我感觉思路挺好的呢！
然后因为这个题比较简单，所以我至今不知道大神啥思维，说说我自己的这个拿不出手的思路吧。
public boolean isValid(String s) {
int len = 0;
//当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;
}
如图吧，只要是有效的括号，肯定会有最内层的括号,所以讲内层的括号直接剔除（也有可能是并列的括号，反正直接剔除），然后再继续下一轮再剔除，如果是有效的格式则会被剔除成“”空串，如果不是有效的格式则会无可提出而不满足while的条件，跳出while。结果集如果是空则ture，不是空则false。
接下来！！！大神解析：
看个屁的大神解析，看了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();
}
}
然后今天就这样吧，目标每日3——5题，今天做了四道。每天进步一点点嘛~
如果稍微帮到了你麻烦点个喜欢点个关注啥的，也祝大家工作顺顺利利！
