Two Pointers

283. Move Zeros

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.

一根指针指向第一个非0的位置，第二根第一个0(如果不是0，自己跟自己换）

    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                // swap
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                j++;
            }
        }
    }

360. Sort Transformed Array

Given a sorted array of integers nums and integer values a, b and c. Apply a quadratic function of the form f(x) = ax2 + bx + c to each element x in the array.

The returned array must be in sorted order.

Expected time complexity: O(n)

Example:
nums = [-4, -2, 2, 4], a = 1, b = 3, c = 5,
Result: [3, 9, 15, 33]

nums = [-4, -2, 2, 4], a = -1, b = 3, c = 5
Result: [-23, -5, 1, 7]

关键是在O(n)内返回sorted过的结果，就要利用a的符号来判断。假设a大于0，说明两端的值比中间大，要想得到一个从小到大的数组就要把值从后往前填。因为给的数组也是排过序的，一根指针指头一个指尾，往中间凑。想清楚while里的是小于等于号。

    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        // if a = 0, b's sign doesn't matter
        int left = 0, right = nums.length - 1;
        int[] res = new int[nums.length];
        int idx = (a >= 0) ? nums.length - 1 : 0;
        while (left <= right) {
            if (a >= 0) {
                if (cal(a, b, c, nums[left]) >= cal(a, b, c, nums[right])) {
                    res[idx--] = cal(a, b, c, nums[left]);
                    left++;
                } else {
                    res[idx--] = cal(a, b, c, nums[right]);
                    right--;  
                }
            } else {
                if (cal(a, b, c, nums[left]) >= cal(a, b, c, nums[right])) {
                    res[idx++] = cal(a, b, c, nums[right]);
                    right--;
                } else {
                    res[idx++] = cal(a, b, c, nums[left]);
                    left++;  
                }
            }
        }
        return res;
    }