周赛373(模拟、前缀和、排序+分组循环、质因数分解+前缀和+哈希表)

2023-11-28 08:01

本文主要是介绍周赛373(模拟、前缀和、排序+分组循环、质因数分解+前缀和+哈希表),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 周赛373
    • [2946. 循环移位后的矩阵相似检查](https://leetcode.cn/problems/matrix-similarity-after-cyclic-shifts/)
      • 模拟
    • [2947. 统计美丽子字符串 I](https://leetcode.cn/problems/count-beautiful-substrings-i/)
      • 前缀和 + 暴力枚举
    • [2948. 交换得到字典序最小的数组](https://leetcode.cn/problems/make-lexicographically-smallest-array-by-swapping-elements/)
      • 排序 + 分组循环
    • [2949. 统计美丽子字符串 II](https://leetcode.cn/problems/count-beautiful-substrings-ii/)
      • 质因数分解 + 前缀和 + 哈希表

周赛373

2946. 循环移位后的矩阵相似检查

简单

给你一个大小为 m x n 的整数矩阵 mat 和一个整数 k 。请你将矩阵中的 奇数 行循环 k 次,偶数 行循环 k 次。

如果初始矩阵和最终矩阵完全相同,则返回 true ,否则返回 false

示例 1:

输入:mat = [[1,2,1,2],[5,5,5,5],[6,3,6,3]], k = 2
输出:true
解释:初始矩阵如图一所示。
图二表示对奇数行右移一次且对偶数行左移一次后的矩阵状态。
图三是经过两次循环移位后的最终矩阵状态,与初始矩阵相同。
因此,返回 true 。

示例 2:

输入:mat = [[2,2],[2,2]], k = 3
输出:true
解释:由于矩阵中的所有值都相等,即使进行循环移位,矩阵仍然保持不变。因此,返回 true 。

示例 3:

输入:mat = [[1,2]], k = 1
输出:false
解释:循环移位一次后,mat = [[2,1]],与初始矩阵不相等。因此,返回 false 。

提示:

  • 1 <= mat.length <= 25
  • 1 <= mat[i].length <= 25
  • 1 <= mat[i][j] <= 25
  • 1 <= k <= 50

模拟

class Solution {public boolean areSimilar(int[][] mat, int k) {int m = mat.length, n = mat[0].length;while(k > n) k -= n;int flag = 1;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(mat[i][j] != mat[i][(j + flag * (k) + n) % n])return false;}flag = -flag;}return true;}
}

2947. 统计美丽子字符串 I

提示

中等

0

相关企业

给你一个字符串 s 和一个正整数 k

vowelsconsonants 分别表示字符串中元音字母和辅音字母的数量。

如果某个字符串满足以下条件,则称其为 美丽字符串

  • vowels == consonants,即元音字母和辅音字母的数量相等。
  • (vowels * consonants) % k == 0,即元音字母和辅音字母的数量的乘积能被 k 整除。

返回字符串 s非空美丽子字符串 的数量。

子字符串是字符串中的一个连续字符序列。

英语中的 元音字母'a''e''i''o''u'

英语中的 辅音字母 为除了元音字母之外的所有字母。

示例 1:

输入:s = "baeyh", k = 2
输出:2
解释:字符串 s 中有 2 个美丽子字符串。
- 子字符串 "baeyh",vowels = 2(["a","e"]),consonants = 2(["y","h"])。
可以看出字符串 "aeyh" 是美丽字符串,因为 vowels == consonants 且 vowels * consonants % k == 0 。
- 子字符串 "baeyh",vowels = 2(["a","e"]),consonants = 2(["b","y"])。
可以看出字符串 "baey" 是美丽字符串,因为 vowels == consonants 且 vowels * consonants % k == 0 。
可以证明字符串 s 中只有 2 个美丽子字符串。

示例 2:

输入:s = "abba", k = 1
输出:3
解释:字符串 s 中有 3 个美丽子字符串。
- 子字符串 "abba",vowels = 1(["a"]),consonants = 1(["b"])。
- 子字符串 "abba",vowels = 1(["a"]),consonants = 1(["b"])。
- 子字符串 "abba",vowels = 2(["a","a"]),consonants = 2(["b","b"])。
可以证明字符串 s 中只有 3 个美丽子字符串。

示例 3:

输入:s = "bcdf", k = 1
输出:0
解释:字符串 s 中没有美丽子字符串。

提示:

  • 1 <= s.length <= 1000
  • 1 <= k <= 1000
  • s 仅由小写英文字母组成。

前缀和 + 暴力枚举

class Solution {/**统计子数组 元音和辅音的出现次数然后枚举所有子数组*/public int beautifulSubstrings(String s, int k) {int n = s.length();int[] prev = new int[n+1];int[] prec = new int[n+1];for(int i = 0; i < n; i++){prev[i+1] = prev[i] + (check(s.charAt(i)) ? 1 : 0);prec[i+1] = prec[i] + (check(s.charAt(i)) ? 0 : 1);}int res = 0;for(int i = 1; i <= n; i++){for(int j = i+1; j <= n; j++){int vowel = prev[j] - prev[i-1];int cons = prec[j] - prec[i-1];if(vowel == cons && (vowel*cons)%k == 0)res += 1;}}return res;}public boolean check(char c){return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';}
}

2948. 交换得到字典序最小的数组

中等

给你一个下标从 0 开始的 正整数 数组 nums 和一个 正整数 limit

在一次操作中,你可以选择任意两个下标 ij如果 满足 |nums[i] - nums[j]| <= limit ,则交换 nums[i]nums[j]

返回执行任意次操作后能得到的 字典序最小的数组

如果在数组 a 和数组 b 第一个不同的位置上,数组 a 中的对应字符比数组 b 中的对应字符的字典序更小,则认为数组 a 就比数组 b 字典序更小。例如,数组 [2,10,3] 比数组 [10,2,3] 字典序更小,下标 0 处是两个数组第一个不同的位置,且 2 < 10

示例 1:

输入:nums = [1,5,3,9,8], limit = 2
输出:[1,3,5,8,9]
解释:执行 2 次操作:
- 交换 nums[1] 和 nums[2] 。数组变为 [1,3,5,9,8] 。
- 交换 nums[3] 和 nums[4] 。数组变为 [1,3,5,8,9] 。
即便执行更多次操作,也无法得到字典序更小的数组。
注意,执行不同的操作也可能会得到相同的结果。

示例 2:

输入:nums = [1,7,6,18,2,1], limit = 3
输出:[1,6,7,18,1,2]
解释:执行 3 次操作:
- 交换 nums[1] 和 nums[2] 。数组变为 [1,6,7,18,2,1] 。
- 交换 nums[0] 和 nums[4] 。数组变为 [2,6,7,18,1,1] 。
- 交换 nums[0] 和 nums[5] 。数组变为 [1,6,7,18,1,2] 。
即便执行更多次操作,也无法得到字典序更小的数组。

示例 3:

输入:nums = [1,7,28,19,10], limit = 3
输出:[1,7,28,19,10]
解释:[1,7,28,19,10] 是字典序最小的数组,因为不管怎么选择下标都无法执行操作。

提示:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= limit <= 109

排序 + 分组循环

https://leetcode.cn/problems/make-lexicographically-smallest-array-by-swapping-elements/solutions/2542762/pai-xu-fen-zu-xun-huan-pythonjavacgo-by-pbfey/

class Solution {/**把nums排序后,需要找到一个最长的连续段,相邻的数组差<=limit这一整段对应的下标集合,这些位置是可以排序的*/public int[] lexicographicallySmallestArray(int[] nums, int limit) {int n = nums.length;Integer[] ids = new Integer[n];for (int i = 0; i < n; i++) {ids[i] = i;}Arrays.sort(ids, (i, j) -> nums[i] - nums[j]);// ids[i]不是有序的,但是nums[ids[i]]是有序的int[] ans = new int[n];for (int i = 0; i < n; ) {int st = i;i++;while(i < n && nums[ids[i]] - nums[ids[i-1]] <= limit)i++;Integer[] subIds = Arrays.copyOfRange(ids, st, i);Arrays.sort(subIds);for (int j = 0; j < subIds.length; j++) {ans[subIds[j]] = nums[ids[st + j]];}}return ans;}
}

2949. 统计美丽子字符串 II

困难

给你一个字符串 s 和一个正整数 k

vowelsconsonants 分别表示字符串中元音字母和辅音字母的数量。

如果某个字符串满足以下条件,则称其为 美丽字符串

  • vowels == consonants,即元音字母和辅音字母的数量相等。
  • (vowels * consonants) % k == 0,即元音字母和辅音字母的数量的乘积能被 k 整除。

返回字符串 s非空美丽子字符串 的数量。

子字符串是字符串中的一个连续字符序列。

英语中的 元音字母'a''e''i''o''u'

英语中的 辅音字母 为除了元音字母之外的所有字母。

示例 1:

输入:s = "baeyh", k = 2
输出:2
解释:字符串 s 中有 2 个美丽子字符串。
- 子字符串 "baeyh",vowels = 2(["a","e"]),consonants = 2(["y","h"])。
可以看出字符串 "aeyh" 是美丽字符串,因为 vowels == consonants 且 vowels * consonants % k == 0 。
- 子字符串 "baeyh",vowels = 2(["a","e"]),consonants = 2(["b","y"])。
可以看出字符串 "baey" 是美丽字符串,因为 vowels == consonants 且 vowels * consonants % k == 0 。
可以证明字符串 s 中只有 2 个美丽子字符串。

示例 2:

输入:s = "abba", k = 1
输出:3
解释:字符串 s 中有 3 个美丽子字符串。
- 子字符串 "abba",vowels = 1(["a"]),consonants = 1(["b"])。
- 子字符串 "abba",vowels = 1(["a"]),consonants = 1(["b"])。
- 子字符串 "abba",vowels = 2(["a","a"]),consonants = 2(["b","b"])。
可以证明字符串 s 中只有 3 个美丽子字符串。

示例 3:

输入:s = "bcdf", k = 1
输出:0
解释:字符串 s 中没有美丽子字符串。

提示:

  • 1 <= s.length <= 5 * 104
  • 1 <= k <= 1000
  • s 仅由小写英文字母组成。

质因数分解 + 前缀和 + 哈希表

https://leetcode.cn/problems/count-beautiful-substrings-ii/solutions/2542274/fen-jie-zhi-yin-zi-qian-zhui-he-ha-xi-bi-ceil/

class Solution {/**转化:把元音看作1,辅音看作-1「元音字母和辅音字母的数量相等」就等价于:找到一个和为 0 的连续子数组。注意这种子数组的长度一定是偶数,因为元音辅音数量相等。设子数组长度为L,那么元音辅音数量都等于L/2所以「元音字母和辅音字母的数量的乘积能被 kkk 整除」等价于 (L/2)^2 mod k = 0==>   L^2 mod 4k = 0 如何去掉平方?如果一个数 L 的平方能被 n 整除,意味着什么?*/private static final int AEIOU_MASK = 1065233;public long beautifulSubstrings(String s, int k) {k = pSqrt(k * 4);Map<Integer, Integer> cnt = new HashMap<>();int n = s.length();int sum = n; // 保证非负cnt.put((k - 1) << 16 | sum, 1); // 添加 (k-1, sum)long ans = 0;for (int i = 0; i < n; i++) {int bit = (AEIOU_MASK >> (s.charAt(i) - 'a')) & 1;sum += bit * 2 - 1; // 1 -> 1    0 -> -1ans += cnt.merge((i % k) << 16 | sum, 1, Integer::sum) - 1; // ans += cnt[(i%k,sum)]++}return ans;}private int pSqrt(int n) {int res = 1;for (int i = 2; i * i <= n; i++) {int i2 = i * i;while (n % i2 == 0) {res *= i;n /= i2;}if (n % i == 0) {res *= i;n /= i;}}if (n > 1) {res *= n;}return res;}
}

这篇关于周赛373(模拟、前缀和、排序+分组循环、质因数分解+前缀和+哈希表)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/429357

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路: 1. 用一个 hash[ ] 数组存放输入的数字,令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ,检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999,第二行数从 10到99。 4. 剪枝。 代码: /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

usaco 1.2 Transformations(模拟)

我的做法就是一个一个情况枚举出来 注意计算公式: ( 变换后的矩阵记为C) 顺时针旋转90°:C[i] [j]=A[n-j-1] [i] (旋转180°和270° 可以多转几个九十度来推) 对称:C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时

hdu4431麻将模拟

给13张牌。问增加哪些牌可以胡牌。 胡牌有以下几种情况: 1、一个对子 + 4组 3个相同的牌或者顺子。 2、7个不同的对子。 3、13幺 贪心的思想: 对于某张牌>=3个,先减去3个相同,再组合顺子。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOExcepti