首页 > 其他分享 >[Leetcode] 0821. 字符的最短距离

[Leetcode] 0821. 字符的最短距离

时间:2023-10-23 14:45:28浏览次数:52  
标签:字符 下标 idx 0821 abs 短距离 ans textit Leetcode

821. 字符的最短距离

题目描述

给你一个字符串 s 和一个字符 c ,且 cs 中出现过的字符。

返回一个整数数组 answer ,其中 answer.length == s.lengthanswer[i]s 中从下标 i 到离它 最近 的字符 c距离

两个下标 ij 之间的 距离abs(i - j) ,其中 abs 是绝对值函数。

 

示例 1:

输入:s = "loveleetcode", c = "e"
输出:[3,2,1,0,1,0,0,1,2,2,1,0]
解释:字符 'e' 出现在下标 3、5、6 和 11 处(下标从 0 开始计数)。
距下标 0 最近的 'e' 出现在下标 3 ,所以距离为 abs(0 - 3) = 3 。
距下标 1 最近的 'e' 出现在下标 3 ,所以距离为 abs(1 - 3) = 2 。
对于下标 4 ,出现在下标 3 和下标 5 处的 'e' 都离它最近,但距离是一样的 abs(4 - 3) == abs(4 - 5) = 1 。
距下标 8 最近的 'e' 出现在下标 6 ,所以距离为 abs(8 - 6) = 2 。

示例 2:

输入:s = "aaab", c = "b"
输出:[3,2,1,0]

 

提示:
  • 1 <= s.length <= 104
  • s[i]c 均为小写英文字母
  • 题目数据保证 cs 中至少出现一次

解法

方法一:两次遍历

问题可以转换成,对 \(s\) 的每个下标 \(i\),求

\(s[i]\) 到其左侧最近的字符 \(c\) 的距离
\(s[i]\) 到其右侧最近的字符 \(c\) 的距离
这两者的最小值。

对于前者,我们可以从左往右遍历 \(s\),若 \(s[i]=c\) 则记录下此时字符 \(c\) 的的下标 \(\textit{idx}\)。遍历的同时更新 \(\textit{answer}[i]=i-\textit{idx}\)。

对于后者,我们可以从右往左遍历 \(s\),若 \(s[i]=c\) 则记录下此时字符 \(c\) 的的下标 \(\textit{idx}\)。遍历的同时更新 \(\textit{answer}[i]=\min(\textit{answer}[i],\textit{idx}-i)\)。

代码实现时,在开始遍历的时候 \(\textit{idx}\) 可能不存在,为了简化逻辑,我们可以用 \(-n\) 或 \(2n\) 表示,这里 \(n\) 是 \(s\) 的长度。

复杂度分析

时间复杂度:\(O(n)\),其中 \(n\) 是字符串 \(s\) 的长度。

空间复杂度:\(O(1)\)。返回值不计入空间复杂度。

Python3

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        n = len(s)
        ans = [0] * n

        idx = -n
        for i,ch in enumerate(s):
            if ch == c:
                idx = i
            ans[i] = i - idx

        idx = 2*n
        for i in range(n - 1,-1,-1):
            if s[i] == c:
                idx = i
            ans[i] = min(ans[i],idx-i)
        
        return ans

C++

class Solution {
public:
    vector<int> shortestToChar(string s, char c) {
        int n = s.length();
        vector<int> ans(n);
        for(int i=0,idx=-n;i<n;i++){
            if(s[i]== c){
                idx = i;
            }
            ans[i] = i - idx;
        }
        for(int i=n-1,idx=2*n;i>=0;i--){
            if(s[i] == c){
                idx = i;
            }
            ans[i] = min(ans[i],idx - i);
        }
        return ans;
    }
};

标签:字符,下标,idx,0821,abs,短距离,ans,textit,Leetcode
From: https://www.cnblogs.com/yege/p/17782347.html

相关文章

  • LeetCode 300. 最长递增子序列
    最长递增子序列题目链接:300.最长递增子序列题目描述:给你一个整数数组nums,找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。示例1:输入:nums=[10,9,2,5,3,......
  • LeetCode 376. 摆动序列
    最长递增子序列题目链接:376.摆动序列题目描述:如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为**摆动序列。**第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。例如,[1,7,4,9,2,5]是一个摆动序列,因为差值......
  • leetcode102-二叉树层序遍历
    目标:将每层的结果放在每层的集合中问题:如何将不同父节点的同层节点,例如4和6,按照顺序放在一个list中思路:4和6的关联在与它们的父节点,遍历他们的父节点时将其子节点放在一个缓存队列中,从队列中取值就能够实现目标代码:点击查看代码classSolution{publicList<List<Inte......
  • Leetcode原题 -- 螺旋矩阵相关
    第一题:54. 螺旋矩阵题目描述:给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。示例:输入:matrix=[[1,2,3],[4,5,6],[7,8,9]]输出:[1,2,3,6,9,8,7,4,5]解题思路:按层遍历,如图所示,找到规律后就差不多了publicList<Integer>spiral......
  • 6.使用leetcode去练习语言
    目录1本章预览2简单题举例2.1题目描述2.2题目解析2.3题解2.4涉及基础语法3中等题举例3.1题目描述3.2题目解析3.3题解3.4涉及基础语法4本章小结1本章预览事实上本章并不会去讲述go语言的基础情况,而是去介绍如何使用Leetcode去帮助我们去学习go语言的基本语法,当然本......
  • 算法训练day39LeetCode738.968.
    算法训练day39LeetCode738.968.738.单调递增的数字题目738.单调递增的数字-力扣(LeetCode)题解代码随想录(programmercarl.com)classSolution{public:intmonotoneIncreasingDigits(intn){stringstrNum=to_string(n);//int转换string......
  • [LeetCode] 1726. Tuple with Same Product
    Givenanarray nums of distinct positiveintegers,return thenumberoftuples (a,b,c,d) suchthat a*b=c*d where a, b, c,and d areelementsof nums,and a!=b!=c!=d.Example1:Input:nums=[2,3,4,6]Output:8Explanation:Ther......
  • [Leetcode] 0083. 删除排序链表中的重复元素
    83.删除排序链表中的重复元素题目描述给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回已排序的链表 。 示例1:输入:head=[1,1,2]输出:[1,2]示例2:输入:head=[1,1,2,3,3]输出:[1,2,3] 提示:链表中节点数目在范围[0,300]......
  • [Leetcode] 0070. 爬楼梯
    70.爬楼梯题目描述假设你正在爬楼梯。需要n 阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢? 示例1:输入:n=2输出:2解释:有两种方法可以爬到楼顶。1.1阶+1阶2.2阶示例2:输入:n=3输出:3解释:有三种方法可以爬到楼顶。1......
  • 算法训练day37 LeetCode860.406.452.
    算法训练day37LeetCode860.406.452.860.柠檬水找零题目860.柠檬水找零-力扣(LeetCode)题解代码随想录(programmercarl.com)5:收五元10:收十元,返五元20:优先还十元+五元;否则还五元*3classSolution{public:boollemonadeChange(vector<int>&bills)......