【题解】—— LeetCode一周小结35

简介: LeetCode每日一道一周小结35

🌟欢迎来到 我的博客 —— 探索技术的无限可能!

🌟博客的简介(文章目录)


【题解】—— 每日一道题目栏


上接:【题解】—— LeetCode一周小结34

26.员工的重要性

题目链接:690. 员工的重要性

你有一个保存员工信息的数据结构,它包含了员工唯一的 id ,重要度和直系下属的 id 。

给定一个员工数组 employees,其中:

employees[i].id 是第 i 个员工的 ID。

employees[i].importance 是第 i 个员工的重要度。

employees[i].subordinates 是第 i 名员工的直接下属的 ID 列表。

给定一个整数 id 表示一个员工的 ID,返回这个员工和他所有下属的重要度的 总和。

示例 1:

输入:employees = [[1,5,[2,3]],[2,3,[]],[3,3,[]]], id = 1

输出:11

解释: 员工 1 自身的重要度是 5 ,他有两个直系下属 2 和 3 ,而且 2 和 3 的重要度均为 3 。因此员工 1 的总重要度是 5

  • 3 + 3 = 11 。

示例 2:

输入:employees = [[1,2,[5]],[5,-3,[]]], id = 5

输出:-3

解释:员工 5 的重要度为 -3 并且没有直接下属。 因此,员工 5 的总重要度为 -3。

提示:

1 <= employees.length <= 2000

1 <= employees[i].id <= 2000

所有的 employees[i].id 互不相同。

-100 <= employees[i].importance <= 100

一名员工最多有一名直接领导,并可能有多名下属。

employees[i].subordinates 中的 ID 都有效。

题解:

方法:哈希表

       

/*
// Definition for Employee.
class Employee {
    public int id;
    public int importance;
    public List<Integer> subordinates;
};
*/
class Solution {
    public int getImportance(List<Employee> employees, int id) {
        Map<Integer, Employee> employeeMap = new HashMap<>(employees.size());
        for (Employee e : employees) {
            employeeMap.put(e.id, e);
        }
        return dfs(employeeMap, id);
    }
    private int dfs(Map<Integer, Employee> employeeMap, int id) {
        Employee e = employeeMap.get(id);
        int res = e.importance;
        for (int subId : e.subordinates) {
            res += dfs(employeeMap, subId);
        }
        return res;
    }
}

27.找出唯一性数组的中位数

题目链接:3134. 找出唯一性数组的中位数

给你一个整数数组 nums 。数组 nums 的 唯一性数组 是一个按元素从小到大排序的数组,包含了 nums 的所有非空

子数组

中不同元素的个数。

换句话说,这是由所有 0 <= i <= j < nums.length 的 distinct(nums[i…j]) 组成的递增数组。

其中,distinct(nums[i…j]) 表示从下标 i 到下标 j 的子数组中不同元素的数量。

返回 nums 唯一性数组 的 中位数 。

注意,数组的 中位数 定义为有序数组的中间元素。如果有两个中间元素,则取值较小的那个。

示例 1:

输入:nums = [1,2,3]

输出:1

解释:

nums 的唯一性数组为 [distinct(nums[0…0]), distinct(nums[1…1]),

distinct(nums[2…2]), distinct(nums[0…1]), distinct(nums[1…2]),

distinct(nums[0…2])],即 [1, 1, 1, 2, 2, 3] 。唯一性数组的中位数为 1 ,因此答案是 1 。

示例 2:

输入:nums = [3,4,3,4,5]

输出:2

解释:

nums 的唯一性数组为 [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3] 。唯一性数组的中位数为

2 ,因此答案是 2 。

示例 3:

输入:nums = [4,3,5,4]

输出:2

解释:

nums 的唯一性数组为 [1, 1, 1, 1, 2, 2, 2, 3, 3, 3] 。唯一性数组的中位数为 2 ,因此答案是 2 。

提示:

1 <= nums.length <= 105

1 <= nums[i] <= 105

题解:

方法:二分

       

