当前位置: 首页> 科技> IT业 > seo教程百度云_西安产品设计公司有哪些_宁德市自然资源局_刷seo关键词排名软件

seo教程百度云_西安产品设计公司有哪些_宁德市自然资源局_刷seo关键词排名软件

时间:2025/7/11 8:27:04来源:https://blog.csdn.net/mmlhbjk/article/details/144001435 浏览次数:0次
seo教程百度云_西安产品设计公司有哪些_宁德市自然资源局_刷seo关键词排名软件

两个字符串得切换距离

1、题目描述

给你两个长度相同的字符串 st ,以及两个整数数组 nextCostpreviousCost

一次操作中,你可以选择 s 中的一个下标 i ,执行以下操作 之一 :

  • s[i] 切换为字母表中的下一个字母,如果 s[i] == 'z' ,切换后得到 'a' 。操作的代价为 nextCost[j] ,其中 j 表示 s[i] 在字母表中的下标。
  • s[i] 切换为字母表中的上一个字母,如果 s[i] == 'a' ,切换后得到 'z' 。操作的代价为 previousCost[j] ,其中 js[i] 在字母表中的下标。

切换距离 指的是将字符串 s 变为字符串 t 的 最少 操作代价总和。

请你返回从 st切换距离

2、解题思路

1、字符与字母表的映射
  • 字母表有 26 个字母,从 'a''z'
  • 每个字符都有对应的下标 index,计算公式为: i n d e x = o r d ( c ) − o r d ( a ) index=ord(c)−ord(a) index=ord(c)ord(a)
2、切换规则
  • 从字符 s[i] 到 ,可能需要:
    1. 顺时针切换(下一个字母)。
    2. 逆时针切换(上一个字母)。
  • 字符切换可能经过 0 到 25 个字母,因此需要考虑两种切换的代价并取较小值。
3、代价计算
  • 对于顺时针切换: c o s t = n e x t c o s t [ i n d e x ( s [ i ] ) ] + … + n e x t c o s t [ i n d e x ( t [ i ] ) ] cost=nextcost[index(s[i])]+…+nextcost[index(t[i])] cost=nextcost[index(s[i])]++nextcost[index(t[i])]
  • 对于逆时针切换: c o s t = p r e v i o u s c o s t [ i n d e x ( s [ i ] ) ] + … + p r e v i o u s c o s t [ i n d e x ( t [ i ] ) ] cost=previouscost[index(s[i])]+…+previouscost[index(t[i])] cost=previouscost[index(s[i])]++previouscost[index(t[i])]
4、贪心策略
  • 对于每对字符 ( s [ i ] , t [ i ] ) (s[i],t[i]) (s[i],t[i]),计算顺时针和逆时针切换的代价,选择较小值。

3、代码实现

class Solution {
public:long long shiftDistance(string s, string t, vector<int>& nextCost, vector<int>& previousCost) {int n = s.size();int alphabetSize = 26;   // 字母表大小long long totalCost = 0; // 使用 long long 防止溢出for (int i = 0; i < n; ++i) {int start = s[i] - 'a'; // 起始字符的下标int end = t[i] - 'a';   // 目标字符的下标// 计算顺时针代价long long clockwiseCost = 0;for (int j = start; j != end; j = (j + 1) % alphabetSize) {clockwiseCost += nextCost[j];}// 计算逆时针代价long long counterClockwiseCost = 0;for (int j = start; j != end; j = (j - 1 + alphabetSize) % alphabetSize) {counterClockwiseCost += previousCost[j];}// 累加到总代价中,选择顺时针和逆时针中的较小值totalCost += min(clockwiseCost, counterClockwiseCost);}return totalCost;}
};

关键点

  1. 代价累加使用 long long
    • totalCostclockwiseCostcounterClockwiseCost 均使用 long long 类型,防止溢出。
  2. 顺时针与逆时针的灵活计算
    • 顺时针使用 (j + 1) % alphabetSize
    • 逆时针使用 (j - 1 + alphabetSize) % alphabetSize

4、复杂度分析

  1. 时间复杂度
    • 对于每个字符对 ( s [ i ] , t [ i ] ) (s[i],t[i]) (s[i],t[i]),最多需要遍历 O(26) 次字母表。
    • 总时间复杂度为 O ( n × 26 ) = O ( n ) O(n×26)=O(n) O(n×26)=O(n)
  2. 空间复杂度
    • 仅使用常数额外空间。
    • 空间复杂度为 O(1) 。
关键字:seo教程百度云_西安产品设计公司有哪些_宁德市自然资源局_刷seo关键词排名软件

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: