52. 正则表达式匹配
请实现一个函数用来匹配包括’.’和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”ab*a”均不匹配
思路： 首先，考虑特殊情况：
- 两个字符串都为空，返回true`
- 当第一个字符串不空，而第二个字符串空了，返回false（因为这样，就无法匹配成功了,而如果第一个字符串空了，第二个字符串非空，还是可能匹配成功的，比如第二个字符串是“a*a*a*a*”,由于‘*’之前的元素可以出现0次，所以有可能匹配成功）
之后就开始匹配第一个字符，这里有两种可能：匹配成功或匹配失败。但考虑到pattern下一个字符可能是‘*’， 这里我们分两种情况讨论：pattern下一个字符为‘*’或不为‘*’：
-
pattern下一个字符不为‘*’：这种情况比较简单，直接匹配当前字符。如果匹配成功，继续匹配下一个；如果匹配失败，直接返回false。注意这里的匹配成功”，除了两个字符相同的情况外，还有一种情况，就是pattern的当前字符为‘.’,同时str的当前字符不为空。
-
pattern下一个字符为‘*’时，稍微复杂一些，因为‘*’可以代表0个或多个。`
这里把这些情况都考虑到： a. 当‘*’匹配0个字符时，str当前字符不变，pattern当前字符后移两位，跳过这个‘*’符号；` b. 当‘*’匹配1个或多个时，str当前字符移向下一个，pattern当前字符不变。（这里匹配1个或多个可以看成一种情况，因为：当匹配一个时，由于str移到了下一个字符，而pattern字符不变，就回到了上边的情况a；当匹配多于一个字符时，相当于从str的下一个字符继续开始匹配）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Solution {
public boolean match(char[] str, char[] pattern) {
if (str == null || pattern == null) return false;
int strIndex = 0;
int patternIndex = 0;
return matchCore(str, strIndex, pattern, patternIndex);
}
public boolean matchCore(char[] str, int strIndex, char[] pattern, int patternIndex) {
if (strIndex == str.length && patternIndex == pattern.length) return true;
if (strIndex != str.length && patternIndex == pattern.length) return false;
if (strIndex == str.length && patternIndex != pattern.length) {
if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') {
return matchCore(str, strIndex, pattern, patternIndex + 2);
}
return false;
}
if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') {
if (pattern[patternIndex] == str[strIndex] || (pattern[patternIndex] == '.' && strIndex != str.length)) {
return matchCore(str, strIndex, pattern, patternIndex + 2)
|| matchCore(str, strIndex + 1, pattern, patternIndex + 2)
|| matchCore(str, strIndex + 1, pattern, patternIndex);
} else return matchCore(str, strIndex, pattern, patternIndex + 2);
}
if (pattern[patternIndex] == str[strIndex] || (pattern[patternIndex] == '.' && strIndex != str.length)) {
return matchCore(str, strIndex + 1, pattern, patternIndex + 1);
}
return false;
}
}
53. 表示数值的字符串
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。 但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。
思路： 1. 枚举if判断不合法输入。 2. 正则表达式。 3. 异常处理。
解法一：if判断不合法输入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
public boolean isNumeric(char[] str) {
if(str.length == 0) return false;
int dcount = 0, ecount = 0;
for(int i = 0; i < str.length; i++){
if(i == 0 && (str[i] == '+' || str[i] == '-')) {
if(str.length == 1) return false;
}
else if(str[i] == 'e' || str[i] == 'E'){
if(ecount >= 1) return false;
else ecount++;
if(i + 1 >= str.length) return false;
if(str[i + 1] == '-') i++;
if(str[i + 1] == '+') i++;
}
else if(str[i] == '.') {
if(dcount >= 1 || ecount >= 1) return false;
else dcount++;
}
else if(48 <= str[i] && str[i] <= 57) continue;
else return false;
}
return true;
}
}
解法二：正则表达式
1
2
3
4
5
6
public class Solution {
public boolean isNumeric(char[] str) {
String string = String.valueOf(str);
return string.matches("[\\+-]?[0-9]*(\\.[0-9]*)?([eE][\\+-]?[0-9]+)?");
}
}
解法三：异常处理
1
2
3
4
5
6
7
8
9
10
public class Solution {
public boolean isNumeric(char[] str) {
try {
double output = Double.parseDouble(new String(str));
} catch(NumberFormatException e){
return false;
}
return true;
}
}
54. 字符流中的第一个不重复的字符
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。
输出描述:
如果当前字符流没有存在出现一次的字符，返回#字符。
思路： 利用有序的LinkedHashMap，统计字符出现次数，并且从头寻找只出现一次的字符。再此基础上增加一个队列用来存储只出现一次的字符可以减少遍历。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.LinkedHashMap;
import java.util.Iterator;
import java.util.Map;
public class Solution {
private Map map = new LinkedHashMap();
//Insert one char from stringstream
public void Insert(char ch){
if(!map.containsKey(ch)) map.put(ch, 1);
else map.put(ch, (Integer)map.get(ch) + 1);
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce(){
char output = '#';
Iterator it = map.entrySet().iterator();
while(it.hasNext()){
Map.Entry e = (Map.Entry) it.next();
if ((Integer)e.getValue() == 1) return (Character)e.getKey();
}
return output;
}
}
55. 链表中的环的入口结点
一个链表中包含环，请找出该链表的环的入口结点。
思路： 利用两个指向头部的指针p1，p2。p1每次往后走一个节点，p2每次走两个节点。当p1和p2相遇的时候，此时，令环的长度为n，环之前p1路过的节点为x，环内p1走过的节点为c，则p1路过的节点为x + c，p2路过的结点为x + n + c，且p2路过的结点数为p1的两倍，则(x + n + c) = 2 (x + c)，因此n =x + c，p1正好走了一个环的距离。
令p2再指向头部并没次走一个节点，当两个节点相遇的时候，此时p1就是环的入口。
解法一：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead){
if(pHead == null || pHead.next == null) return null;
ListNode p1 = pHead, p2 = pHead;
while(p1.next!=null && p2.next!=null){
p1 = p1.next;
p2 = p2.next.next;
if(p1 == p2){
p2 = pHead;
while(p1 != p2){
p1 = p1.next;
p2 = p2.next;
}
if(p1 == p2) return p1;
}
}
return null;
}
}