【算法】算法题-20231211

在这里插入图片描述

这里写目录标题

一、387. 字符串中的第一个唯一字符
二、1189. “气球” 的最大数量
三、1221. 分割平衡字符串

一、387. 字符串中的第一个唯一字符

简单

给定一个字符串 s ，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1 。

示例 1：
输入: s = “leetcode”
输出: 0

示例 2:
输入: s = “loveleetcode”
输出: 2

示例 3:
输入: s = “aabb”
输出: -1

def test(s):
    top=[]
    dic={}
    for i in s:
        if i not in dic:
            dic[i]=1
            top.append(i)
        else:
            dic[i]+=1
            if i in top:
                top.remove(i)
    if len(top)==0:
        return -1
    else:
        return s.index(top[0])

s="leetcode"
print(test(s))

二、1189. “气球” 的最大数量

提示
简单
给你一个字符串 text，你需要使用 text 中的字母来拼凑尽可能多的单词 “balloon”（气球）。
字符串 text 中的每个字母最多只能被使用一次。请你返回最多可以拼凑出多少个单词 “balloon”。
在这里插入图片描述

def fn1(text, balloon):
    cnt = Counter(text)
    target = Counter(balloon)
    return min(cnt[k] // target[k] for k in target)


text = "nlaebolko"
balloon = "balloon"
print(fn1(text, balloon))

三、1221. 分割平衡字符串

提示
简单

平衡字符串中，‘L’ 和 ‘R’ 字符的数量是相同的。
给你一个平衡字符串 s，请你将它分割成尽可能多的子字符串，并满足：
每个子字符串都是平衡字符串。
返回可以通过分割得到的平衡字符串的最大数量。

示例 1：
输入：s = “RLRRLLRLRL”
输出：4
解释：s 可以分割为 “RL”、“RRLL”、“RL”、“RL” ，每个子字符串中都包含相同数量的 ‘L’ 和 ‘R’ 。

示例 2：
输入：s = “RLRRRLLRLL”
输出：2
解释：s 可以分割为 “RL”、“RRRLLRLL”，每个子字符串中都包含相同数量的 ‘L’ 和 ‘R’ 。
注意，s 无法分割为 “RL”、“RR”、“RL”、“LR”、“LL” 因为第 2 个和第 5 个子字符串不是平衡字符串。

示例 3：
输入：s = “LLLLRRRR”
输出：1
解释：s 只能保持原样 “LLLLRRRR” 。

无脑走栈的操作，思路：
循环字符串s
当栈为空或者栈顶元素等于当前元素时，入栈
否则出栈
每次循环结束如果栈内为空表示找到了一个符合条件，结果+1
最终返回结果ret即可

def Solution(s):
    ret=0
    stack=[]
    for i in s:
        if not stack or stack[-1]==i:
            stack.append(i)
        else:
            stack.pop()
        if not stack:
            ret+=1
    return ret

s = "RLRRRLLRLL"
print(Solution(s))