LeetCode(27) -- 575, 581, 589

P575. Distribute Candies (Easy)

把偶数个糖果平均分给哥哥和妹妹，不同的数字代表不同各类的糖果。问妹妹最多可以得到多少种糖果？

我的思路

实际上这题就是问，在不超过半数的情况下，一共有多少个不同的数。可以用HashMap做。先找到最大的数，然后自制一个简易版HashMap.

我的代码

public class E_575_DistributeCandies {
    public int distributeCandies(int[] candies) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < candies.length; i++) {
            if (candies[i] > max) {
                max = candies[i];
            }
            if (candies[i] < min) {
                min = candies[i];
            }
        }
        boolean[] map = new boolean[max - min + 1];
        for (int i = 0; i < candies.length; i++) {
            map[candies[i] - min] = true;
        }
        int res = 0;
        for (int i = 0; i < map.length; i++) {
            if (map[i]) res++;
        }
        return Math.min(res, candies.length / 2);
    }
}

99%

答案

public class Solution {
    public int distributeCandies(int[] candies) {
        HashSet < Integer > set = new HashSet < > ();
        for (int candy: candies) {
            set.add(candy);
        }
        return Math.min(set.size(), candies.length / 2);
    }
}

刚才想错了，不应该用Hashmap, 用HashSet.

最优解

class Solution {
    public int distributeCandies(int[] candies) {
        int len = candies.length;
        if (len == 0) return 0;
        int half = len / 2;

        // 种类有上限 [-100000, 100000]
        byte[] kinds = new byte[200001];
        int count = 0;

        for (int kind : candies) {
            count += 1 - kinds[kind + 100000];
            kinds[kind + 100000] = 1;
            if (count == half) break;
        }

        return count;
    }
}

直接通过给定的范围确定了数组的长度，不需要像我一样设定最大最小值。这行代码比较有意思： count += 1 - kinds[kind + 100000];。 因为他用了byte类型的数组，（当然其实我用boolean是一样的）如果是0，就用1减去0，就是1，也就是说，只要没出现过，count++。如果出现过就不加了。

P581. Shortest Unsorted Continuous Subarray (Easy)

给一个数组，找出最短的连续子数组，满足条件：只要把这个子数组从小到大排序， 整个数组也就从小到大排序了。

我的思路

可以先把这个数组从小到大排个序，然后比较原数组，找到第一个不一样的和最后一个不一样的。就是需要排序的子数组的范围。

我的代码

public class E_581_ShortestUnsortedContinuousSubarray {
    public int findUnsortedSubarray(int[] nums) {
        int[] sortedNums = nums.clone();
        Arrays.sort(sortedNums);
        Integer firstDiff = null;
        int lastDiff = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != sortedNums[i]) {
                if (firstDiff == null) {
                    firstDiff = i;
                }
                lastDiff = i;
            }
        }
        if (firstDiff == null) {
            return 0;
        }
        return lastDiff - firstDiff + 1;
    }
}

41%

最优解

class Solution {
    public int findUnsortedSubarray(int[] a) {
        int l = a.length-1, r  = 0, max = a[0], min = a[a.length-1];
        for(int i = 1; i < a.length; i++) {
            if(a[i] < max) r = i;
            if(a[i] > max) max = a[i];
        }
        for(int i = a.length-2; i >=0; i--) {
            if(a[i] > min) l = i;
            if(a[i] < min) min = a[i];
        }
        if(r <= l)return 0;
        return r-l+1;
    }
}

这个解法绝了！从前往后走一趟，再从后往前走一趟。第一趟保存随时保存最大值，如果有任何一个数小于当时遇到的最大值，就说明最右边界至少会在这里。也就是说，无论前面怎么波动，只有不断地刷新历史最大值，我才保持最右边界不变。从右往左也是一样的道理。

答案

public class Solution {
    public int findUnsortedSubarray(int[] nums) {
        Stack <Integer> stack = new Stack <Integer> ();
        int l = nums.length, r = 0;
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] > nums[i])
                l = Math.min(l, stack.pop());
            stack.push(i);
        }
        stack.clear();
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i])
                r = Math.max(r, stack.pop());
            stack.push(i);
        }
        return r - l > 0 ? r - l + 1 : 0;
    }
}

P589. N-ary Tree Preorder Traversal (Easy)

前序遍历一棵树。

我的思路

这也太基础了。。。

我的代码

public class E_589_NaryTreePreorderTraversal {
    List<Integer> res = new ArrayList<>();
    public List<Integer> preorder(Node root) {
        if (root == null) return res;
        res.add(root.val);
        for (Node child : root.children) {
            preorder(child);
        }
        return res;
    }
}

100%

最优解

class Solution {

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

    public List<Integer> preorder(Node root) {
        if(root == null){
            return al;
        }
        preorderDFS(root);
        return al;
    }

    public void preorderDFS(Node root) {
        if(root != null) {
            al.add(root.val);
            List<Node> child = root.children;
            for(Node c: child) {
                preorderDFS(c);
            }
        }
    }
}

跟我的没什么不一样的，反而觉得没必要再写个辅助方法。