class Solution {
    public int medianOfUniquenessArray(int[] nums) {
        int n = nums.length;
        long k = ((long) n * (n + 1) / 2 + 1) / 2;
        int left = 0;
        int right = n;
        while (left + 1 < right) {
            int mid = (left + right) / 2;
            if (check(nums, mid, k)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }
    private boolean check(int[] nums, int upper, long k) {
        long cnt = 0;
        int l = 0;
        HashMap<Integer, Integer> freq = new HashMap<>();
        for (int r = 0; r < nums.length; r++) {
            freq.merge(nums[r], 1, Integer::sum); // 移入右端点
            while (freq.size() > upper) { // 窗口内元素过多
                int out = nums[l++];
                if (freq.merge(out, -1, Integer::sum) == 0) { // 移出左端点
                    freq.remove(out);
                }
            }
            cnt += r - l + 1; // 右端点固定为 r 时,有 r-l+1 个合法左端点
            if (cnt >= k) {
                return true;
            }
        }
        return false;
    }
}

28.分割字符频率相等的最少子字符串

题目链接:3144. 分割字符频率相等的最少子字符串

给你一个字符串 s ,你需要将它分割成一个或者更多的 平衡 子字符串。比方说,s == “ababcc” 那么 (“abab”, “c”, “c”) ,(“ab”, “abc”, “c”) 和 (“ababcc”) 都是合法分割,但是 (“a”, “bab”, “cc”) ,(“aba”, “bc”, “c”) 和 (“ab”, “abcc”) 不是,不平衡的子字符串用粗体表示。

请你返回 s 最少 能分割成多少个平衡子字符串。

注意:一个 平衡 字符串指的是字符串中所有字符出现的次数都相同。

示例 1:

输入:s = “fabccddg”

输出:3

解释:

我们可以将 s 分割成 3 个子字符串:("fab, “ccdd”, “g”) 或者 (“fabc”, “cd”, “dg”) 。

示例 2:

输入:s = “abababaccddb”

输出:2

解释:

我们可以将 s 分割成 2 个子字符串:(“abab”, “abaccddb”) 。

提示:

1 <= s.length <= 1000

s 只包含小写英文字母。

题解:

方法:记忆化搜索

       

class Solution {
    public int minimumSubstringsInPartition(String S) {
        char[] s = S.toCharArray();
        int n = s.length;
        int[] memo = new int[n];
        return dfs(n - 1, s, memo);
    }
    private int dfs(int i, char[] s, int[] memo) {
        if (i < 0) {
            return 0;
        }
        if (memo[i] > 0) { // 之前计算过
            return memo[i];
        }
        int res = Integer.MAX_VALUE;
        int[] cnt = new int[26];
        int k = 0, maxCnt = 0;
        for (int j = i; j >= 0; j--) {
            k += cnt[s[j] - 'a']++ == 0 ? 1 : 0;
            maxCnt = Math.max(maxCnt, cnt[s[j] - 'a']);
            if (i - j + 1 == k * maxCnt) {
                res = Math.min(res, dfs(j - 1, s, memo) + 1);
            }
        }
        memo[i] = res; // 记忆化
        return res;
    }
}

29.判断矩阵是否满足条件

题目链接:3142. 判断矩阵是否满足条件

给你一个大小为 m x n 的二维矩阵 grid 。你需要判断每一个格子 grid[i][j] 是否满足:

如果它下面的格子存在,那么它需要等于它下面的格子,也就是 grid[i][j] == grid[i + 1][j] 。

如果它右边的格子存在,那么它需要不等于它右边的格子,也就是 grid[i][j] != grid[i][j + 1] 。

如果 所有 格子都满足以上条件,那么返回 true ,否则返回 false 。

示例 1:

输入:grid = [[1,0,2],[1,0,2]]

输出:true

解释:

网格图中所有格子都符合条件。

示例 2:

输入:grid = [[1,1,1],[0,0,0]]

输出:false

解释:

同一行中的格子值都相等。

示例 3:

输入:grid = [[1],[2],[3]]

输出:false

解释:

同一列中的格子值不相等。

提示:

1 <= n, m <= 10

0 <= grid[i][j] <= 9

题解:

       

class Solution {
    public boolean satisfiesConditions(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (j > 0 && grid[i][j] == grid[i][j - 1] ||
                    i > 0 && grid[i][j] != grid[i - 1][j]) {
                    return false;
                }
            }
        }
        return true;
    }
}

30.所有数对中数位差之和

题目链接:3153. 所有数对中数位差之和

你有一个数组 nums ,它只包含 正 整数,所有正整数的数位长度都 相同 。

两个整数的 数位差 指的是两个整数 相同 位置上不同数字的数目。

请你返回 nums 中 所有 整数对里,数位差之和。

示例 1:

输入:nums = [13,23,12]

输出:4

解释: 计算过程如下:

