反转字符串
使用数组
public void reverse(char[] ch, int i, int j) {for (; i < j; i++, j--) {char temp = ch[i];ch[i] = ch[j];ch[j] = temp;}
使用SringBuilder
public void reverse(StringBuilder sb, int left, int right) {while (left < right){char temp = sb.charAt(left);sb.setCharAt(left, sb.charAt(right));sb.setCharAt(right, temp);left++;right--;}}
344. 反转字符串
使用前后指针两指针逐步逼近,临界条件是left < right
class Solution {public void reverseString(char[] s) {int left = 0;int right = s.length - 1;//if (s.length == 0){//数组长度为0时,防止错误 *没必要,逻辑已经覆盖// right = 0;//}while (left < right){char temp = s[left];s[left] = s[right];s[right] = temp;left++;right--;}}}
541. 反转字符串 II
考虑先转换成数组然后好运算
// 解法3class Solution {public String reverseStr(String s, int k) {char[] ch = s.toCharArray();// 1. 每隔 2k 个字符的前 k 个字符进行反转for (int i = 0; i< ch.length; i += 2 * k) {// 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符if (i + k <= ch.length) {reverse(ch, i, i + k -1);continue;}// 3. 剩余字符少于 k 个，则将剩余字符全部反转reverse(ch, i, ch.length - 1);}return new String(ch);}// 定义翻转函数public void reverse(char[] ch, int i, int j) {for (; i < j; i++, j--) {char temp = ch[i];ch[i] = ch[j];ch[j] = temp;}}}
//解法一
class Solution {
public String reverseStr(String s, int k) {
StringBuffer res = new StringBuffer();
int length = s.length();
int start = 0;
while (start < length) {
// 找到k处和2k处
StringBuffer temp = new StringBuffer();
// 与length进行判断，如果大于length了，那就将其置为length
int firstK = (start + k > length) ? length : start + k;
int secondK = (start + (2 * k) > length) ? length : start + (2 * k);
//无论start所处位置，至少会反转一次
temp.append(s.substring(start, firstK));
res.append(temp.reverse());
// 如果firstK到secondK之间有元素，这些元素直接放入res里即可。
if (firstK < secondK) { //此时剩余长度一定大于k。
res.append(s.substring(firstK, secondK));
}
start += (2 * k);
}
return res.toString();
}
}
//解法二（似乎更容易理解点）
//题目的意思其实概括为 每隔2k个反转前k个，尾数不够k个时候全部反转
class Solution {
public String reverseStr(String s, int k) {
char[] ch = s.toCharArray();
for(int i = 0; i < ch.length; i += 2 * k){
int start = i;
//这里是判断尾数够不够k个来取决end指针的位置
int end = Math.min(ch.length - 1, start + k - 1);
//用异或运算反转
while(start < end){
ch[start] ^= ch[end];
ch[end] ^= ch[start];
ch[start] ^= ch[end];
start++;
end--;
}
}
return new String(ch);
}
}
剑指 Offer 05. 替换空
因为String是定长的不支持拓展,利用stringbuilder 不过需要额外的空间
class Solution {
public String replaceSpace(String s) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == ' '){
sb.append("%20");
}else {
sb.append(ch);
}
}
return sb.toString();
}
}
//使用一个新的对象，复制 str，复制的过程对其判断，是空格则替换，否则直接复制，类似于数组复制
public static String replaceSpace(StringBuffer str) {
if (str == null) {
return null;
}
//选用 StringBuilder 单线程使用，比较快，选不选都行
StringBuilder sb = new StringBuilder();
//使用 sb 逐个复制 str ，碰到空格则替换，否则直接复制
for (int i = 0; i < str.length(); i++) {
//str.charAt(i) 为 char 类型，为了比较需要将其转为和 " " 相同的字符串类型
//if (" ".equals(String.valueOf(str.charAt(i)))){
if (s.charAt(i) == ' ') {
sb.append("%20");
} else {
sb.append(str.charAt(i));
}
}
return sb.toString();
}
//方式二：双指针法
public String replaceSpace(String s) {
if(s == null || s.length() == 0){
return s;
}
//扩充空间，空格数量2倍
StringBuilder str = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if(s.charAt(i) == ' '){
str.append(" ");
}
}
//若是没有空格直接返回
if(str.length() == 0){
return s;
}
//有空格情况 定义两个指针
int left = s.length() - 1;//左指针：指向原始字符串最后一个位置
s += str.toString();
int right = s.length()-1;//右指针：指向扩展字符串的最后一个位置
char[] chars = s.toCharArray();
while(left>=0){
if(chars[left] == ' '){
chars[right--] = '0';
chars[right--] = '2';
chars[right] = '%';
}else{
chars[right] = chars[left];
}
left--;
right--;
}
return new String(chars);
}
151. 颠倒字符串中的单词
方法一
- 先去除空格
- 在反转整个字符串
最后单独反转每一个单词
class Solution { public String reverseWords(String s) { //1 去除首尾和中间多余的空格 StringBuilder sb = removeSpace(s); //2 反转整个字符串 reverseString(sb, 0, sb.length() - 1); //3 反转每个单词即可 reverseEachWord(sb); return new String(sb); } /** * 3 反转每个单词即可 * @param sb */ private void reverseEachWord(StringBuilder sb) { //设置初始单词长度开始在start结束在end最开始默认单词只有一个长度单位 int start = 0; int end = 1; int n = sb.length(); while (start < n){ while (end < n && sb.charAt(end)!= ' '){//找单词末位 end++; } //反转单词 reverseString(sb,start,end -1); //递增到下一个单词 start = end +1; end = start+1; } } /** * 2 反转字符串指定区间[left, right]的字符 * @param sb * @param left * @param right */ private void reverseString(StringBuilder sb, int left, int right) { while (left < right){ char temp = sb.charAt(left); sb.setCharAt(left, sb.charAt(right)); sb.setCharAt(right, temp); left++; right--; } } /** * 1 去除首尾和中间多余的空格 * @param s * @return */ private StringBuilder removeSpace(String s) { int start = 0; int end = s.length()-1; //去除首尾的空格 while (s.charAt(start) ==' '){ start++; } while (s.charAt(end) == ' '){ end--; } //去除中间的空格 StringBuilder sb = new StringBuilder(); while (start <= end){ char c = s.charAt(start); if (c != ' '|| sb.charAt(sb.length()-1) != ' '){//这段逻辑可以处理中间多余的空格 sb.append(c); } start++; } return sb; } }剑指 Offer 58 - II. 左旋转字符串
空间复杂度为o(n)的方法
class Solution {
public String reverseLeftWords(String s, int n) {
StringBuilder sb = new StringBuilder();
if (n <= s.length()){
for(int i = n; i < s.length(); i++){
sb.append(s.charAt(i));
}
for (int i = 0; i <= n-1;i++){
sb.append(s.charAt(i));
}
}
return new String(sb);
}
}
不能申请额外空间，只能在本串上操作。空间复杂度为O(1)
class Solution {
public String reverseLeftWords(String s, int n) {
int len=s.length();
StringBuilder sb=new StringBuilder(s);
reverseString(sb,0,n-1);
reverseString(sb,n,len-1);
return sb.reverse().toString();
}
public void reverseString(StringBuilder sb, int start, int end) {
while (start < end) {
char temp = sb.charAt(start);
sb.setCharAt(start, sb.charAt(end));
sb.setCharAt(end, temp);
start++;
end--;
}
}
}
28. 实现 strStr()
代码随想录解法
KMP算法
// 方法一
class Solution {
public void getNext(int[] next, String s){
int j = -1;
next[0] = j;
for (int i = 1; i<s.length(); i++){
while(j>=0 && s.charAt(i) != s.charAt(j+1)){
j=next[j];
}
if(s.charAt(i)==s.charAt(j+1)){
j++;
}
next[i] = j;
}
}
public int strStr(String haystack, String needle) {
if(needle.length()==0){
return 0;
}
int[] next = new int[needle.length()];
getNext(next, needle);
int j = -1;
for(int i = 0; i<haystack.length();i++){
while(j>=0 && haystack.charAt(i) != needle.charAt(j+1)){
j = next[j];
}
if(haystack.charAt(i)==needle.charAt(j+1)){
j++;
}
if(j==needle.length()-1){
return (i-needle.length()+1);
}
}
return -1;
}
}
459. 重复的子字符串
KMP算法
class Solution {
public void getNext(int[] next,String s){
int j = -1;
next[0] = j;
for (int i = 1; i < s.length(); i++) {
while (j > 0 && s.charAt(i) != s.charAt(j+1)){
j = next[j];
}
if (s.charAt(i) == s.charAt(j+1)){
j++;
}
next[i] = j;
}
}
public boolean repeatedSubstringPattern(String s) {
if (s.length() == 0) {
return false;
}
int[] next = new int[s.length()];
getNext(next,s);
int length = next.length;
if (next[length-1]!=-1 && length%(length - (next[length-1]+1)) == 0){
return true;
}
return false;
}
}
若有收获，就点个赞吧
0 人点赞
