Leetcode 第396场周赛 问题和解法
问题
有效单词
有效单词需要满足以下几个条件:
至少包含3个字符。
由数字0-9和英文大小写字母组成。(不必包含所有这类字符。)
至少包含一个元音字母。
至少包含一个辅音字母。
给你一个字符串word。如果word是一个有效单词,则返回true,否则返回false。
注意:
‘a’、‘e’、‘i’、‘o’、'u’及其大写形式都属于元音字母。
英文中的辅音字母是指那些除元音字母之外的字母。
示例 1:
输入:word = “234Adas”
输出:true
解释:
这个单词满足所有条件。
解题思路
用两个变量 f0和 f1记录字符串中是否有辅音或元音,必须都为 true才返回 true
如果字符串长度不足 333 或者包含除了数字或字母以外的字符,返回 false。
class Solution {public boolean isValid(String word) {if (word.length() < 3) {return false;}boolean[] f = new boolean[2];Arrays.fill(f, false);for (char c : word.toCharArray()) {if (Character.isAlphabetic(c)) {c = Character.toLowerCase(c);f[c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ? 1 : 0] = true;} else if (!Character.isDigit(c)) {return false;}}return f[0] && f[1];}
}
K 周期字符串需要的最少操作次数
给你一个长度为n的字符串word和一个整数k,其中k是n的因数。
在一次操作中,你可以选择任意两个下标i和j,其中0<=i,j<n,且这两个下标都可以被k整除,然后用从j开始的长度为k的子串替换从i开始的长度为k的子串。也就是说,将子串word[i…i+k-1]替换为子串word[j…j+k-1]。
返回使word成为K周期字符串所需的最少操作次数。
如果存在某个长度为k的字符串s,使得word可以表示为任意次数连接s,则称字符串word是K周期字符串。例如,如果word==“ababab”,那么word就是s="ab"时的2周期字符串。
示例1:
输入:word=“leetcodeleet”,k=4
输出:1
解释:可以选择i=4和j=0获得一个4周期字符串。这次操作后,word变为"leetleetleet"。
解题思路
1、分段统计。使用哈希表记录各段出现次数,并记录相同段的最大次数。
2、使用贪心策略。求最少操作次数,以相同段最多的作为替换基准
class Solution {public int minimumOperationsToMakeKPeriodic(String word, int k) {int len = word.length();// 1、分段统计。使用哈希表记录各段出现次数,并记录相同段的最大次数HashMap<String, Integer> segmentCntMap = new HashMap<>();int maxSegmentCnt = 0;for (int i = 0; i < len; ) {StringBuilder sb = new StringBuilder();for (int j = 0; j < k; i++, j++) {sb.append(word.charAt(i));}String segment = sb.toString();int cnt = segmentCntMap.getOrDefault(segment, 0) + 1;segmentCntMap.put(segment, cnt);maxSegmentCnt = Math.max(cnt, maxSegmentCnt);}// 2、贪心策略。求最少操作次数,以相同段最多的作为替换基准int totalSegment = len / k;return totalSegment - maxSegmentCnt;}
}
同位字符串连接的最小长度
给你一个字符串s,它由某个字符串t和若干t的同位字符串连接而成。
请你返回字符串t的最小可能长度。
同位字符串指的是重新排列一个单词得到的另外一个字符串,原来字符串中的每个字符在新字符串中都恰好只使用一次。
示例1:
输入:s=“abba”
输出:2
解释:
一个可能的字符串t为"ba"。
解题思路
1.len的因子作为 一段段字符串的截取长度。
2.都是小写字母,长度为26的数组判断是否相同就行。
class Solution {public static int minAnagramLength(String s) {char[] ch = s.toCharArray();int len = s.length();for (int i = 1; i <= len; i++) {if (len % i != 0) continue;if (minCheck(ch, i)) return i;}return len;}//不是滑窗 是一个个相同长度的字符串 截取。public static boolean minCheck(char[] ch, int m) {int len = ch.length;if (len % m != 0) return false;//比较的母体。int[] arr = new int[26];for (int i = 0; i < m; i++) {arr[ch[i] - 'a']++;}int[] nowArr = new int[26];//要跟母体比较的字符串从下标m开始。为了不错过最后一段,i能取到lenfor (int i = m; i <= len; i++) {if (i != m && i % m == 0) {//当下标不是m 且 是m的倍数时。// 那就是一段长度为m的字符串了,就可以跟母体比较了if (!Arrays.equals(nowArr, arr)) return false;nowArr = new int[26]; //比较完 清空长度为26的数组}if (i == len) break; //到底了 就要跳出了,不然要越界。nowArr[ch[i] - 'a']++; //计数}return true;}
}
使数组中所有元素相等的最小开销
给你一个整数数组nums和两个整数cost1和cost2。你可以执行以下任一操作任意次:
从nums中选择下标i并且将nums[i]增加1,开销为cost1。
选择nums中两个不同下标i和j,并且将nums[i]和nums[j]都增加1,开销为cost2。
你的目标是使数组中所有元素都相等,请你返回需要的最小开销之和。
由于答案可能会很大,请你将它对109+7取余后返回。
示例1:
输入:nums=[4,1],cost1=5,cost2=2
输出:15
解释:
执行以下操作可以使数组中所有元素相等:
将nums[1]增加1,开销为5,nums变为[4,2]。
将nums[1]增加1,开销为5,nums变为[4,3]。
将nums[1]增加1,开销为5,nums变为[4,4]。
总开销为15。
解题思路
贪心解题
class Solution {int r = 1000000007;public int minCostToEqualizeArray(int[] nums, int cost1, int cost2) {int n = nums.length;long ans = 0;long sum = 0,res=0;// System.out.println(maxn);Arrays.sort(nums);int maxn = nums[n - 1];for(int i=0;i<n;i++){nums[i]=maxn-nums[i];}Arrays.sort(nums);maxn=nums[n-1];System.out.println(sum+"a"+maxn);if (n == 2) {long a=nums[1],b=nums[0];return (int)(( a-b ) * cost1%r);}for (int num : nums)sum += num;if (cost1 * 2 <= cost2) {return (int) (sum*cost1%r);}if(maxn*2>sum){//res=sum-2*(sum-maxn);ans=(ans+(sum-maxn)*cost2)%r;res=2*maxn-sum;}else{ans=(ans+sum/2*cost2)%r;if(sum%2==1)res=1;}System.out.println(ans+" "+res);//如果存在多个n-2-2k正好构成resif(n%2==0&&res%2==1){ans=(ans+cost1)%r;res--;if(res==0)return (int) ans % r;}// long a1=cost1*res;// long a2=cost2*// ans+=Math.min();for(int k=0;k*2+2<n&&res>0;k++){long x=n-2-2*k;long u=res/x;ans=(ans+Math.min(u*(x+1+k)*cost2,x*u*cost1))%r;res=res-x*u;}return (int) ans % r;}
}
来源
LeetCode周赛
相关文章:
Leetcode 第396场周赛 问题和解法
问题 有效单词 有效单词需要满足以下几个条件: 至少包含3个字符。 由数字0-9和英文大小写字母组成。(不必包含所有这类字符。) 至少包含一个元音字母。 至少包含一个辅音字母。 给你一个字符串word。如果word是一个有效单词,则…...

OC foudation框架(上)学习
foundation框架 文章目录 foundation框架字符串(NSString && NSMutableString)NSString的其他功能NSMutableString 日期与时间 (NSDate)2.1 日期与时间(NSDate)2.2日期格式器日历与日期组件定时器&…...

【机器学习300问】83、深度学习模型在进行学习时梯度下降算法会面临哪些局部最优问题?
梯度下降算法是一种常用的优化方法,用于最小化损失函数以训练模型。然而,在使用梯度下降算法时,可能会面临以下局部最优问题。 (一)非凸函数的局部极小值 问题描述:在复杂的损失函数中,如果目…...
基于springboot的校园管理系统源码数据库
基于springboot的校园管理系统源码数据库 随着科学技术的飞速发展,社会的方方面面、各行各业都在努力与现代的先进技术接轨,通过科技手段来提高自身的优势,校园管理系统当然也不能排除在外。校园管理系统是以实际运用为开发背景,…...

图形网络的自适应扩散 笔记
1 Title Adaptive Diffusion in Graph Neural Networks(Jialin Zhao、Yuxiao Dong、Ming Ding、Evgeny Kharlamov、Jie Tang)【NIPS 2021】 2 Conclusion The neighborhood size in GDC is manually tuned for each graph by conductin…...
vue基础配置
vite.config.ts import { defineConfig } from vite import vue from vitejs/plugin-vue import path from "path"; //引入svg需要用到的插件 import { createSvgIconsPlugin } from vite-plugin-svg-icons //mock插件提供方法 import { viteMockServe } from vite-…...

C++基础中的存储类别
存储的类别是变量的属性之一,C语言定义了4种变量的存储类别,分别是auto变量、static变量、register变量和extern变量。以下重点介绍这几种类型。 一、auto变量 auto变量是C默认的存储类型。函数内未加存储类型说明的变量均被称为自动变量,即…...

【NPM】Nginx Proxy Manager 一键申请 SSL 证书,自动续期,解决阿里云SSL免费证书每3个月失效问题
文章目录 1、NPM 简介2、实战Step 1:环境搭建 也可以看作者安装笔记 Step 2:创建容器 2.1 在系统任意位置创建一个文件夹,此文档以~/nginx-proxy-manager为例。2.2 创建docker-compose.yaml2.3 启动NPM服务 Step 3:配置反向代理3…...

教你解决PUBG绝地求生游戏中闪退掉线无法重连回去的问题
《绝地求生》(PUBG),作为一款在全球范围内掀起热潮的战术竞技游戏,以其栩栩如生的战场环境和令人心跳加速的生存冒险博得了广大玩家的青睐。然而,一些玩家在经历了一场惊心动魄的对局后,却面临了一个不大不…...
24 Debian如何配置Apache2(4)LAMP+phpMyAdmin部署
作者:网络傅老师 特别提示:未经作者允许,不得转载任何内容。违者必究! Debian如何配置Apache2(4)LAMP+phpMyAdmin部署 《傅老师Debian小知识库系列之24》——原创 ==前言== 傅老师Debian小知识库特点: 1、最小化拆解Debian实用技能; 2、所有操作在VM虚拟机实测完成;…...
centos安装paddlespeech各种报错解决方案
背景 windows系统安装paddlespeech一路顺利 centos安装之前也是正常 今天centos再次安装各种报错,避免以后遇到浪费时间,记录下来,也给大家节约时间 报错 报错1 module numpy has no attribute complex. 解决方案 降低numpy # 1. 卸载当前numpy库 pip uninstall numpy…...

谈基于ATTCK框架的攻击链溯源
引言 网络安全在当今数字化时代变得尤为关键,而MITRE公司开发的ATT&CK框架则成为了安全专业人员的重要工具。ATT&CK是一种广泛使用的攻击行为分类和描述框架。其目的在于提供一个共同的语言,使安全专业人员能够更好地理解攻击者的行为和目标&…...
在Ubuntu下搭建自己的以太坊私有链
最近要对链及链上应用进行压测,为了方便操作及分析问题,就自己搭建了一个eth私链。当前版本安装官方指引发现有卡点,于是决定整理一个文档,为其他有需要的朋友提供便捷操作,节约时间。 一、环境配置 linux操作系统:Ubuntu 20.04.6 LTS (Focal Fossa) go version: go1…...
巩固学习4
python中函数逆置的几种方法 s input()for i in range(len(s)-1,-1,-1):#从最后一位开始,步长为-1print(s[i],end)用for语句循环逆置 s input() s list(s) n len(s) for i in range(n//2):s[i],s[n-1-i] s[n-1-i],s[i]#从中间反转字符串 res "".j…...

Conda安装rasterio报错
Conda安装rasterio报错 文章目录 Conda安装rasterio报错问题解决参考 问题 在conda环境中安装rasterio包之后,本来可以正常运行的,但是之后又重新安装了一个gdal,导致原来的引用rasterio的包的程序不可正常运行了 conda install rasterio c…...

linux安装 mysql
环境:centOS8 一、安装 1 安装wget库 sudo yum -y install wget 2. 安装 mysql 换yum源 亲测成功!!!!!! 换yum源 1.下载对应版本的repo文件 wget -O CentOS-Base.repo http://mirrors…...

暴力法解决最近对问题和凸包问题-实现可视化
目录 最近对问题 凸包问题 最近对问题 顾名思义就是采用蛮力法求出所有点之间的距离,然后进行比较找出第一个最近对,一个一个进行比较。 大概思路就是如图(每个圈代表一个数对) 第一个和其他四个比较 第二个和其他三个比较 …...

[Kubernetes] Rancher 2.7.5 部署 k8s
server: 192.168.66.100 master: 192.168.66.101 node1: 192.168.66.102 文章目录 1.rancher server 安装docker2.部署k8s3.kubeconfig4.测试集群 1.rancher server 安装docker 所有主机开通ipv4 vi /etc/sysctl.conf#加入 net.ipv4.ip_forward 1#配置生效 sysctl -prancher…...

码题杯 世界警察 思想:双指针
https://www.matiji.net/exam/brushquestion/4/4446/16A92C42378232DEB56179D9C70DC45C 双指针 思路是这样的,首先r指针向右走,如果r指针遇到了和l指针一样的,那么l指针就,一直加到r指针的位置,此时a[l]a[r]࿰…...

drawio 网页版二次开发(1):源码下载和环境搭建
目录 一 说明 二 源码地址以及下载 三 开发环境搭建 1. 前端工程地址 2. 配置开发环境 (1)安装 node.js (2)安装 serve 服务器 3. 运行 四 最后 一 说明 应公司项目要求,需要对drawio进行二次开发&…...

网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...

Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

定时器任务——若依源码分析
分析util包下面的工具类schedule utils: ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类,封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz,先构建任务的 JobD…...

高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...

USB Over IP专用硬件的5个特点
USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中,从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备(如专用硬件设备),从而消除了直接物理连接的需要。USB over IP的…...