[LeetCode周赛复盘] 第 94 场双周赛20221225

news/2024/2/21 4:11:49

[LeetCode周赛复盘] 第 94 场双周赛20221225

    • 一、本周周赛总结
    • 二、 [Easy] 6273. 最多可以摧毁的敌人城堡数目
      • 1. 题目描述
      • 2. 思路分析
      • 3. 代码实现
    • 三、[Medium] 6274. 奖励最顶尖的 K 名学生
      • 1. 题目描述
      • 2. 思路分析
      • 3. 代码实现
    • 四、[Medium] 6295. 最小化两个数组中的最大值
      • 1. 题目描述
      • 2. 思路分析
      • 3. 代码实现
    • 五、[Hard] 6276. 统计同位异构字符串数目
      • 1. 题目描述
      • 2. 思路分析
      • 3. 代码实现
    • 六、参考链接

一、本周周赛总结

  • 都挺难的。
  • T1dp。
  • T2哈希+排序。
  • T3容斥+二分。
  • T4排列组合模板题。

二、 [Easy] 6273. 最多可以摧毁的敌人城堡数目

链接: 6273. 最多可以摧毁的敌人城堡数目

1. 题目描述

在这里插入图片描述

2. 思路分析

  • dp计算出连续的0的个数。
  • 然后遍历每个不为0的位置和计数:(i,v),显然这代表的连续0段的两个边界外界是l,r = [i-v,i+1]
  • 当l和r合法,且分别是一个-1,1时则可更新ans
  • 显然这等价于forts[l]*forts[r] == -1

3. 代码实现

class Solution:def captureForts(self, forts: List[int]) -> int:n = len(forts)f = [0]*nif forts[0] == 0:f[0] = 1for i in range(1,n):if forts[i] == 0:f[i] = f[i-1] + 1ans = 0for i,v in enumerate(f):l,r = i-v,i+1if l>=0 and r<n and forts[l]*forts[r] == -1:ans = max(ans,v)return ans

三、[Medium] 6274. 奖励最顶尖的 K 名学生

链接: 6274. 奖励最顶尖的 K 名学生

1. 题目描述

在这里插入图片描述

2. 思路分析

按题意模拟即可。

  • 由于是python 因此直接split计算分数排序即可。
  • 当然topk可以用小顶堆,但没必要。

3. 代码实现

class Solution:def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:ps = set(positive_feedback)ns = set(negative_feedback)ans = []for w,i in zip(report,student_id):p = 0for s in w.split():if s in ps:p += 3elif s in ns:p -= 1ans.append((-p,i))return [i for _,i in sorted(ans)[:k]]

四、[Medium] 6295. 最小化两个数组中的最大值

链接: 6295. 最小化两个数组中的最大值

1. 题目描述

在这里插入图片描述

2. 思路分析

  • 最大值最小化=二分答案。
  • 令函数ok(x)代表以x为最大值(答案)时,能否找到满足题意的元素。
  • ok函数需要用容斥实现。1~x的x个元素分别分到4组里:同时被ab整除的数,仅能被a整除的数,仅能被b整除的数,不能被a或b整除的数。
  • 那么显然arr1应该优先取仅能被b整除的数,然后取不能被整除的数,arr2同理。
  • 当数不够取了,则无有效解,这个过程是O(1)的,但同时被整除的数由于要取lcm,是log。但lcm是固定的,可以预处理,因此还是O(1)
  • 这个结果显然是单调的。
  • 整体复杂度O(logn+log(max(a,b))),

3. 代码实现

class Solution:def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:dd  = lcm(divisor1,divisor2)def ok(x):p1 = x // divisor1  # 能被d1整除p2 = x // divisor2  # 能被d2整除p3 = x // dd  # 能同时被d1,d2整除a = p1 - p3  # 仅能被d1整除b = p2 - p3  # 仅能被d2整除c = x - a-b-p3  # 不能被整除u1,u2 = uniqueCnt1,uniqueCnt2if u1>0:u1 -= bif u1>0:c -= u1if c < 0:return 0if u2>0:u2 -= aif u2>0:c -= u2if c < 0:return 0return 1return bisect_left(range(10**10),1,key=ok)

五、[Hard] 6276. 统计同位异构字符串数目

链接: 6276. 统计同位异构字符串数目

1. 题目描述

在这里插入图片描述

2. 思路分析

  • 显然每个单词时独立的,可以计算每个单词的异构体数目,然后乘法原理即可。
  • 如何计算呢?问题转化成如果计算含有重复元素的数组排列数。
  • 假设长度n,含x种元素,分别计数为[c1,c2,c3…cx]。
  • 放第一种c1个元素,考虑它们能选的位置有C(n,c1)个;然后放c2,显然从n-c1个位置里挑。
  • 因此ans=C(n,c1) * C(n-c1,c2) * C(n-c1-c2,c3) * … * C(cx,cx);另一种计算方法看代码。
  • 这里整理成模板。

