1. N 字形变换（06）
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
P A H N A P L S I I G Y I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
思想： 巧设flag实现z反转
class Solution { public String convert(String s, int numRows) { if (numRows<2) return s; ArrayList<StringBuilder> rows = new ArrayList<StringBuilder>(); for (int i = 0; i <numRows ; i++) { rows.add(new StringBuilder()); } int i=0; int flag = -1; //表示反向 for (char c : s.toCharArray()) { rows.get(i).append(c); if(i==0 || i ==numRows-1) flag = -flag; i += flag; } StringBuilder res = new StringBuilder(); for (StringBuilder row : rows) { res.append(row); } return res.toString(); } }
2. 整数反转 （07）
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
思想： −2^31≤rev*10+digit≤2^31−1是否成立，可改为判断不等式⌈−2^31⌉/10≤rev≤⌊2^31−1⌋/10
class Solution { public int reverse(int x) { int res =0; while (x!=0){ if (Integer.MAX_VALUE /10 <res || Integer.MIN_VALUE /10 >res ) return 0 ; int digit = x%10; x /=10; res = res*10+digit; } return res; } }
3. 字符串变整数（08）
将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）
思想：首部空格： 删除之即可；符号位： 三种情况，即 ''+++'' , ''−-−'' , ''无符号" ；新建一个变量保存符号位，返回前判断正负即可；非数字字符： 遇到首个非数字的字符时，应立即返回；字符转数字： “此数字的 ASCII 码” 与 “ 000 的 ASCII 码” 相减即可； 若从左向右遍历数字，设当前位字符为 c，当前位数字为 x ，数字结果为 res ，则数字拼接公式为：res=10×res+x ， x=ascii(c)−ascii(′0′)
class Solution { public int myAtoi(String s) { // 去除首端是空白字符 char[] chars = s.trim().toCharArray(); if (chars.length==0) return 0; int res =0; int bndry = Integer.MAX_VALUE /10; int i = 1; // 符号位 int sign = 1; if (chars[0]=='-') sign=-1; else if (chars[0]!='+') i = 0; for (int j = i; j <chars.length ; j++) { // 第一个不是数字的字符 if (chars[j]<'0' ||chars[j]>'9') break; // 数字拼接是否超出32位 // 乘上10 超出 // 数字个位数超出 if(res >bndry || (res ==bndry&& chars[j] >'7')) return sign ==1? Integer.MAX_VALUE :Integer.MIN_VALUE; res =res*10+chars[j]-'0'; } return res*sign; } }
4. 回文数（09）
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
思想：负数一定不是回文数， 正数逆序与原值相同。
class Solution { public boolean isPalindrome(int x) { if (x<0) return false; int res =0; int num =x; while (num!=0){ int digit = num%10; num /=10; res = res*10+digit; } return res == x; } }
5. 正则表达式匹配（10）
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。'.' 匹配任意单个字符；'*' 匹配零个或多个前面的那一个元素
思想： 动态规划+ 分类讨论，
class Solution { public boolean isMatch(String s, String p) { int m = s.length()+1; int n = p.length()+1; boolean[][] dp =new boolean[m][n]; dp[0][0]=true;//dp[0][0] 代表的是空字符的状态,一定匹配 //dp[i][j] 对应的添加字符是 s[i - 1] 和 p[j - 1] //当 p[j - 1] = '*' 时， dp[i][j] 在当以下任一情况为 true 时等于 true //dp[i][j - 2]==true ： 即将字符组合 p[j - 2] * 看作出现 0 次时，能否匹配。 //dp[i - 1][j]==true 且 s[i - 1] = p[j - 2]: 即让字符 p[j - 2] 出现 1 次时，能否匹配。 //dp[i - 1][j] ==true 且 p[j - 2] = '.': 即让字符 '.' 出现 1 次时，能否匹配。 //当 p[j - 1] != '*' 时， dp[i][j] 在当以下任一情况为 true时等于 true //dp[i - 1][j - 1]==true 且 s[i - 1] = p[j - 1]： 即让字符 p[j - 1] 出现一次时，能否匹配。 //dp[i - 1][j - 1] ==true 且 p[j - 1] = '.'： 即将字符 . 看作字符 s[i - 1] 时，能否匹配。 for (int j = 2; j <n ; j+=2) { dp[0][j] = dp[0][j-2] && p.charAt(j-1) == '*'; //匹配空字符 } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j]= (p.charAt(j-1)=='*')? (dp[i][j-2] || (dp[i-1][j] && s.charAt(i-1) ==p.charAt(j-2))|| (dp[i-1][j] && '.'==p.charAt(j-2)) ):((dp[i-1][j-1] && s.charAt(i-1) ==p.charAt(j-1))||(dp[i-1][j-1] && '.'==p.charAt(j-1))); } } return dp[m-1][n-1]; } }