LeetCode(10) -- 448, 453, 455

P448. Find All Numbers Disappeared in an Array (Easy)

给一个数组长度为n，找出所有1到n之间未出现的数。要求不增加新内存，并且O(n)

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

我的思路

如果允许新加内存空间，直接新建一个布尔数组存一下每个数是否出现过即可。不新加内存我暂时想不出。

我的代码

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        boolean[] bool = new boolean[nums.length];
        for (int i = 0; i < nums.length; i++) {
            bool[nums[i]-1] = true;
        }
        List<Integer> integers = new ArrayList<>();
        for (int i = 0; i < bool.length; i++) {
            if (!bool[i]) {
                integers.add(i + 1);
            }
        }
        return integers;
    }
}

99%

最优解

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {

        int[] arr = new int[nums.length+1];

        for(int i=0;i<nums.length;i++) {
            arr[nums[i]]++;
        }

        List<Integer> list=new ArrayList<>();

        for(int i=1;i<arr.length;i++) {
            if(arr[i]==0) {
              list.add(i);
            }
        }

        return list;
    }
}

同样新开了一个空间。基本思路差不多，没什么特别的。

讨论区

public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> list = new ArrayList<Integer>();
        int value = 0, index = 1, len = nums.length;
        for( int i = 0; i < len; i++ )
            value |= (1 << (nums[i]-1));

        while( value > 0 || len > 0) {
            if ((value & 1) == 0)
                list.add(index);
            index++;
            len--;
            value >>= 1;
        }
        return list;

这个解法非常新颖。他用二进制每个位置上的1代表这个数出现过，用0代表没出现过。实际上相当于把二进制当作一个boolean数组来使用。如果出现了1，那二进制表示就是“1”，如果出现了2，那二进制表示就是“11”，如果跳过了3，而出现了两次4，那二进制表示就是“1011”。总之，这个二进制的数，从右数，第几位是1，就代表那个数出现过。比如从右数第二位是1，就代表2出现过。

最后用while循环时，记录一个长度len，然后从右向左依次检查该位置上是否是1。如果是1，就把这个数添加进List。

P453. Minimum Moves to Equal Array Elements (Easy)

给一个长度为n的数组，可以进行如下操作：对其中的n-1个数分别增加1。问：进行多少次这样的操作，可以使用数组内所有的数都相等？

Input:
[1,2,3]

Output:
3

Explanation:
Only three moves are needed (remember each move increments two elements):

[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

我的思路

每次把所有的n-1个数都加1，实际上相当于把最大的数减1。因为最终目标是让所有数都相等，所有这两种操作实际上是等价的。那就把所有的数跟最小的数做差，然后把它们加起来就是要返回的结果。

实现的时候，我不想整个数组跑两趟。先假定第一个数就是最小值，然后后面的数如果比它大，就累加上它们的差；如果比它小，就把所有的数都更新，全部累加上它们的差，并更新最小值min。

我的代码

public class E_453_MinimumMovesToEqualArrayElements {
    public int minMoves(int[] nums) {
        int min = nums[0];
        int res = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > min) {
                res += nums[i] - min;
            } else if (nums[i] < min) {
                res += (min - nums[i]) * i;
                min = nums[i];
            }
        }
        return res;
    }
}

90%

最优解

class Solution {
    public int minMoves(int[] nums) {

        int min = Integer.MAX_VALUE;
        int sum =0;
        for(int i : nums){
            if(i<min){
                min = i;
            }
            sum += i;
        }
        sum = sum - min;
        return sum-((nums.length-1)*min);

    }
}

这种方法确实更好：遍历数组，记录最小值并求和。最后用sum减去n个最小值就是结果。

P455. Assign Cookies (Easy)

每个孩子最多给一个饼干。饼干的大小不一样。每个孩子都有一个贪婪因子gi，代表能满足他的最小尺寸（的饼干）。-.-

每个饼干都有一个尺寸sj，如果sj >= gi，就可以把这个饼干分给这个孩子i。求最多可以满足多少个孩子。

我的思路

这个题其实就是田忌赛马，求第二个数组最多有多少个数是大于等于第一个数组里的数的。如果用nlogn把两个数组都排个序，那其实是很容易解决的。但如果想降到m+n，暂时想不到。。。

我的代码

public class E_455_AssignCookies {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int counter = 0;
        for (int i = 0, j = 0; i < s.length && j < g.length; i++) {
            if (s[i] >= g[j]) {
                counter++;
                j++;
            }
        }
        return counter;
    }
}

98%

看了最优解，他自己实现了一个排序算法，不理解为啥不用Java自带的。。。另外一个答案代码也很长，提升性能也很有限，不如就用我自己这个。