[LeetCode周赛复盘] 第 354 场周赛20230716

news/2024/2/28 1:00:10

[LeetCode周赛复盘] 第 354 场周赛20230716

    • 一、本周周赛总结
    • 6889. 特殊元素平方和
      • 1. 题目描述
      • 2. 思路分析
      • 3. 代码实现
    • 6929. 数组的最大美丽值
      • 1. 题目描述
      • 2. 思路分析
      • 3. 代码实现
    • 6927. 合法分割的最小下标
      • 1. 题目描述
      • 2. 思路分析
      • 3. 代码实现
    • 6924. 最长合法子字符串的长度
      • 1. 题目描述
      • 2. 思路分析
      • 3. 代码实现
    • 参考链接

一、本周周赛总结

  • T1 模拟。
  • T2 RUPQ 差分/树状数组。
  • T3 前后缀分解。
  • T4 双指针+trie(py负优化)。
    在这里插入图片描述

6889. 特殊元素平方和

6889. 特殊元素平方和

1. 题目描述

在这里插入图片描述

2. 思路分析

按题意模拟即可。

3. 代码实现

class Solution:def sumOfSquares(self, nums: List[int]) -> int:return sum(v*v for i,v in enumerate(nums,start=1) if len(nums)%i==0)

6929. 数组的最大美丽值

6929. 数组的最大美丽值

1. 题目描述

在这里插入图片描述

2. 思路分析

  • 注意到值域很小,因此可以值域当下标,记录每个下标可以被访问多少次。
  • 那么其实是个区间+1。用差分可以搞。树状数组也可以。
  • 实现时,只需要对值域mn~mx处理即可,因为所有数都加相同的k,边界以外的次数一定不会超过边界(它们一定会路过边界)。

3. 代码实现

class Solution:def maximumBeauty(self, nums: List[int], k: int) -> int:mx = max(nums)d = [0]*(mx+2)for v in nums:x,y = max(0,v-k), min(mx,v+k)d[x] += 1d[y+1] -= 1 return max(accumulate(d))

6927. 合法分割的最小下标

6927. 合法分割的最小下标

1. 题目描述

在这里插入图片描述

2. 思路分析

  • 前后缀分解。
  • 先计算出主元素x和它出现的次数y。那么前后缀的相同主元素只能是x。
  • 那么可以从头向后遍历,记录x的出现次数p,并计算后边剩余的次数y-p。
  • 找到第一个满足条件的下标即可。

3. 代码实现

class Solution:def minimumIndex(self, nums: List[int]) -> int:n = len(nums)cnt = Counter(nums)x,y = cnt.most_common(1)[0]p = 0for i,v in enumerate(nums):if v == x:p += 1 if p*2 > i+1 and (y-p)*2>(n-i-1):return ireturn -1

6924. 最长合法子字符串的长度

6924. 最长合法子字符串的长度

1. 题目描述

在这里插入图片描述

2. 思路分析

  • 最长子段首先想到双指针/滑窗。
  • 枚举每个字母作为子段的右端点。尝试检查这个尾缀里是否再forbid里。
  • 由于forbid长度最多10,因此只需要暴力检查10次尾缀,找到最短那个fb尾缀,把左窗口挪过来,注意是l=j+1,因为要破坏这个非法单词。
  • 这样复杂度是n1010,每个字符要检查10次,每次检查复杂度是len(s)=10。

  • 可以用字典树trie优化成n*10。但是实测py果然还是切片+朴素set更快。
  • 对forbid逆序建树。
  • 枚举c为右端点时,也逆序向前组成字符串,然后去trie里判断是否存在这个单词。
  • 由于检查也是从右向左,同步检查,因此复杂度就是10。

3. 代码实现

朴素set

class Solution:def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:fb = set(forbidden)l = ans = 0 for r,c in enumerate(word):            for j in range(r,max(l-1,r-10),-1):if word[j:r+1] in fb:l = j+1break# print(r,l)ans = max(ans, r-l+1)return ans                       

trie

class Solution:def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:trie = {}for s in  forbidden:s = s[::-1]cur = trie for c in s:if c not in cur:cur[c] = {}cur = cur[c]cur['#'] = 1def query(s):cur = triefor i,c in enumerate(s,start=1):if c not in cur:return 0 cur = cur[c]if '#' in cur:return i return 0l = ans = 0 for r,c in enumerate(word):     s = word[max(l,r-9):r+1] i = query(s[::-1])if i:l = r - i+2ans = max(ans, r-l+1)return ans                 

参考链接


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

相关文章

在Matlab环境下高效实施均值偏移(Mean Shift)算法并运用于灰度测试图像的快速原型设计:特征空间中的收敛过程

在科学研究和工业界,图像处理已经成为了一个重要的应用领域。而在图像处理中,均值偏移(Mean Shift)算法是一个在计算机视觉中非常重要的技术。本文将介绍如何在Matlab环境中实现均值偏移算法,并应用到灰度测试图像上&a…

Three.js 播放glb,fbx,gltf,obj 模型文件自带动画

three.js中模型动画的播放 首页在上一篇 Three.js加载外部glb,fbx,gltf,obj 模型文件 的文章基础上新加入 三个函数方法 1.开始执行动画方法: onStartModelAnimaion 2.设置模型动画方法:onSetModelAnimaion 3.模型动画帧渲染方法:animationF…

可以在手机上互联网期货开户

现在是互联网时代,在网上就可以开户。电脑开户在期货公司官网,手机开户在期货公司的App,准备好本人的身份证和银行卡,20-30分钟就可以开完。但是期货公司为了赚钱,默认给客户的手续费都比较高,基本是最低手…

记录C#知识点(二)21-40

