算法入门第四天

双指针

「算法」 – 学习计划 – 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)

还是基础练习，双指针，这题就是二分法的那个操作

344. 反转字符串

/**
 344. 反转字符串
 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

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



 示例 1：

 输入：s = ["h","e","l","l","o"]
 输出：["o","l","l","e","h"]
 示例 2：

 输入：s = ["H","a","n","n","a","h"]
 输出：["h","a","n","n","a","H"]


 提示：

 1 <= s.length <= 105
 s[i] 都是 ASCII 码表中的可打印字符

 * @author zeroheart
 *
 */
public class Question344 {
    public void reverseString(char[] s) {
        int low = 0;
        int high = s.length-1;
        while (low<=high){
            char temp = s[low];
            s[low] = s[high];
            s[high] = temp;
            low++;
            high--;
        }
    }
}

557. 反转字符串中的单词 III

这题借用上面写好的函数

/**
 557. 反转字符串中的单词 III
 给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。



 示例 1：

 输入：s = "Let's take LeetCode contest"
 输出："s'teL ekat edoCteeL tsetnoc"
 示例 2:

 输入： s = "God Ding"
 输出："doG gniD"


 提示：

 1 <= s.length <= 5 * 10^4
 s 包含可打印的 ASCII 字符。
 s 不包含任何开头或结尾空格。
 s 里 至少 有一个词。
 s 中的所有单词都用一个空格隔开。

 * @author zeroheart
 *
 */
public class Question557 {
    public String reverseWords(String s) {
        StringBuilder sb = new StringBuilder();
        String[] arr = s.split(" ");
        for(int i=0; i<arr.length; i++){
            String rs = reverseString(arr[i].toCharArray());
            sb.append(rs);
            if(i != arr.length - 1){
                sb.append(" ");
            }
        }
        return new String(sb);
    }

    public String reverseString(char[] s) {
        int low = 0;
        int high = s.length-1;
        while (low<=high){
            char temp = s[low];
            s[low] = s[high];
            s[high] = temp;
            low++;
            high--;
        }
        return new String(s);
    }
}