- KMP算法
- 给一串英文语句，让你对语句进行翻转(this is a word -> word a is this)
- 字符串左旋
- 一个字符串中找到最开始出现的不重复的字符
- 给定一个只包括 ‘(’，’)'的字符串，判断字符串是否有效。注：空字符串属于有效字符串
- 俩大数相加
- 验证回文串 ； 找出 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
基本思想是：
-
从主串的第一个字符起与子串的第一个字符进行比较，若相等，则继续逐对字符进行后续的比较；
-
若不相等，则从主串第二个字符起与子串的第一个字符重新比较，以此类推， 直到子串中每个字符依次和主串中的一个连续的字符序列相等为止，此时称为匹配成功。
-
如果不能在主串中找到与子串相同的字符序列，则匹配失败。
public static int bruteForce(String s,String p) {
int index = -1; //成功匹配的位置，匹配不到返回-1
int sLength = s.length();
int pLength = p.length();
if(sLength < pLength) {
System.out.println("Error.The main string is greater than the sub string length.");
return -1;
}
int i = 0;//当前遍历主串的下标
int j = 0;//当前遍历字串的下标
//暴力遍历串
while(i < sLength && j < pLength) {
if(s.charAt(i) == p.charAt(j)) {
//字符相等，指针后移
i++;
j++;
}else {
//主串回到上次匹配的字符的下一个字符，子串从0开始
i = i - j + 1;//主串需要归还i向前走的j步，然后加1
j = 0; //子串无须关注向前走了多少步，直接归零
}
}
if(j == pLength) { //匹配成功
index = i - j;
System.out.println("Successful match,index is:" + index);
} else {// 匹配失败
System.out.println("Match failed.");
}
return index;
}KMP的核心思想是主串不回溯。模式串少回溯。
”Harry”的真前缀包括{”H”, ”Ha”, ”Har”, ”Harr”}
”Potter”的真后缀包括{”otter”, ”tter”, ”ter”, ”er”, ”r”}
字符串既是自身的前缀也是自身的后缀，不包含自身的，则称为真前缀和真后缀。
实现KMP算法的核心在于PMT （部分匹配表，Partial Match Table）这个数据结构。对于字符串“abababca” ，它的PMT如下表示：
| char | a | b | a | b | a | b | c | a |
|---|---|---|---|---|---|---|---|---|
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| PMT | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |
PMT 中记录的是模式串“abababca” 截止index位置的子串，即[0,index]区间内构成的子串，前缀集合与后缀集合的交集中最长元素的长度。 例如：i = 4处，子串为“ababa” ，前缀集合{"a","ab","aba,"abab"}, 后缀集合 {"baba","aba","ba","a"} , 该处PMT值就为“aba”的长度3.
为了方便失配时回溯， 我们不直接使用PMT数组，而是将PMT数组向后偏移一位。我们把新得到的这个数组称为next数组。在把PMT进行向右移时，第0位的值，我们将其设成了-1，i 对应的值，就是 i 处的字符之前的子串的“前后缀最大交集元素个数”，假设是m。这样，一旦在 i 位置发生失配（该位置之前都是匹配成功的），不需要从模式串头再重新匹配，而是“跳过”前面 m个元素的长度，或者说模式串向右移动 i- m 位，然后接着比较。
next数组：
| char | a | b | a | b | a | b | c | a | |
|---|---|---|---|---|---|---|---|---|---|
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| PMT | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 | |
| next | -1 | 0 | 0 | 1 | 2 | 3 | 4 | 0 |
例如在 i= 4处 字符 ‘a’ 失配，对应的next[4] = 2 表示 "abab" 前后缀最大公共子集长度为2，即{"a","ab","aba"} ∩ {“bab”,"ab","b"} = "ab" 。模式串回溯、新一轮比较时，0，1位置的“ab” 就直接略过比较，从i=2位置开始。从效果上看，就是前缀的“ab” ，移动到了后缀"ab" 的位置。
public static void kmp(String s ,String p) {
int[] next = buildNext(p);//姑且设定有个函数，可以提供next[]数组，告知失配时模式串最多右移位数
int index = -1;//返回成功匹配的位置，没查找到返回-1
int sLength = s.length();
int pLength = p.length();
if(sLength < pLength) {
return;
}
int i = 0;
int j = 0;
while(i < sLength && j <pLength) {
// j==-1 处理第0个位置的元素失配的情况
if(j == -1 || s.charAt(i) == p.charAt(j)) {
i++;
j++;
}else {
// 主串 i 不变
j = next[j];//表示在j位置失配时，查找一下next表中记录的，前后缀相交个数，作为下次匹配时的起始下标。
}
}
if(j >= pLength) {
index = i -j;
System.out.println("KMP Successful match,index is:" + index);
}else {
System.out.println("Match failed.");
}
long endTime = System.currentTimeMillis();
System.out.println("KMP cost time = "+(endTime - beginTime));
}每个字符串都有固定的next数组，它可以看作是字符串本身关于前后缀的一种特性。但是怎么通过程序得出模式串的这种特性 -- 构造出next数组呢？
对于位置i ， 其前缀是固定的，后缀是相对的。
因为，前缀第一个字符固定是从0开始的，
而变量 i 对应的字符，表示的是后缀第一个字符，也就是最小真后缀。
前缀 j 即 i-1 从0开始与之匹配，理想状态下，最大真前缀与最大真后缀完全相同的，比如串 “aaaaaa” , j一直指向最大真前缀最后一个字符 ， 可以一直递增，即next[i] 可以一直递增。如果失配，表示最大真前缀与最大真后缀不匹配了， 要退而求其次 ， 仍通过kmp的算法思想，回溯尝试找到次大真前缀与之匹配，直到j 回溯为 0，如果仍然匹配失败，说明最小真前缀与最小真后缀不匹配，本轮查找前后缀公共子集结束。
//构造next表
private static int[] buildNext(String p) {
int pLength = p.length();
int[] next = new int[pLength]; //next数组跟串本身是等长的
next[0] = -1; // 把第0 位置空出来，直接赋值 -1 ；从而实现PMT表右移；
int i = 0; // 前缀
int j = -1; // 后缀
while (i < pLength - 1) {
if (j == -1 || p.charAt(i) == p.charAt(j)) {//匹配结果存到next[i++]位置
i++;
j++;
next[i] = j; // next[1] = 0；后缀第二个字符 i = 1 与 前缀第一个字符 j = 0 ，根据next表的定义，仍记入0
// next[i] : 连续匹配成功， i 位置之前，连续匹配成功字符数
} else {
j = next[j]; // 如果失配，按照kmp算法思想，取出j处字符之前的字串，前后缀最大交集数，再与i位置字符（最小真后缀）比较，
}
}
return next;
}对于特殊模式串，x处发生失配，但是子串“aaaaa” 前缀后缀都是相同，按照之前j=next[j] ,那 j 就要5，4，3，2，1这样依次回溯比对，这是没有必要的。新一轮应直接从头开始比对。
//构造next表
public static int[] buildNext(String p) {
int pLength = p.length();
int[] next = new int[pLength];
next[0] = -1; // 把第0 位置空出来，直接赋值 -1 ；从而实现PMT表右移；
int i = 0; // 后缀
int j = -1; // 前缀
while (i < pLength - 1) {
if (j == -1 || p.charAt(i) == p.charAt(j)) {
i++;
j++;
if (p.charAt(i) != p.charAt(j)) { //
next[i] = j;
} else {
next[i] = next[j];
}
} else {
j = next[j]; // 如果失配，取出成功上轮匹配成功时保存的数，子串回溯到 next[j]
}
}
for (int index = 0; index < next.length; index++) {
System.out.println(" " + index + " = " + next[index]);
}
return next;
}二度反转
/**
* 字符串反转，双指针法
* 1. 加工源字符串，去除首尾及单词间多余空格
* 2. 对整个串反转 -- 首尾两个指针不断交换指向的字符，同步向中间走
* 3. 二度反转 -- 对每个单词进行反转
*
* @param s
* @return
*/
public String reverseWords(String s) {
StringBuilder sb = trimSpace(s);
reverse(sb, 0, sb.length() - 1);
//查找单词位置
reverseWord(sb);
return sb.toString();
}
private StringBuilder trimSpace(String s) {
s = s.trim();//去首尾空格
StringBuilder trimStr = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == ' ' && (i > 0 && s.charAt(i - 1) == ' ')) {
//排除单词间多余空格
continue;
}
trimStr.append(c);
}
return trimStr;
}
private void reverseWord(StringBuilder sb) {
int n = sb.length();
int start = 0, end = 1;
while (end < n) {
//单词末尾
while (end < n && sb.charAt(end) != ' ') {
end++;
}
reverse(sb, start, end - 1);//end处是空格，不参与反转
end++;
start = end;
}
}
private void reverse(StringBuilder sb, int start, int end) {
int head = start;
int tail = end;
while (head < tail) {
char tmp = sb.charAt(head);
sb.setCharAt(head, sb.charAt(tail));
sb.setCharAt(tail, tmp);
head++;
tail--;
}
}
给一串英文语句，让你对语句进行翻转(this is a word -> word a is this)。
解释:
-
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
-
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
/**
* 单词反转
* 输入: " hello world! "
* 输出: "world! hello"
* 解释: 1. 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
* 2. 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
*/
public String reverseWords(String s) {
if (s == null) {
return "";
}
StringBuilder res = new StringBuilder();
String[] splitArr = s.trim().split(" ");
int length = splitArr.length;
for (int i = length -1 ;i >= 0; i--){
if ("".equals(splitArr[i])){
continue;
}
res.append(splitArr[i]);
if (i > 0){
res.append(" ");
}
}
return res.toString();
}
示例 1：
输入: s = "abcdefg", k = 2
输出: "cdefgab"
/**
* 字符串左旋
* 思想：
* 以index = n 为中轴，分别读两次源字符串s，通过StringBuilder res拼接起来
*
* @param s 源字符串
* @param n 旋转中轴（将下标n之前的元素旋转）
* @return 结果字符串 res
*/
public String reverseLeftWords(String s, int n) {
StringBuilder res = new StringBuilder();
if (s == null){
return null;
}
for (int i = n; i < s.length(); i++) {
res.append(s.charAt(i));
}
for (int i = 0; i < n; i++) {
res.append(s.charAt(i));
}
return res.toString();
}
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
示例:
s = "abaccdeff" 返回 "b"
s = "" 返回 " "
限制：
0 <= s 的长度 <= 50000
/**
* 循环一遍源字符串，按照字符出现的顺序，构建字典
*
* @param s
* @return
*/
public char firstUniqueChar(String s) {
HashMap<Character, Boolean> dic = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
dic.put(c, !dic.containsKey(c));//已经存在了相同字符的话，置为false。
}
//因为要求s中第一个出现的不重复字符，所以要再遍历一遍s
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (dic.get(c)){
return c;
}
}
return "";
}
关于“第一个出现的不重复字符” ，字符串长度是无限的，但是组成字符串的小写字母是固定的不多于26个。如果选用的字典数据结构是有序存储的话，用就可以遍历一次字典取代遍历源字符串
public char firstUniqChar(String s) {
if (s == null){
return ' ';
}
LinkedHashMap<Character, Boolean> dic = new LinkedHashMap<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
dic.put(c, !dic.containsKey(c));//已经存在了相同字符的话，置为false。
}
//字典是有序的，所以只要查找字典中 value 为true对应的key即可。
for (Map.Entry<Character, Boolean> entry : dic.entrySet()) {
if (entry.getValue()){
return entry.getKey();
}
}
return ' ';
}
描述：
给定一个只包括 ‘(’，’)'的字符串，判断字符串是否有效。注：空字符串属于有效字符串
示例 1:输入: "(())"输出: true 实例 2： 输入: "())("输出: false 12345678
思路：
读到左括号则压栈，读到右括号，尝试与栈顶左括号进行匹配，匹配成功则弹出
/**
* 1. 括号匹配
* 读到左括号则压栈，读到右括号，尝试与栈顶左括号进行匹配，匹配成功则弹出
* [](){}
* 判定条件：栈为空
*/
public static boolean isParenthesesValid(String bracketsStr){
Stack<Character> charStack = new Stack<>();
char c = ' ';
for (int i = 0; i < bracketsStr.length(); i++) {
c = bracketsStr.charAt(i);
if (c == '{' || c == '[' || c =='('){
charStack.push(c);
}else{
if (charStack.empty()){
return false;
}
//check top char in stack
char topChar = charStack.peek();
//the target char match the top char
char matchChar = ' ';
if (topChar == '{'){
matchChar = '}';
}else if (topChar == '['){
matchChar = ']';
}else {
matchChar = ')';
}
if (c != matchChar){
break;
}
charStack.pop();
}
}
if (charStack.empty()){
return true;
}
return false;
}
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。
提示：
num1 和num2 的长度都小于 5100 num1 和num2 都只包含数字 0-9 num1 和num2 都不包含任何前导零 你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/add-strings 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
/**
* 大数相加
* 模拟列竖式，双指针从两个串的末位同时向首部移动，同时一个变量记录是否有满10进位
* 计算结果用StringBuilder 记录，结束后反转一下
*
* @param num1
* @param num2
* @return
*/
public String addStrings(String num1, String num2) {
int i = num1.length() - 1;
int j = num2.length() - 1;
int add = 0; //记录上一轮计算是否有进位
StringBuilder ans = new StringBuilder();
while (i >= 0 || j >= 0 || add > 0) {
int x = i >= 0 ? num1.charAt(i) - '0' : 0;
int y = j >= 0 ? num2.charAt(j) - '0' : 0;
int sum = x + y + add;
ans.append(sum % 10);
add = sum / 10;
i--;
j--;
}
//计算过程是个十百千...的顺序，结果需要是从高到低的顺序
ans.reverse();
return ans.toString();
}
36进制加法
思想类似， 用0~9,a-z 共36位，满36进位
描述：
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
示例2:
输入: "race a car"
输出: false
思路：
一开始先建立两个指针，left 和 right , 让它们分别从字符的开头和结尾处开始遍历整个字符串。
如果遇到非字母数字的字符就跳过，继续往下找，直到找到下一个字母数字或者结束遍历，如果遇到大写字母，就将其转为小写。
当左右指针都找到字母数字时，可以进行比较的时候，比较这两个字符，如果相等，则两个指针向它们的前进方向挪动，然后继续比较下面两个分别找到的字母数字，若不相等，直接返回 false。
/**
* 验证回文串
* 双指针分别从头、尾同步向中间移动（只考虑字母和数字字符，跳过无效字符）
* ，若两指针总指向想等的字符则为回文串；
*
* @param s
* @return
*/
public boolean isPalindrome(String s) {
if (s.length() == 0)
return true;
int l = 0, r = s.length() - 1;
while (l <= r) {
char left = s.charAt(l);
char right = s.charAt(r);
if (!isValidChar(left)) {
l++;
continue;
}
if (!isValidChar(right)) {
r--;
continue;
}
if (Character.toLowerCase(left) == Character.toLowerCase(right)) {
l++;
r--;
continue;
}
return false;
}
return true;
}
private boolean isValidChar(char c) {
return c >= '0' && c <= '9' || c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z';
}