LeetCode(4) -- 268, 278, 283

P268. Missing Number (Easy)

给一个包含n个不同的整数的数组，从0，1，2，…，n。找到缺失的那个数。

比如：

Input: [3,0,1]
Output: 2

我的思路

把这n个数加起来，然后用等差数列求和公式算出它本来应该的和，减去实际的和，就是差的那个数。

我的代码

public class E_268_MissingNumber {
    public int missingNumber(int[] nums) {
        int sum = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
        }
        return (1 + n) * n / 2 - sum;
    }
}

超过100%

最优解

class Solution {
    public int missingNumber(int[] nums) {
        int sum = 0;
        int expectedSum = 0;

        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            expectedSum += (i+1);
        }
        return expectedSum-sum;
    }
}

感觉不如我的，因为他没用等差数列求和，期望和是手工算出来的。

答案

答案提供了四种解法，其中位运算的解法比较有意思，时间复杂度也是O(n)

class Solution {
    public int missingNumber(int[] nums) {
        int missing = nums.length;
        for (int i = 0; i < nums.length; i++) {
            missing ^= i ^ nums[i];
        }
        return missing;
    }
}

利用了任何数跟它本身求XOR都等于0。把数组里实际的数和期望的数全放在一起求XOR，无论顺序，最终都会是缺失的那个数。

P278. First Bad Version (Easy)

假设你是一个产品经理。现在有n个版本的代码（线性的）。在最新的测试中，产品没通过。所有需要找出引起问题的第一个版本。有一个API，isBadVersion(int version)，可以用来验证。

我的思路

用二分查找法测试。

这个题难点在实现–如何通过二分查找法找出边界。因为要找的是第一个坏版本，所以如果中点是好版本，下次循环就应该把起始点放在中点+1的位置；如果中点是坏版本，结束点就设为中点，不减一。这样跳出循环的时候，起始点就一定是第一个坏版本。

我的代码

public class E_278_FirstBadVersion {

    private boolean isBadVersion(int version) {
        return false; // dummy API
    }
    public int firstBadVersion(int n) {
        int start = 1;
        int end = n;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (isBadVersion(mid)) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }
}

超过99.55%

最优解

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int l = 1, r = n;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (isBadVersion(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        return l;
    }
}

跟我的完全一样 ^^

P283. Move Zeroes (Easy)

给一个数组，把其中所有的0移动到结尾，要保持其他的数顺序不变。要求不能复制数组，只能在本数组内进行操作。

我的思路

跟快慢指针类似，快指针就是循环的i, 慢指针记录第一个0的位置。首先要找到第一个0的位置，因为找到前和找到后，要做的事情是不一样的。找到第一个0以前，移动指针就完了；找到后需要对调。

所以先用一个while找出第一个0，然后用for追踪两个指针，并完成对调。

我的代码

public class E_283_MoveZeroes {
    public void moveZeroes(int[] nums) {
        int firstZeroIndex = -1;
        int j = 0;
        while (j < nums.length && nums[j] != 0) {
            j++;
        }
        if (j >= nums.length - 1) {
            return;
        }
        firstZeroIndex = j;
        for (int i = j + 1; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[firstZeroIndex] = nums[i];
                nums[i] = 0;
                firstZeroIndex++;
            }
        }
    }
}

超过100%

最优解

class Solution {
    public void moveZeroes(int[] nums) {
        int index = 0;
        for (int i = 0; i< nums.length; i++){
            if(nums[i] != 0){
                nums[index] = nums[i];
                index = index +1;
            }
        }
        for (int i = index; i < nums.length; i++){
            nums[i]=0;
        }
    }
}

其实不需要像我的代码那么麻烦，只需要从头开始，找所有的非零数，然后按顺序覆盖前面的即可，最后把index以后的全重写成0。