且听疯吟

leetcode weekly contest 398

2024-05-21

leetcode weekly contest 398

连续两周难的题目，又变成简单题目了，T4 确实太暴力模板了。

100310. 特殊数组 I

如果数组的每一对相邻元素都是两个奇偶性不同的数字，则该数组被认为是一个 特殊数组 。

Aging 有一个整数数组 nums。如果 nums 是一个 特殊数组 ，返回 true，否则返回 false。

示例 1：

输入：nums = [1]

输出：true

解释：

只有一个元素，所以答案为 true。

示例 2：

输入：nums = [2,1,4]

输出：true

解释：

只有两对相邻元素： (2,1) 和 (1,4)，它们都包含了奇偶性不同的数字，因此答案为 true。

示例 3：

输入：nums = [4,3,1,6]

输出：false

解释：

nums[1] 和 nums[2] 都是奇数。因此答案为 false。

提示：

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100

https://leetcode.cn/contest/weekly-contest-396/problems/valid-word/

题意

直接模拟

思路

  1. 直接模拟即可，检测前后相邻两个元素的奇偶性是否不同即可。
  2. 复杂度分析：
  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(1)$。

代码

class Solution:
    def isArraySpecial(self, nums: List[int]) -> bool:
        return sum(1 for i in range(1, len(nums)) if ((nums[i] ^ nums[i - 1]) & 1) == 0) == 0
impl Solution {
    pub fn is_array_special(nums: Vec<i32>) -> bool {
        for i in 1..nums.len() {
            if ((nums[i] ^ nums[i - 1]) & 1) == 0 {
                return false;
            }
        }
        return true;
    }
}

3152. 特殊数组 II

如果数组的每一对相邻元素都是两个奇偶性不同的数字，则该数组被认为是一个 特殊数组 。

周洋哥有一个整数数组 nums 和一个二维整数矩阵 queries，对于 queries[i] = [fromi, toi]，请你帮助周洋哥检查子数组 nums[fromi..toi] 是不是一个 特殊数组 。

返回布尔数组 answer，如果 nums[fromi..toi] 是特殊数组，则 answer[i] 为 true ，否则，answer[i] 为 false 。

示例 1：

输入：nums = [3,4,1,2,6], queries = [[0,4]]

输出：[false]

解释：

子数组是 [3,4,1,2,6]。2 和 6 都是偶数。

示例 2：

输入：nums = [4,3,1,6], queries = [[0,2],[2,3]]

输出：[false,true]

解释：

  1. 子数组是 [4,3,1]。3 和 1 都是奇数。因此这个查询的答案是 false。
  2. 子数组是 [1,6]。只有一对：(1,6)，且包含了奇偶性不同的数字。因此这个查询的答案是 true。

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105
  • 1 <= queries.length <= 105
  • queries[i].length == 2
  • 0 <= queries[i][0] <= queries[i][1] <= nums.length - 1

地址

https://leetcode.cn/contest/weekly-contest-398/problems/special-array-ii/

题意

统计长度即可

思路

  1. 依次统计以 $i$ 为结尾的特殊数组的最大长度，每次查询时检测是否满足要求即可。
  2. 复杂度分析：
  • 时间复杂度：$O(n)$，其中 $n$ 表示给定的数组的长度。
  • 空间复杂度：$O(n)$，其中 $n$ 表示给定的数组的长度。

代码

class Solution:
    def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:
        cnt = [1] * len(nums)
        for i in range(1, len(nums)):
            cnt[i] = 1 + cnt[i - 1] if ((nums[i] ^ nums[i - 1]) & 1) == 1 else 1
        return [True if cnt[r] >= r - l + 1 else False for l, r in queries]
impl Solution {
    pub fn is_array_special(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<bool> {
        let mut cnt = vec![1; nums.len()];
        for i in 1..nums.len() {
            if ((nums[i] ^ nums[i - 1]) & 1) == 1 {
                cnt[i] = cnt[i - 1] + 1;
            }
        }
        let mut res = vec![false; queries.len()];
        for (i, q) in queries.iter().enumerate() {
            let l = q[0];
            let r = q[1];
            if cnt[r as usize] >= r - l + 1 {
                res[i] = true;
            }
        }
        return res;
    }
}

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 中的整数都有相同的数位长度。

地址

https://leetcode.cn/contest/weekly-contest-398/problems/sum-of-digit-differences-of-all-pairs/

题意

数学

思路