  • 13 和 23 的数位差为 1 。
  • 13 和 12 的数位差为 1 。
  • 23 和 12 的数位差为 2 。 所以所有整数数对的数位差之和为 1 + 1 + 2 = 4 。

示例 2:

输入:nums = [10,10,10,10]

输出:0

解释: 数组中所有整数都相同,所以所有整数数对的数位不同之和为 0 。

提示:

2 <= nums.length <= 105

1 <= nums[i] < 109

nums 中的整数都有相同的数位长度。

题解:

方法:拆位法

       

class Solution {
    public long sumDigitDifferences(int[] nums) {
        long ans = 0;
        int[][] cnt = new int[Integer.toString(nums[0]).length()][10];
        for (int k = 0; k < nums.length; k++) {
            int x = nums[k];
            for (int i = 0; x > 0; x /= 10, i++) {
                ans += k - cnt[i][x % 10]++;
            }
        }
        return ans;
    }
}

31.构造相同颜色的正方形

题目链接:3127. 构造相同颜色的正方形

给你一个二维 3 x 3 的矩阵 grid ,每个格子都是一个字符,要么是 ‘B’ ,要么是 ‘W’ 。字符 ‘W’ 表示白色,字符 ‘B’ 表示黑色。

你的任务是改变 至多一个 格子的颜色,使得矩阵中存在一个 2 x 2 颜色完全相同的正方形。

如果可以得到一个相同颜色的 2 x 2 正方形,那么返回 true ,否则返回 false 。

示例 1:

输入:grid = [[“B”,“W”,“B”],[“B”,“W”,“W”],[“B”,“W”,“B”]]

输出:true

解释:

修改 grid[0][2] 的颜色,可以满足要求。

示例 2:

输入:grid = [[“B”,“W”,“B”],[“W”,“B”,“W”],[“B”,“W”,“B”]]

输出:false

解释:

只改变一个格子颜色无法满足要求。

示例 3:

输入:grid = [[“B”,“W”,“B”],[“B”,“W”,“W”],[“B”,“W”,“W”]]

输出:true

解释:

grid 已经包含一个 2 x 2 颜色相同的正方形了。

提示:

grid.length == 3

grid[i].length == 3

grid[i][j] 要么是 ‘W’ ,要么是 ‘B’ 。

题解:

方法:遍历

       

class Solution {
    public boolean canMakeSquare(char[][] grid) {
        return check(grid, 0, 0) || check(grid, 0, 1) || check(grid, 1, 0) || check(grid, 1, 1);
    }
    private boolean check(char[][] grid, int i, int j) {
        int[] cnt = new int[2];
        cnt[grid[i][j] & 1]++;
        cnt[grid[i][j + 1] & 1]++;
        cnt[grid[i + 1][j] & 1]++;
        cnt[grid[i + 1][j + 1] & 1]++;
        return cnt[0] != 2;
    }
}

2024.9

1.在既定时间做作业的学生人数

题目链接:1450. 在既定时间做作业的学生人数

给你两个整数数组 startTime(开始时间)和 endTime(结束时间),并指定一个整数 queryTime 作为查询时间。

已知,第 i 名学生在 startTime[i] 时开始写作业并于 endTime[i] 时完成作业。

请返回在查询时间 queryTime 时正在做作业的学生人数。形式上,返回能够使 queryTime 处于区间 [startTime[i], endTime[i]](含)的学生人数。

示例 1:

输入:startTime = [1,2,3], endTime = [3,2,7], queryTime = 4

输出:1

解释:一共有 3 名学生。

第一名学生在时间 1 开始写作业,并于时间 3 完成作业,在时间 4 没有处于做作业的状态。

第二名学生在时间 2 开始写作业,并于时间 2 完成作业,在时间 4 没有处于做作业的状态。

第三名学生在时间 3 开始写作业,预计于时间 7 完成作业,这是是唯一一名在时间 4 时正在做作业的学生。

示例 2:

输入:startTime = [4], endTime = [4], queryTime = 4

输出:1

解释:在查询时间只有一名学生在做作业。

示例 3:

输入:startTime = [4], endTime = [4], queryTime = 5

输出:0

示例 4:

输入:startTime = [1,1,1,1], endTime = [1,3,2,4], queryTime = 7

输出:0

示例 5:

输入:startTime = [9,8,7,6,5,4,3,2,1], endTime =

[10,10,10,10,10,10,10,10,10], queryTime = 5

输出:5

提示:

startTime.length == endTime.length

1 <= startTime.length <= 100

1 <= startTime[i] <= endTime[i] <= 1000

1 <= queryTime <= 1000

题解:

方法:遍历

       

class Solution {
    public int busyStudent(int[] startTime, int[] endTime, int queryTime) {
        int ans = 0;
        for (int i = 0; i < startTime.length; i++) {
            if (startTime[i] <= queryTime && queryTime <= endTime[i]) {
                ans++;
            }
        }
        return ans;
    }
}

下接:【题解】—— LeetCode一周小结36


相关文章
|
1月前
|
测试技术 索引
【题解】—— LeetCode一周小结40
LeetCode每日一道一周小结40
|
3月前
|
Perl
|
5月前
|
人工智能 BI
|
5月前
|
算法
|
4月前
|
测试技术 索引
|
5月前
|
机器学习/深度学习