代码随想录Day07

LeetCode344 反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1：
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：
输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

思路：

双指针，头尾进行交换操作。和之前做过很多题目类似，思路是公用的。

class Solution {
    public void reverseString(char[] s) {
        int l = 0;
        int r = s.length - 1;
        while (l < r) {
            s[l] ^= s[r];  //构造 a ^ b 的结果，并放在 a 中
            s[r] ^= s[l];  //将 a ^ b 这一结果再 ^ b ，存入b中，此时 b = a, a = a ^ b
            s[l] ^= s[r];  //a ^ b 的结果再 ^ a ，存入 a 中，此时 b = a, a = b 完成交换
            l++;
            r--;
        }
    }
}

LeetCode 541 反转字符串II

给定一个字符串 s 和一个整数 k，从字符串开头算起, 每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符。

如果剩余字符少于 k 个，则将剩余字符全部反转。

如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例:

输入: s = "abcdefg", k = 2
输出: "bacdfeg"

思路：和第一题类似，想清楚边界条件和终止条件即可。难倒是不难，真正麻烦的是对过程的掌握

代码：

package com.dwj.LeetCode.String;

/**
 *
 * 给定一个字符串 s 和一个整数 k，从字符串开头算起, 每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符。
 *
 * 如果剩余字符少于 k 个，则将剩余字符全部反转。
 *
 * 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
 *
 * 示例:
 *
 * 输入: s = "abcdefg", k = 2
 * 输出: "bacdfeg"
 */
public class ReverseII {
    //解法一
    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 Solution2 {
        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);
        }
    }

    // 解法3
    class Solution3 {
        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;
            }

        }
    }
}