8. 字符串转整数 (atoi)
题目
实现 atoi，将字符串转为整数。
在找到第一个非空字符之前，需要移除掉字符串中的空格字符。如果第一个非空字符是正号或负号，选取该符号，并将其与后面尽可能多的连续的数字组合起来，这部分字符即为整数的值。如果第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
字符串可以在形成整数的字符后面包括多余的字符，这些字符可以被忽略，它们对于函数没有影响。
当字符串中的第一个非空字符序列不是个有效的整数；或字符串为空；或字符串仅包含空白字符时，则不进行转换。
若函数不能执行有效的转换，返回 0。
说明：
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [?231, 231 ? 1]。如果数值超过可表示的范围，则返回 INT_MAX (231 ? 1) 或 INT_MIN (?231) 。
示例 1:
输入: “42”
输出: 42
示例 2:
输入: ” -42”
输出: -42
解释: 第一个非空白字符为 ‘-‘, 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:
输入: “4193 with words”
输出: 4193
解释: 转换截止于数字 ‘3’ ，因为它的下一个字符不为数字。
示例 4:
输入: “words and 987”
输出: 0
解释: 第一个非空字符是 ‘w’, 但它不是数字或正、负号。
因此无法执行有效的转换。
示例 5:
输入: “-91283472332”
输出: -2147483648
解释: 数字 “-91283472332” 超过 32 位有符号整数范围。
因此返回 INT_MIN (?231) 。
思路
这个题目即需要自己实现一个字符串解析整数的功能方法，根据以上示例可以得出三个结论
- 在没有遇到数字或正负号之前，只能出现空格否则不能转换。
- 遇到数字或者正负号之后在遇见空格或者其他字符（包括正负号）转换停止之后的数字不在转换。
- 转化的值可能会超出int范围，一旦转化的当前整数值超出int范围，停止转化。
知道这些特征之后就很好解决问题了，直接通过循环判断对应的条件然后做出相应的操作即可
代码
其中flag表示是否出现过数字或者正负号。未出现之前，只能接受空格字符，当出现过之后只能接受数字字符。不符合的条件一成立则停止转化，输出结果，最后做防止溢出转化。
class Solution {
public int myAtoi(String str) {boolean flag = false;boolean posi = true;long res = 0;for(int i=0;i<str.length();i++){char c = str.charAt(i);if(c>='0'&&c<='9')res = res*10+(c-'0');else if(c=='-'&&!flag)posi = false;else if(c=='+'&&!flag)posi = true;else if(flag||!flag&&c!=' ')break;if(!flag&&c!=' ')flag = true;if(res-1>Integer.MAX_VALUE)break;}return posi?(int)Math.min(res,Integer.MAX_VALUE):(int)Math.max(-1*res,Integer.MIN_VALUE);}
}9. 回文数
题目
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1:
输入: 121
输出: true
示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
思路
这个题目比较简单，首先明确一点负数因为含有’-‘所以绝对不是回文数。0是回文数。然后对整数逐位反转。组成一个新数，比较是否一致即可。
代码
class Solution {public boolean isPalindrome(int x) {if(x==0)return true;else if(x<0)return false;int temp = x;int contrast = 0;while(temp>0){contrast = contrast*10+temp%10;temp/=10;}return contrast==x;}
}10. 正则表达式匹配
题目
给定一个字符串 (s) 和一个字符模式 (p)。实现支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
‘.’ 匹配任意单个字符。
‘*’ 匹配零个或多个前面的元素。
匹配应该覆盖整个字符串 (s) ，而不是部分字符串。
说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
示例 1:
输入:
s = “aa”
p = “a”
输出: false
解释: “a” 无法匹配 “aa” 整个字符串。
示例 2:
输入:
s = “aa”
p = “a*”
输出: true
解释: ‘*’ 代表可匹配零个或多个前面的元素, 即可以匹配 ‘a’ 。因此, 重复 ‘a’ 一次, 字符串可变为 “aa”。
示例 3:
输入:
s = “ab”
p = “.*”
输出: true
解释: “.” 表示可匹配零个或多个(‘‘)任意字符(‘.’)。
示例 4:
输入:
s = “aab”
p = “c*a*b”
输出: true
解释: ‘c’ 可以不被重复, ‘a’ 可以被重复一次。因此可以匹配字符串 “aab”。
示例 5:
输入:
s = “mississippi”
p = “mis*is*p*.”
输出: false
思路。
题目的要求是实现一个正则表达式的部分功能，首先并且一下’.’和’ * ‘的功能。’.’是匹配任意一个字符。’ * ‘是匹配前面一个元素零个或多个组成的字符串。比如a*,可以表示”“、a、aa、aaa、aaaa……，之前就是这个地方没有看清楚，纠结了很久。
那么知道这些条件之后就能开始来判断了。首先’.’和’ * ‘这两者前者更容易匹配判断，因为只要判断其存在则两串继续往下判断即可，后者匹配更复杂。有多种情景，当判断的当前字符的下一个字符为’ * ‘时，首先判断当前字符是否相等，如果不相等，即’ * ‘失去作用。则把p串的位置向后移动两位(当前位判断失败，’ * ‘字符失去作用，直接匹配其后的字符)。
如果当前的字符匹配成功,那么也有三种情况，第一种直接将p串向后移2位，这样的话相当于忽略当前判断成功结果，直接比较之后的字符是否与当前s串位置上的字符是否相等。（这样做是为了避免一些特定情况的出现，即pa,p*pa，这种情况，当p 被略后才能正确的匹配成功）。第二种 即当匹配0个当前字符，将s串后移一位，p串后移两位，直接与下面的字符进行匹配。第三种 即匹配多个当前字符。因为采取递归。直接将s串后移一位，继续与p串当前字符进行判断。如果当前字符的下一个字符不为’ * ‘时，判断当前字符是否相等相等两串后移继续判断，否则返回false。因为下一个不为’ * ‘，当当前字符串的第一个和模式串中的第一不想匹配直接返回false即可(切不可将匹配当做寻找子串，两者完全不同)。
class Solution {public boolean isMatch(String s, String p) {if(s==null||p==null)return false;return match(s,0,p,0);}private boolean match(String s,int sIndex,String p,int pIndex){if(sIndex==s.length()&&pIndex==p.length())return true;else if(sIndex!=s.length()&&pIndex==p.length())return false;if(pIndex + 1<p.length() && p.charAt(pIndex+1)=='*'){if(sIndex != s.length()&&p.charAt(pIndex)==s.charAt(sIndex)||p.charAt(pIndex) == '.' && sIndex !=s.length())return match(s,sIndex,p,pIndex+2)||match(s,sIndex+1,p,pIndex+2)||match(s,sIndex+1,p,pIndex);elsereturn match(s,sIndex,p,pIndex+2);}else if(sIndex!=s.length()&&(p.charAt(pIndex)==s.charAt(sIndex)||p.charAt(pIndex)=='.'))return match(s,sIndex+1,p,pIndex+1);return false;}
}