「剑指Offer」Day13：双指针（简单）

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

题目描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

输入：nums = [1,2,3,4] 输出：[1,3,2,4] 注：[3,1,2,4] 也是正确的答案之一。

题目链接：https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/

方法一：头尾指针

通过头尾指针继续遍历判断：

左为偶数，右为奇数就交换，否则就移动右指针；
左为奇数，右为奇数就左指针，否则就左右指针同时移

class Solution {
    public int[] exchange(int[] nums) {
        if(nums == null || nums.length == 0){
            return nums;
        }
        int left = 0; 
        int right = nums.length - 1;
        while(left <= right){
            int lval = nums[left] % 2;
            int rval = nums[right] % 2;
            if(lval == 0){ //左为偶数
                if(rval != 0){ //右为奇数，就交换
                    int temp = nums[left];
                    nums[left] = nums[right];
                    nums[right] = temp;
                    left++;
                    right--;
                }else{ //右为偶数，移右指针
                    right--;
                }
            }else{  //左为奇数
                if(rval != 0){ //右为奇数，就移左指针
                    left++;
                }else{ //右为偶数，左右指针同时移
                    left++;
                    right--;
                }
            }
        }
        return nums;
    }
}

方法二：一次快排过程

模拟快速排序的一次交换过程

在一次循环中，左指针所指为奇数就继续移动，直到遇到偶数；
右指针为偶数就继续移动，直到遇到奇数；
这时左为偶，右为奇，则交换左右元素。

class Solution {
    public int[] exchange(int[] nums) {
        if(nums == null || nums.length == 0){
            return nums;
        }
        int left = 0; 
        int right = nums.length - 1;
        while(left < right){
            while(left < right && nums[left] % 2 != 0){ //为奇数继续移动，直到遇到偶数
                left++;
            }
            while(left < right && nums[right] % 2 == 0){ //为偶数继续移动，直到遇到奇数
                right--;
            }
            if(left < right){ //这时左为偶，右为奇，需交换左右元素
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
            }
        }
        return nums;
    }
}

剑指 Offer 57. 和为s的两个数字

题目描述

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

输入：nums = [2,7,11,15], target = 9 输出：[2,7] 或者 [7,2]

题目链接：https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof/

思路

解法1：这道题其实就是两数之和，可以采用哈希法，但这样的话没有用上递增排序这个条件，时间复杂度为 $O(n)$ ;

解法2：采用二分查找，从头遍历数组，将目标值减去当前值得到相减值，从当前值往后的数组中二分查找相减值，时间复杂度为 $O(nlogn)$ ;

解法3：充分利用递增的条件，设置头尾指针，将相加值与目标值进行比较，相等就返回结果，大于就移动右指针减小相加值，小于就移动左指针进行增大，时间复杂度为 $O(n)$

实现代码

解法2：二分查找

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int length = nums.length;
        if(length == 1){
            return new int[0];
        }
        int[] res = new int[2];
        for(int i = 0; i < length - 1; i++){
            if(nums[i] >= target){ //数组是递增的且元素 >= 1，则大于等于目标值就可直接跳出循环
                break;
            }
            if(binarySearch(nums, i + 1, target - nums[i])){ //从该元素往后的数组中查找相减值
                res[0] = nums[i];
                res[1] = target - nums[i];
                return res;
            }
        }
        return new int[0];
    }
    public boolean binarySearch(int[] nums, int left, int target){ //二分查找
        int right = nums.length - 1;
        int mid = 0;
        while(left <= right){
            mid = left + (right - left) / 2;
            if(nums[mid] == target){
                return true;
            }else if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return false;
    }
}

解法3：头尾指针

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int length = nums.length;
        if(length == 1){
            return new int[0];
        }
        int[] res = new int[2];
        int left = 0;
        int right = length - 1;
        while(left < right){
            int sum = nums[left] + nums[right];
            if(sum == target){
                res[0] = nums[left];
                res[1] = nums[right];
                return res;
            }else if(sum < target){ //相加值大于目标值，就移动左指针
                left++;
            }else{ //小于就转移右指针
                right--;
            }
        }
        return new int[0];
    }
}

剑指 Offer 58 - I. 翻转单词顺序

题目描述

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。

无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

题目链接：https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof

方法一：调用分割方法

使用String类自带的根据正则表达式分割字符串的方法split()，\s 匹配任何空白字符，包括空格、制表符、换页符等，\s+ 可匹配一个或多个空白符

class Solution {
    public String reverseWords(String s) {
        if(s.length() == 0){
            return s;
        }
        String[] strs = s.split("\\s+"); //正则匹配一个或者多个连续的空白字符作为分隔符分割
        StringBuilder sbr = new StringBuilder();
        for(int i = strs.length - 1; i >= 0; i--){
            sbr.append(strs[i]);
            sbr.append(" ");
        }
        return sbr.toString().trim(); //trim()方法删除字符串的头尾空白符
    }
}

方法二：双指针

移动右指针遍历字符串，遇到空格就循环遍历，直到遇到下一个非空格的字符，接着进行截取，并把前后的空格去除，即获得一个完整的单词，左指针记录下一个单词的起始位置

class Solution {
    public String reverseWords(String s) {
        String str = s.trim(); //先删除头尾多余空格
        int len = str.length();
        String[] strArr = new String[len];
        int index = 0;
        int left = 0;
        int right = 0;
        while(right < len){ //截取单词放入数组中
            if(str.charAt(right) == ' '){
                while(str.charAt(right) == ' '){ //为空格就循环移动右指针
                    right++;
                }
                strArr[index++] = str.substring(left, right).trim(); //截取单词
                left = right; //左指针记录下一个单词的起始
            }
            if(right == len - 1){ //最后一个字符不是空格就直接截取
                strArr[index++] = str.substring(left, right+1).trim();
            }
            right++;
        }
        StringBuilder sb = new StringBuilder();
        for(int i = strArr.length - 1; i >= 0; i--){ //逆序拼接数组元素
            if(strArr[i] != null){
                sb.append(strArr[i] + " ");
            }
        }
        return sb.toString().trim();
    }
}