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

Easy 原题连接：调整数组顺序使奇数位于偶数前面

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

示例：

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

限制：

  • 0 <= nums.length <= 50000`
  • 0 <= nums[i] <= 10000

解题思路

双指针，一头一尾向中间遍历，满足前为奇数头指针后移，满足后为偶数尾指针前移，直到两个都不可移动，交换到两个指针相交

Java代码

class Solution {
    public int[] exchange(int[] nums) {
        int n = nums.length, i = 0, j = n-1;
        while(i<j) {
            while(i < n && nums[i]%2==1) i++;
            while(j > 0 && nums[j]%2==0) j--;
            if(i>=j) break;
            swap(nums,i,j);
        }
        return nums;
    }

    public static void swap(int[] nums, int i, int j){
        int mid = nums[i];
        nums[i] = nums[j];
        nums[j] = mid;
    }
}

和为s的两个数字

Easy 原题连接：和为s的两个数字

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

示例：

输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]
输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]

限制：

  • 1 <= nums.length <= 10^5

  • 1 <= nums[i] <= 10^6

解题思路

这是一个递增排序的数组，就先将大于target的部分跳过，从第一个小于target的部分与头部最小数据做双指针

数字过小就头指针后移，数据过大就尾指针前移

逻辑：因为 a < b < c < d；所以 a + c < a + d < b + d， a + b < a + c < b + c，b + c < b + d < c + d

这说明了什么呢？

看第一个结果 a + d ，将对于a和d的结果划分为了两个部分：大于 a + d 的和小于a + d 的

看第二个结果的 a + c ，将对于a和c的结果划分为了两个部分：大于 a + c 的和小于a + c的

看第三个结果的 b+ d ，将对于b和d的结果划分为了两个部分：大于 b + d 的和小于 b + d的

也就是说，将这个相加的结果视为一个二维数组的话

​ a b c d

a a+a a+b a+c a+d

b b+a b+b b+c b+d

c c+a c+b c+c c+d

d d+a d+b d+c d+d

这个数组满足：每一行都递增，每一列都递增

看看以前的一道题：《在二维数组中查找》

leetcode剑指Offer第五天 | IT蛋的个人博客 (xcscx.github.io)

我们可以得到结论，要想找到某个值，可以从二维数组右上角入手，小就向左移动，大就朝下移动

Java代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int l = 0, r = nums.length-1;
        for(l=0; l<r;) {
            if(nums[r] > target) {
                r--;
                continue;
            }
            int mid = nums[l] + nums[r];
            if(mid == target) {
                return new int[] { nums[r], nums[l] };
            }else if(mid > target) {
                r--;
            }else {
                l++;
            }
        }
        return null;
    }
}

翻转单词顺序

Easy 原题连接：翻转单词顺序

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

示例：

输入: "the sky is blue"
输出: "blue is sky the"
输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

限制：

  • 无空格字符构成一个单词。

  • 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

  • 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

解题思路

重复的车轮，其实也可以将String拆成char[]去一个个判断，被空格分隔的作为一个整体倒叙填入StringBuilder，空格跳过

Java代码

class Solution {
    public String reverseWords(String s) {
        String[] strs = s.trim().split(" ");
        StringBuilder ans = new StringBuilder();
        for(int i = strs.length - 1; i >= 0; i--) {
            if(strs[i].equals("")) continue;
            ans.append(strs[i] + " ");
        }
        return ans.toString().trim();
    }
}