3. 代码实现

class ModComb:def __init__(self, n, p):"""初始化,为了防止模不一样,因此不写默认值,强制要求调用者明示:param n:最大值,通常是2*(10**5)+50:param p: 模,通常是10**9+7"""self.p = pself.inv_f, self.fact = [1] * (n + 1), [1] * (n + 1)  # 阶乘的逆元、阶乘inv_f, fact = self.inv_f, self.factfor i in range(2, n + 1):fact[i] = i * fact[i - 1] % pinv_f[-1] = pow(fact[-1], p - 2, p)for i in range(n, 0, -1):inv_f[i - 1] = i * inv_f[i] % pdef comb(self, m, r):if m < r or r < 0:return 0return self.fact[m] * self.inv_f[r] % self.p * self.inv_f[m - r] % self.pdef perm_count_with_duplicate(self, a):"""含重复元素的列表a,全排列的种类。假设长度n,含x种元素,分别计数为[c1,c2,c3..cx]则答案是C(n,c1)*C(n-c1,c2)*C(n-c1-c2,c3)*...*C(cx,cx)或:n!/c1!/c2!/c3!/../cn!"""ans = self.fact[len(a)]for c in Counter(a).values():ans = ans * self.inv_f[c] % self.p           return ans # 下边这种也可以# s = len(a)# ans = 1# for c in Counter(a).values():#     ans = ans * self.comb(s,c) % MOD #     s -= c# return ans MOD = 10  ** 9 + 7
class Solution:def countAnagrams(self, s: str) -> int:ret = 1mc = ModComb(len(s),MOD)      for w in s.split():ret = ret * mc.perm_count_with_duplicate(w) %MODreturn (ret)%MOD

六、参考链接


http://www.ppmy.cn/news/6634.html

相关文章

torch.einsum() 用法说明

torch.einsum( equation , * operands ) → Tensor 对输入元素operands沿指定的维度、使用爱因斯坦求和符号的乘积求和。 参数&#xff1a; equation ( string ) – 爱因斯坦求和的下标。 operands&#xff08;List [ Tensor ]&#xff09;——计算爱因斯坦求和的张量。 ​…

数据结构---A星寻路算法

A星寻路算法第一步第二步第三步第四步JAVA实现用于寻找有效路径的算法。定义俩个集合 OpenList&#xff1a;可到达的格子 CloseList&#xff1a;已到达的格子 每一个格子都具有F、G、H这3个属性 G&#xff1a;从起点走到当前格子的成本&#xff0c;也就是已经花费了多少步。H&a…

【nowcoder】笔试强训Day6

目录 一、单选题 二、多选题 三、编程题 3.1不要二 3.2 把字符串转成整数 一、单选题 1.下面哪段程序能够正确的实现了GBK编码字节流到UTF-8编码字节流的转换&#xff1a; A dstString.frombytes(src,”GBK”).getbytes(“UTF-8”) B dstnew String (src,”GBK”).getb…

R语言使用MASS包的qda函数拟合二次判别分析多分类模型、使用caret包基于交叉验证的方式训练二次判别分析多分类模型

R语言使用MASS包的qda函数拟合二次判别分析多分类模型、使用caret包基于交叉验证的方式训练二次判别分析多分类模型 目录

【Python语法】一篇文章带你快速入门Python

✍个人博客&#xff1a;https://blog.csdn.net/Newin2020?spm1011.2415.3001.5343 &#x1f4e3;专栏定位&#xff1a;为 0 基础 python 或者想要快速复习这门语言的小伙伴整理 python重点语法&#xff0c;帮助大家快速掌握其中重点内容~ &#x1f4da;专栏简介&#xff1a;在…

《教育的目的》笔记——如何让学生通过树木看见森林

目录 作者简介 个人感悟 经典摘录 1、学生所受的训练应该比他们最终投身的专业更为广泛 2、学习新语言用途 3、教师的责任 4、教育的主题 5、学到的有用之物 6、教育目的 7、所有事物都不是静态的、定型的&#xff0c;而是处于形成&#xff08;becoming&#xff09;过…

九、Express 基本使用(简)

前一篇内容讲到Express框架的安装以及对Express项目的目录文件有一定的认识了解之后&#xff0c;使用Express创建了最基本的一个Web服务器&#xff0c;接下来进行对Express框架的一些内容来做一个基本的使用&#xff1b; 创建 Web 服务器 node 或 nodemon 执行app.js文件&#…

JSP ssh学生信息管理系统myeclipse开发mysql数据库MVC模式java编程计算机网页设计

一、源码特点 JSP ssh 学生信息管理系统是一套完善的web设计系统&#xff08;系统采用ssh框架进行设计开发&#xff09;&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用 B/S模式开发。开发环境为TOMCAT7.…

【数组中数字出现的次数-有限状态自动机】

