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

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

使用Spring AI和MCP协议构建图片搜索服务

目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式&#xff08;本地调用&#xff09; SSE模式&#xff08;远程调用&#xff09; 4. 注册工具提…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.

ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #&#xff1a…...

Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?

Pod IP 的本质与特性 Pod IP 的定位 纯端点地址&#xff1a;Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址&#xff08;如 10.244.1.2&#xff09;无特殊名称&#xff1a;在 Kubernetes 中&#xff0c;它通常被称为 “Pod IP” 或 “容器 IP”生命周期&#xff1a;与 Pod …...

图解JavaScript原型:原型链及其分析 | JavaScript图解

​​ 忽略该图的细节&#xff08;如内存地址值没有用二进制&#xff09; 以下是对该图进一步的理解和总结 1. JS 对象概念的辨析 对象是什么&#xff1a;保存在堆中一块区域&#xff0c;同时在栈中有一块区域保存其在堆中的地址&#xff08;也就是我们通常说的该变量指向谁&…...

qt+vs Generated File下的moc_和ui_文件丢失导致 error LNK2001

qt 5.9.7 vs2013 qt add-in 2.3.2 起因是添加一个新的控件类&#xff0c;直接把源文件拖进VS的项目里&#xff0c;然后VS卡住十秒&#xff0c;然后编译就报一堆 error LNK2001 一看项目的Generated Files下的moc_和ui_文件丢失了一部分&#xff0c;导致编译的时候找不到了。因…...