LeetCode(24) -- 643, 645, 653

P643. Maximum Average Subarray I (Easy)

一个数组，给定一个长度，求这个长度的连续子数组，平均数最大是多少。

我的思路

最简单的动态规划，每次加一个新的数，减掉第一个数。然后更新这个sum的最大值。

我的代码

public class E_643_MaximumAverageSubarrayI {
    public double findMaxAverage(int[] nums, int k) {
        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        int max = sum;
        for (int i = k; i < nums.length; i++) {
            sum += nums[i];
            sum -= nums[i - k];
            max = Math.max(max, sum);
        }
        return (double) max / k;
    }
}

97.35%

最优解

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int i = 0;
        double sum = 0;
        while(i < k) {
            sum += nums[i];
            ++i;
        }
        double max = sum;
        while (i < nums.length) {
            sum += nums[i] - nums[i - k];
            max = sum > max ? sum : max;
            ++i;
        }
        return max / k;
    }
}

没什么区别。

P645. Set Mismatch (Easy)

一个数组本来是从1到n，但其中有一个数重复了，而另一个数丢失了。找到这个重复的数和丢失的数。

我的思路

无论在任何位置，只要发生了异常，那它一定是那个重复的数。（总不可能是那个丢失的数吧，见了鬼了？）

原来数组可以不按顺序的。题目没说清楚。

我的代码

class Solution {
    public int[] findErrorNums(int[] nums) {
        int[] res = new int[2];
        boolean[] exist = new boolean[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (!exist[nums[i] - 1]) {
                exist[nums[i] - 1] = true;
            } else {
                res[0] = nums[i];
            }
        }
        for (int i = 0; i < exist.length; i++) {
            if (!exist[i]) {
                res[1] = i + 1;
            }
        }
        return res;
    }
}

96%

最优解

class Solution {
    public int[] findErrorNums(int[] nums) {
        boolean[] arr = new boolean[nums.length];
        int[] output = new int[2];
        for (int i : nums) {
            if (arr[i - 1]) output[0] = i;
            arr[i - 1] = true;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!arr[i]) {
                output[1] = i + 1;
                return output;
            }
        }
        return output;
    }
}

遍历过程中只要存在就存到结果中，然后再把它变成true，这样就不需要像我一样再判断一下了。

另外在最后一次遍历中，如果发现false可以直接中止循环。

P653. Two Sum IV - Input is a BST (Easy)

一个BST，和一个目标值，如果树中有两个数的和等于这个目标值，返回true

我的思路

用HashSet

我的代码

class Solution {
    Set<Integer> set = new HashSet<>();
    public boolean findTarget(TreeNode root, int k) {
        if (root == null) {
            return false;
        }
        int diff = k - root.val;
        if (set.contains(diff)) {
            return true;
        }
        set.add(root.val);
        return findTarget(root.left, k) || findTarget(root.right, k);
    }
}

72%

最优解

class Solution {
    public boolean findTarget(TreeNode root, int k) {
        return dfs(root,root, k);
    }
    private boolean dfs(TreeNode node, TreeNode curr, int k) {
        if (curr==null) return false;
        return search(node, curr, k) || dfs(node, curr.left, k) || dfs(node, curr.right, k);
    }
    private boolean search(TreeNode node, TreeNode curr, int k) {
        if(node == null) return false;
        if(node.val + curr.val == k && node != curr) return true;
        else if (node.val + curr.val > k) return search(node.left, curr, k);
        else if (node.val + curr.val < k) return search(node.right, curr, k);
        return false;
    }
}

我忘记了这是个BST，所以搜索时可以根据大小，相应地去左右子树找。