- 正则表达式的匹配
leetcode的题目，解析描述更加全面
https://leetcode-cn.com/problems/regular-expression-matching/
请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配。
/*
当模式中的第二个字符不是“*”时：
1、如果字符串第一个字符和模式中的第一个字符相匹配，
那么字符串和模式都后移一个字符，然后匹配剩余的。
2、如果字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。
而当模式中的第二个字符是“*”时：
如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，继续匹配。
如果字符串第一个字符跟模式第一个字符匹配，可以有3种匹配方式：
1、模式后移2字符，相当于x*被忽略；
2、字符串后移1字符，模式后移2字符； 相当于x*算一次
3、字符串后移1字符，模式不变，即继续匹配字符下一位，因为*可以匹配多位，相当于算多次
这里需要注意的是：Java里，要时刻检验数组是否越界。*/
public class Zhengze {
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) {
// 有效性检验：str到尾，pattern到尾，匹配成功
if (strIndex == str.length && patternIndex == pattern.length)
return true;
// pattern先到尾，匹配失败
if (strIndex != str.length && patternIndex == pattern.length)
return false;
// 模式第2个是*，且字符串第1个跟模式第1个匹配,分3种匹配模式；如不匹配，模式后移2位
if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') {
if ((strIndex != str.length && pattern[patternIndex] == str[strIndex])
|| (pattern[patternIndex] == '.' && strIndex != str.length)) {
return // 模式后移2，视为x*匹配0个字符
matchCore(str, strIndex, pattern, patternIndex + 2)
// 视为模式匹配1个字符
|| matchCore(str, strIndex + 1, pattern, patternIndex + 2)
// *匹配1个，再匹配str中的下一个
|| matchCore(str, strIndex + 1, pattern, patternIndex);
} else {
return matchCore(str, strIndex, pattern, patternIndex + 2);
}
} // 模式第2个不是*，且字符串第1个跟模式第1个匹配，则都后移1位，否则直接返回false
if ((strIndex != str.length && pattern[patternIndex] == str[strIndex])
|| (pattern[patternIndex] == '.' && strIndex != str.length)) {
return matchCore(str, strIndex + 1, pattern, patternIndex + 1);
}
return false;
}
}
- 表示数值的字符串
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
正则表达式解法：
[+-]? 表示+或者-出现0次或1次。[0-9]{0,}表示0到9出现0次或者更多次。()表示这个分组作为一个整体。 \.?表示.出现0次或1次。[0-9]{1,}表示0到9出现1次或者多次。()表示一个分组。如果把两个分组去掉进行判断是不准确的。100匹配到[0-9]{1,}出错。
public boolean isNumeric(char[] str) {
String res = String.valueOf(str);
return res.matches("[+-]?[0-9]{0,}(\\.?[0-9]{1,})?([Ee][+-]?[0-9]{1,})?");
}
逻辑思路：
思路:按照一定的规则，如果第一位是+或-，就后移一位。
如果是数字，索引后移，数字表示1.
如果是点，要判断至此点的数量和e的数量是否已经有了，因为java 中e要求后面为整数，如果有了肯定false。索引后移，dotnum增加。
如果是e，判断是否重复e，或者前面没有数字返回false。enum++， 索引++，此时还要判断最后一位是不是e或者+或者-，如果是false。
public boolean isNumeric(char[] str) {
if(str == null)
return false;
int length = str.length;
int dotNum = 0;//记录点的数量
int index = 0;//索引
int eNum = 0;//记录e的数量
int num = 0;//记录数字的数量
if (str[0] == '+' || str[0] == '-') {
index++;
}
while (index < length) {
if(str[index]>='0' && str[index]<='9') {
index++;
num = 1;
// .前面可以没有数字,所以不需要判断num是否为0
}else if(str[index]=='.') {
// e后面不能有.,e的个数不能大于1.java科学计数要求aeb，b为整数
if(dotNum >0 || eNum >0)
return false;
dotNum++;
index++;
}else if(str[index] == 'e' || str[index] == 'E') {
// 重复e或者e前面没有数字
if(eNum > 0 || num ==0)
return false;
eNum++;
index++;
// 符号不能在最后一位
if(index < length &&(str[index]=='+'||str[index]=='-'))
index++;
// 表示e或者符号在最后一位
if(index == length)
return false;
}else {
return false;
}
}
return true;
}
- 第一个只出现一次的字符
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.
private LinkedHashMap<Character,Integer> hm = null;
public int FirstNotRepeatingChar(String str) {
hm = new LinkedHashMap<>();
for(int i=0;i<str.length();i++) {
if(!hm.containsKey(str.charAt(i))) {
hm.put(str.charAt(i), 1);
}else {
hm.put(str.charAt(i),hm.get(str.charAt(i))+1);
}
}
for (int i = 0; i < str.length(); i++) {
if (hm.get(str.charAt(i)) == 1) {
return i;
}
}
return -1;
}
3.1 字符流中第一个不重复的字符
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
思路：参考两个博客一种用hashmap来做，一种用字符数组来做。
HashMap<Character, Integer> map = new HashMap<>();//记录字符出现次数
ArrayList<Character> list = new ArrayList<>();//记录当前的所有的字符
//Insert one char from stringstream
public void Insert(char ch)
{
if(map.containsKey(ch))
map.put(ch, map.get(ch)+1);
else
map.put(ch,1);
list.add(ch);
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce()
{
for(char c:list) {
if(map.get(c)==1)
return c;
}
return '#';
}
字符数组的方法：
char类型和int类型数值在 0-255之内的可以通用
默认初始值是ASCII的0（int）;char类型会自动转换成(int型)ASCII进行算术运算
char [] chars = new char[256];//ascii字符共128，其他字符非中文认为256个，
//为每个字符预留空间。默认每个存的ascii值为0
StringBuffer sb = new StringBuffer();//记录当前的所有字符
//Insert one char from stringstream
public void Insert(char ch)
{
sb.append(ch);
chars[ch]++;//如果字符是1，那么就是在字符1对应的下标的地方
//也就是49的下标处，ascii加1.此时如果输出chars[ch],里面存ascii值
//为1，所以是一个不可显示的字符。
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce()
{
char [] str = sb.toString().toCharArray();
for(char c:str) {
if(chars[c] == 1)//判断这个字符数组中在这个字符下标处值是否为1.
return c;
}
return '#';
}
- 左旋转字符串
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
public String LeftRotateString(String str,int n) {
if(str.length() == 0) {
return "";
}
if(str.length() == 1) {
return str;
}
String s = str.substring(0,n);
String t = str.substring(n);
return t.concat(s);
}
不知道要考什么，过于简单
- 把字符串转换为整数
将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0
思路：若为负数，则输出负数，字符0对应48,9对应57，不在范围内则返回false。
public int StrToInt(String str) {
if (str == null || str.length() == 0)
return 0;
int mark = 0;
long number = 0;
char[] chars = str.toCharArray();
if (chars[0] == '-')
mark = 1;//第一位如果是-号，则从第二位开始循环
for (int i = mark; i < chars.length; i++) {
if(chars[i] == '+')
continue;
if(chars[i]<48 || chars[i]>57)
return 0;
number = number * 10+chars[i] - 48;
}
if(mark==0 && number > Integer.MAX_VALUE) {
return 0;
}
if(-number < -2147483648) {
return 0;
}
return (int)(mark==0?number:-number);//最后根据mark标记的正负号来决定数字正负
}
注意边界判断
- 字符串的排列
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
public ArrayList<String> Permutation(String str) {
List <String> res = new ArrayList<String>();
if(str != null && str.length() >0){
PermutationHelp(str.toCharArray(),0,res);
Collections.sort(res); //按字典序 输出字符串数组。
}
return (ArrayList)res;
}
public void PermutationHelp(char[] chars, int index, List<String> list) {
if(index == chars.length -1){ //当递归交换到最后一个位置的时候，就看看list有么有这个字符串，没有的话就放进去。
String val = String.valueOf(chars);
if (!list.contains(val)) {//如果最后list没有这个string，因为可能交换后有重复的
list.add(val);
}
}
else {
for (int i = index; i < chars.length; i++) { //循环来执行交换操作，先交换，然后固定这个，下一个交换。最后要交换回来不要影响执行
swap(chars, index, i);
PermutationHelp(chars, index+1, list);//依次固定一个
swap(chars, index, i);
}
}
}
public void swap(char[] chars,int i, int j) {//交换数组中的两个位置中的值
char temp =chars[i];
chars[i] = chars[j];
chars[j] = temp;
}
网友评论