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

Leetcode第 368 场周赛

元素和最小的山形三元组 II

预处理前缀和后缀最小值,记为pre[i]和sa[i]
对于当前编号i,如果前面的最小值和后面的最大值都小于nums[i],则记录ans[i] = nums[i]+pre[i-1]+sa[i+1]
结果输出最小的ans[i]即可。

合法分组的最少组数

统计每一个数字出现的次数。将每一个数字分为大小为 d d d d + 1 d+1 d+1的组,令 d d d尽可能大。
d d d不满足单调性,不好二分。思路时直接暴力。
计最小出现次数为 m n mn mn,出现过的数字个数为 c n t cnt cnt,显然有 m n ∗ c n t ≤ n u m s . l e n g t h mn*cnt \le nums.length mncntnums.length
而显然有 d + 1 ≤ m n d+1 \le mn d+1mn,因此直接枚举d
对于某个数字i,其出现次数为 t o t i tot_i toti,若 d d d成立则需要满足存在x令 x d ≤ t o t i ≤ x ( d + 1 ) xd \le tot_i \le x(d+1) xdtotix(d+1)
x = t o t i / d x = tot_i/d x=toti/d,即以 d d d为标准将 t o t i tot_i toti分为x组,此时还剩 t o t i % d tot_i\%d toti%d个元素,每一组中最多可以容纳 d + 1 d+1 d+1个元素,最多可以容纳x个元素,使x组的个数都变为%d+1%。因此只要满足 t o t i % d ≤ x tot_i\%d \le x toti%dx t o t i % d ≤ t o t i / d tot_i\%d \le tot_i/d toti%dtoti/d,则对数字 i i i而言 d d d是合法的分组。
已知d,数字i的分组个数为 t o t i + d m n + 1 \frac{tot_i+d}{mn+1} mn+1toti+d x x x需要取最小值满足 x d ≤ t o t i ≤ x ( d + 1 ) xd \le tot_i \le x(d+1) xdtotix(d+1),有 ⌈ t o t i / ( d + 1 ) ⌉ ≤ x \lceil tot_i/(d+1)\rceil \le x toti/(d+1)⌉x,因此取 x = ⌈ t o t i d + 1 ⌉ x =\lceil \frac{tot_i}{d+1}\rceil x=d+1toti
枚举 d d d,计算分组个数,求分组最小值即可,复杂度为 O ( m n ∗ c n t ) O(mn*cnt) O(mncnt)

得到 K 个半回文串的最少修改次数

数据只有200,想法是纯暴力
M i n T i m e s [ i ] [ j ] MinTimes[i][j] MinTimes[i][j]为子串 s t r i j str_{ij} strij变成半回文串最少的次数,暴力计算,复杂度为 O ( n 4 ) O(n^4) O(n4)
令dp[i][j]为以 s t r i str_i stri为结尾时分为 j j j段最少的操作次数
d p [ i ] [ j ] = min ⁡ d p [ z ] [ j − 1 ] + M i n T i m e s [ z + 1 ] [ i ] dp[i][j] = \min dp[z][j-1]+MinTimes[z+1][i] dp[i][j]=mindp[z][j1]+MinTimes[z+1][i]
总复杂度 O ( n 4 ) O(n^4) O(n4)
计算MinTimes时可以将一个n优化成 n \sqrt n n 甚至预处理成 lg ⁡ n \lg n lgn,但是 O ( n 4 ) O(n^4) O(n4)也能过就是了,大概是数据比较弱吧

class Solution {
public:int MinTimes[210][210];int dp[210][210];int calTimes(string &s,int l,int r){int ret = (1<<30);int len = r-l+1;while(--len){if((r-l+1)%len)continue;int ans = 0;for(int i=0;i<len;++i){string t1;for(int j=l+i;j<=r;j+=len)t1 += s[j];for(int c=0;c<t1.size()/2;++c)if(t1[c]!=t1[t1.size()-1-c])ans++;}ret = min(ret,ans);}return ret;}int minimumChanges(string s, int k) {memset(dp,0x3f,sizeof(dp));dp[0][0] = 0;int l = s.size();     for(int i=0;i<l;++i){for(int j=i+1;j<l;++j){MinTimes[i][j] = calTimes(s,i,j);}MinTimes[i][i] = (1<<30);}for(int i=0;i<l;++i){for(int j=0;j<=i;++j){for(int z=1;z<=k;++z){dp[i+1][z] = min(dp[i+1][z],dp[j][z-1]+MinTimes[j][i]);}}}return dp[l][k];}
};

