力扣(leetcode)第821题字符的最短距离(Python)

这篇具有很好参考价值的文章主要介绍了力扣(leetcode)第821题字符的最短距离(Python)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

821.字符的最短距离

题目链接:821.字符的最短距离

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

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

两个下标 i 和 j 之间的 距离 为 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 均为小写英文字母
题目数据保证 c 在 s 中至少出现一次

解答

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

最后,我写了一篇MySQL教程,里面详细的介绍了MySQL的基本概念以及操作指令等内容,欢迎阅读!
MySQL数据库万字保姆级教程文章来源地址https://www.toymoban.com/news/detail-804410.html

到了这里,关于力扣(leetcode)第821题字符的最短距离(Python)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 不同整数的最少数目和单词直接最短距离

    写是为了更好的思考,坚持写作,力争更好的思考。 今天分享两个关于“最小、最短”的算法题,废话少说,show me your code! 给你一个整数数组arr和一个整数k。现需要从数组中恰好移除k个元素,请找出移除后数组中不同整数的最少数目? 输入: arr=[5,4,5],k=1 输出:1 解释:

    2024年01月18日
    浏览(72)
  • GEE机器学习——利用最短距离方法进行土地分类和精度评定

    最短距离方法(Minimum Distance)是一种常用的模式识别算法,用于计算样本之间的相似度或距离。该方法通过计算样本之间的欧氏距离或其他距离度量,来确定样本之间的相似程度或差异程度。 最短距离方法的具体步骤如下: 1. 数据准备:收集并准备用于训练的数据集,确保

    2024年01月20日
    浏览(53)
  • 2023河南萌新联赛第(二)场:河南工业大学 F - 最短距离

    时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 262144K,其他语言524288K 64bit IO Format: %lld 题目描述 给定一棵包含 n n n 个顶点的树 T T T ,以及 m m m 个查询请求。每个查询包含三个参数 : x 、 y :x、y : x 、 y 和 k k k 。其中 x x x 和 y y y 是树中的两个顶点, k k k 是一个整数。对于

    2024年02月15日
    浏览(41)
  • 最短路径-任意两点间最短距离-Floyd算法的matlab实现(详细教程)

    目录 简介 核心思路 优缺点分析 算法过程          示例 Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德

    2024年02月05日
    浏览(41)
  • matlab算法模型——图的最短路径和距离

    目录 一、前言 二、最短路径 1.sqarse创建稀疏矩阵 ​​2.有向图的最短路径         使用graphallshortestpaths函数 使用dijkstra.ma函数(直接引用) 3.无向图的最短路径 使用函数graphallshortestpaths(2021的版本不能用了) 使用shortestpath函数 三、未解决的问题 动态规划——求解某类问题

    2024年02月04日
    浏览(33)
  • 力扣72. 编辑距离(动态规划)

    Problem: 72. 编辑距离 由于易得将字符串word1向word2转换和word2向word1转换是等效的,则我们假定统一为word1向word2转换!!! 1.确定状态:我们假设现在有下标i,j分别指向字符串word1和word2 尾部的字符 ,dp(i,j)表示当前的操作则: 1.1. dp(i- 1, j) + 1;表示 删除 ,直接把word1[i]的这个字

    2024年02月21日
    浏览(45)
  • 【Leetcode】移除后集合的最多元素数

    目录 💡题目描述 💡思路 💡总结 100150. 移除后集合的最多元素数 给你两个下标从 0 开始的整数数组 nums1 和 nums2 ,它们的长度都是偶数 n 。 你必须从 nums1 中移除 n / 2 个元素,同时从 nums2 中也移除 n / 2 个元素。移除之后,你将 nums1 和 nums2 中剩下的元素插入到集合 s 中。

    2024年01月24日
    浏览(30)
  • leetcode 2114. 句子中的最多单词数

    题目: 一个 句子 由一些 单词 以及它们之间的单个空格组成,句子的开头和结尾不会有多余空格。 给你一个字符串数组 sentences ,其中 sentences[i] 表示单个 句子 。 请你返回单个句子里 单词的最多数目 。 解题方法: 1.遍历列表,获取每个值,将值(字符串)用split转换成列

    2024年02月02日
    浏览(40)
  • 力扣题解(1030. 距离顺序排列矩阵单元格),带注释

    链接:点我 注意 :多看几遍题目,开始没看懂…相当于计算矩阵网格里面的点(不要计算边界) 我开了题解才明白题的意思 orz…

    2024年02月11日
    浏览(34)
  • LeetCode1578. 使绳子变成彩色的最短时间

    拆除成本 = 全部拆除 - 最大的不拆除 在统计成本的同时,维持一个成本的最大值

    2024年02月11日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包