算法分享第1题

题目：要求定义一个方法，实现对传入的字符串进行反转并返回

如：传入字符串ABCDEFG -> 返回GFEDCBA

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

思路：

• 既然是反转，也就是倒序重新组合字符，那就for循环一遍重新排列吧;

倒序循环反转

• 又想了想遍历一次字符串是不是太浪费时间了，直接以中间字符为中心，交换两端字符更省时间.

折半交换反转

方法一：倒序遍历字符串重新组合

// 时间复杂度：O(n)
public String reverse(String str) {
    int length = str.length();
    StringBuilder sb = new StringBuilder();
    for (int index = length - 1; index >= 0; index--) {
        sb.append(str.charAt(index));
    }
    return sb.toString();
}

方法二：调用Java中StringBuilder类的reverse方法

// 核心代码参考如下 - 时间复杂度：O(n)
public AbstractStringBuilder reverse() {
    int n = count - 1;
    for (int j = (n-1) >> 1; j >= 0; j--) {
        // 以中间字符为界限，左右两边字符交换 相比较方法一减少(n-(n+1)/2)次循环
        // 如字符串长度为7，则 n = 6，j = 2，将 0 1 2 和 6 5 4 位置交换
        // 如字符串长度为6，则 n = 5，j = 2，将 0 1 2 和 5 4 3 位置交换
        int k = n - j;
        char cj = value[j];
        char ck = value[k];
        value[j] = ck;
        value[k] = cj;
    }
    return this;
}

方法三：定义两个指针分别指向字符串的头和尾，一个向后走，一个向前走，直到两个相遇则结束

// 时间复杂度：O(n)
public String reverse(String str) {
    char[] charArray = str.toCharArray();
    for (int i = 0, j = charArray.length - 1; i < j; i++, j--) {
        char temp = charArray[i];
        charArray[i] = charArray[j];
        charArray[j] = temp;
    }
    return new String(charArray);
}

方法四：思路和方法三相同，精华在交换数据时不引入暂存变量

// 时间复杂度：O(n)
public String reverse(String str) {
    char[] charArray = str.toCharArray();
    for (int i = 0, j = charArray.length - 1; i < j; i++, j--) {
        charArray[i] = (char) (charArray[i] ^ charArray[j]);
        charArray[j] = (char) (charArray[i] ^ charArray[j]);
        charArray[i] = (char) (charArray[i] ^ charArray[j]);
    }
    return new String(charArray);
}