新网站注册,高唐住房建设局网站,阳江网络问政平台新闻发布会,网页制作与设计网课字符串 字符串可能在算法处理上面和数组是类似的#xff0c;但是String和数组的数据结构还是有一些不一样的 1、反转字符串
344. 反转字符串 - 力扣#xff08;LeetCode#xff09;
双指针的经典应用#xff0c;两个指针同时向中间移动
public void reverseString(char[…字符串 字符串可能在算法处理上面和数组是类似的但是String和数组的数据结构还是有一些不一样的 1、反转字符串
344. 反转字符串 - 力扣LeetCode
双指针的经典应用两个指针同时向中间移动
public void reverseString(char[] s) {for(int i 0,j s.length - 1; i s.length/2; i,j--){char tmp s[i];s[i] s[j];s[j] tmp;}
}2、反转字符串2
541. 反转字符串 II - 力扣LeetCode 这个题就是要求复杂一些需要注意的就是不要上来用for循环就想着 i。应该是i 2k每次只是反转i 到 ik可以单独写一个方法注意一般编程语言中都是左闭右开的所以是不包括 ik的但是需要有一个条件if ( ik s.length )不能超过数组长度了这个if里判断的是最后剩余的部分是大于k的如果不大于k的也需要被考虑到所以在上面 if 的语句内需要加上一个continue
public String reverseStr(String s, int k) {char[] arr s.toCharArray(); // 0.需要学会怎么将字符串转成数组for(int i 0; i arr.length; i (2*k)){ // 1. 每隔 2k 个字符的前 k 个字符进行反转if(i k arr.length){reverse(arr,i,ik-1); // 2. 剩余字符小于 2k 但大于或等于 k 个则反转前 k 个字符continue;}reverse(arr,i,arr.length-1); // 3. 剩余字符少于 k 个则将剩余字符全部反转}return new String(arr);
}
//对第i到第ik进行反转
public void reverse(char[] s,int i,int j){for(int m i,n j; m n; m,n--){char tmp s[m];s[m] s[n];s[n] tmp;}
}3、翻转字符串⾥的单词较为综合
151. 反转字符串中的单词 - 力扣LeetCode 这个题复杂在空格的位置是不确定的单词的前面中间后面都可能有。但是我们最后的结果中不能包含额外空格 可以首先对整个字符串进行一次反转这样单词的对应位置就是正确的了 之后再对每一个单词再进行单独的反转 需要注意的就是对空格的处理 而对空格的处理想到了之前总结数组部分中的移动元素这一个题用双指针解决的问题 但是在用双指针去移动元素的过程中需要注意最后需要重新获取我们需要的部分只要0-slow部分
class Solution {public String reverseWords(String s) {// 1.去除首尾以及中间多余空格char[] arr s.toCharArray();arr removeSpace(arr);// 2.反转整个字符串reverseString(arr, 0, arr.length - 1);// 3.反转各个单词reverseEachWord(arr);return new String(arr); }//用 快慢指针 去除首尾以及中间多余空格可参考数组元素移除的题解private char[] removeSpace(char[] arr) {int slow 0;for(int fast 0; fast arr.length; fast){if(arr[fast] ! ){ //遇到非空格就处理即删除所有空格。if(slow ! 0) //手动控制空格给单词之间添加空格 slow ! 0说明不是第一个单词需要单词前添加空格arr[slow] ; while(fast arr.length arr[fast] ! )arr[slow] arr[fast];}}//这里需要注意的是最后需要重新获取我们需要的部分只要0-slow部分char[] newChars new char[slow];System.arraycopy(arr, 0, newChars, 0, slow);return newChars;}//双指针实现指定范围内字符串反转public void reverseString(char[] arr, int start, int end) {while (start end) {char tmp arr[start];arr[start] arr[end];arr[end] tmp;start;end--;}}//单词反转private void reverseEachWord(char[] arr) {int start 0;//end s.length() 这里的 是为了让 end 永远指向单词末尾后一个位置这样 reverse 的实参更好设置for (int end 0; end arr.length; end) {// end 每次到单词末尾后的空格或串尾,开始反转单词if (end arr.length || arr[end] ) {reverseString(arr, start, end - 1);start end 1;}}}}4、KMP
目标是对目标文本串进行模式匹配给定一个文本串和一个模式串去寻找文本串中有无模式串出现
这里的关键是找到模式串的最长相等前后缀
模式串aabaaf
那么a0、aa1、aab0、aaba1、aabaa2、aabaaf0 所以如果模式串aabaaf 的next数组就是[010120]
这就说明比如在匹配到模式串5位置如果不匹配就需要按照前面一个字符的next数组元素值去跳到模式串的序号2的位置接替f位置 next数组构造过程 需要两个指针i 指向后缀末尾位置j 指向前缀末尾位置同时代表最长相等的前后缀长度 首先初始化 让 j 0此时next[0] 0。j直接初始化为0是因为它是前缀的一个末尾而 i 的初始化是放在for循环中for(int i 1;i长度i) 如果i 和 j 不相等那就需要让j 进行回退是看它前一位的next数组元组其实也就是类似在实际匹配过程中使用next数组一样 但是不能一直回退前提是j 0 回退是一个连续的过程所以“前提是j 0”这个是while中不是if中 如果i 和 j 相等让j同时更新next数组值next[i] j
private 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(j) ! s.charAt(i)) j next[j - 1];if (s.charAt(j) s.charAt(i)) j;next[i] j; }
}整体代码 class Solution {//前缀表不减一Java实现public int strStr(String haystack, String needle) {if (needle.length() 0) return 0;int[] next new int[needle.length()];getNext(next, needle);int j 0;for (int i 0; i haystack.length(); i) {while (j 0 needle.charAt(j) ! haystack.charAt(i)) j next[j - 1];if (needle.charAt(j) haystack.charAt(i)) j;if (j needle.length()) return i - needle.length() 1;}return -1;}private 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(j) ! s.charAt(i)) j next[j - 1];if (s.charAt(j) s.charAt(i)) j;next[i] j; }}
}5、重复的子字符串
459. 重复的子字符串 - 力扣LeetCode 有两种思路 比较巧的思路是如果两个相同字符串s拼接起来并移除第一个和最后一个字符。如果 s 是该字符串的子串那么 s 就满足题目要求。[这个是可以证明的不过比较难理解] 下面代码的含义是检查字符串 s 在自身重复连接后即 s s中从第二个 s 开始的位置是否不等于 s 字符串的长度。如果不相等则返回 true否则返回 false。 class Solution {public boolean repeatedSubstringPattern(String s) {return (s s).indexOf(s, 1) ! s.length(); //从索引位置 1 开始搜索。搜索第一个 s 出现的位置。这意味着它将忽略新字符串的第一个字符从第二个字符开始搜索。如果在去除掉首元素后去查找有无s这个子串查找到的的起始位置是s.length()那就说明这个是只能在后面拼接上的那个s匹配上并不能靠中间部分匹配上}
}用kmp【这个方法暂时还未具体实践】
