文章

每日LeetCode 118-121

2021.4.16 ・ 共 764 字,您可能需要 2 分钟阅读

Tags: LeetCode

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

示例 1:

输入:
    3
   / \
  9  20
    /  \
   15   7
输出:[3, 14.5, 11]
解释:
第 0 层的平均值是 3 ,  第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Integer> counts = new ArrayList<>();
        List<Double> sums = new ArrayList<>();
        dfs(root, 0, counts, sums);
        List<Double> ans = new ArrayList<>();
        for (int i = 0 ; i < counts.size(); i++) {
            ans.add(sums.get(i) / counts.get(i));
        }
        return ans;
    }
    public void dfs(TreeNode root, int level, List<Integer> counts, List<Double> sums) {
        if (root == null) {
            return;
        }
        if (level < sums.size()){
            sums.set(level, sums.get(level) + root.val);
            counts.set(level, counts.get(level) + 1);
        }
        else {
            sums.add(1.0 * root.val);
            counts.add(1);
        }
        dfs(root.left, level + 1, counts, sums);
        dfs(root.right, level + 1, counts, sums);
    }
}

给定 n 个整数,找出平均数最大且长度为 k 的连续子数组,并输出该最大平均数。

示例:

输入:[1,12,-5,-6,50,3], k = 4
输出:12.75
解释:最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int n = nums.length;
        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        int maxSum = sum;
        for (int i = 1; i <= n - k; i++) {
            sum -= nums[i - 1];
            sum += nums[i + k - 1];
            maxSum = Math.max(sum, maxSum);
        }
        return 1.0 * maxSum / k;
    }
}

集合 s 包含从 1n 的整数。不幸的是,因为数据错误,导致集合里面某一个数字复制了成了集合里面的另外一个数字的值,导致集合 丢失了一个数字 并且 有一个数字重复

给定一个数组 nums 代表了集合 S 发生错误后的结果。

请你找出重复出现的整数,再找到丢失的整数,将它们以数组的形式返回。

示例 1:

输入:nums = [1,2,2,4]
输出:[2,3]
class Solution {
    public int[] findErrorNums(int[] nums) {
        int[] ans = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : nums) {
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        for (int i = 1; i <= nums.length; i++) {
            if (map.containsKey(i)) {
                if (map.get(i) == 2) {
                    ans[0] = i;
                }
            }
            else {
                ans[1] = i;
            }
        }
        return ans;
    }
}

给定两个以字符串形式表示的非负整数 num1num2,返回 num1num2 的乘积,它们的乘积也表示为字符串形式。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"
class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        int m = num1.length();
        int n = num2.length();
        int[] ans = new int[m + n];
        for (int i = m - 1; i >= 0; i--) {
            int x = num1.charAt(i) - '0';
            for (int j = n - 1; j >= 0; j--) {
                int y = num2.charAt(j) - '0';
                ans[i + j + 1] += x * y;
            }
        }
        for (int i = m + n - 1; i >= 1; i--) {
            if (ans[i] >= 10) {
                ans[i - 1] += ans[i] / 10;
                ans[i] %= 10;
            }
        }
        int index = ans[0] == 0 ? 1 : 0;
        StringBuffer ansStr = new StringBuffer();
        while (index < m + n) {
            ansStr.append(ans[index]);
            index++;
        }
        return ansStr.toString();
    }
}