目录 21.性能优化 22.动态dynamic使用 23.中文乱码 24.启动项目之前,执行文件 25.深拷贝-反射实现 26.丢弃运算符 _ 27.winform程序使用管理员运行 28.wpf程序使用管理员运行 21.性能优化 1.检查空字符串:使用string.Empty 2.更改类型转换&…

深度学习系列8——分类模型评估指标

1. 概述 1.1 分类 分类:标签为离散值。 回归:标签为连续值。 2. 混淆矩阵 二分类的混淆矩阵: TP 和 TN 为网络预测正确的部分,FP 和 FN 为网络预测错误的部分。 3. 二级指标 准确率: 针对模型的整体评估&#xf…

openwrt双wan环境搭建以及适配UPnP

最基本双wan环境搭建 1.修改网络配置文件network 2.修改防火墙配置文件firwall 3.添加策略路由 UPnP适配 修改UPnP配置文件以适配双wan环境

播放dlna服务器上文件,群晖使用教程:DLNA/UPnP协议和Kodi在多设备上播放媒体文件...

摘要: 起始缘由:使用Transmission下载到文件夹里的电影在电视上的Kodi文件未更新(如图)如何安装Transmission(bt/PT软件)教程 https://ww... 起始缘由:使用Transmission下载到文件夹里的电影在电视上的Kodi文件未更新(如图) 如图两个文件夹没有显示,解决方法也非常简单,且…

简单聊聊OpenWrt的UPnP协议

一、UPnP起源 通用即插即用(Universal Plug and Play,UPnP)是一种分布式、开放的网络架构,此 标准由微软公司于 1999 年提出,由非盈利的通用即插即用论坛(UPnP Forum)负责体系 架构和标准的维护…

upnp linux 树莓派,树莓派3-搭建DLNA/UPnP服务器

搭建DLNA/UPnP媒体服务器 说明 建立一个Raspberry Pi的DLNA/UPnP使用外部硬盘驱动器作为存储媒体服务器。 一个地方存储你所有的媒体包括视频、图片和音乐,在家庭网络中随意访问。 便宜,保持运行24/7, 稳定和可靠运行的解决方案 步骤 安装你的…

UPNP端口映射简单流程

文章目录 0 简介1 寻址2发现2.1 广播2.2 响应 3 描述3.1 GET描述文件3.2 获取并解析XML描述文件 4 控制4.1 获取状态信息4.2 获取外网IP4.3 获取端口映射信息4.4端口映射 5 一些疑问5.1 端口映射的有效期是多久?5.2 多级路由如何映射成功 6 开源库 参考文档&#xf…

P2P端口映射 UPnP设置功能和使用详解

P2P端口映射 UPnP设置功能和使用详解 在网上看了很多关于如何打开UPnP功能的文章,发现竟然没有一篇文章能把整个UPnP的设置过程介绍全的,都是只讲到一部分。所以决定写篇文章,至少把设置UPnP的整体思路理一下,因为涉及到不同的操…

UPnP详解

在网上看了很多关于如何打开UPnP功能的文章,发现竟然没有一篇文章能把整个UPnP的设置过程介绍全的,都是只讲到一部分。所以决定写篇文章,至少把设置UPnP的整体思路理一下,因为涉及到不同的操作系统以及不同型号的ADSL Modem&#…

Openwrt 安装UPnP

1. miniupnpd 2. luci-app-upnp

openwrt 安装 UPnP

UPnP是一种对等即插即用网络协议,主要用于视频,音频领域的传输协议,对使用者来说,打开UPnP之后可以增加迅雷等下载软件的下载速度。 提示:UPnP服务开机启动会消耗一点CPU和内存资源。 安装必要的包 确保接入互联网&a…

Linux/Openwrt路由安装配置UPNP服务提高迅雷下载速度

Linux/Openwrt路由安装配置UPNP服务提高迅雷下载速度 发布时间:September 7, 2012 // 分类:OpenWrt // 1 Comment 路由器下电脑为实现互联网端到端的连接需要配置DNAT(端口映射),UPNP就相当于自动化DNAT的实现&#xf…

Android 实现UPNP功能

通过upnp端口映射 可以实现外网访问到当前android设备。当然你的路由需要打开upnp功能 使用下面的方法进行端口映射,这里默认使用7878端口也可以另行设置 private void discoverUPNP() {int discoveryTiemout 5000; // 5 secstry {System.out.println("Looki…

upnp 文件服务器,windows作为upnp服务器

windows作为upnp服务器 内容精选 换一换 按需购买的两台同类型弹性云服务器(操作系统类型相同,如Windows和Windows,Linux和Linux),关机卸载系统盘后,重新挂载至对方弹性云服务器,实现系统盘互换。互换成功后,弹性云服务器的登录密码或密钥可能会发生改变。此时,如何登录…

26-Openwrt 端口转发 dmz upnp

我们经常会在路由器上面配置端口转发的规则,用来访问内网机器的某个端口,openwrt上面有很多中实现端口转发的方式。 1、端口转发 比如我想用wan口的IP,192.168.2.180,远程连接lan口内网192.168.18.235的ubuntu,如何实现: 建立一…

upnp 文件服务器,upnp服务器

upnp服务器 内容精选 换一换 内网环境下,Windows云服务器之间怎样实现文件夹共享?部分运营商可能会屏蔽139、445端口,导致广域网无法访问共享。因此,Windows云服务器文件共享方案建议仅在内网环境下使用。确保“Tcp/IP NetBIOS He…

UPnP技术总结

一、UPnP简介 全称:Universal Plug and Play(通用即插即用) 应用:主要用于设备的智能互联互通,简化家庭或企业中智能设备的联网过程。 二、UPnP工作原理 UPnP工作主要分为以下六个步骤: 2.1 寻址 寻址就是获取一个可用的ip地址用以上网。…
最新文章