4. 替换空格为『%20』
思路：从后往前遍历，【替换为02%】
public String replaceSpace(StringBuffer str) {
StringBuffer res = new StringBuffer();
int len = str.length() - 1;
for(int i = len; i >= 0; i--){
if(str.charAt(i) == ' ')
res.append("02%");
else
res.append(str.charAt(i));
}
return res.reverse().toString();
}
28. 字符串的排列
描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。（字符串长度不超过9(可能有字符重复),字符只包括大小写字母）
例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
思路
- 求所有可能出现在第一个位置的字符（即把第一个字符和后面的所有字符交换[相同字符不交换]）
- 固定第一个字符，求后面所有字符的排列。这时候又可以把后面的所有字符拆成两部分（第一个字符以及剩下的所有字符），依此类推。
public ArrayList<String> Permutation(String str) {
ArrayList<String> list = new ArrayList<>();
if(str.length()==0||str==null)
return list;
helper(list,str.toCharArray(),0);
Collections.sort(list);
return list;
}
public void helper(ArrayList<String> list, char[] str, int i) {
if (i == str.length) {
list.add(String.valueOf(str));
} else {
for (int j = i; j < str.length; j++) {
if (j != i && str[i] == str[j]) {
continue;
}
swap(str, i, j);
helper(list, str, i + 1);
swap(str, i, j);
}
}
}
42. 翻转单词顺序
“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。
思路：先翻转整个字符串，再翻转每个单词
public String ReverseSentence(String str) {
// String str = "i am a student.";
if (str == null || str.length() == 0)
return "";
if (str.trim().equals(""))
return str;
str = new StringBuilder(str).reverse().toString();
// str=".tneduts a ma I"
String ss[] = str.split(" ");
String res = new StringBuilder(ss[0]).reverse().toString();
for (int i = 1; i < ss.length; i++) {
res = res + " " + (new StringBuilder(ss[i]).reverse().toString());
}
return res;
}
42. 左旋转字符串
描述
符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”
思路
方法一：两个字符串拼接
方法二：字符串分为两部分【abc】【XYZdef】，分别翻转后为【cbafedZYX】,再整体翻转【XYZdefabc】
public String LeftRotateString(String str,int n) {
int len = str.length();
if(len == 0)
return "";
n = n % len;
String s1 = str.substring(n, len);
String s2 = str.substring(0, n);
return s1+s2;
}
39. 把字符串转换成整数
思路
注意上下溢出
常规思路，先判断第一位是不是符号位，如果有符号，有flag 做标记。
遍历字符串中的每个字符，如果存在非数字的字符，直接返回 0，否则，用当前字符减去’0’得到当前的数字，再进行运算。
public int StrToInt(String str) {
if (str == null || str.length() == 0)
return 0;
int start;
int tag;
if (str.charAt(0) == '+') {
tag = 1;
start = 1;
} else if (str.charAt(0) == '-') {
tag = 0;
start = 1;
} else {
tag = 1;
start = 0;
}
long result = 0;
for (int i = start; i < str.length(); i++) {
char tmp = str.charAt(i);
if (tmp >= '0' && tmp <= '9') {
result = result * 10 + (tmp - '0');
if (tag == 1 && result > Integer.MAX_VALUE)
throw new RuntimeException("上溢出");
if (tag == 0 && result < Integer.MIN_VALUE)
throw new RuntimeException("下溢出");
} else {
return 0;
}
}
if (tag == 0)
return (int) (-1 * result);
else {
return (int) result;
}
}
53. 正则表达式匹配
描述
请实现一个函数用来匹配包括’.’和’’的正则表达式。模式中的字符’.’表示任意一个字符，而’’表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”ab*a”均不匹配
思路
当模式中的第二个字符不是“*”时：
1、如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的。
2、如果 字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。
而当模式中的第二个字符是“*”时：
如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，继续匹配。如果字符串第一个字符跟模式第一个字符匹配，可以有3种匹配方式：
1、模式后移2字符，相当于x*被忽略；
2、字符串后移1字符，模式后移2字符；
3、字符串后移1字符，模式不变，即继续匹配字符下一位，因为*可以匹配多位。
public boolean match(char[] str, char[] pattern) {
int sindex = 0, pindex = 0;
return matchCore(str, sindex, pindex, pattern);
}
public boolean matchCore(char[] str, int sindex, int pindex, char[] pattern) {
if (sindex >= str.length && pindex == pattern.length)
return true;
if (pindex >= pattern.length && sindex < str.length)
return false;
if (pindex + 1 < pattern.length && pattern[pindex + 1] == '*') {
if (sindex < str.length && (str[sindex] == pattern[pindex] || pattern[pindex] == '.')) {
return matchCore(str, sindex, pindex + 2, pattern) ||
matchCore(str, sindex + 1, pindex + 2, pattern) ||
matchCore(str, sindex + 1, pindex, pattern);
} else {
return matchCore(str, sindex, pindex + 2, pattern);
}
}
if (sindex < str.length && (str[sindex] == pattern[pindex] || pattern[pindex] == '.'))
return matchCore(str, sindex + 1, pindex + 1, pattern);
return false;
}
网友评论