相似度为 K 的字符串
题目链接
相似度为 K 的字符串
题目描述
注意
- s1和s2只包含集合 {‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’} 中的小写字母
- s2是s1的一个字母异位词
解答思路
- 可以深度优先遍历交换字母使得s1和s2尽可能接近,基本思路是:设定一个指针idx指向s1和s2的相同位置,如果此时指针处的字母不同(此时前面的字母已经相同),则需要将此处的字母与后面的字母进行交换,使用该位置处的字母相同后再继续深度优先遍历,深搜过后需要进行回溯,防止对其他深搜过程造成影响
- 为了降低时间复杂度,还要注意进行剪枝
- 在进入本次dfs时,如果交换次数过多,则可以直接进行剪枝
- 在寻找后面的字母对idx处字母进行交换时,如果相似度仍然相同(arr1[j] != arr2[j]),则可以进行剪枝
- 在寻找后面的字母对idx处字母进行交换时,如果如果交换后对应i位和j位处的字母都相等,则可以认为已是最优交换(一次交换相似度最多减少2),可以进行剪枝
代码
class Solution {int n;int res;public int kSimilarity(String s1, String s2) {n = s1.length();res = Integer.MAX_VALUE;char[] arr1 = s1.toCharArray();char[] arr2 = s2.toCharArray();dfs(arr1, arr2, 0, 0);return res;}public void dfs(char[] arr1, char[] arr2, int idx, int count) {// 交换次数过多,直接剪枝if (count >= res) {return;}for (int i = idx; i < n; i++) {if (arr1[i] != arr2[i]) {for (int j = i + 1; j < n; j++) {// 贪心选择->保证交换后相似度更低if (arr1[j] == arr2[i] && arr1[j] != arr2[j]) {swap(arr1, i, j);dfs(arr1, arr2, i + 1, count + 1);// 回溯swap(arr1, i, j);// 贪心选择->如果交换后对应i位和j位处的字母都相等,则可以认为已是最优交换if (arr1[i] == arr2[j]) {break;}}}return;}}res = Math.min(res, count);}public void swap(char[] arr, int i, int j) {char tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}
}
关键点
- 深度优先遍历的思想
- 注意剪枝的情况
相关文章:
相似度为 K 的字符串
题目链接 相似度为 K 的字符串 题目描述 注意 s1和s2只包含集合 {‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’} 中的小写字母s2是s1的一个字母异位词 解答思路 可以深度优先遍历交换字母使得s1和s2尽可能接近,基本思路是:设定一个指针idx指向s1和s2的…...
[云] Project Analysis
项目要求分析: 开放性选题: 主题范围:任何与云计算系统相关的主题。项目类型:可以是技术、商业或研究项目。团队规模:最多可组成三人小组。 示例主题: 分析公共云数据:例如,AWS公共数…...
腾讯六宫格本地识别,本地模型识别,腾讯六图识别
基于K哥爬虫昨天发的文章,特此训练了一版腾讯模型,效果不错,特此感谢K哥的指导,效果如下图: 有需求,有疑问的欢迎评论区点出...
Transformer图解以及相关的概念
前言 transformer是目前NLP甚至是整个深度学习领域不能不提到的框架,同时大部分LLM也是使用其进行训练生成模型,所以transformer几乎是目前每一个机器人开发者或者人工智能开发者不能越过的一个框架。接下来本文将从顶层往下去一步步掀开transformer的面…...
Nginx缓存静态文件
在Python项目中,通过Nginx缓存静态文件(如CSS、JS、图片等),可以有效提升网页的加载性能。Nginx可以帮助你缓存静态资源,减少服务器负担,并加速页面加载。 1. 配置Nginx缓存静态文件 首先,你需…...
【隐私计算】隐语HEU同态加密算法解读
HEU: 一个高性能的同态加密算法库,提供了多种 PHE 算法, 包括ZPaillier、FPaillier、IPCL、Damgard Jurik、DGK、OU、EC ElGamal 以及基于FPGA和GPU硬件加速版本的Paillier版本。 本文我们会基于GPU运行HEU Docker容器,编译打包GPaillier并测…...
用C#实现互斥操作
1、传统的lock lock简单易用,适合大多数场景,但在高竞争用情况下可能会导致线程阻塞; Object obj new object(); void method1(){lock (obj){// 进行互斥操作}}2、SpinLock SpinLock在低延迟情况下更有效,因为SpinLock会在忙等…...
【黑马点评优化】之使用Caffeine+Redis实现应用级二层缓存
【黑马点评优化】之使用CaffeineRedis实现应用级二层缓存 1 缓存雪崩定义及解决方案2 为什么要使用多级缓存3 RedisCaffeine实现应用层二级缓存原理4 利用CaffeineRedis解决Redis突然宕机导致的缓存雪崩问题4.1 pom.xml文件引入相关依赖4.2 本地缓存配置类4.3 修改ShopServiceI…...
CEEMDAN +组合预测模型(BiLSTM-Attention + ARIMA)
往期精彩内容: 时序预测:LSTM、ARIMA、Holt-Winters、SARIMA模型的分析与比较 全是干货 | 数据集、学习资料、建模资源分享! EMD、EEMD、FEEMD、CEEMD、CEEMDAN的区别、原理和Python实现(一)EMD-CSDN博客 EMD、EEM…...
2.1.ReactOS系统中断描述符的格式KIDTENTRY结构体
2.1.ReactOS系统中断描述符的格式KIDTENTRY结构体 2.1.ReactOS系统中断描述符的格式KIDTENTRY结构体 文章目录 2.1.ReactOS系统中断描述符的格式KIDTENTRY结构体KIDTENTRY KIDTENTRY 数据结构KIDTENTRY定义了CPU对中断描述符的格式 // // …...
三、ElementPlus下拉搜索加弹窗组件的封装
近期产品提出了一个需求,要求一个form的表单里面的一个组件既可以下拉模糊搜索,又可以弹窗搜索,我就为这个封装了一个组件,下面看效果图。 效果大家看到了,下面就看组件封装和实现方法 第一步,组件封装&…...
androidStudio编译导致的同名.so文件冲突问题解决
files found with path lib/arm64-v8a/libserial_port.so from inputs: ...\build\intermediates\library_jni\debug\jni\arm64-v8a\libserial_port.so C:\Users\...\.gradle\caches\transforms-3\...\jni\arm64-v8a\XXX.so 解决方式如下: 1.将gradle缓存文件删…...
大学新生编程入门指南:如何选择编程语言与制定学习计划
大学新生编程入门指南:如何选择编程语言与制定学习计划 编程已成为当代大学生的必备技能,尤其是在信息技术高速发展的今天,编程能力不仅能帮助你在课堂学习中脱颖而出,更能为未来职业生涯打下坚实的基础。然而,面对如…...
SpringAI快速上手
一、导入依赖 镜像(导入maven依赖) <repositories><repository><id>spring-snapshots</id><name>Spring Snapshots</name><url>https://repo.spring.io/snapshot</url><releases><enabled>…...
07 django管理系统 - 部门管理 - 搜索部门
在dept_list.html中,添加搜索框 <div class"container-fluid"><div style"margin-bottom: 10px" class"clearfix"><div class"panel panel-default"><!-- Default panel contents --><div clas…...
数据操作学习
1.导入torch。虽然被称为PyTorch,但应导入torch而不是pytorch import torch 2.张量表示一个数值组成的数组,这个数组可能有多个维度 xtorch.arange(12)x 3.通过张量的shape属性来访问张量的形状和张量中元素的总数 x.shape x.numel() 4.要改变张量的形…...
什么是网络代理
了解网络代理 网络代理是一种特殊的网络服务,它允许一个网络终端(通常指客户端)通过这个服务与另一个网络终端(通常指服务器)进行非直接的连接。网络代理服务器位于发送主机和接收主机之间,接收网络请求&a…...
安防监控摄像头图传模组,1公里WiFi无线传输方案,监控新科技
在数字化浪潮汹涌的今天,安防监控领域也迎来了技术革新的春风。今天,我们就来聊聊这一领域的产品——摄像头图传模组,以及它如何借助飞睿智能1公里WiFi无线传输技术,为安防监控带来未有的便利与高效。 一、安防监控的新篇章 随着…...
问:JVM中GC类型有哪些?触发条件有哪些?区别是啥?
在Java虚拟机(JVM)中,垃圾收集(GC)是自动管理内存的关键机制。GC负责识别并回收那些不再被程序使用的对象,以释放内存空间。根据回收的区域和策略的不同,JVM中的GC可以分为多种类型。 一、GC的…...
【操作系统的使用】Linux 输入输出重定向:掌握控制台的高级用法
文章目录 Linux 输入输出重定向:掌握控制台的高级用法输出重定向将命令输出保存到文件将命令输出追加到文件 输入重定向从文件读取输入 管道操作将多个命令的输出链接起来 错误重定向将错误信息保存到文件同时重定向输出和错误信息 Linux 输入输出重定向:…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在K8S群集中。 具体可参…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中,新增了一个本地验证码接口 /code,使用函数式路由(RouterFunction)和 Hutool 的 Circle…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...
iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈
在日常iOS开发过程中,性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期,开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发,但背后往往隐藏着系统资源调度不当…...
HubSpot推出与ChatGPT的深度集成引发兴奋与担忧
上周三,HubSpot宣布已构建与ChatGPT的深度集成,这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋,但同时也存在一些关于数据安全的担忧。 许多网络声音声称,这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...
苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会
在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...
