当前位置: 首页 > news >正文

力扣 第 399 场周赛 解题报告 | 珂学家 | 调和级数 + 分块DP


前言

image.png

T1. 优质数对的总数 I

题型: 签到

class Solution:def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:res = 0for v1 in nums1:for v2 in nums2:if v1 % (v2 * k) == 0:res += 1return res

T2. 压缩字符串 III

思路: 模拟

感觉引入一个栈,操作更加的方便

当然加限制的分组循环也可以

class Solution:def compressedString(self, word: str) -> str:stk = []for i, c in enumerate(word):if len(stk) == 0 or stk[-1][0] != c or stk[-1][1] == 9:stk.append([c, 1])else:stk[-1][1] += 1return ''.join(map(lambda x: str(x[1]) + x[0], stk))

T3. 优质数对的总数 II

思路: 调和级数

很典的结论题,时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)
∑ i = 1 i = n 1 / i = l o g ( n ) \sum_{i=1}^{i=n} 1/i = log(n) i=1i=n1/i=log(n)

class Solution:def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:        mp1 = Counter()for v in nums1:if v % k == 0:mp1[v//k] += 1if len(mp1) == 0:return 0mz = max(mp1.keys())res = 0mp2 = Counter(nums2)for (k1, v1) in mp2.items():for i in range(1, mz // k1 + 1):res += v1 * mp1[i * k1]return res

T4. 不包含相邻元素的子序列的最大和

思路: 分块 + DP

因为数据规模不大, O ( n ∗ q ) O(\sqrt{n} * q) O(n q) 在合理的范围内

所以用分块,思路更加的纯朴和简洁。

每次更新块大小内的状态

然后按块间重算最后的整体解

DP 引入块状态, 表示首尾的0-1状态

具体来讲

image.png

class Solution {static long inf = Long.MIN_VALUE / 10;static class Block {int l, r;int[] arr;long[][][] pre;int n;public Block(int l, int r, int[] arr) {this.l = l;this.r = r;this.arr = arr;this.n = r - l + 1;pre = new long[n][2][2];}public void modify() {pre[0][0][0] = 0;pre[0][0][1] = inf;pre[0][1][0] = inf;pre[0][1][1] = arr[l];for (int i = 1; i < n; i++) {pre[i][0][0] = Math.max(pre[i - 1][0][0], pre[i - 1][0][1]);pre[i][1][0] = Math.max(pre[i - 1][1][0], pre[i - 1][1][1]);pre[i][0][1] = pre[i - 1][0][0] + arr[l + i];pre[i][1][1] = pre[i - 1][1][0] + arr[l + i];}}long[][] val() {return pre[n - 1];}}public int maximumSumSubsequence(int[] nums, int[][] queries) {int n = nums.length;int z = (int)Math.sqrt(n);int m = (n + z - 1) / z;Block[] blocks = new Block[m];for (int i = 0; i < m; i++) {blocks[i] = new Block(i * z, Math.min((i + 1) * z - 1, n - 1), nums);blocks[i].modify();}long mod = (long)1e9 + 7;long res = 0;for (int i = 0; i < queries.length; i++) {int[] q = queries[i];int p = q[0], x = q[1];int idx = p / z;nums[p] = x;blocks[idx].modify();long[][] dp = new long[m][2];dp[0][0] = Math.max(blocks[0].val()[0][0], blocks[0].val()[1][0]);dp[0][1] = Math.max(blocks[0].val()[0][1], blocks[0].val()[1][1]);for (int j = 1; j < m; j++) {long[][] next = blocks[j].val();dp[j][0] = Math.max(dp[j - 1][0] + Math.max(next[0][0], next[1][0]), dp[j - 1][1] + next[0][0]);dp[j][1] = Math.max(dp[j - 1][0] + Math.max(next[0][1], next[1][1]), dp[j - 1][1] + next[0][1]);}long tmp = Math.max(dp[m - 1][0], dp[m - 1][1]);res = (res + tmp) % mod;res = (res % mod + mod) % mod;}return (int)res;}
}

写在最后

image.png

相关文章:

力扣 第 399 场周赛 解题报告 | 珂学家 | 调和级数 + 分块DP

前言 T1. 优质数对的总数 I 题型: 签到 class Solution:def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:res 0for v1 in nums1:for v2 in nums2:if v1 % (v2 * k) 0:res 1return resT2. 压缩字符串 III 思路: 模拟 感觉引入一个栈&…...

Redis的下载、安装、启动和初尝试【超级简单】

redis最好是在Linux系统中使用&#xff0c;这是最接近生产实际的环境。 不过&#xff0c;我们初学者&#xff0c;目的是学习Redis的使用、原理&#xff0c;如果在Linux下直接学习Redis&#xff0c;很可能会因为命令不熟悉而劝退&#xff0c;这是不好的。 因此&#xff0c;我主张…...

v-cloak 用于在 Vue 实例渲染完成之前隐藏绑定的元素

如果你是后端开发者&#xff08;php&#xff09;&#xff0c;在接触一些vue2开发的后台时&#xff0c;会发现有这段代码&#xff1a; # CDN <script src"https://cdn.jsdelivr.net/npm/vue2/dist/vue.js"></script> # 或 <script src"https://cd…...

港股:并不意外的获利了结

中金公司表示&#xff0c;风险偏好驱动的反弹已经较为充分&#xff0c;分歧和获利了结也不意外。接下来或在当前水平震荡盘整&#xff0c;等待更多催化剂。 在持续一个月的大涨后&#xff0c;港股市场上周出现明显回调。此前我们多次提示&#xff0c;市场已经超买&#xff0c;情…...

Python项目开发实战:工厂库存管理系统(案例教程)

一、项目背景与意义 随着制造业的快速发展,工厂库存管理成为了企业运营中不可或缺的一部分。一个高效的库存管理系统能够确保物料供应的及时性、降低库存成本、提高生产效率。因此,我们决定使用Python开发一个工厂库存管理系统,以满足工厂日常库存管理的需求。 二、系统需求…...

VS2022 嘿嘿

还是大二的时候就开始用这个&#xff0c;但居然是为了用PB&#xff0c;-_-|| 用了段时间换成了C#&#xff0c;依稀还记得大佬们纠正我的读法&#xff0c;别读C井&#xff0c;应该读C夏普。。。 安装过程其实也没啥&#xff0c;就是关键Key得花时间找&#xff0c;我好不容易搞…...

Flutter 中的 PhysicalShape 小部件:全面指南

Flutter 中的 PhysicalShape 小部件&#xff1a;全面指南 在Flutter中&#xff0c;PhysicalShape小部件是一个能够为子组件添加物理效果的边框和阴影的装饰性小部件。它能够模拟真实世界中物体的立体感&#xff0c;通过在子组件的周围创建一个可自定义的形状&#xff0c;并添加…...

CAD二次开发(6)-用户交互之选择集

1. 简单测试 测试让选中的图形描红 [CommandMethod("SeleDemo")]public void SeleDemo(){Database db HostApplicationServices.WorkingDatabase;Editor ed Application.DocumentManager.MdiActiveDocument.Editor;PromptSelectionResult psr ed.GetSelection();…...

如何使用性能监控工具分析JVM性能瓶颈

1、jConsole&#xff1a; jConsole是JDK自带的Java监控和管理控制台。它提供了一个图形用户界面&#xff08;GUI&#xff09;&#xff0c;用于监控和管理Java应用程序的性能和资源消耗。 使用方法&#xff1a;打开jdk\bin\jconsole.exe&#xff0c;连接到正在运行的Java进程&a…...

解决vite打包只生成了一个css和js文件问题

文章目录 1. 打包遇到的问题2. 问题原因及修改3. 调整后再次打包&#x1f197; 1. 打包遇到的问题 今天整了一个项目&#xff0c;试了下打包&#xff0c;发下打包后只生成了一个css文件&#xff0c;和一个js文件&#xff0c; 这样肯定是不行的&#xff0c;因为这样这个文件的包…...

数据访问层设计_4.灵活运用XML Schema

1.XML Schema XML Schema用来描述XML文档合法结构、内容和限制。XML Schema由XML1.0自描述&#xff0c;并且使用了命名空间&#xff0c;有丰富的内嵌数据类型及其强大的数据结构定义功能&#xff0c;充分地改造了并且极大地扩展了DTDs&#xff08;传统描述XML文档结构和内容限…...

【Linux安全】Firewalld防火墙基础

目录 一、Firewalld概述 二、Firewalld和iptables的关系 三、Firewalld网络区域 1、firewalld防火墙预定义了9个区域: 2、firewalld 数据包处理原则 3、firewalld数据处理流程 4、firewalld检查数据包的源地址的规则 四、Firewalld防火墙的配置方法 1、firewalld 命令…...

先进制造aps专题八 基于ai大模型的ai超级应用,ai生管

目前正在研发的面向消费者的ai超级应用有ai文员&#xff0c;ai教师&#xff0c;ai家教&#xff0c;ai护士&#xff0c;ai翻译 而ai生管无疑是面向制造业的ai超级应用 从商业角度来说&#xff0c;ai生管&#xff0c;必然是aps公司必然要研发的ai超级应用...

Textual for Mac:轻量级IRC客户端

在寻找一款高效、轻量级的IRC客户端时&#xff0c;Textual for Mac无疑是你的不二之选。它集成了众多现代技术&#xff0c;如本机IPv6、最新的IRCv3规范&#xff0c;以及客户端证书身份验证&#xff0c;让你的聊天体验更加顺畅和安全。 Textual for Mac v7.2.2免激活版下载 Tex…...

Facebook:连接世界,畅游社交之旅

作为全球最大的社交平台之一&#xff0c;Facebook不仅仅是一个网站&#xff0c;更是一个连接世界的桥梁&#xff0c;让人们可以轻松地与全球各地的朋友、家人和同事保持联系&#xff0c;分享生活、交流想法&#xff0c;畅游社交的无边界之旅。本文将带领读者探索Facebook的魅力…...

部署PIM-SM

拓扑图 配置 使能组播路由 配置OSPF 组播路由器接口配置pim-sm 连接组成员的接口使能igmp pim路由器上配置静态RP sysname AR1 # multicast routing-enable # interface GigabitEthernet0/0/0ip address 10.1.12.1 255.255.255.0 pim sm # interface GigabitEthernet0/0/…...

一分钟揭秘面试官真实意图,稳拿offer的面试秘诀!

想要在面试中脱颖而出&#xff0c;顺利获得心仪的offer吗&#xff1f;那么&#xff0c;你需要了解面试官背后的潜台词。通过解析这些潜台词&#xff0c;你将能更准确地把握面试官的期望&#xff0c;并给出他们最喜欢的回答。下面&#xff0c;就让我们一起揭开这层神秘的面纱&am…...

【源码】2024心悦搜剧源码百万级网盘资源

1、一键转存他人链接&#xff1a;就是将别人的分享链接转为你自己的 2、转存心悦搜剧资源&#xff1a;就是将心悦搜剧平台上的所有资源都转成你自己的 3、每日自动更新&#xff1a;自动转存每天的资源并入库 前端uin-app&#xff0c;后端PHP&#xff0c;兼容微信小程序...

燃数科技前端25-40K*14薪一面超简单,下周二面啦

​​​​​​​ 文章末尾扫描二维码领取地址 一面 1、自我介绍 2、低代码如何设计的 3、react路由原理 4、react生命周期 5、什么是回调地狱&#xff0c;如何解决 6、jwt和session有什么区别 7、js文件相互引用有什么问题&#xff1f;如何解决 8、一个很大的json文件…...

读人工智能时代与人类未来笔记14_管控人工智能

1. 管控人工智能 1.1. 历史上的战场进一步推进到与数字网络相连的所有地方 1.2. 数字程序现在控制着一个由众多实体系统构成的庞大且仍在不断增长的领域&#xff0c;而且越来越多的此类系统已实现网络化 1.2.1. 在某些情况下甚至连门锁和冰箱都实现了网络化 1.2.2. 这催生出…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了&#xff0c;要么要会员、要么写的乱七八糟。这里我整理一下&#xff0c;把问题说清楚并且给出代码&#xff0c;拿去用就行&#xff0c;照着葫芦画瓢。 问题 在继承QWebEngineView后&#xff0c;重写mousePressEvent或event函数无法捕获鼠标按下事…...