  1. 对于两个字符串 $s,t$ ，判断其是否为同位字符串，方法比较简单，我们只需要要比较 $s,t$ 中所有的字符数目是否相等即可，按照题目要求需要找到同位字符串的最小连接长度，我们依次从小到大枚举长度 $l$ 即可，此时需要满足 $n \mod l = 0$ 即可，即 $l$ 一定是 $n$ 的因子，此时我们直接枚举 $l$ 即可，对于给定的整数 $n$ ，它最多有 $\log n$ 个因子，我们直接枚举即可，并检测在长度 $l$ 下，字符串 $s$ 分割程长度为 $l$ 的子字符串是否满足均为同位字符串即可。

  2. 复杂度：

  • 时间复杂度：$O(n \log n |\Sigma|)$，其中 $n$ 表示给定的字符串的长度，$|\Sigma|$ 表示字符集的数目；
  • 空间复杂度：$O(|\Sigma|)$；

代码

class Solution:
    def sumDigitDifferences(self, nums: List[int]) -> int:
        n = len(nums)
        cnt = [[0] * 10 for _ in range(10)]
        res = 0
        for i, x in enumerate(nums):
            s = str(x)
            for j, ch in enumerate(s):
                res += i - cnt[j][ord(ch) - ord('0')]
            for j, ch in enumerate(s):
                cnt[j][ord(ch) - ord('0')] += 1
        return res
impl Solution {
    pub fn sum_digit_differences(nums: Vec<i32>) -> i64 {
        let n = nums.len();
        let mut cnt = vec![vec![0; 10]; 10];
        let mut res = 0 as i64;

        for (i, &x) in nums.iter().enumerate() {
            let s = x.to_string();
            for (j, ch) in s.chars().enumerate() {
                res += (i as i32 - cnt[j][ch.to_digit(10).unwrap() as usize]) as i64;
            }
            for (j, ch) in s.chars().enumerate() {
                cnt[j][ch.to_digit(10).unwrap() as usize] += 1;
            }
        }
        res
    }
}

3154. 到达第 K 级台阶的方案数

给你有一个 非负 整数 k 。有一个无限长度的台阶，最低 一层编号为 0 。

虎老师有一个整数 jump ，一开始值为 0 。虎老师从台阶 1 开始，虎老师可以使用 任意 次操作，目标是到达第 k 级台阶。假设虎老师位于台阶 i ，一次 操作 中，虎老师可以：

  • 向下走一级到 i - 1 ，但该操作 不能 连续使用，如果在台阶第 0 级也不能使用。
  • 向上走到台阶 i + 2jump 处，然后 jump 变为 jump + 1 。

请你返回虎老师到达台阶 k 处的总方案数。

注意 ，虎老师可能到达台阶 k 处后，通过一些操作重新回到台阶 k 处，这视为不同的方案。

示例 1：

输入：k = 0

输出：2

解释：

2 种到达台阶 0 的方案为：

  • 虎老师从台阶 1 开始。
    • 执行第一种操作，从台阶 1 向下走到台阶 0 。
  • 虎老师从台阶 1 开始。
    • 执行第一种操作，从台阶 1 向下走到台阶 0 。
    • 执行第二种操作，向上走 20 级台阶到台阶 1 。
    • 执行第一种操作，从台阶 1 向下走到台阶 0 。

示例 2：

输入：k = 1

输出：4

解释：

4 种到达台阶 1 的方案为：

  • 虎老师从台阶 1 开始，已经到达台阶 1 。
  • 虎老师从台阶 1 开始。
    • 执行第一种操作，从台阶 1 向下走到台阶 0 。
    • 执行第二种操作，向上走 20 级台阶到台阶 1 。
  • 虎老师从台阶 1 开始。
    • 执行第二种操作，向上走 20 级台阶到台阶 2 。
    • 执行第一种操作，向下走 1 级台阶到台阶 1 。
  • 虎老师从台阶 1 开始。
    • 执行第一种操作，从台阶 1 向下走到台阶 0 。
    • 执行第二种操作，向上走 20 级台阶到台阶 1 。
    • 执行第一种操作，向下走 1 级台阶到台阶 0 。
    • 执行第二种操作，向上走 21 级台阶到台阶 2 。
    • 执行第一种操作，向下走 1 级台阶到台阶 1 。

提示：

