

LeetCode 月报 202105
source link: https://blog.nodr.ink/leetcode-monthly-202105/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

劳逸结合、快乐生活。
690. 员工的重要性
给定一个保存员工信息的数据结构,它包含了员工唯一的 id
、重要度和直系下属的 id
。
比如,员工 1
是员工 2
的领导,员工 2
是员工 3
的领导。他们相应的重要度为 15
、10
、5
。那么员工 1
的数据结构是 [1, 15, [2]]
,员工 2
的数据结构是 [2, 10, [3]]
,员工 3
的数据结构是 [3, 5, []]
。注意虽然员工 3
也是员工 1
的一个下属,但是由于并不是直系下属,因此没有体现在员工 1
的数据结构中。
现在输入一个公司的所有员工信息,以及单个员工 id
,返回这个员工和他所有下属的重要度之和。
输入:employees = [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], id = 1
输出:11
解释:员工 1 自身的重要度是 5,他有两个直系下属 2 和 3,而且 2 和 3 的重要度均为 3。因此员工 1 的总重要度是 5 + 3 + 3 = 11。
- 一个员工最多有一个直系领导,但是可以有多个直系下属;
- 员工数量不超过
2000
。
深度优先搜索。
Python"""
# Definition for Employee.
class Employee:
def __init__(self, id: int, importance: int, subordinates: List[int]):
self.id = id
self.importance = importance
self.subordinates = subordinates
"""
class Solution:
def getImportance(self, employees: list['Employee'], id: int) -> int:
return get_importance(employees, id)
def get_importance(employees: list['Employee'], id: int) -> int:
employees = {employee.id: employee for employee in employees}
stack, importance = [id], 0
while stack:
employee = employees[stack.pop()]
importance += employee.importance
stack += employee.subordinates
return importance
554. 砖墙
你的面前有一堵矩形的、由 n
行砖块组成的砖墙。这些砖块高度相同(也就是一个单位高)但是宽度不同。每一行砖块的宽度之和应该相等。
你现在要画一条自顶向下的、穿过最少砖块的垂线。如果你画的线只是从砖块的边缘经过,就不算穿过这块砖。你不能沿着墙的两个垂直边缘之一画线,这样显然是没有穿过一块砖的。
给你一个二维数组 wall
,该数组包含这堵墙的相关信息。其中,wall[i]
是一个代表从左至右每块砖的宽度的数组。你需要找出怎样画才能使这条线穿过的砖块数量最少,并且返回穿过的砖块数量。
输入:wall = [[1, 2, 2, 1], [3, 1, 2], [1, 3, 2], [2, 4], [3, 1, 2], [1, 3, 1, 1]]
输出:2
输入:wall = [[1], [1], [1]]
输出:3
n == len(wall)
;1 <= n <= 1e4
;1 <= len(wall[i]) <= 1e4
;1 <= sum(len(row) for row in wall[i]) <= 2e4
- 对于每一行
i
,sum(wall[i])
应当是相同的; 1 <= wall[i][j] <= 2 ** 31 - 1
。
impl Solution {
pub fn least_bricks(wall: Vec<Vec<i32>>) -> i32 {
let wall = wall.iter().map(|row| row.iter().map(|&brick| brick as usize));
least_bricks(wall) as i32
}
}
use std::collections::HashMap;
pub fn least_bricks<W, R>(wall: W) -> usize
where
W: IntoIterator<Item = R>,
R: IntoIterator<Item = usize>,
{
let (mut bounds, mut count) = (HashMap::new(), 0);
for row in wall {
let mut bound = 0;
for brick in row {
*bounds.entry(bound).or_insert(0) += 1;
bound += brick;
}
count += 1;
}
bounds.remove(&0);
count - bounds.values().max().copied().unwrap_or(0)
}
class Solution:
def leastBricks(self, wall: list[list[int]]) -> int:
return least_bricks(wall)
from collections import Counter
from itertools import accumulate, chain
def least_bricks(wall: list[list[int]]) -> int:
bounds = Counter(chain.from_iterable(accumulate(row[:-1]) for row in wall))
return len(wall) - max(bounds.values(), default=0)
7. 整数反转
给你一个 32 位的有符号整数 x
,返回将 x
中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围,则返回 0
。
假设环境不允许存储 64 位整数(有符号或无符号)。
输入:x = 123
输出:321
输入:x = -123
输出:-321
输入:x = 120
输出:21
输入:x = 0
输出:0
-2 ** 31 <= x <= 2 ** 31 - 1
。
impl Solution {
pub fn reverse(x: i32) -> i32 {
checked_reverse(x).unwrap_or(0)
}
}
pub fn checked_reverse(mut x: i32) -> Option<i32> {
let mut r: i32 = 0;
while x != 0 {
r = r.checked_mul(10)?.checked_add(x % 10)?;
x /= 10;
}
r.into()
}
1720. 解码异或后的数组
未知整数数组 arr
由 n
个非负整数组成。
经编码后变为长度为 n - 1
的另一个整数数组 encoded
,其中 encoded[i] = arr[i] ^ arr[i + 1]
。例如,arr = [1, 0, 2, 1]
经编码后得到 encoded = [1, 2, 3]
。
给你编码后的数组 encoded
和原数组 arr
的第一个元素 first
,也即 arr[0]
。
请解码返回原数组 arr
。可以证明答案存在并且是唯一的。
输入:encoded = [1, 2, 3], first = 1
输出:[1, 0, 2, 1]
解释:若 arr = [1, 0, 2, 1],那么 first = 1 且 encoded = [1 ^ 0, 0 ^ 2, 2 ^ 1] = [1, 2, 3]。
输入:encoded = [6, 2, 7, 3], first = 4
输出:[4, 2, 0, 7, 4]
2 <= n <= 1e4
;encoded.length == n - 1
;0 <= encoded[i] <= 1e5
;0 <= first <= 1e5
。
impl Solution {
pub fn decode(encoded: Vec<i32>, first: i32) -> Vec<i32> {
let (mut decoded, mut last) = (Vec::with_capacity(encoded.len()), first);
decoded.push(first);
for n in encoded {
last ^= n;
decoded.push(last);
}
decoded
}
}
use std::iter::once;
impl Solution {
pub fn decode(encoded: Vec<i32>, first: i32) -> Vec<i32> {
once(first)
.chain(encoded.into_iter().scan(first, |st, n| {
*st ^= n;
Some(*st)
}))
.collect()
}
}
class Solution:
def decode(self, encoded: list[int], first: int) -> list[int]:
return decode(encoded, first)
from operator import xor
from itertools import accumulate
def decode(encoded: list[int], first: int) -> list[int]:
return list(accumulate(encoded, xor, initial=first))
1486. 数组异或操作
给你两个整数,n
和 start
。
数组 nums
定义为:nums[i] = start + 2 * i
(下标从 0
开始)且 n == len(nums)
。
请返回 nums
中所有元素按位异或后得到的结果。
输入:n = 5, start = 0
输出:8
解释:数组 nums 为 [0, 2, 4, 6, 8],其中 0 ^ 2 ^ 4 ^ 6 ^ 8 = 8。
输入:n = 4, start = 3
输出:8
解释:数组 nums 为 [3, 5, 7, 9],其中 3 ^ 5 ^ 7 ^ 9 = 8。
输入:n = 1, start = 7
输出:7
输入:n = 10, start = 5
输出:2
1 <= n <= 1e3
;0 <= start <= 1e3
;n == len(nums)
。
impl Solution {
pub fn xor_operation(n: i32, start: i32) -> i32 {
xor_operation(n as usize, start as usize) as i32
}
}
use std::iter::successors;
use std::ops::BitXor;
pub fn xor_operation(n: usize, start: usize) -> usize {
successors(start.into(), |p| p.checked_add(2))
.take(n)
.fold(0, BitXor::bitxor)
}
首先,将原异或和式转变为计算连续整数的异或和,即
⨁k=0n−1(start+2k)=⨁k=0n−1(s+k)⏞high bits r×2+(startmod2)(nmod2)⏞low bit e,
其中 s=⌊start2⌋。这样一来,可以利用异或的对合律可知
r=(⨁k=0s−1k)⊕(⨁k=0s+n−1k).
将 ⨁k=0n−1k 记作 f(n),利用异或的如下性质
∀i∈N,⨁k=03(4i+k)=0,
可以快速计算
f(n)={0,if nmod4=0,n−1,if nmod4=1,1,if nmod4=2,n,if nmod4=3.
综合上述结论有
⨁k=0n−1(start+2k)=f(n)⊕f(s+n)⏞high bits r×2+(startmod2)(nmod2)⏞low bit e.
Rustimpl Solution {
pub fn xor_operation(n: i32, start: i32) -> i32 {
xor_operation(n as usize, start as usize) as i32
}
}
pub fn xor_operation(n: usize, start: usize) -> usize {
let (s, e) = (start >> 1, n & start & 1);
let r = sum_xor(s) ^ sum_xor(s + n);
r << 1 | e
}
fn sum_xor(n: usize) -> usize {
match n % 4 {
0 => 0,
1 => n - 1,
2 => 1,
3 => n,
_ => unreachable!(),
}
}
172. 阶乘后的零
给定一个整数 n
,返回 n!
结果尾数中零的数量。
输入: 3
输出: 0
解释: 3! = 6,尾数中没有零。
输入: 5
输出: 1
解释: 5! = 120,尾数中有 1 个零。
你算法的时间复杂度应为 O(logn)。
Rust
impl Solution {
pub fn trailing_zeroes(n: i32) -> i32 {
trailing_zeroes(n as usize) as i32
}
}
pub fn trailing_zeroes(n: usize) -> usize {
prime_factor_order_to(n, 5)
}
fn prime_factor_order_to(mut n: usize, f: usize) -> usize {
let mut p = 0;
while n >= f {
n /= f;
p += n;
}
p
}
872. 叶子相似的树
请考虑一棵二叉树上所有的叶子,这些叶子的值按从左到右的顺序排列形成一个叶值序列。
如果有两棵二叉树的叶值序列是相同,那么我们就认为它们是叶相似的。
如果给定的两个根结点分别为 root1
和 root2
的树是叶相似的,则返回 true
;否则返回 false
。
输入:root1 = [3, 5, 1, 6, 2, 9, 8, null, null, 7, 4], root2 = [3, 5, 1, 6, 7, 4, 2, null, null, null, null, null, null, 9, 8]
输出:true
输入:root1 = [1], root2 = [1]
输出:true
输入:root1 = [1], root2 = [2]
输出:false
输入:root1 = [1, 2], root2 = [2, 2]
输出:true
输入:root1 = [1, 2, 3], root2 = [1, 3, 2]
输出:false
- 给定的两棵树可能会有
1
到200
个结点; - 给定的两棵树上的值介于
0
到200
之间。
深度优先搜索
Rust// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn leaf_similar(
root1: Option<Rc<RefCell<TreeNode>>>,
root2: Option<Rc<RefCell<TreeNode>>>,
) -> bool {
leaves(root1) == leaves(root2)
}
}
fn leaves(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
root.map(|root| {
let (mut stack, mut leaves) = (vec![root], vec![]);
while let Some(node) = stack.pop() {
let node = node.borrow();
node.left.as_ref().cloned().map(|l| stack.push(l));
node.right.as_ref().cloned().map(|r| stack.push(r));
if node.left.as_ref().or(node.right.as_ref()).is_none() {
leaves.push(node.val);
}
}
leaves
}).unwrap_or_default()
}
叶子迭代器
Rust// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn leaf_similar(
root1: Option<Rc<RefCell<TreeNode>>>,
root2: Option<Rc<RefCell<TreeNode>>>,
) -> bool {
Iterator::eq(LeavesIter::new(root1), LeavesIter::new(root2))
}
}
struct LeavesIter {
stack: Vec<Rc<RefCell<TreeNode>>>,
}
impl LeavesIter {
fn new(root: Option<Rc<RefCell<TreeNode>>>) -> Self {
Self {
stack: root.into_iter().collect(),
}
}
}
impl Iterator for LeavesIter {
type Item = Rc<RefCell<TreeNode>>;
fn next(&mut self) -> Option<<Self as Iterator>::Item> {
while let Some(node) = self.stack.pop() {
let inner = node.borrow();
inner.left.as_ref().cloned().map(|l| self.stack.push(l));
inner.right.as_ref().cloned().map(|r| self.stack.push(r));
if inner.left.as_ref().or(inner.right.as_ref()).is_none() {
return node.clone().into();
}
}
return None;
}
}
1734. 解码异或后的排列
给你一个整数数组 perm
,它是前 n
个正整数的排列,且 n
是个奇数。
它被加密成另一个长度为 n - 1
的整数数组 encoded
,满足 encoded[i] = perm[i] ^ perm[i + 1]
。比方说,如果 perm = [1, 3, 2]
,那么 encoded = [2, 1]
。
给你 encoded
数组,请你返回原始数组 perm
。题目保证答案存在且唯一。
输入:encoded = [3, 1]
输出:[1, 2, 3]
解释:如果 perm = [1, 2, 3],那么 encoded = [1 ^ 2, 2 ^ 3] = [3, 1]。
输入:encoded = [6, 5, 4, 6]
输出:[2, 4, 1, 5, 3]
3 <= n < 1e5
;n
是奇数;len(encoded) == n - 1
。
正整数排列的全异或为
total=⨁k=1nk=⨁k=0n−1permk=perm0⊕(⨁k=1n−1permk).
编码结果的奇数项异或为
odd=⨁k=1⌊n/2⌋encoded2k−1=⨁k=1⌊n/2⌋(perm2k−1⊕perm2k)=⨁k=1n−1permk.
total⊕odd=perm0⊕(⨁k=1n−1permk)⊕(⨁k=1n−1permk)=perm0.
Pythonclass Solution:
def decode(self, encoded: list[int]) -> list[int]:
return decode(encoded)
from operator import xor
from itertools import accumulate
from functools import reduce
def decode(encoded: list[int]) -> list[int]:
first = reduce(xor, range(len(encoded) + 2)) ^ reduce(xor, encoded[1::2])
return list(accumulate(encoded, xor, initial=first))
use std::iter::once;
use std::ops::BitXor;
impl Solution {
pub fn decode(encoded: Vec<i32>) -> Vec<i32> {
let n = encoded.len() + 1;
let first = (1..=n as i32)
.chain(encoded.iter().skip(1).step_by(2).copied())
.fold(0, BitXor::bitxor);
once(first)
.chain(encoded.into_iter().scan(first, |st, e| {
*st ^= e;
Some(*st)
}))
.collect()
}
}
1310. 子数组异或查询
有一个正整数数组 arr
,现给你一个对应的查询数组 queries
,其中 queries[i] = [li, ri]
。
对于每个查询 i
,请你计算从 li
到 ri
的异或值(即 arr[li] ^ arr[li+1] ^ ... ^ arr[ri]
)作为本次查询的结果。
并返回一个包含给定查询 queries
所有结果的数组。
输入:arr = [1, 3, 4, 8], queries = [[0, 1], [1, 2], [0, 3], [3, 3]]
输出:[2, 7, 14, 8]
输入:arr = [4, 8, 2, 10], queries = [[2, 3], [1, 3], [0, 0], [0, 3]]
输出:[8, 0, 4, 4]
1 <= len(arr) <= 3e4
;1 <= arr[i] <= 1e9
;1 <= len(queries) <= 3e4
;len(queries[i]) == 2
;0 <= queries[i][0] <= queries[i][1] < len(arr)
。
impl Solution {
pub fn xor_queries(arr: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
let queries: Vec<_> = queries
.into_iter()
.map(|queries| (queries[0] as usize, queries[1] as usize))
.collect();
xor_queries(&arr, &queries)
}
}
pub fn xor_queries(arr: &[i32], queries: &[(usize, usize)]) -> Vec<i32> {
let prefix: Vec<_> = arr
.iter()
.scan(0, |st, n| {
*st ^= n;
Some(*st)
})
.collect();
queries
.iter()
.map(|&(l, r)| {
if l > 0 {
prefix[l - 1] ^ prefix[r]
} else {
prefix[r]
}
})
.collect()
}
class Solution:
def xorQueries(self, arr: list[int], queries: list[list[int]]) -> list[int]:
return xor_queries(arr, queries)
from operator import xor
from itertools import accumulate
def xor_queries(arr: list[int], queries: list[tuple[int, int]]) -> list[int]:
prefix = list(accumulate(arr, xor, initial=0))
return [prefix[l] ^ prefix[r + 1] for l, r in queries]
1679. K 和数对的最大数目
给你一个整数数组 nums
和一个整数 k
。
每一步操作中,你需要从数组中选出和为 k
的两个整数,并将它们移出数组。
返回你可以对数组执行的最大操作数。
输入:nums = [1, 2, 3, 4], k = 5
输出:2
输入:nums = [3, 1, 3, 4, 3], k = 6
输出:1
1 <= len(nums) <= 1e5
;1 <= nums[i] <= 1e9
;1 <= k <= 1e9
。
impl Solution {
pub fn max_operations(nums: Vec<i32>, k: i32) -> i32 {
max_operations(&nums, k) as i32
}
}
use std::collections::HashMap;
pub fn max_operations(nums: &[i32], k: i32) -> usize {
let (mut counter, mut result) = (HashMap::new(), 0);
for &n in nums {
match counter.get_mut(&(k - n)) {
Some(count) if *count > 0 => {
*count -= 1;
result += 1;
}
_ => *counter.entry(n).or_insert(0) += 1,
}
}
result
}
12. 整数转罗马数字
罗马数字包含以下七种字符:I、V、X、L、C、D、M。
例如,罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII,即为 X + II。27 写做 XXVII, 即为 XX + V + II。
通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:
- I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
- X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。
- C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。
给定一个整数,将其转为罗马数字。
输入:3
输出:"III"
输入:4
输出:"IV"
输入:9
输出:"IX"
输入:58
输出:"LVIII"
输入:1994
输出:"MCMXCIV"
1 <= num < 4e3
。
impl Solution {
pub fn int_to_roman(num: i32) -> String {
roman_impl::int_to_roman(num as usize)
}
}
pub mod roman_impl {
const VALUE_TO_DIGIT: [(usize, &str); 13] = [
(1, "I"),
(4, "IV"),
(5, "V"),
(9, "IX"),
(10, "X"),
(40, "XL"),
(50, "L"),
(90, "XC"),
(100, "C"),
(400, "CD"),
(500, "D"),
(900, "CM"),
(1000, "M"),
];
struct RomanIter {
left: usize,
index: usize,
}
impl RomanIter {
fn new(num: usize) -> Self {
Self {
left: num,
index: VALUE_TO_DIGIT.len() - 1,
}
}
}
impl Iterator for RomanIter {
type Item = &'static str;
fn next(&mut self) -> Option<<Self as Iterator>::Item> {
loop {
let (value, digit) = VALUE_TO_DIGIT[self.index];
if let Some(left) = self.left.checked_sub(value) {
self.left = left;
return digit.into();
} else {
self.index = self.index.checked_sub(1)?;
}
}
}
}
pub fn int_to_roman(num: usize) -> String {
RomanIter::new(num).collect()
}
}
Recommend
-
65
前言 掘金翻译计划目前翻译完成 1236 篇文章,官方文档及手册 13 个,共有近 1000 名译者贡献翻译和校对,GitHub Star 16600+。 掘金翻译计划 是一个翻译优质互联网技术文章的社区,内容覆盖 Android、iOS、前端、后端、区块链、
-
23
2019年4月,全球区块链投融资市场急剧降温。 根据互链脉搏研究院不完全统计,2019年4月,全球区块链领域共斩获37笔融资,项目数量接近3月份,但...
-
12
2021年周报 上周完成的事情 上周的收获和反思 完成的事情 本周完成的事情: Bob Jiang博客文章1篇,什么是敏捷开发 微信公众号5...
-
2
心到神知、上供人吃。共完成 17 题。 1006. 笨阶乘 🔗 来源 通常,正整数 n 的阶乘是所有小于或等于 n 的正整数的乘积。例如,fac...
-
7
假期正式结束了!这是新学期的第一份月报。诸事缠身,共完成 23 题。 303. 区域和检索 - 数组不可变 🔗 来源 给定一个整数数组 nums,求出数...
-
6
新年新气象,跑步逃离魔幻的 2020 年。 共计 30 题。充满并查集的一个月,已会默写。 605. 种花问题 🔗 来源 假设你有一个很长的花坛,一部分地块种植了花...
-
4
快过年了。重启「Rust 从入门到放弃」计划。 本月大概是滑动窗口月了,战绩 30 题。 888. 公平的糖果棒交换 🔗 来源 爱丽丝和鲍勃有不同大小的糖果棒:...
-
3
这个月也是顽张的一个月呢,共完成了 66 道题目。 34. 在排序数组中查找元素的第一个和最后一个位置 🔗 来源 给定一个按照...
-
4
慢慢变富 # 组合月报(202105) 2021-06-05...
-
1
202105 - 维基萌 快来收集自己喜欢的角色卡牌吧!
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK