5993. 将找到的值乘以 2-周赛题1⭐️寒假新坑——代码之狐的每日做题笔记
给你一个整数数组 nums ，另给你一个整数 original ，这是需要在 nums 中搜索的第一个数字。
接下来，你需要按下述步骤 *** 作：
- 如果在 nums 中找到 original ，将 original 乘以 2 ，得到新 original（即，令 original = 2 * original）。否则，停止这一过程。只要能在数组中找到新 original ，就对新 original 继续 重复 这一过程**。**
返回 original 的 最终 值。
class Solution {
public int findFinalValue(int[] nums, int original) {
Arrays.sort(nums);
for(int i:nums){
if(original==i){
original*=2;
}
}
return original;
}
}
5981. 分组得分最高的所有下标-周赛题2
给你一个下标从 0 开始的二进制数组 nums ，数组长度为 n 。nums 可以按下标 i（ 0 <= i <= n ）拆分成两个数组（可能为空）：numsleft 和 numsright 。
numsleft 包含 nums 中从下标 0 到 i - 1 的所有元素**（包括** 0 和 i - 1 ），而 numsright 包含 nums 中从下标 i 到 n - 1 的所有元素**（包括** i 和 n - 1 ）。如果 i == 0 ，numsleft 为 空 ，而 numsright 将包含 nums 中的所有元素。如果 i == n ，numsleft 将包含 nums 中的所有元素，而 numsright 为 空 。
下标 i 的 分组得分 为 numsleft 中 0 的个数和 numsright 中 1 的个数之 和 。
返回 分组得分 最高 的 所有不同下标 。你可以按 任意顺序 返回答案。
class Solution {
public List maxScoreIndices(int[] nums) {
List list=new ArrayList<>();
for(int i=1;i0?(i-nums[i-1]+nums[nums.length-1]-nums[i-1]):nums[nums.length-1]);
if(max();
list.add(i);
max=mid;
}
else if(max==mid){
list.add(i);
}
}
return list;
}
}
5994. 查找给定哈希值的子串-Mid-周赛题3
题目描述：
给定整数 p 和 m ，一个长度为 k 且下标从 0 开始的字符串 s 的哈希值按照如下函数计算：
hash(s, p, m) = (val(s[0]) * p0 + val(s[1]) * p1 + ... + val(s[k-1]) * pk-1) mod m.
其中 val(s[i]) 表示 s[i] 在字母表中的下标，从 val('a') = 1 到 val('z') = 26 。
给你一个字符串 s 和整数 power，modulo，k 和 hashValue 。请你返回 s 中 第一个 长度为 k 的 子串 sub ，满足 hash(sub, power, modulo) == hashValue 。
测试数据保证一定 存在 至少一个这样的子串。
子串 定义为一个字符串中连续非空字符组成的序列。
解题思路：此题正解是使用滑动窗口，找到每次滑动窗口hash值的增减规律，从后往前滑动，每次删除最后一个字母附加的值，剩余值统一乘以power（相当于位置附加价值后移一位），然后补入新值
代码实现：//此题非本人实现，仅仅添加部分代码以供理解
//暴力破解
class Solution {
public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
long[] pows = new long[k];
pows[0] = 1;
for (int i = 1; i < k; i++) {
pows[i] = pows[i - 1] * power % modulo;
}
for (int i = 0; i <= s.length() - k; i++) {
String subStr = s.substring(i, i + k);
if (val(subStr, pows, modulo) == hashValue) {
return subStr;
}
}
return "";
}
private int val(String subStr, long[] pows, int modulo) {
long res = 0;
for (int i = 0; i < subStr.length(); i++) {
res += (subStr.charAt(i) - 'a' + 1) * pows[i];
res %= modulo;
}
return (int) (res % modulo);
}
}
//从后往前滑动窗口,利用数学规律
class Solution {
public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
char[] str = s.toCharArray();
int n = str.length;
long x = 0, b = 1;
String ans = null;
//从后往前计算值，最后一个 k长子串 hash值
for (int i = 0; i < k; i++) {
char ch = str[n - 1 - i];
x = (x * power + ch - 'a' + 1) % modulo;
}
if (x == hashValue)
ans = s.substring(n - k);
//计算pow(power,k-1)%modulo待用
for (int i = 0; i < k - 1; i++)
b = b * power % modulo;
//每次回退1个，减去最后一个字母的值（b * (str[i + k] - 'a' + 1)，剩余值同一乘以power，在加上前移录入的一个字母值
for (int i = n - k - 1; i >= 0; i--) {
x = (x + modulo - (b * (str[i + k] - 'a' + 1) % modulo)) % modulo;
char ch = str[i];
x = (x * power + ch - 'a' + 1) % modulo;
if (x == hashValue)
ans = s.substring(i, i + k);
}
return ans;
}
}
5995. 字符串分组-Hard-周赛题4
题目描述：
给你一个下标从 0 开始的字符串数组 words 。每个字符串都只包含 小写英文字母 。words 中任意一个子串中，每个字母都至多只出现一次。
如果通过以下 *** 作之一，我们可以从 s1 的字母集合得到 s2 的字母集合，那么我们称这两个字符串为 关联的 ：
往 s1 的字母集合中添加一个字母。从 s1 的字母集合中删去一个字母。将 s1 中的一个字母替换成另外任意一个字母（也可以替换为这个字母本身）。
数组 words 可以分为一个或者多个无交集的 组 。一个字符串与一个组如果满足以下 任一 条件，它就属于这个组：
它与组内 至少 一个其他字符串关联。它是这个组中 唯一 的字符串。
注意，你需要确保分好组后，一个组内的任一字符串与其他组的字符串都不关联。可以证明在这个条件下，分组方案是唯一的。
请你返回一个长度为 2 的数组 ans ：
ans[0] 是 words 分组后的 总组数 。ans[1] 是字符串数目最多的组所包含的字符串数目。 解题思路：
预处理：根据题目要求，可以利用26位保存字符串状态，使用Map保存字符串状态和个数
使用深度优先，每次提取一组——具体方法
从Map中获取一个字符串，存入List中，从Map中移除该字符串，分组数+1，该组初始个数为该字符串个数只要List没有空，每次移除首部使用，寻找该首部变形可以得到的所有在Map中的字符串每次找到一个字符串，从Map中移除，加入List，组内计数器增加该字符串个数
具体方法见下：
代码实现：class Solution {
public int[] groupStrings(String[] words) {
//位运算预存数组
int[] j=new int[27];
for(int i=0;i<=26;i++){
j[i]=1< oMap=new HashMap<>();
for(String i:words){
//使用StoInt将小写字母不重复的String表示为用位上的1表示该字母的int类型
int mid=StoInt(i);
oMap.put(mid,oMap.getOrDefault(mid,0)+1);
}
//count为组数目,max为当前最大组内数目
int count=0;
int max=0;
while(!oMap.isEmpty()){
int midc=0;
List list=new ArrayList<>();
//从Map中获取一个元素，并移除，初始化该组组内数量
for(Map.Entry e:oMap.entrySet()){
list.add(e.getKey());
midc+=e.getValue();
break;
}
oMap.remove(list.get(0));
//循环直到找到所有oMap中的该组成员
while(!list.isEmpty()){
int mid=list.get(0);
list.remove(0);
//增减变形，每次反转1位即可
for(int i:j){
int mid_i=mid^i;
if(oMap.get(mid_i)!=null){
midc+=oMap.get(mid_i);
list.add(mid_i);
oMap.remove(mid_i);
}
}
//字符转换变形，每次反转1，再反转一个0
for(int i:j){
if((mid&i)>0){
for(int k:j){
if((mid&k)==0){
int mid_i=mid^i^k;
if(oMap.get(mid_i)!=null){
midc+=oMap.get(mid_i);
list.add(mid_i);
oMap.remove(mid_i);
}
}
}
}
}
}
//如果组内元素大于当前max
if(midc>max){
max=midc;
}
//分组+1
count++;
}
return new int[]{count,max};
}
int StoInt(String s){
int res=0;
for(int i=0;i
结尾
题目来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems
⭐️关注作者，带你刷题，从简单的算法题了解最常用的算法技能（寒假每日一题）
⭐️关注作者刷题——简单到进阶，让你不知不觉成为无情的刷题机器，有问题请私信
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）