周赛367（模拟、枚举 + 有序哈希、同向双指针、前后缀分解）

2023-10-22 12:28
文章标签 指针 模拟 有序 哈希 周赛 后缀 枚举 367 分解 同向

本文主要是介绍周赛367（模拟、枚举 + 有序哈希、同向双指针、前后缀分解），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 周赛367
    • [2903. 找出满足差值条件的下标 I](https://leetcode.cn/problems/find-indices-with-index-and-value-difference-i/)
      • 模拟
    • [2904. 最短且字典序最小的美丽子字符串](https://leetcode.cn/problems/shortest-and-lexicographically-smallest-beautiful-string/)
      • 枚举
      • 同向双指针
    • [2905. 找出满足差值条件的下标 II](https://leetcode.cn/problems/find-indices-with-index-and-value-difference-ii/)
      • 枚举 + 有序哈希
    • [2906. 构造乘积矩阵](https://leetcode.cn/problems/construct-product-matrix/)
      • 前后缀分解
    • [238. 除自身以外数组的乘积](https://leetcode.cn/problems/product-of-array-except-self/)

周赛367

2903. 找出满足差值条件的下标 I

简单

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，以及整数 indexDifference 和整数 valueDifference 。

你的任务是从范围 [0, n - 1] 内找出 2 个满足下述所有条件的下标 i 和 j ：

  • abs(i - j) >= indexDifference 且
  • abs(nums[i] - nums[j]) >= valueDifference

返回整数数组 answer。如果存在满足题目要求的两个下标，则 answer = [i, j] ；否则，answer = [-1, -1] 。如果存在多组可供选择的下标对，只需要返回其中任意一组即可。

注意：i 和 j 可能 相等 。

示例 1：

输入：nums = [5,1,4,1], indexDifference = 2, valueDifference = 4
输出：[0,3]
解释：在示例中，可以选择 i = 0 和 j = 3 。
abs(0 - 3) >= 2 且 abs(nums[0] - nums[3]) >= 4 。
因此，[0,3] 是一个符合题目要求的答案。
[3,0] 也是符合题目要求的答案。

示例 2：

输入：nums = [2,1], indexDifference = 0, valueDifference = 0
输出：[0,0]
解释：
在示例中，可以选择 i = 0 和 j = 0 。 
abs(0 - 0) >= 0 且 abs(nums[0] - nums[0]) >= 0 。 
因此，[0,0] 是一个符合题目要求的答案。 
[0,1]、[1,0] 和 [1,1] 也是符合题目要求的答案。

示例 3：

输入：nums = [1,2,3], indexDifference = 2, valueDifference = 4
输出：[-1,-1]
解释：在示例中，可以证明无法找出 2 个满足所有条件的下标。
因此，返回 [-1,-1] 。

提示：

  • 1 <= n == nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= indexDifference <= 100
  • 0 <= valueDifference <= 50

模拟

class Solution {public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {int n = nums.length;for(int i = 0; i < n; i++){for(int j = i; j < n; j++){if(Math.abs(i - j) >= indexDifference && Math.abs(nums[i] - nums[j]) >= valueDifference)return new int[]{i, j};}}return new int[]{-1, -1};}
}

2904. 最短且字典序最小的美丽子字符串

中等

给你一个二进制字符串 s 和一个正整数 k 。

如果 s 的某个子字符串中 1 的个数恰好等于 k ，则称这个子字符串是一个 美丽子字符串 。

令 len 等于 最短 美丽子字符串的长度。

返回长度等于 len 且字典序 最小 的美丽子字符串。如果 s 中不含美丽子字符串，则返回一个 空 字符串。

对于相同长度的两个字符串 a 和 b ，如果在 a 和 b 出现不同的第一个位置上，a 中该位置上的字符严格大于 b 中的对应字符，则认为字符串 a 字典序 大于 字符串 b 。

  • 例如，"abcd" 的字典序大于 "abcc" ，因为两个字符串出现不同的第一个位置对应第四个字符，而 d 大于 c 。

示例 1：

输入：s = "100011001", k = 3
输出："11001"
解释：示例中共有 7 个美丽子字符串：
1. 子字符串 "100011001" 。
2. 子字符串 "100011001" 。
3. 子字符串 "100011001" 。
4. 子字符串 "100011001" 。
5. 子字符串 "100011001" 。
6. 子字符串 "100011001" 。
7. 子字符串 "100011001" 。
最短美丽子字符串的长度是 5 。
长度为 5 且字典序最小的美丽子字符串是子字符串 "11001" 。

示例 2：

输入：s = "1011", k = 2
输出："11"
解释：示例中共有 3 个美丽子字符串：
1. 子字符串 "1011" 。
2. 子字符串 "1011" 。
3. 子字符串 "1011" 。
最短美丽子字符串的长度是 2 。
长度为 2 且字典序最小的美丽子字符串是子字符串 "11" 。

示例 3：

输入：s = "000", k = 1
输出：""
解释：示例中不存在美丽子字符串。

提示：

  • 1 <= s.length <= 100
  • 1 <= k <= s.length

枚举

class Solution {public String shortestBeautifulSubstring(String s, int k) {// 1 的个数不足 kif (s.replace("0", "").length() < k) {return "";}// 否则一定有解for (int size = k; ; size++) {String ans = "";for (int i = size; i <= s.length(); i++) {String t = s.substring(i - size, i);if ((ans.isEmpty() || t.compareTo(ans) < 0) && t.replace("0", "").length() == k) {ans = t;}}if (!ans.isEmpty()) {return ans;}}}
}

同向双指针

class Solution {public String shortestBeautifulSubstring(String s, int k) {int cnt1 = 0;// 统计字符串s中1的个数，若大于k，则一定有答案for(char c : s.toCharArray()) if(c == '1') cnt1 += 1;if(cnt1 < k) return "";cnt1 = 0;String res = s;int minlen = Integer.MAX_VALUE;int left = 0, right = 0;// 枚举右端点，缩小左端点for(; right < s.length(); right++){if(s.charAt(right) == '1')cnt1 += 1;while(cnt1 > k){if(s.charAt(left) == '1')cnt1 -= 1;left += 1;}// 即使排除s[left]=0 的合法情况，确保当前字符串长度最小while(cnt1 == k && s.charAt(left) == '0')left += 1;if(cnt1 == k && minlen >= (right - left + 1)){if(minlen == right - left + 1)res = s.substring(left, right + 1).compareTo(res) < 0 ? s.substring(left, right + 1) : res;else{minlen = right - left + 1;res = s.substring(left, right + 1);}}}return res;}
}

2905. 找出满足差值条件的下标 II

中等

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，以及整数 indexDifference 和整数 valueDifference 。

你的任务是从范围 [0, n - 1] 内找出 2 个满足下述所有条件的下标 i 和 j ：

  • abs(i - j) >= indexDifference 且
  • abs(nums[i] - nums[j]) >= valueDifference

返回整数数组 answer。如果存在满足题目要求的两个下标，则 answer = [i, j] ；否则，answer = [-1, -1] 。如果存在多组可供选择的下标对，只需要返回其中任意一组即可。

注意：i 和 j 可能 相等 。

示例 1：

输入：nums = [5,1,4,1], indexDifference = 2, valueDifference = 4
输出：[0,3]
解释：在示例中，可以选择 i = 0 和 j = 3 。
abs(0 - 3) >= 2 且 abs(nums[0] - nums[3]) >= 4 。
因此，[0,3] 是一个符合题目要求的答案。
[3,0] 也是符合题目要求的答案。

示例 2：

输入：nums = [2,1], indexDifference = 0, valueDifference = 0
输出：[0,0]
解释：
在示例中，可以选择 i = 0 和 j = 0 。 
abs(0 - 0) >= 0 且 abs(nums[0] - nums[0]) >= 0 。 
因此，[0,0] 是一个符合题目要求的答案。 
[0,1]、[1,0] 和 [1,1] 也是符合题目要求的答案。

示例 3：

输入：nums = [1,2,3], indexDifference = 2, valueDifference = 4
输出：[-1,-1]
解释：在示例中，可以证明无法找出 2 个满足所有条件的下标。
因此，返回 [-1,-1] 。

提示：

  • 1 <= n == nums.length <= 105
  • 0 <= nums[i] <= 109
  • 0 <= indexDifference <= 105
  • 0 <= valueDifference <= 109

枚举 + 有序哈希

class Solution {/**i - j >= indexDifi >= indexDif + j从小到大枚举iabs(nums[i] - nums[j]) >= valDiffnums[i] - nums[j] >= valDiff or nums[i] - nums[j] <= -valDiffnums[i] >= valDiff + nums[j]nums[i] <= -valDiff + nums[j]*/public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {int n = nums.length;if(n == 1){if(indexDifference == 0 && valueDifference == 0)return new int[]{0, 0};return new int[]{-1, -1};}TreeMap<Integer, Integer> map = new TreeMap<>();for(int i = indexDifference; i < n; i++){// 将窗口外的值i - indexDifference放入treemap中此时满足i - j >= indexDif条件map.put(nums[i - indexDifference], i - indexDifference);// 查看另外一个条件是否满足if(map.floorEntry(nums[i] - valueDifference) != null)return new int[]{map.floorEntry(nums[i] - valueDifference).getValue(), i};if(map.ceilingEntry(nums[i] + valueDifference) != null)return new int[]{map.ceilingEntry(nums[i] + valueDifference).getValue(), i};}return new int[]{-1, -1};}
}

2906. 构造乘积矩阵

中等

给你一个下标从 0 开始、大小为 n * m 的二维整数矩阵 grid ，定义一个下标从 0 开始、大小为 n * m 的的二维矩阵 p。如果满足以下条件，则称 p 为 grid 的 乘积矩阵 ：

  • 对于每个元素 p[i][j] ，它的值等于除了 grid[i][j] 外所有元素的乘积。乘积对 12345 取余数。

返回 grid 的乘积矩阵。

示例 1：

输入：grid = [[1,2],[3,4]]
输出：[[24,12],[8,6]]
解释：p[0][0] = grid[0][1] * grid[1][0] * grid[1][1] = 2 * 3 * 4 = 24
p[0][1] = grid[0][0] * grid[1][0] * grid[1][1] = 1 * 3 * 4 = 12
p[1][0] = grid[0][0] * grid[0][1] * grid[1][1] = 1 * 2 * 4 = 8
p[1][1] = grid[0][0] * grid[0][1] * grid[1][0] = 1 * 2 * 3 = 6
所以答案是 [[24,12],[8,6]] 。

示例 2：

输入：grid = [[12345],[2],[1]]
输出：[[2],[0],[0]]
解释：p[0][0] = grid[0][1] * grid[0][2] = 2 * 1 = 2
p[0][1] = grid[0][0] * grid[0][2] = 12345 * 1 = 12345. 12345 % 12345 = 0 ，所以 p[0][1] = 0
p[0][2] = grid[0][0] * grid[0][1] = 12345 * 2 = 24690. 24690 % 12345 = 0 ，所以 p[0][2] = 0
所以答案是 [[2],[0],[0]] 。

提示：

  • 1 <= n == grid.length <= 105
  • 1 <= m == grid[i].length <= 105
  • 2 <= n * m <= 105
  • 1 <= grid[i][j] <= 109

前后缀分解

class Solution {// 同238 前后缀分解，把二维数组看成一维数组private static final int MOD = 12345;public int[][] constructProductMatrix(int[][] grid) {int n = grid.length, m = grid[0].length;int[][] res = new int[n][m];long suf = 1; // 后缀乘积for(int i = n-1; i >= 0; i--){for(int j = m-1; j >= 0; j--){res[i][j] = (int)suf; // 初始化程后缀乘积suf = suf * grid[i][j] % MOD;}}long pre = 1;for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){res[i][j] = (int)(res[i][j] * pre % MOD);pre = pre * grid[i][j] % MOD;}}return res;}
}

238. 除自身以外数组的乘积

中等

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 **不要使用除法，**且在 O(*n*) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示：

  • 2 <= nums.length <= 105
  • -30 <= nums[i] <= 30
  • 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

**进阶：**你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）

class Solution {/**第 i 位的乘积 = [0:i]的乘积 * [i+1:]的乘积==> 前后缀分解*/public int[] productExceptSelf(int[] nums) {int n = nums.length;int[] suf = new int[n+1];suf[n] = 1;for(int i = n-1; i >= 0; i--){suf[i] = suf[i+1] * nums[i];}int pre = 1;int[] res = new int[n];for(int i = 0; i < n; i++){res[i] = pre * suf[i+1];pre *= nums[i];}return res;}
}

空间优化

class Solution {/**第 i 位的乘积 = [0:i]的乘积 * [i+1:]的乘积==> 前后缀分解枚举后缀的时候直接记到答案数组里*/public int[] productExceptSelf(int[] nums) {int n = nums.length;int suf = 1;int[] res = new int[n];for(int i = n-1; i >= 0; i--){res[i] = suf;suf *= nums[i];}int pre = 1;for(int i = 0; i < n; i++){res[i] = pre * res[i];pre *= nums[i];}return res;}
}

这篇关于周赛367（模拟、枚举 + 有序哈希、同向双指针、前后缀分解）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/261437。

相关文章

C++中unordered_set哈希集合的实现

C++中unordered_set哈希集合的实现

《C++中unordered_set哈希集合的实现》std::unordered_set是C++标准库中的无序关联容器,基于哈希表实现,具有元素唯一性和无序性特点,本文就来详细的介绍一下unorder... 目录一、概述二、头文件与命名空间三、常用方法与示例1. 构造与析构2. 迭代器与遍历3. 容量相关4
阅读更多...
一文解析C#中的StringSplitOptions枚举

一文解析C#中的StringSplitOptions枚举

《一文解析C#中的StringSplitOptions枚举》StringSplitOptions是C#中的一个枚举类型,用于控制string.Split()方法分割字符串时的行为,核心作用是处理分割后... 目录C#的StringSplitOptions枚举1.StringSplitOptions枚举的常用
阅读更多...
Redis中的有序集合zset从使用到原理分析

Redis中的有序集合zset从使用到原理分析

《Redis中的有序集合zset从使用到原理分析》Redis有序集合(zset)是字符串与分值的有序映射,通过跳跃表和哈希表结合实现高效有序性管理,适用于排行榜、延迟队列等场景,其时间复杂度低,内存占... 目录开篇：排行榜背后的秘密一、zset的基本使用1.1 常用命令1.2 Java客户端示例二、zse
阅读更多...
Rust 智能指针的使用详解

Rust 智能指针的使用详解

《Rust智能指针的使用详解》Rust智能指针是内存管理核心工具,本文就来详细的介绍一下Rust智能指针（Box、Rc、RefCell、Arc、Mutex、RwLock、Weak）的原理与使用场景,... 目录一、www.chinasem.cnRust 智能指针详解1、Box<T>：堆内存分配2、Rc<T>：
阅读更多...
Java 单元测试之Mockito 模拟静态方法与私有方法最佳实践

Java 单元测试之Mockito 模拟静态方法与私有方法最佳实践

《Java单元测试之Mockito模拟静态方法与私有方法最佳实践》本文将深入探讨如何使用Mockito来模拟静态方法和私有方法,结合大量实战代码示例,带你突破传统单元测试的边界,写出更彻底、更独立... 目录Mockito 简介：为什么选择它？环境准备模拟静态方法：打破“不可变”的枷锁传统困境解法一：使用M
阅读更多...
Kotlin 枚举类使用举例

Kotlin 枚举类使用举例

《Kotlin枚举类使用举例》枚举类（EnumClasses）是Kotlin中用于定义固定集合值的特殊类,它表示一组命名的常量,每个枚举常量都是该类的单例实例,接下来通过本文给大家介绍Kotl... 目录一、编程枚举类核心概念二、基础语法与特性1. 基本定义2. 带参数的枚举3. 实现接口4. 内置属性三、
阅读更多...
C#之枚举类型与随机数详解

C#之枚举类型与随机数详解

《C#之枚举类型与随机数详解》文章讲解了枚举类型的定义与使用方法,包括在main外部声明枚举,用于表示游戏状态和周几状态,枚举值默认从0开始递增,也可手动设置初始值以生成随机数... 目录枚举类型1.定义枚举类型(main外)2.使用生成随机数总结枚举类型1.定义枚举类型(main外)enum 类型名字
阅读更多...
C语言自定义类型之联合和枚举解读

C语言自定义类型之联合和枚举解读

《C语言自定义类型之联合和枚举解读》联合体共享内存,大小由最大成员决定,遵循对齐规则；枚举类型列举可能值,提升可读性和类型安全性,两者在C语言中用于优化内存和程序效率... 目录一、联合体1.1 联合体类型的声明1.2 联合体的特点1.2.1 特点11.2.2 特点21.2.3 特点31.3 联合体的大小1
阅读更多...
python运用requests模拟浏览器发送请求过程

python运用requests模拟浏览器发送请求过程

《python运用requests模拟浏览器发送请求过程》模拟浏览器请求可选用requests处理静态内容,selenium应对动态页面,playwright支持高级自动化,设置代理和超时参数,根据需... 目录使用requests库模拟浏览器请求使用selenium自动化浏览器操作使用playwright
阅读更多...
C++11作用域枚举(Scoped Enums)的实现示例

C++11作用域枚举(Scoped Enums)的实现示例

《C++11作用域枚举(ScopedEnums)的实现示例》枚举类型是一种非常实用的工具,C++11标准引入了作用域枚举,也称为强类型枚举,本文主要介绍了C++11作用域枚举(ScopedEnums... 目录一、引言二、传统枚举类型的局限性2.1 命名空间污染2.2 整型提升问题2.3 类型转换问题三、C
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2