字符串
344.反转字符串
编写一个函数，其作用是将输入的字符串反转过来。 输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1： 输入：["h","e","l","l","o"] 输出：["o","l","l","e","h"]
示例 2： 输入：["H","a","n","n","a","h"] 输出：["h","a","n","n","a","H"]
解答：
class Solution {
public void reverseString(char[] s) {
char c;
int n =s.length;
for(int i = 0; i < n/2; i++){
c = s[i];
s[i] = s[n - i - 1];
s[n - i - 1] = c;
}
}
}
//异或操作
class Solution {
public void reverseString(char[] s) {
int n =s.length;
for(int i = 0; i < n/2; i++){
s[i] ^= s[n - i - 1];
s[n - i - 1] ^= s[i];
s[i] ^= s[n - i -1];
}
}
}
541. 反转字符串 II
给定一个字符串 s 和一个整数 k，从字符串开头算起, 每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
示例:
输入: s = "abcdefg", k = 2 输出: "bacdfeg"
class Solution {
public String reverseStr(String s, int k) {
char[] ss = s.toCharArray();
int n = s.length()/k;
String res = new String("");
for(int i = 0; 2*i + 1 <= n; i++){
reverseString(ss, 2*i*k, k);
}
if(n%2 == 0){
reverseString(ss, k*n, s.length() - k*n);
}
return new String(ss);
}
public void reverseString(char[] ss , int start, int len) {
for(int i = 0; i < len/2; i++){
ss[i + start] ^= ss[start + len - i - 1];
ss[start + len - i - 1] ^= ss[i + start];
ss[i + start] ^= ss[start + len - i - 1];
}
}
}
替换数字
给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为 number。
例如，对于输入字符串 "a1b2c3"，函数应该将其转换为 "anumberbnumbercnumber"。
对于输入字符串 "a5b"，函数应该将其转换为 "anumberb"
输入：一个字符串 s,s 仅包含小写字母和数字字符。
输出：打印一个新的字符串，其中每个数字字符都被替换为了 number
样例输入：a1b2c3
样例输出：anumberbnumbercnumber
数据范围：1 <= s.length < 10000。
解答：
//费时费空间
import java.util.*;
class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
String s = in.nextLine();
String res = new String("");
char[] ss = s.toCharArray();
for(char c : ss){
if(c - '9' <= 0 && c - '0' >= 0){
res += "number";
} else{
res += String.valueOf(c);
}
}
System.out.println(res);
}
}
151.翻转字符串里的单词
给定一个字符串，逐个翻转字符串中的每个单词。
示例 1： 输入: "the sky is blue" 输出: "blue is sky the"
示例 2： 输入: " hello world! " 输出: "world! hello" 解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3： 输入: "a good example" 输出: "example good a" 解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
解答：
class Solution {
public String reverseWords(String s) {
char[] ss = s.toCharArray();
char[] res = new char[ss.length];
int cnt = -1;
int flag = 0;
//去除首尾以及中间多余空格
for(int i = 0; i < ss.length; i++){
if(ss[i] != ' '){
cnt++;
if(flag == -1){
res[cnt] = ' ';
cnt++;
}
res[cnt] = ss[i];
flag = 1;
} else if(flag == 1){
flag = -1;
}
}
//去除首尾以及中间多余空格(更加简洁)
// for(int i = 0; i < ss.length; i++){
// if(ss[i] != ' '){
// if(cnt != 0){
// res[cnt++] = ' ';
// }
// while(i < ss.length && ss[i] != ' ') res[cnt++] = ss[i++];
// }
// }
//反转整个字符串
reverseString(res , 0, cnt + 1);
//反转各个单词
char[] res1 = new char[cnt+1];
for(int i = 0,j = 0; i < cnt+1; i++){
res1[i] = res[i];
if(res[i] == ' '){
reverseString(res1 , j, i - j);
j = i+1;
}
if(i == cnt){
reverseString(res1 , j, i - j + 1);
j = i+1;
}
}
return new String(res1);
}
public void reverseString(char[] ss , int start, int len) {
for(int i = 0; i < len/2; i++){
ss[i + start] ^= ss[start + len - i - 1];
ss[start + len - i - 1] ^= ss[i + start];
ss[i + start] ^= ss[start + len - i - 1];
}
}
}
右旋字符串
字符串的右旋转操作是把 字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。
例如，对于输入字符串 "abcdefg" 和整数 2，函数应该将其转换为 "fgabcde"。
输入：输入共包含两行，第一行为一个正整数 k，代表右旋转的位数。第二行为字符串 s，代表需要旋转的字符串。
输出：输出共一行，为进行了右旋转操作后的字符串。
样例输入：
2
abcdefg
样例输出：
fgabcde
数据范围：1 <= k < 10000, 1 <= s.length < 10000;
解答：
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int len = Integer.parseInt(scanner.nextLine());
String s = scanner.nextLine();//next.Int()与next.Line()不能连用，next.Line()不忽略换行符，换行符会被作为next.Line()的值，除非专门加一个next.Line()吸收换行符
char[] ss = s.toCharArray();
Main m = new Main();
m.reverseString(ss, 0, ss.length);
m.reverseString(ss, 0, len);
m.reverseString(ss, len, ss.length - len);
System.out.println(new String(ss));
}
public void reverseString(char[] ss , int start, int len) {
for(int i = 0; i < len/2; i++){
ss[i + start] ^= ss[start + len - i - 1];
ss[start + len - i - 1] ^= ss[i + start];
ss[i + start] ^= ss[start + len - i - 1];
}
}
}
28. 实现 strStr()
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从 0 开始)。如果不存在，则返回 -1。
示例 1: 输入: haystack = "hello", needle = "ll" 输出: 2
示例 2: 输入: haystack = "aaaaa", needle = "bba" 输出: -1
说明: 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
解答：
//滑动窗口
class Solution {
public int strStr(String haystack, String needle) {
char[] ss = haystack.toCharArray();
char[] c = needle.toCharArray();
int fast = 0, slow = 0;
for(; fast < ss.length; fast++){
if(ss[fast] == c[slow]) slow++;
else{
fast -= slow;
slow = 0;
}
if(slow == c.length) return fast - slow + 1;
}
return -1;
}
}
//kmp next前缀表都减了1
class Solution {
public int strStr(String haystack, String needle) {
char[] ss = haystack.toCharArray();
char[] c = needle.toCharArray();
int[] next_c = getnext(c);
int j = -1;
for(int i = 0; i < ss.length; i++){
while(j >= 0 && ss[i] != c[j+1]){
j = next_c[j];
}
if(ss[i] == c[j+1]){
j++;
}
if(j == c.length - 1) return i - j;
}
return -1;
}
public int[] getnext(char[] c){
int[] next = new int[c.length];
int j = -1;
next[0] = j;
for(int i = 1; i < next.length; i++){
while(j >= 0 && c[i] != c[j+1]){
j = next[j];
}
if(c[i] == c[j+1]){
++j;
}
next[i] = j;
}
return next;
}
}
459.重复的子字符串
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过 10000。
示例 1:
- 输入: "abab"
- 输出: True
- 解释: 可由子字符串 "ab" 重复两次构成。
示例 2:
- 输入: "aba"
- 输出: False
示例 3:
- 输入: "abcabcabcabc"
- 输出: True
- 解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
解答：
class Solution {
public boolean repeatedSubstringPattern(String s) {
int len = s.length();
if(len <= 1) return false;
char[] ss = s.toCharArray();
int[] next_ss = getnext(ss);
if(next_ss[len-1] > 0 && len%(len - next_ss[len-1]) == 0) return true;
return false;
}
public int[] getnext(char[] ss){
int[] next = new int[ss.length];
int j = 0;
next[0] = j;
for(int i = 1; i < ss.length; i++){
while(j > 0 && ss[j] != ss[i]){
j = next[j-1];
}
if(ss[j] == ss[i]){
j++;
}
next[i] = j;
}
return next;
}
}
总结
双指针法是字符串处理的常客
KMP 算法是字符串查找最重要的算法
其他
925.长按键入
你的朋友正在使用键盘输入他的名字 name。偶尔，在键入字符 c 时，按键可能会被长按，而字符可能被输入 1 次或多次。
你将会检查键盘输入的字符 typed。如果它对应的可能是你的朋友的名字（其中一些字符可能被长按），那么就返回 True。
解答：
class Solution {
public boolean isLongPressedName(String name, String typed) {
int first = 0, second = 0;
while(first < name.length() && second < typed.length()){
if(name.charAt(first) == typed.charAt(second)){
first++;
second++;
}else if(second > 0 && typed.charAt(second) == typed.charAt(second-1)){
second++;
}else{
return false;
}
}
while(second < typed.length() && typed.charAt(second) == typed.charAt(second-1)) second++;
return first == name.length() && second == typed.length();
}
}
844.比较含退格的字符串
给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
解答：
// 代码太复杂，可以在学习一下其他的方法
class Solution {
public boolean backspaceCompare(String s, String t) {
int first = s.length() - 1;
int second = t.length() - 1;
while(first >= 0 || second >= 0){
int backspaceCount = 0;
while(first >= 0 && s.charAt(first) == '#'){
first--;
backspaceCount++;
}
while(backspaceCount > 0 && first >= 0){
if(s.charAt(first) == '#') backspaceCount++;
else backspaceCount--;
first--;
}
backspaceCount = 0;
while(second >= 0 && t.charAt(second) == '#'){
second--;
backspaceCount++;
}
while(backspaceCount > 0 && second >= 0){
if(t.charAt(second) == '#') backspaceCount++;
else backspaceCount--;
second--;
}
if((first >= 0 && s.charAt(first) == '#') || (second >= 0 && t.charAt(second) == '#')) continue;
if(first >= 0 && second >= 0){
if(s.charAt(first) != t.charAt(second)) return false;
else{
first--;
second--;
}
}
else if(second >= 0 || first >= 0) return false;
else return true;
}
return true;
}
}