算法之常见字符串题目
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
leedcode344. 反转字符串
编写一个函数其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1
输入s = [“h”,“e”,“l”,“l”,“o”] 输出[“o”,“l”,“l”,“e”,“h”]
示例 2
输入s = [“H”,“a”,“n”,“n”,“a”,“h”] 输出[“h”,“a”,“n”,“n”,“a”,“H”]
方法一、双指针
// 第一种方法用temp来交换数值更多人容易理解些
class Solution {
public void reverseString(char[] s) {
int l = 0;
int r = s.length - 1;
while(l < r){
char temp = s[l];
s[l] = s[r];
s[r] = temp;
l++;
r--;
}
}
}
方法二、位运算
class Solution {
public void reverseString(char[] s) {
int l = 0;
int r = s.length - 1;
while (l < r) {
s[l] ^= s[r]; //构造 a ^ b 的结果并放在 a 中
s[r] ^= s[l]; //将 a ^ b 这一结果再 ^ b 存入b中此时 b = a, a = a ^ b
s[l] ^= s[r]; //a ^ b 的结果再 ^ a 存入 a 中此时 b = a, a = b 完成交换
l++;
r--;
}
}
}
leedcode541. 反转字符串 II
给定一个字符串 s 和一个整数 k从字符串开头算起每计数至 2k 个字符就反转这 2k 字符中的前 k 个字符。
如果剩余字符少于 k 个则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个则反转前 k 个字符其余字符保持原样。
示例 1
输入s = “abcdefg”, k = 2 输出“bacdfeg”
示例 2
输入s = “abcd”, k = 2 输出“bacd”
class Solution {
//满足一下条件
//1.从字符串开头算起每计数至2k个字符就反转2k个字符中的前k个字符。
//2.如果字符小于2k个但大于等于k个则反转前k个其余字符串保存不变
//3.如果字符少于k个则将剩余字符全部反转
//仔细观察第2个条件其实和第一个条件可以同时处理
public String reverseStr(String s, int k) {
char[] ch=s.toCharArray();
for(int i=0;i<ch.length;i=i+2*k){
//完成第1个和第二个条件
if(i+k<=ch.length){ //防止加到后面超出范围至于是<=可以带个数字进行例如abc此时i=0指向alength是3k是3,满足条件2需要进行反转
//进行反转
reserve(ch,i,i+k-1);//i+k-1是因为i从0开始然后reserve中i到i+k-1是左闭右闭
continue;//进行下一轮循环
}
//如果剩余字符小于k的话
reserve(ch,i,ch.length-1);//反转全部
}
//将字符数组转成字符串
return new String(ch);
}
//自定义反转函数
public void reserve(char[] s,int left,int right){
while(left<right){
char temp=s[left];
s[left]=s[right];
s[right]=temp;
left++;
right--;
}
}
}
leedcode151. 反转字符串中的单词
给你一个字符串 s 请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中单词间应当仅用单个空格分隔且不包含任何额外的空格。
示例 1
输入s = “the sky is blue” 输出“blue is sky the”
示例 2
输入s = " hello world " 输出“world hello”
解释反转后的字符串中不能存在前导空格和尾随空格。
示例 3
输入s = “a good example” 输出“example good a”
解释如果两个单词间有多余的空格反转后的字符串需要将单词间的空格减少到仅有一个。
class Solution {
//原字符串" hello world "
//删除多余空格"hello world"
//字符串反转"dlrow olleh"
//单词反转"world hello"
public String reverseWords(String s) {
char[] chars=s.toCharArray();
//去除首尾和中间多余的空格
char[] newchar=removeExtraSpaces(chars);
//反转字符串
reserve(newchar,0,newchar.length-1);
//单词反转
reserveWord(newchar);
return new String(newchar);
}
//和数组中移除元素的双指针方法很像
public char[] removeExtraSpaces(char[] chars){
//定义慢指针用于更新元素
int slow=0;
for(int hight=0;hight<chars.length;hight++){
//通过快指针来判断出空格的位置然后让慢指针来判断是否对其添加空格
if(chars[hight]!=' '){//说明到下一个单词
//因为首个位置不能是空格
if(slow!=0){
chars[slow]=' ';//此时快指针指向的不是空格慢指针指向的字符增加一个空格
slow++;//同时移动慢指针
}
//因为要hight++所以要判断hight<chars.length,当快指针不执行空格快慢指针同时移动
while(hight<chars.length&&chars[hight]!=' '){
chars[slow]=chars[hight];
slow++;
hight++;
}
}
}
//复制数组,新建一个数组将chars[slow]的元素复制过来
char[] newchar= new char[slow];//slow刚好是多移出1位所以数组长度是slow
/**
第一个参数是要被复制的数组
第二个参数是被复制的数字开始复制的下标
第三个参数是目标数组也就是要把数据放进来的数组
第四个参数是从目标数据第几个下标开始放入数据
第五个参数表示从被复制的数组中拿几个数值放到目标数组中
*/
System.arraycopy(chars,0,newchar,0,slow);
return newchar;
}
//反转字符串
public void reserve(char[] chars,int left,int right){
if (right >= chars.length) {
System.out.println("set a wrong right");
return;
}
while(right>left){
//方法一
// chars[left]^=chars[right];
// chars[right]^=chars[left];
// chars[left]^=chars[right];
//方法二
char temp=chars[left];
chars[left]=chars[right];
chars[right]=temp;
left++;
right--;
}
}
//反转单词
public void reserveWord(char[] chars){
int start=0;
//end <= s.length() 这里的 = 是为了让 end 永远指向单词末尾后一个位置这样我们最后能对start到end-1进行反转
for(int end=0;end<=chars.length;end++){
if(end==chars.length||chars[end]==' '){
end 每次到单词末尾后的空格或最后一个单词的后面,开始反转单词
reserve(chars,start,end-1);
//start位置为end位置加1比如end为空格位置start就为空格的后一个字符
start=end+1;
}
}
}
}
剑指 Offer 58 - II. 左旋转字符串
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如输入字符串"abcdefg"和数字2该函数将返回左旋转两位得到的结果"cdefgab"。
示例 1
输入: s = “abcdefg”, k = 2 输出: “cdefgab”
示例 2
输入: s = “lrloseumgh”, k = 6 输出: “umghlrlose”
示例 1
class Solution {
/**abcdefg k = 2
1.反转区间为前n的子串ba cdefg
2.反转区间为n到末尾的子串ba gfedc
3.反转整个字符串 cdefgab
*/
public String reverseLeftWords(String s, int n) {
char[] chars=s.toCharArray();
reserve(chars,0,n-1);
reserve(chars,n,chars.length-1);
reserve(chars,0,chars.length-1);
return new String(chars);
}
public void reserve(char[] chars,int left,int right){
while(left<right){
chars[left]^=chars[right];
chars[right]^=chars[left];
chars[left]^=chars[right];
left++;
right--;
}
}
}
leedcode459. 重复的子字符串
给定一个非空的字符串 s 检查是否可以通过由它的一个子串重复多次构成。
示例 1:
输入: s = “abab” 输出: true 解释: 可由子串 “ab” 重复两次构成。
示例 2:
输入: s = “aba” 输出: false
示例 3:
输入: s = “abcabcabcabc” 输出: true 解释: 可由子串 “abc” 重复四次构成。 (或子串 “abcabc”
重复两次构成。)
方法一移动匹配
class Solution {
//移动匹配
//判断字符串s是否由重复子串组成只要两个s拼接在一起里面还出现一个s的话就说明是由重复子串组成。
public boolean repeatedSubstringPattern(String s) {
String t=s+s;
//字符串截取substring是左闭右开的原则
//我们在判断 s + s 拼接的字符串里是否出现一个s的的时候要刨除 s + s 的首字符和尾字符
//这样避免在s+s中搜索出原来的s我们要搜索的是中间拼接出来的s
if(t.substring(1,t.length()-1).contains(s)){
return true;
}else{
return false;
}
}
}
方法二KMP
class Solution {
//kmp算法因为最长相等前后缀的规则当一个字符串由重复子串组成的最长相等前后缀不包含的子串就是最小重复子串
public boolean repeatedSubstringPattern(String s) {
if(s.length()==0){
return false;
}
int[] next=new int[s.length()];
//获取next数组也就是最长相等前后缀
getNext(next,s);
//如果s.length()%(s.length()-next[s.length()-1])==0,则说明数组的长度正好可以被 (数组长度-最长相等前后缀的长度) 整除说明该字符串有重复的子字符串。
if(next[s.length()-1]!=0&&s.length()%(s.length()-next[s.length()-1])==0){
return true;
}
return false;
}
public void getNext(int[] next,String s){
//初始化
int j=0;
next[0]=0;
for(int i=1;i<s.length();i++){
while(j>0&&s.charAt(i)!=s.charAt(j)){
//回退
j=next[j-1];
}
if(s.charAt(i)==s.charAt(j)){
j++;
}
next[i]=j;
}
}
}
小明的字符串
小明有两个字符串分别为 S,TS,T。
请你求出 TT 串的前缀在 SS 串中出现的最长长度为多少。
输入描述
输入包含两行每行包含一个字符串分别表示 S,T。保证 S,TS,T 只包含小写字母。
输出描述
输出共 11 行包含一个整数表示答案。
输入输出样例
示例 1
输入
aabba
abb
输出
3
示例 2
输入
aabba
aba
输出
2
使用KMP算法求得 TT 串的前缀在 SS 串中出现的最长长度
public class KmpTest {
static int sum=0;
static int[] next=new int[1000000];
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String s1 = scan.next();
String s2 = scan.next();
getNext(next,s2);
Kmp(s1,s2);
System.out.println(sum);
}
private static void Kmp(String s1, String s2) {
int j=0;
for(int i=0;i<s1.length();i++){
while(j>0&&s1.charAt(i)!=s2.charAt(j)){
j=next[j-1];
}
if(s1.charAt(i)==s2.charAt(j)){
j++;
}
//当j最长也就是 TT 串在 SS 串中出现的最长长度
sum=Math.max(j,sum);
//当j如果完全满足等于s2的长度时要记得返回不然i下次循环时比较j会越界
if(j==s2.length()){
return;
}
}
}
//求next数组获取最长相等前后缀
private static void getNext(int[] next, String s2) {
int j=0;
next[0]=0;
for(int i=1;i<s2.length();i++){
while(j>0&&s2.charAt(i)!=s2.charAt(j)){
j=next[j-1];
}
if(s2.charAt(i)==s2.charAt(j)){
j++;
}
next[i]=j;
}
}
}