数组中数字出现的次数一&#xff0c;有限状态自动机解法二&#xff0c;一般解法想必大家对数组中数字出现的次数的这种题并不少见&#xff0c; 主要有三种&#xff1a; 1&#xff0c;找出数组中只出现一次的数字&#xff08;其他数字出现两次&#xff09; 2&#xff0c;找出数组…

node.js+uni计算机毕设项目交流微信小程序LW(程序+小程序+LW)

该项目含有源码、文档、程序、数据库、配套开发软件、软件安装教程。欢迎交流 项目运行 环境配置&#xff1a; Node.js Vscode Mysql5.7 HBuilderXNavicat11VueExpress。 项目技术&#xff1a; Express框架 Node.js Vue 等等组成&#xff0c;B/S模式 Vscode管理前后端分离等…

渗透测试指操作系统漏洞发现与防御概述

今天继续给大家介绍渗透测试相关知识&#xff0c;本文主要内容是渗透测试指操作系统漏洞发现与防御概述。 免责声明&#xff1a; 本文所介绍的内容仅做学习交流使用&#xff0c;严禁利用文中技术进行非法行为&#xff0c;否则造成一切严重后果自负&#xff01; 再次强调&#x…

cadence SPB17.4 - orcad - WARNING(ORCAP-2354) - Wire is hanging at Point

文章目录cadence SPB17.4 - orcad - WARNING(ORCAP-2354) - Wire is hanging at Point概述普通画法, 引起的不可理解的hang wire 警告ENDcadence SPB17.4 - orcad - WARNING(ORCAP-2354) - Wire is hanging at Point 概述 在使用SPB17.4从一个PCB中反推原理图. 原理图重建的差…

2022圣诞代码合集(圣诞树+圣诞老人)

文章目录前言使用方法圣诞树圣诞老人前言 圣诞节里的喜悦&#xff0c;飘扬万里&#xff1b;圣诞树上的星星&#xff0c;璀璨耀眼&#xff1b;圣诞星空绽放的烟花&#xff0c;迎来吉祥&#xff1b;圣诞钟声奏响的旋律&#xff0c;传递欢乐&#xff1b;圣诞老人送给你的礼物&…

Golang 【basic_leaming】4 函数

阅读目录Go 语言函数Go 语言函数章节目录Go 语言函数定义_声明_调用&#xff08;超详细&#xff09;一、定义一个普通函数1.1 函数名1.2 参数列表1.3 返回参数列表1.4 函数体二、参数列表简写三、函数返回值3.1 同一类型的返回值3.2 带有变量名的返回值四、调用函数Go 语言函数…

C语言—结构体

结构体&#xff1a;将不同数据类型组合成一个新的数据类型&#xff1b; #include <stdio.h> struct Person {char name[50];int age;bool gender; }; int main() {} 定义了一个结构体Person&#xff0c;它包含一个字符数组成员name&#xff0c;int类型的age和bool类型的…

CSS Flex 布局的 flex-direction 属性讲解

flex-direction 设置了主轴&#xff0c;从而定义了弹性项目放置在弹性容器中的方向。 Flexbox 是一种单向布局概念&#xff0c;可将弹性项目视为主要以水平行或垂直列布局。 .container {flex-direction: row | row-reverse | column | column-reverse; }几种支持的属性&#x…

H3CIE A套需求说明

实验配置&#xff1a;点击跳转 组网需求&#xff1a; 总部网络由两台路由器r1 r2和三台交换机 sw1 sw2 sw3组成&#xff0c;其中r1作为企业所有分支二节点广域网接入路由器&#xff0c;r2作为企业所有分支一节点广域网接入路由器&#xff0c;sw1 sw2 sw3组成总部局域网核心&a…

(一)LTspice简介2

文章目录前言一、LTspice的仿真过程二、spice的模型三、LTspice的工具栏和快捷键四、LTspice中的数量级前言 上一节我们学习了LTspice的安装&#xff0c;很简单&#xff0c;无脑安装 &#xff08;一&#xff09;LTspice安装 这一节我们继续学习LTspice的简介&#xff0c;主要包…

vue3 antd table表格——自定义单元格样式(二)利用rowClassName给table添加行样式

vue3 antd项目实战——修改ant design vue组件中table表格的默认样式&#xff08;二&#xff09;知识调用场景复现修改table表格的行样式一、rowClassName添加行样式二、表格的不可控操作写在最后知识调用 文章中可能会用到的知识链接vue3ant design vuets实战【ant-design-vu…

AcWing第83场周赛

目录 1.奇偶 2.闯关 3.构造序列 1.奇偶 题目描述 给定一个由小写字母组成的字符串,请你统计其中包含不同小写字母的数量。 如果给定字符串中包含奇数个不同的小写字母,则输出odd。 如果给定字符串中包含偶数个不同的小写字母,则输出even。 输入格式 共一行,一个…
最新文章