算法笔记|Day7字符串

☆☆☆☆☆leetcode 344.反转字符串

题目链接：leetcode 344.反转字符串

题目分析

1.定义两个指针（索引下标），一个从字符串前面，一个从字符串后面，两个指针同时向中间移动，并交换元素；
2.时间复杂度为O(n)，空间复杂度为O(1)。

代码

1.常见的交换数值
class Solution {
    public void reverseString(char[] s) {
        int i=0,j=s.length-1;
        while(i<j){
            char temp=s[i];
            s[i]=s[j];
            s[j]=temp;
            i++;
            j--;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.通过位运算
class Solution {
    public void reverseString(char[] s) {
        int i=0,j=s.length-1;
        while(i<j){
            s[i]^=s[j];
            s[j]^=s[i];
            s[i]^=s[j];
            i++;
            j--;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

提示：交换元素还可以采用位运算的方法，即使用异或运算符（^），它的作用是对两个二进制数的每一位进行逻辑异或，即相同为0，不同为1，异或运算有以下性质：
①任何数和自己异或都等于0，即x ^ x = 0
②任何数和0异或都等于自己，即x ^ 0 = x
③异或运算满足交换律和结合律，即x ^ y = y ^ x，(x ^ y) ^ z = x ^ (y ^ z)
故y=x^yx，x=y^xy.

☆☆☆☆☆leetcode 541. 反转字符串II

题目链接：leetcode 541. 反转字符串II

题目分析

1.在遍历字符串的过程中，只要让 i += (2 * k)，i 每次移动 2 * k ，在此基础上判断每次反转的区间（是否到达末尾）；
2.时间复杂度为O(n)，空间复杂度为O(1)。

代码

class Solution {
    public String reverseStr(String s, int k) {
        char ch[]=s.toCharArray();
        for(int i=0;i<ch.length;i+=2*k){
            int left=i;
            int right=Math.min(ch.length-1,i+k-1);
            while(left<right){
                char temp=ch[left];
                ch[left]=ch[right];
                ch[right]=temp;
                left++;
                right--;
            }
        }
        String res=new String(ch);
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

☆☆☆☆kamacoder 54. 替换数字（待补充）

题目链接：kamacoder 54. 替换数字

题目分析

代码

1