双指针问题1

1. 移动零（283）

题目描述：

算法原理：
设置两个指针分别为cur以及dest，cur指针和dest指针将nums数组分为三个部分，[0,dest]为处理后的不为0的部分，[dest+1,cur-1]为处理后的为0的部分，[cur,nums.length-1]为未处理的部分。cur就是用来指向即将处理的元素，dest就是用来指向处理后的位置，具体来说就是使用cur来遍历nums数组，如果元素等于0那么直接cur+1，如果元素不等于0那么就将该位置元素与dest+1位置的元素交换，这样就能保证将nums数组划分出以上的三部分（dest指针走的要比cur指针要慢一点）。
代码如下：

class Solution {
    public void moveZeroes(int[] nums) {
        int left = -1, right = 0;
        for (; right < nums.length; right++) {
            if (nums[right] != 0) {
                left++;
                int temp = nums[right];
                nums[right] = nums[left];
                nums[left] = temp;
            }
        }
    }
}

题目链接

2. 复写零（1089）

题目描述：

算法原理：
这题不能使用上题相同的思想，cur和dest不能从左边开始，如果从左边每次复写0的时候，dest一次要加2，所以dest位置是有可能会超过cur的，这就会导致cur读到错误的值。
这题我们的cur和dest从数组的右边开始操作，但是此时起始处理的数字不是数组末尾的元素，而是数组复写零后的最后一个数字，所以我们要在操作之前找到这个复写零后的最后一个数字，这个找的过程也是通过双指针来实现，left遍历数组，如果元素为0则right+2，如果不为0则right+1，当此时right走到数组尾部时，left指向的元素就是数组复写零后尾部的数字。之后按照第一题类似的过程即可得到复写数组，但是此时有一种特殊情况会导致数组越界问题，就是当前面的right等于arr.length时，说明复写时left最后一个数字为0。因此我们在真正使用cur和dest进行复写之前先判断right是否为arr.length，如果是那么将left-1以及将arr[arr.length]赋为0并且将right-2，经过这样的操作之后再进行复写（其实这种情况就是left遍历的最后一个数字是0，但是此时right位置为arr.length-2了，已经无法复写两个0，但是right还是加了2），具体看代码。
代码如下：

 class Solution {
    public void duplicateZeros(int[] arr) {
        int left = 0, right = -1;
        for (; left < arr.length; left++) {
            if (arr[left] == 0) {
                right += 2;
            } else {
                right++;
            }
            if (right >= arr.length - 1) {
                break;
            }
        }

        if (right == arr.length) {
            arr[arr.length - 1] = 0;
            right = arr.length - 2;
            left--;
        }
        int cur = left, dest = right;
        for (; cur >= 0; cur--) {
            if (arr[cur] == 0) {
                arr[dest] = 0;
                arr[dest - 1] = 0;
                dest -= 2;
            } else {
                arr[dest] = arr[cur];
                dest--;
            }
        }
    }
}

题目链接

3. 快乐数（202）

题目描述：

算法原理：
通过理解上述的题目描述我们可以理解到一个n对于这种不断的各位的平方和有三种可能，第一种可能就是出现平方和为1的情况然后一直循环下去，第二种情况也是发生循环但是循环的节点不是平方和为1的情况，而是平方和为其它值的情况，第三种情况就是不发生循环。事实上是没有第三种情况的，假设n这个数字最多就是10位的数字，那么它最大就是9999999999构成，这样的话它的后面的平方和取值范围为1到810,在无限循环中很容易遍历完这样小的范围，一旦第二次遍历到范围内的数就会出现循环，所以肯定会发生循环。根据以上分析，我们设置快慢指针，快指针一次计算两次平方和，慢指针一次计算一次平方和，并且慢指针初始值为n，快指针初始值为n计算一次的平方和，通过不断循环这个过程，快指针肯定是能追上慢指针的，此时跳出循环，返回相同的值，如果值为1那么就返回true反之则返回false.
代码如下：

class Solution {
    public int bitSum(int n) {
        int sum = 0;
        while (n != 0) {
            int t = n % 10;
            sum += t * t;
            n = n / 10;
        }

        return sum;

    }

    public boolean isHappy(int n) {
        int slow = n, fast = bitSum(n);
        while (slow != fast) {
            slow = bitSum(slow);
            fast = bitSum(bitSum(fast));
        }

        return slow == 1 ? true : false;
    }
}

题目链接

4. 盛最多水的容器（11）

题目描述：


算法原理：
在做这题之前我们先分析一个小区间[6,1,5,2]，首先对首尾的6和2进行分析，此时2除了6还可以搭配1和5，但是我们思考一下不难发现2和5搭配的话长度先减少然后高度不变，整体面积肯定减小；2和1搭配不仅长度减小，连高度也减小，此时面积肯定也是减小的。我们先分析的是尾部的元素，其实首部也是一样的，我们将数组首尾调换即[2,1,5,6]，不难发现首部的2除了与6搭配，向内搭配面积都会减小。
其实这样举例就是为了说明一个规律，当一对元素配对时对于height数组值较小的那个元素它向数组内匹配的面积大小肯定是没有原来的搭配大的，因此我们在每次配对时使用左右指针分别指向两边的元素，记录此时面积，然后比较两个height数组值，将指向小height值的指针向内聚拢一个单位。这样达到的效果就是相当于去掉了那个元素，因为那个元素的搭配的最大面积我们已经得到了就是最初记录的面积，将那个元素和其它元素搭配肯定不如原搭配的面积的（前面分析了规律）。通过不断重复这样的过程也就是记录面积后去掉height值小的元素即指针向内靠拢一个单位，最终左右指针相遇循环结束，当然在这个过程中记录的面积要进行比较，从而得到最终的最大面积。
代码如下：

class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1, area = 0;
        while (left < right) {
            int temp = Math.min(height[left], height[right]) * (right - left);
            area = Math.max(temp, area);
            if (height[left] >= height[right]) {
                right--;
            } else if (height[left] < height[right]) {
                left++;
            }

        }
        return area;
    }
}

题目链接