【数据结构与算法】之字符串系列-20240118

发布时间:2024年01月19日

在这里插入图片描述


一、13. 罗马数字转整数

简单
在这里插入图片描述
示例 1:

输入: s = “III”
输出: 3
示例 2:

输入: s = “IV”
输出: 4
示例 3:

输入: s = “IX”
输出: 9
示例 4:

输入: s = “LVIII”
输出: 58
解释: L = 50, V= 5, III = 3.
示例 5:

输入: s = “MCMXCIV”
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

from collections import Counter, defaultdict


class Solution:
    def romanToInt(self, s):
        dic = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
        i = 0
        res = 0  # -1         4
        while i < len(s) - 1:
            if dic[s[i]] < dic[s[i + 1]]:
                res = res - dic[s[i]]  # -1
            else:
                res = res + dic[s[i]]  # 0+ 50 =50+5+1+1+1
            i += 1

        return res + dic[s[-1]]  #


s = Solution()
strs = "LVIII"
print(s.romanToInt(strs))

二、14. 最长公共前缀

简单
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 “”。

示例 1:
输入:strs = [“flower”,“flow”,“flight”]
输出:“fl”
示例 2:
输入:strs = [“dog”,“racecar”,“car”]
输出:“”
解释:输入不存在公共前缀。

class Solution:
    def func(self, strs):
        n = ''
        s = list(zip(*strs))
        for item in s:
            if len(set(item)) == 1:
                n += item[0]
        return n


ss = Solution()
strs = ["flower", "flow", "flight"]
print(ss.func(strs))

三、20. 有效的括号

简单
给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1:
输入:s = “()”
输出:true

示例 2:
输入:s = “()[]{}”
输出:true

示例 3:
输入:s = “(]”
输出:false

class Solution:
    def func1(self, strs):
        d = {"(": ")", "{": "}", "[": "]"}
        t = ['?']
        for i in strs:
            if i in d:
                t.append(i)
            elif d[t.pop()] != i:
                return False
        return len(t) == 1


ss = Solution()
s = "()"
print(ss.func1(s))

四、28. 找出字符串中第一个匹配项的下标

简单
给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回 -1 。

示例 1:
输入:haystack = “sadbutsad”, needle = “sad”
输出:0
解释:“sad” 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ,所以返回 0 。

示例 2:
输入:haystack = “leetcode”, needle = “leeto”
输出:-1
解释:“leeto” 没有在 “leetcode” 中出现,所以返回 -1 。

class Solution:
    def func(self, haystack, needle):
        s = haystack.split(needle)
        if len(s) == 1:
            return -1
        else:
            return len(s[0])


ss = Solution()
haystack = "leetcode"
needle = "leeto"
print(ss.func(haystack, needle))

五、58. 最后一个单词的长度

简单
给你一个字符串 s,由若干单词组成,单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。
单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

示例 1:
输入:s = “Hello World”
输出:5
解释:最后一个单词是“World”,长度为5。
示例 2:
输入:s = " fly me to the moon "
输出:4
解释:最后一个单词是“moon”,长度为4。
示例 3:
输入:s = “luffy is still joyboy”
输出:6
解释:最后一个单词是长度为6的“joyboy”。

s = "Hello World"
print(len(s.split()[-1]))

特别注意:s.split()默认按照空格进行拆分


在这里插入图片描述

文章来源:https://blog.csdn.net/YZL40514131/article/details/135686740
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。