字符串

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--;
        }
    }
}