【算法】算法题-20231222

发布时间:2023年12月22日

在这里插入图片描述

一、1002. 查找共用字符

给你一个字符串数组 words ,请你找出所有在 words 的每个字符串中都出现的共用字符( 包括重复字符),并以数组形式返回。你可以按 任意顺序 返回答案。

示例 1:
输入:words = [“bella”,“label”,“roller”]
输出:[“e”,“l”,“l”]
示例 2:
输入:words = [“cool”,“lock”,“cook”]
输出:[“c”,“o”]

class Solution1:

    def common(self,words):
        res=[]
        if not words:
            return res

        key=set(words[0])   #{b,e,l,a}
        for k in key:
            minimum=min(a.count(k) for a in words)
            res+=minimum*k
        return res

words = ["bella","label","roller"]
s1=Solution1()
res=s1.common(words)
print(res)

二、1047. 删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 S,重复项删除操作会选择两个相邻且相同的字母,并删除它们。
在 S 上反复执行重复项删除操作,直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例:
输入:“abbaca”
输出:“ca”
解释:
例如,在 “abbaca” 中,我们可以删除 “bb” 由于两字母相邻且相同,这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”,其中又只有 “aa” 可以执行重复项删除操作,所以最后的字符串为 “ca”。

解题思路
根据题意的充分理解,我们可分析如下:
多组相邻重复项,我们无论先删除哪一项,都不会影响最终结果。
删除当前项是需要拿上一项出来对比的,所以我们需要用临时栈存放之前的内容。
当前项和栈顶一致,弹出栈顶抵消即可。若不一致,压入栈留存,供后续使用。

def test6(s):
    li=[]
    for i in s:
        if li and li[-1]==i:
            li.pop()
        else:
            li.append(i)

    return "".join(li)

三、面试题 01.04. 回文排列

给定一个字符串,编写一个函数判定其是否为某个回文串的排列之一。
回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。
回文串不一定是字典当中的单词。

示例1:

输入:“tactcoa”
输出:true(排列有"tacocat"、“atcocta”,等等)

思路:
利用Counter函数可以统计每个字符出现的次数。
如果单个字符的个数超过1,则不是回文串

class Solution:
    def canPermutePalindrome(self, s):
        d={}
        for i in s:
            if i not in d:
                d[i]=1
            else:
                d[i]+=1
        print(d)
        odd = 0
        for val in d.values():
            if val % 2 == 1:
                odd += 1
                if odd > 1:
                    return False
        return True


ss=Solution()
w="tactcoaq"
print(ss.canPermutePalindrome(w))

在这里插入图片描述

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