字符串
1、反转字符串
题目链接：力扣
描述
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例
输入：s = [“h”,“e”,“l”,“l”,“o”]
输出：[“o”,“l”,“l”,“e”,“h”]
思路
使用两个指针分别指向数组的第一个和最后一个元素，两个指针同时向中间移动，依次交换数值
实现代码
方法一：
使用一个额外空间
temp来交换数值
class Solution {
public void reverseString(char[] s) {
int left = 0;
int right = s.length-1;
while(left < right ){
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}
}
方法二：
位运算
^原地交换两个数 (a , b)
参与运算的两个值，如果两个相应bit位相同，则结果为0，否则为1。
即： 0^0 = 0， 1^0 = 1， 0^1 = 1， 1^1 = 0
任意一个变量a与其自身进行异或运算，结果为0，即a^a=0。
任意一个变量a与0进行异或运算，结果不变，即 a^0=a。
异或运算具有可结合性 异或运算具有可交换性
step1: a = a ^ b (完成后 a 变量的结果,代入step2)
step2: b = a ^ b (b = a ^ b = a ^ b ^ b = a ^ 0 = a)
经过前两步，a = a ^ b , b = a；
step3: a = a ^ b (a = a ^ b = a ^ b ^ a = a ^ a ^ b = 0 ^ b = b)
class Solution {
public void reverseString(char[] s) {
int left = 0;
int right = s.length-1;
while(left < right ){
s[left] ^= s[right];
s[right] ^= s[left];
s[left] ^= s[right];
left++;
right--;
}
}
}
2、反转字符串 II
题目链接: 力扣
描述
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
示例
输入：s = “abcdefg”, k = 2
输出：“bacdfeg”
思路
使用 l 和 r 两个指针分别圈出每次需要翻转的范围，每次翻转完更新 l 和 r，同时注意范围 [l,r] 内不足 k 个的情况（将 r 与真实边界 n - 1取个 min）。
实现代码
class Solution {
public String reverseStr(String s, int k) {
char[] ch = s.toCharArray();
for (int i = 0; i < ch.length-1; i += 2*k){
int l = i;
int r = Math.min(l+k-1, ch.length-1);
while(l < r){
ch[l] ^= ch[r];
ch[r] ^= ch[l];
ch[l] ^= ch[r];
l++;
r--;
}
}
return String.valueOf(ch);
}
}
3、字符串变形
题目链接：牛客
描述
对于一个长度为 n 字符串，我们需要对它做一些变形。
首先这个字符串中包含着一些空格，就像"Hello World"一样，然后我们要做的是把这个字符串中由空格隔开的单词反序，同时反转每个字符的大小写。
比如"Hello World"变形后就变成了"wORLD hELLO"。
输入描述：
给定一个字符串s以及它的长度n(1 ≤ n ≤ 10^6)
返回值描述：
请返回变形后的字符串。题目保证给定的字符串均由大小写字母和空格构成。
示例
输入：“This is a sample”,16
返回值：“SAMPLE A IS tHIS”
思路
step 1：遍历字符串，反转每个字符的大小写。
step 2：第一次反转整个字符串，这样基本的单词逆序就有了，但是每个单词的字符也是逆的。
step 3：再次遍历字符串，以每个空间为界，将每个单词反转回正常。
实现代码
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* @param s string字符串
* @param n int整型
* @return string字符串
*/
public String trans (String s, int n) {
// write code here
char[] ch = s.toCharArray();
for(int i = 0; i < n; i++){
if('A'<=ch[i]&&ch[i]<='Z') ch[i] = (char)(ch[i] - 'A' + 'a');
else if('a'<=ch[i]&&ch[i]<='z') ch[i] = (char)(ch[i] - 'a' + 'A');
}
// 先整体翻转
reverseArr(ch, 0, n-1);
// 此时每个单词也逆序了，需要根据空格将每个单元重新反转回去
for(int i=0; i<n; i++){
if(ch[i] == ' ') continue;
int j=i;
while(j<n && ch[j]!=' ') j++;
reverseArr(ch, i, j-1);
i=j;
}
return String.valueOf(ch);
}
// 字符串数组翻转函数
public void reverseArr(char[] arr, int i, int j){
int l = i;
int r = j;
while(l < r){
char temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
l++;
r--;
}
}
}