相关文章:

Leetcode第 368 场周赛

元素和最小的山形三元组 II 预处理前缀和后缀最小值,记为pre[i]和sa[i] 对于当前编号i&#xff0c;如果前面的最小值和后面的最大值都小于nums[i],则记录ans[i] nums[i]pre[i-1]sa[i1] 结果输出最小的ans[i]即可。 合法分组的最少组数 统计每一个数字出现的次数。将每一个数…...

Mysql数据库 3.SQL语言 DML数据操纵语言 增删改

DML语句&#xff1a;用于完成对数据表中数据的插入、删除、修改操作 一.表数据插入 插入数据语法&#xff1a; 步骤例&#xff1a; 1.声明数据库&#xff1a;use 数据库名; 2.删除操作&#xff1a;drop table if exists 表名; 3.创建数据库中的表&#xff1a;create table 表…...

Java中,如何去掉字符串中前面所有的0

大家好&#xff0c;我是三叔&#xff0c;这期主要给大家分享下在开发中使用的字符串的一些常见方法。 例如&#xff1a;00000000110&#xff0c;现在需要去掉前面所有补的0&#xff0c;得到110&#xff0c;相信大家在开发中肯定有遇到过类似的开发需求&#xff0c;如何做&…...

数组能开空间大小

奈何辰星无可奈_leetcode,中等难度,算法-CSDN博客 这个博客介绍的很好&#xff0c;可以参考下...

Python 数据类 - dataclass 的作用与不足

https://docs.python.org/zh-cn/3/library/dataclasses.html https://peps.python.org/pep-0526/ https://peps.python.org/pep-0557/ dataclass 简单示例 from dataclasses import dataclassdataclass class User:name: strage: intif __name__ __main__:response_json {na…...

【C++初阶】类与对象(一)

目录 1、初识面向对象思想2、类 struct2.1 C中的struct及使用 3、类 class3.1 类的定义3.2 类的访问限定符3.2.1 访问限定符是什么3.2.2 访问限定符的使用3.2.3 访问限定符的使用规范3.2.4 访问限定符与封装 3.3 类做声明和定义分离3.3.1 声明和定义分离3.3.2 在函数声明的地方…...

thinkPHP框架详解+部署

目录 什么是ThinkPHP: ThinkPHP的主要特性&#xff1a; 什么是ThinkPHP: ThinkPHP是一个快速、兼容而且简单的轻量级国产PHP开发框架&#xff0c;诞生于2006年初&#xff0c;由国内的技术爱好者创建&#xff0c;遵循Apache2开源协议发布&#xff0c;是为了敏捷WEB应用开发和…...

Java拦截器(Interceptor)和过滤器(Filter)实例详解

一、Java过滤器和拦截器 1.1、过滤器(Filter) Filter过滤器&#xff0c;是Servlet&#xff08;Server Applet&#xff09;技术中的技术&#xff0c;开发人员可以通过Filter技术&#xff0c;管理web资源&#xff0c;可以对指定的一些行为进行拦截&#xff0c;例如URL级别的权限…...

通过热敏电阻计算温度(二)---ODrive实现分析

文章目录 通过热敏电阻计算温度&#xff08;二&#xff09;---ODrive实现分析测量原理图计算分析计算拟合的多项式系数根据多项式方程计算温度的函数温度计算调用函数 通过热敏电阻计算温度&#xff08;二&#xff09;—ODrive实现分析 ODrive计算热敏电阻的温度采用的时B值的…...

基于typescript+express实现一个简单的接口权限验证

package.json "scripts": {"start": "nodemon src/main.ts","start:a": "nodemon src/a.ts","build": "tsc","build:dev": "tsc src/main.ts"}, express服务器文件 import * as…...

