前言
Leetcode541/151/28
一、541题（反转字符串）
题目描述：
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
题解
mine
class Solution {
public String reverseStr(String s, int k) {
char[] nums = s.toCharArray();
int i=nums.length;
int j=0;
while(i>=2*k){
i = i-2*k;
reverse(nums,j,j+k-1);//反转2*k长度前k个
j = j+2*k;//下一组的起点数索引
}
if(i>k){
//剩余字符大于k，反转前k
reverse(nums,j,j+k-1);
}else{
reverse(nums,j,j+i-1);
}
//return Arrays.toString(nums);//这个是输出nums数组的遍历
return new String(nums);
}
//反转nums数组的[m,n]字符串
public void reverse(char[] nums,int m, int n){
int left=m,right=n;
char tmp;
while(left<right){
tmp=nums[left];
nums[left] = nums[right];
nums[right] = tmp;
//每次都掉了这两句
left++;
right--;
}
}
}
算法思路：写一个反转数组nums的[m,n]区间的字符串的方法reverse()。然后每隔2*k个串调用一次，剩余的串再根据具体情况调用一次reverse()。
易错点：
- 基础错误，每次都忘记写left++和right–。
- String和char互转（忘记了）：
String s；
char[] nums = s.toCharArray();//String转char[]
return new String(nums);//char[]转String
二、151题（翻转字符串里的单词）
题目描述：
给定一个字符串，逐个翻转字符串中的每个单词。
示例 1：
输入：s = “the sky is blue”
输出：“blue is sky the”
示例 2：
输入：s = " hello world "
输出：“world hello”
解释：反转后的字符串中不能存在前导空格和尾随空格。
示例 3：
输入：s = “a good example”
输出：“example good a”
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。
题解1
mine
class Solution {
public String reverseWords(String s) {
char[] nums1 = s.toCharArray();
char[] nums2 = new char[nums1.length];
int left=0,right=0,k=nums1.length-1;
while(left<nums1.length){
//保证left指向单词的第一个字母
if(nums1[left]==' '){
left++;
continue;
}
right = left;
while(right<nums1.length&&nums1[right]!=' '){
right++;
}
//[left,right)是第一个单词，填入到nums2中,长度为j-i
for(int i=right-1;i>=left;i--){
nums2[k--] = nums1[i];
}
if(right<nums1.length){
//表示可以前加空格，不会发生数组出位
nums2[k--] = ' ';
}
left = right+1;
}
//拷贝数组前闭后开
left = 0;
while(nums2[left]=='\u0000'||nums2[left]==' '){
left++;
}
char[] ans = Arrays.copyOfRange(nums2, left, nums2.length);
return new String(ans);
}
}
算法思路：
- 用[left,right)来标注一个单词，然后按照(right->left)方向填入新数组的末尾，并附加上一个空格。
- 处理开头空格：left一定要指向单词的第一个字母，如果是空格，就left++。
- 处理末尾空格：不用处理，如果最后一个单词末尾有多个空格，left会一直往后移动直至走到nums.length跳出循环。
- 处理中间多个空格：假设当前找到了一个单词[left,right)，此时right指向的要么是nums.length处，要么是空格，所以让left=right+1。然后会开始新的循环，那么就回到了“处理开头空格”，left会一直移动，直至找到新单词的第一个字母。
- 所以其实，上述三种空格特殊情况，都是靠如下代码解决的：
while(left<nums1.length){
//保证left指向单词的第一个字母
if(nums1[left]==' '){
left++;
continue;
}
.....
}
注意点：
- 注意看示例，有很多种情况。
- 代码实现：是用和nums1等长的数组num2存储的，最后开头部分可能有空，以及多余的一个空格，所以也要处理：
while(nums2[left]=='\u0000'||nums2[left]==' '){
left++;
}
题解2
在这里插入代码片
三、28题（实现 strStr()）
题目描述：
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1: 输入: haystack = “hello”, needle = “ll” 输出: 2
示例 2: 输入: haystack = “aaaaa”, needle = “bba” 输出: -1
解法1
暴力
class Solution {
public int strStr(String haystack, String needle) {
char[] total = haystack.toCharArray();
int k=needle.length();
for(int i=0;i<=total.length-k;i++){
String s = new String(total,i,k);
if(s.equals(needle)){
return i;
}
}
return -1;
}
}
解法2
见KMP算法文章，其实这道题想考察的是KMP算法
四、459题（重复的子字符串）
题目描述：
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
示例 1:
输入: “abab”
输出: True
解释: 可由子字符串 “ab” 重复两次构成。
在这里插入代码片
总结
- 541简单。
- 替换数字也很简单，如果要原地转换的话，要点就是从后往前转。比如"a1b"变成"a number b"，从后往前遍历，遍历到’b’扔到数组最后，遍历到’1’，数组末尾’b’前面加上"number"。但没什么太大必要，直接两个数组顺着填就好了。
- 151题有点坑，这题要把示例看全。
- 右旋字符串，即把字符串尾部的若k个字符转移到字符串的前面，如"abcdefg" 和 k=2，函数应该将其转换为 “fgabcde”。思路是“全部反转+部分翻转”，先全部翻转变为"gfedcba"，然后把前两个翻转，后五个翻转，就变成答案"fgabcde"。
- 字符串JAVA版本比C++简化了很多，总觉得意义不是特别大了，C++的字符串可以变化，考点是O(1)空间变化，JAVA开辟新空间有点暴力解法的意思了，稍微难一点可能就是一些细节的处理。
- 28题KMP算法。