[数据结构与算法]剑指offer java day13 双指针

T1 21. 调整数组顺序使奇数位于偶数前面

class Solution {
    public int[] exchange(int[] nums) {
        int i=0,j=nums.length-1,tmp;
        while(i < j){
            //i 指针向右移动，直到找到偶数
            while((i<j) && (nums[i]%2 == 1)) i++;
            //j 指针向右移动，直到找到奇数
            while((i<j) && (nums[j]%2 == 0)) j--;
            tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
        return nums;
    }
}

T2 57. 和为s的两个数字

暴力，遍历加折半超时了。 用双指针

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int i=0,j=nums.length-1,sum=0;
        while(i<j){
            sum = nums[i]+nums[j];
            //因为是递增数列，小于目标i右移,大于目标j左移
            if(sum < target) i++;
            else if(sum > target) j--;
            else{
                return new int[]{nums[i],nums[j]};
            }
        }
        return new int[0];
    }
}

T3 58 - I. 翻转单词顺序

库函数调用后发现今天的主题是双指针

class Solution {
    public String reverseWords(String s) {
        s = s.trim(); //去掉首尾空格
        StringBuffer res = new StringBuffer();
        int j = s.length()-1,i=j;
        while(i>=0){ 
            while(i>=0 && (s.charAt(i) !=' ')) i--; //找到单词前第一个空格
            res.append(s.substring(i+1,j+1)+" "); //把单词加入res
            while(i>=0 && (s.charAt(i) ==' ')) i--; //忽略两词之间的空格
            j=i; //新单词的尾部
        }
        return res.toString().trim();
    }
}