  • 0 <= k <= 109

地址

https://leetcode.cn/contest/weekly-contest-398/problems/find-number-of-ways-to-reach-the-k-th-stair/

题意

记忆化搜索，组合数学

思路

  1. 当然 记忆化搜索 的解法就非常容易了，设当前到达的位置为 $pos$，已经使用操作 $2$ 跳了 $jump$ 次，上一次的操作是否为操作 $1$，那么本次进行操作时判断如下：

    • 如果当前的位置大于 $k+1$ 时，此时无论如何操作都无法再回到 $k$ ，此时我们应该直接退出；
    • 如果当前的位置等于 $k$ 时，此时我们将计数加 $1$;
    • 如果上一次的操作是减 $1$ 操作时，此时我们就不能再进行减 $1$ 操作，应该进行操作 $2$，跳到 $i+ 2^{jump}$ 处，同时 $jump + 1$​，标志位同时复原；
    • 如果上一次的操作是操作 $2$ 操作时，此时我们即可以减 $1$ 操作，也可以进行操作 $2$，如果进行减 $1$ 操作，则当前位置变为 $pos - 1$，标记位进行标记；如果进行操作 $2$ ，则跳到 $i + 2^{jump}$​ 处；

  2. 组合数学的解法就非常容易了，由于初始位置处于 $1$ ，我们假设进行了 $j$ 次操作 $2$，进行了 $m$ 次操作 $1$ ，最终到达 $k$，此时可以知道一定满足 $1 + 2^0 + 2^1 + 2^{j-1} - m = k$，将等式变换可以得到 $2^j - m = k$，此时 $m = 2^j - k$，由于相邻两次不能进行减 $1$ 操作，此时我们可以利用隔板法，在 $j + 1$ 个位置中选择 $m$ 个来做减 $1$ 操作，此时方案数即为 $\dbinom{j+1}{m}$, 我们只需要找到满足题目要求的 $j,m$ 即可。

  3. 复杂度分析:

  • 时间复杂度：$O(\log^2 k)$，根据方法一可以知道 $jump$ 最多可以取 $\log k$ 次，；
  • 空间复杂度：$O(1ogk^2)$；

代码

class Solution:
    def waysToReachStair(self, k: int) -> int:        
        @cache
        def dfs(pos, jump, pre):
            res = 0
            if pos == k:
                res += 1
            if pos > k + 1:
                return 0
            if pre == 0 and pos - 1 >= 0:
                res += dfs(pos - 1, jump, 1)
            res += dfs(pos + 2**jump, jump + 1, 0)
            return res
        
        return dfs(1, 0, 0)

    
class Solution:
    def waysToReachStair(self, k: int) -> int:    
        res = 0
        for i in range(30):
            m = 2**i - k
            if m >= 0 and m <= i + 1:
                res += comb(i + 1, m)
        return res
            
                
use std::collections::HashMap;

impl Solution {
    pub fn ways_to_reach_stair(k: i32) -> i32 {
        let mut memo: HashMap<(i32, i32, i32), i32> = HashMap::new();
        fn dfs(k: i32, pos: i32, jump: i32, pre: i32, memo: &mut HashMap<(i32, i32, i32), i32>) -> i32 {
            if pos > k + 1 {
                return 0;
            }
            if let Some(&res) = memo.get(&(pos, jump, pre)) {
                return res;
            }
            let mut res = 0;
            if pos == k {
                res += 1;
            }
            if pre == 0 && pos - 1 >= 0 {
                res += dfs(k, pos - 1, jump, 1, memo);
            }
            res += dfs(k, pos + (1 << jump), jump + 1, 0, memo);
            memo.insert((pos, jump, pre), res);
            res
        }
        return dfs(k, 1, 0, 0, &mut memo);
    }
}
impl Solution {
    pub fn ways_to_reach_stair(k: i32) -> i32 {
        let mut comb: Vec<Vec<i32>> = vec![vec![1; 31]; 31];
        for i in 2..= 30 {
            for j in 1..i {
                comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
            }
        }

        let mut res = 0;
        for i in 0 ..= 30 {
            let m = (1 << i) - k;
            if m >= 0 && m <= i + 1 {
                res += comb[(i + 1) as usize][m as usize];
            }
        }
        res
    }
}

欢迎关注和打赏，感谢支持！

Tags: 题解 力扣周赛赛
← leetcode biweekly contest 129 leetcode biweekly contest 130 →

扫描二维码，分享此文章