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

相似度为 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尽可能接近&#xff0c;基本思路是&#xff1a;设定一个指针idx指向s1和s2的…...

[云] Project Analysis

项目要求分析&#xff1a; 开放性选题&#xff1a; 主题范围&#xff1a;任何与云计算系统相关的主题。项目类型&#xff1a;可以是技术、商业或研究项目。团队规模&#xff1a;最多可组成三人小组。 示例主题&#xff1a; 分析公共云数据&#xff1a;例如&#xff0c;AWS公共数…...

腾讯六宫格本地识别,本地模型识别,腾讯六图识别

基于K哥爬虫昨天发的文章&#xff0c;特此训练了一版腾讯模型&#xff0c;效果不错&#xff0c;特此感谢K哥的指导&#xff0c;效果如下图: 有需求&#xff0c;有疑问的欢迎评论区点出...

Transformer图解以及相关的概念

前言 transformer是目前NLP甚至是整个深度学习领域不能不提到的框架&#xff0c;同时大部分LLM也是使用其进行训练生成模型&#xff0c;所以transformer几乎是目前每一个机器人开发者或者人工智能开发者不能越过的一个框架。接下来本文将从顶层往下去一步步掀开transformer的面…...

Nginx缓存静态文件

在Python项目中&#xff0c;通过Nginx缓存静态文件&#xff08;如CSS、JS、图片等&#xff09;&#xff0c;可以有效提升网页的加载性能。Nginx可以帮助你缓存静态资源&#xff0c;减少服务器负担&#xff0c;并加速页面加载。 1. 配置Nginx缓存静态文件 首先&#xff0c;你需…...

【隐私计算】隐语HEU同态加密算法解读

HEU: 一个高性能的同态加密算法库&#xff0c;提供了多种 PHE 算法&#xff0c; 包括ZPaillier、FPaillier、IPCL、Damgard Jurik、DGK、OU、EC ElGamal 以及基于FPGA和GPU硬件加速版本的Paillier版本。 本文我们会基于GPU运行HEU Docker容器&#xff0c;编译打包GPaillier并测…...

用C#实现互斥操作

1、传统的lock lock简单易用&#xff0c;适合大多数场景&#xff0c;但在高竞争用情况下可能会导致线程阻塞&#xff1b; Object obj new object(); void method1(){lock (obj){// 进行互斥操作}}2、SpinLock SpinLock在低延迟情况下更有效&#xff0c;因为SpinLock会在忙等…...

【黑马点评优化】之使用Caffeine+Redis实现应用级二层缓存

【黑马点评优化】之使用CaffeineRedis实现应用级二层缓存 1 缓存雪崩定义及解决方案2 为什么要使用多级缓存3 RedisCaffeine实现应用层二级缓存原理4 利用CaffeineRedis解决Redis突然宕机导致的缓存雪崩问题4.1 pom.xml文件引入相关依赖4.2 本地缓存配置类4.3 修改ShopServiceI…...

CEEMDAN +组合预测模型(BiLSTM-Attention + ARIMA)

往期精彩内容&#xff1a; 时序预测&#xff1a;LSTM、ARIMA、Holt-Winters、SARIMA模型的分析与比较 全是干货 | 数据集、学习资料、建模资源分享&#xff01; EMD、EEMD、FEEMD、CEEMD、CEEMDAN的区别、原理和Python实现&#xff08;一&#xff09;EMD-CSDN博客 EMD、EEM…...

2.1.ReactOS系统中断描述符的格式KIDTENTRY结构体

2.&#xff11;.ReactOS系统中断描述符的格式KIDTENTRY结构体 2.&#xff11;.ReactOS系统中断描述符的格式KIDTENTRY结构体 文章目录 2.&#xff11;.ReactOS系统中断描述符的格式KIDTENTRY结构体KIDTENTRY KIDTENTRY 数据结构KIDTENTRY定义了CPU对中断描述符的格式 // // …...

三、ElementPlus下拉搜索加弹窗组件的封装

近期产品提出了一个需求&#xff0c;要求一个form的表单里面的一个组件既可以下拉模糊搜索&#xff0c;又可以弹窗搜索&#xff0c;我就为这个封装了一个组件&#xff0c;下面看效果图。 效果大家看到了&#xff0c;下面就看组件封装和实现方法 第一步&#xff0c;组件封装&…...

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 解决方式如下&#xff1a; 1.将gradle缓存文件删…...

大学新生编程入门指南:如何选择编程语言与制定学习计划

大学新生编程入门指南&#xff1a;如何选择编程语言与制定学习计划 编程已成为当代大学生的必备技能&#xff0c;尤其是在信息技术高速发展的今天&#xff0c;编程能力不仅能帮助你在课堂学习中脱颖而出&#xff0c;更能为未来职业生涯打下坚实的基础。然而&#xff0c;面对如…...

SpringAI快速上手

一、导入依赖 镜像&#xff08;导入maven依赖&#xff09; <repositories><repository><id>spring-snapshots</id><name>Spring Snapshots</name><url>https://repo.spring.io/snapshot</url><releases><enabled>…...

07 django管理系统 - 部门管理 - 搜索部门

在dept_list.html中&#xff0c;添加搜索框 <div class"container-fluid"><div style"margin-bottom: 10px" class"clearfix"><div class"panel panel-default"><!-- Default panel contents --><div clas…...

数据操作学习

1.导入torch。虽然被称为PyTorch&#xff0c;但应导入torch而不是pytorch import torch 2.张量表示一个数值组成的数组&#xff0c;这个数组可能有多个维度 xtorch.arange(12)x 3.通过张量的shape属性来访问张量的形状和张量中元素的总数 x.shape x.numel() 4.要改变张量的形…...

什么是网络代理

了解网络代理 网络代理是一种特殊的网络服务&#xff0c;它允许一个网络终端&#xff08;通常指客户端&#xff09;通过这个服务与另一个网络终端&#xff08;通常指服务器&#xff09;进行非直接的连接。网络代理服务器位于发送主机和接收主机之间&#xff0c;接收网络请求&a…...

安防监控摄像头图传模组,1公里WiFi无线传输方案,监控新科技

在数字化浪潮汹涌的今天&#xff0c;安防监控领域也迎来了技术革新的春风。今天&#xff0c;我们就来聊聊这一领域的产品——摄像头图传模组&#xff0c;以及它如何借助飞睿智能1公里WiFi无线传输技术&#xff0c;为安防监控带来未有的便利与高效。 一、安防监控的新篇章 随着…...

问:JVM中GC类型有哪些?触发条件有哪些?区别是啥?

在Java虚拟机&#xff08;JVM&#xff09;中&#xff0c;垃圾收集&#xff08;GC&#xff09;是自动管理内存的关键机制。GC负责识别并回收那些不再被程序使用的对象&#xff0c;以释放内存空间。根据回收的区域和策略的不同&#xff0c;JVM中的GC可以分为多种类型。 一、GC的…...

【操作系统的使用】Linux 输入输出重定向:掌握控制台的高级用法

文章目录 Linux 输入输出重定向&#xff1a;掌握控制台的高级用法输出重定向将命令输出保存到文件将命令输出追加到文件 输入重定向从文件读取输入 管道操作将多个命令的输出链接起来 错误重定向将错误信息保存到文件同时重定向输出和错误信息 Linux 输入输出重定向&#xff1a…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

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 &…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

JS手写代码篇----使用Promise封装AJAX请求

15、使用Promise封装AJAX请求 promise就有reject和resolve了&#xff0c;就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...