当前位置: 首页 > 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文件…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

python打卡day49@浙大疏锦行

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 一、通道注意力模块复习 & CBAM实现 import torch import torch.nn as nnclass CBAM(nn.Module):def __init__…...

Qt Quick Controls模块功能及架构

Qt Quick Controls是Qt Quick的一个附加模块&#xff0c;提供了一套用于构建完整用户界面的UI控件。在Qt 6.0中&#xff0c;这个模块经历了重大重构和改进。 一、主要功能和特点 1. 架构重构 完全重写了底层架构&#xff0c;与Qt Quick更紧密集成 移除了对Qt Widgets的依赖&…...