給自己的目標：[LeetCode](https://leetcode.com/ "Online Judge Platform") 上每日一題
在做題的過程中記錄下解題的思路或者重要的代碼碎片以便后來翻閱诫欠。
項目源碼：github上的Leetcode
6. ZigZag Conversion
題目：將一行字符串按給出的行數(shù)豎向鋸齒形排列，再按行輸出。
input:PAYPALISHIRING
P A H N
A P L S I I G
Y I R
ouput:PAHNAPLSIIGYIR
一道找規(guī)律的題目
對于每一層垂直元素的坐標 (i,j)= (j+1 )n +i；對于每兩層垂直元素之間的插入元素（斜對角元素），(i,j)= (j+1)n -i
public class Solution {
public String convert(String s, int numRows) {
if (numRows == 1) return s;
int len = s.length();
int span = numRows * 2 - 2;
StringBuffer sb = new StringBuffer("");
for (int i = 0; i < numRows; i++) {
int j = i;
while (j < len) {
sb.append(s.charAt(j));
if (j % span == 0 || j % span == (numRows - 1)) {
j += span;
} else {
int k = j + (span - i * 2);
if (k < len) {
sb.append(s.charAt(k));
}
j += span;
}
}
}
return sb.toString();
}
}
7. Reverse Integer
題目：數(shù)字反轉(zhuǎn),當(dāng)反轉(zhuǎn)后數(shù)字超出32位時，設(shè)值為0
Example1: x = 123, return 321
Example2: x = -123, return -321
先將數(shù)字轉(zhuǎn)換為字符串，然后利用字符串反轉(zhuǎn)危尿。當(dāng)反轉(zhuǎn)后數(shù)字溢出時，使用try...catch 捕獲馁痴。
public class Solution {
public int reverse(int x) {
boolean prefix = x < 0;
int ax = Math.abs(x);
StringBuffer sb = new StringBuffer();
sb.append(ax);
String s = sb.reverse().toString();
int value = 0;
try {
value = Integer.valueOf(s);
} catch (NumberFormatException e) {
value = 0;
}
if (prefix) {
return -value;
}
return value;
}
}
8. String to Integer (atoi)
題目：字符串轉(zhuǎn)換為數(shù)字谊娇。需要注意的是允許字符串前面出現(xiàn)的空格和當(dāng)字符串中出現(xiàn)數(shù)字之外的值時要輸出前面的數(shù)值。數(shù)值溢出時取最大或者最小值罗晕。
public class Solution {
public int myAtoi(String str) {
int value = 0;
int prefix = 1;
boolean isFirst = true;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (c == ' ' && isFirst) {
continue;
}
if (isFirst && (c == '+' || c == '-')) {
if (c == '-') {
prefix = -1;
}
isFirst = false;
continue;
}
if (c >= '0' && c <= '9') {
isFirst = false;
int newValue = value * 10 + c - '0';
if (newValue / 10 != value) {
if (prefix < 0) {
return Integer.MIN_VALUE;
} else {
return Integer.MAX_VALUE;
}
}
value = value * 10 + c - '0';
} else {
return value * prefix;
}
}
return value * prefix;
}
}
9. Palindrome Number
題目：回文數(shù)字
將數(shù)字反轉(zhuǎn)判斷是否相等即可
public class Solution {
public boolean isPalindrome(int x) {
if (x < 0) return false;
if (x == 0) return true;
long index = 0;
int s = x;
while (x > 0) {
index = index * 10 + x % 10;
x = x / 10;
}
return index == s;
}
}
10. Regular Expression Matching
題目：'.' 匹配任一字符济欢，'*'匹配前面數(shù)字0或多個字符。輸入一行字符串和一行匹配串小渊，判斷是否匹配法褥。
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
遞歸和動態(tài)規(guī)劃兩種解法。自己先使用的遞歸方法酬屉，耗時有點長半等。
1, If p.charAt(j) == s.charAt(i) : dp[i][j] = dp[i-1][j-1];
2, If p.charAt(j) == '.' : dp[i][j] = dp[i-1][j-1];
3, If p.charAt(j) == '*':
here are two sub conditions:
1 if p.charAt(j-1) != s.charAt(i) : dp[i][j] = dp[i][j-2] //in this case, a* only counts as empty
2 if p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == '.':
dp[i][j] = dp[i-1][j] //in this case, a* counts as multiple a
or dp[i][j] = dp[i][j-1] // in this case, a* counts as single a
or dp[i][j] = dp[i][j-2] // in this case, a* counts as empty
public class Solution {
public boolean isMatch(String s, String p) {
if (s == null || p == null) {
return false;
}
int m = s.length();
int n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int j = 0; j < n; j++) {
if (p.charAt(j) == '*') {
dp[0][j + 1] = dp[0][j - 1];
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (p.charAt(j) == '.') {
dp[i + 1][j + 1] = dp[i][j];
}
if (p.charAt(j) == s.charAt(i)) {
dp[i + 1][j + 1] = dp[i][j];
}
if (p.charAt(j) == '*') {
if (p.charAt(j - 1) != s.charAt(i) && p.charAt(j - 1) != '.') {
dp[i + 1][j + 1] = dp[i + 1][j - 1];
} else {
dp[i + 1][j + 1] = dp[i + 1][j - 1] || dp[i + 1][j] || dp[i][j + 1];
}
}
}
}
return dp[m][n];
}
}
