算法1
实现支持 ‘.’ 和 ‘*’ 的正则表达式匹配
给定一个字符串 (s) 和一个字符模式 (p)。实现支持 ‘.’ 和 ‘’ 的正则表达式匹配。
‘.’ 匹配任意单个字符。
‘’ 匹配零个或多个前面的元素。
匹配应该覆盖整个字符串 (s) ，而不是部分字符串
说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和
思路：
当模式中的下一个字符不是”*”时：
- 如果字符串当前字符和模式中的当前字符相匹配，那么字符串指针和模式指针都后移一个字符，然后匹配剩余的。
- 如果字符串当前字符和模式中当前字符不匹配，直接返回false。
当模式中的下一个是”*”时：
如果字符串当前字符跟模式当前字符不匹配，则模式指针后移2个字符，继续匹配。
如果字符串当前字符跟模式当前字符匹配，可以有3种匹配方式：
1、模式指针后移2字符，相当于x被忽略；
2、字符串指针后移1字符，模式指针后移2字符；
3、字符串指针后移1字符，模式不变，即继续匹配字符下一位，因为可以匹配多位；
代码：
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
35
36
37
38
| public boolean isMatch(String s, String p) {
if (p.equals(".*")){
return true;
}
if (s == null || p == null){
return false;
}
int strIndex = 0, patternIndex = 0;
return matchChar(s, strIndex, p, patternIndex);
}
public boolean matchChar(String str, int strIndex, String pattern, int patternIndex){
if (strIndex == str.length() && patternIndex == pattern.length()){
return true;
}
if (strIndex != str.length() && patternIndex == pattern.length()){
return false;
}
if (patternIndex + 1 < pattern.length() && pattern.charAt(patternIndex + 1) == '*'){
if ((strIndex != str.length() && str.charAt(strIndex) == pattern.charAt(patternIndex)) ||
(strIndex != str.length() && pattern.charAt(patternIndex) == '.') ){
return matchChar(str, strIndex, pattern, patternIndex + 2) ||
matchChar(str, strIndex + 1, pattern, patternIndex + 2) ||
matchChar(str, strIndex + 1, pattern, patternIndex);
}else {
return matchChar(str, strIndex, pattern, patternIndex + 2);
}
}else if ((strIndex!=str.length() && str.charAt(strIndex) == pattern.charAt(patternIndex)) ||
(strIndex != str.length() && pattern.charAt(patternIndex) == '.')){
return matchChar(str, strIndex + 1, pattern, patternIndex + 1);
}
return false;
}
|
算法2
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
例如，121 是回文，而 123 不是。
示例 1：
示例 2：
1
2
3
| 输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
|
示例 3：
1
2
3
| 输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。
|
思路为：
反转数字的一半，该数字是回文，其后半部分反转后应该与原始数字的前半部分相同。
例如:1221的反转数字一半 的过程。
将1221%10=1，则为该数字的最后一个，
倒数第二位：1221/10 = 122；122%10 = 2；第二位计算完毕
将第一个计算的数字×10再加第二位数字，依次进行下去。（r = r*10 + x%10; x = x/10;）
结束条件：当原始数字小于或等于反转后的数字时，就意味着我们已经处理了一半位数的数字了。
代码为：
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public boolean isPalindrome(int x) {
if (x<0 || (x%10==0)&&x!=0){
return false;
}
int r = 0;
while (r<x){
r = r*10 + x%10;
x = x/10;
}
return (x==r) || (x==(r/10));
}
}
|
算法3
有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。
示例 1：
示例 2：
示例 3：
思路：
创建一个栈进行存放'('和'['和'{'。
如果遇到符号的右半部分，则判断栈是否为空，如果为空，直接返回false，如果不为空，判断是否和栈顶元素相等，不相等返回false。
如果遇到符号左半部分，则入栈。
最后判断栈种的元素是否为空来判断是否满足。
代码为：
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
| import java.util.*;
public class Main3 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.next();
int n = s.length();
if (n%2==1){
System.out.println(false);
return;
}
Map<Character,Character> map = new HashMap<>();
map.put(')','(');
map.put(']','[');
map.put('}','{');
Deque<Character> deque = new LinkedList<>();
for (int i = 0;i<n;i++){
char c = s.charAt(i);
if (map.containsKey(c)){
if (deque.isEmpty()||deque.peek()!= map.get(c)){
System.out.println(false);
return;
}
deque.pop();
}else {
deque.push(c);
}
}
System.out.println(deque.isEmpty());
}
}
|