yolov7改进优化之蒸馏(二)

续yolov7改进优化之蒸馏&#xff08;一&#xff09;-CSDN博客 上一篇已经基本写出来yolov7/v5蒸馏的整个过程&#xff0c;不过要真的训起来我们还需要进行一些修改。 Model修改 蒸馏需要对teacher和student网络的特征层进行loss计算&#xff0c;因此我们forward时要能够返回需…...

生产与作业管理(POM)的历史

1800年&#xff0c;惠特尼&#xff1a;零件标准化、质量管理。 1881年&#xff0c;泰勒&#xff1a;人员选拔、计划和时程安排、动作研究。管理与劳动分开。 - 使雇员与工作相适应。 - 提供适当的训练。 - 提供正确的工作方法和工具。 - 建立适当的激励机制促使工作得以完成。 …...

交换机基础(二)

一、VLAN 基础知识 虚拟局域网 (Virtual Local Area Network,VLAN) 是一种将局域网设 备从逻辑上划分成一个个网段&#xff0c;从而实现虚拟工作组的数据交换技术。 这一技术主要应用于3层交换机和路由器中&#xff0c;但主流应用还是在3层交换机中。 VLAN 是基于物理网络上构建…...

回归预测 | MATLAB实现基于BP-Adaboost的BP神经网络结合AdaBoost多输入单输出回归预测

回归预测 | MATLAB实现基于BP-Adaboost的BP神经网络结合AdaBoost多输入单输出回归预测 目录 回归预测 | MATLAB实现基于BP-Adaboost的BP神经网络结合AdaBoost多输入单输出回归预测预测效果基本介绍模型描述程序设计参考资料 预测效果 基本介绍 1.MATLAB实现基于BP-Adaboost的BP…...

【蓝桥每日一题]-动态规划 (保姆级教程 篇11)#方格取数2.0 #传纸条

目录 题目&#xff1a;方格取数 思路&#xff1a; 题目&#xff1a;传纸条 思路&#xff1a; 题目&#xff1a;方格取数 &#xff08;跑两次&#xff09; 思路&#xff1a; 如果记录一种方案后再去跑另一个方案&#xff0c;影响因素太多了&#xff0c;所以两个方案要同时开…...

前端TypeScript学习day05-索引签名、映射与类型声明文件

(创作不易&#xff0c;感谢有你&#xff0c;你的支持&#xff0c;就是我前行的最大动力&#xff0c;如果看完对你有帮助&#xff0c;请留下您的足迹&#xff09; 目录 索引签名类型 映射类型 索引查询&#xff08;访问&#xff09;类型 基本使用 同时查询多个索引的类型…...

Echarts柱状图数据过多设置滚动条效果

未设置前&#xff1a; 设置后&#xff1a; dataZoom: [ { show: true, height:8, bottom:0, startValue: 0, //起始值 endValue: 5, //结束值 showDetail: fals…...

64 最长公共子序列

最长公共子序列 题解1 DP 给定两个字符串 text1 和 text2&#xff0c;返回这两个字符串的 最长公共子序列的长度。如果不存在 公共子序列&#xff0c;返回 0 。 一个字符串的子序列是指这样一个新的字符串&#xff1a;它是由原字符串在不改变字符的相对顺序的情况下删除某些…...

matlab常用函数

绘图函数 一、plot()&#xff1a;二维图形绘制 1、plot(y)&#xff1a; 对于只含一个输入参数的plot函数&#xff0c;如果输入参数y为向量&#xff0c;则以该参数为纵坐标&#xff0c;横坐标从1开始至与向量的长度相等&#xff1b;如果输入参数y是矩阵时&#xff0c;则按列绘…...

Python配置镜像源

Python3安装pika的准备 Windows下配置镜像源可以按照如下操作。 1.winR执行%APPDATA% %APPDATA%后&#xff0c;创建pip文件夹&#xff0c;并创建pip.ini配置文件 查看此目录下是否有pip目录&#xff0c;如果没有则需要创建&#xff0c;并在pip目录下以文本方式添加pip.ini文件…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

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群集中。 具体可参…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...