建网站多少钱合适,百元建站,广西北海网站建设,做笑话网站赚钱吗1、在leetcode分类刷题#xff1a;基于数组的双指针#xff08;一、基于元素移除的O(1)类型#xff09;题目中#xff0c;采用双指针之快慢指针的算法来解决。 2、字符串相邻元素的删除问题#xff0c;用栈来进行管理#xff0c;会非常有效#xff1b;这种题型排在后面的… 1、在leetcode分类刷题基于数组的双指针一、基于元素移除的O(1)类型题目中采用双指针之快慢指针的算法来解决。 2、字符串相邻元素的删除问题用栈来进行管理会非常有效这种题型排在后面的字母会先删除 与 栈先进后出 的思想一致同时也要关注相邻元素的细节是个隐含的连续子序列否则即使思想上与栈一致位置上不相邻栈是没法处理的 3、如果考察最长的相邻重复子串的长度问题按照索引而非元素入栈的方式来写比如题目“32. 最长有效括号”这类题目判断入栈的情况不能太多了否则代码太复杂了 4、括号匹配、有效的字符串类问题也属于字符串相邻元素删除的一种是一种隐含式的相邻元素删除。该类题目处理方式与本章总结的题型基本一致但也有一点细节区别入栈的情况里没有栈为空这种只需要对元素进行不断遍历然后判断入栈或出栈或return等这种题目也有更简单直观的思路遍历元素不加判断地全部入栈不断对后入栈的栈顶连续元素进行匹配性判断进行出栈或者直接赋值为空的操作 844. 比较含退格的字符串 是一道基本的字符串相邻元素删除题目完美符合排在后面的字母会先删除 与 栈先进后出 的思想一致 from typing import List
844. 比较含退格的字符串
给定 s 和 t 两个字符串当它们分别被输入到空白的文本编辑器后如果两者相等返回 true 。# 代表退格字符。
注意如果对空文本输入退格字符文本继续为空。
示例 1:输入s ab#c, t ad#c输出true解释s 和 t 都会变成 ac。
题眼退格字符只会删除位于它之前的字符
思路从后向前比较
class Solution:# 推荐掌握——O(N)空间复杂度的栈管理字符串元素删除问题def backspaceCompare(self, s: str, t: str) - bool:# 第一步得到删除后的ssStack []for ch in s:if ch ! #:sStack.append(ch)elif len(sStack) 0:sStack.pop()sNew .join(sStack)# 第二步得到删除后的ttStack []for ch in t:if ch ! #:tStack.append(ch)elif len(tStack) 0:tStack.pop()tNew .join(tStack)# 第三步比较返回后的两个新字符串return sNew tNew# 不推荐掌握——O(1)空间复杂度的双指针解法需要额外再使用标志 标记当前待删除的字符的数量def backspaceCompare2(self, s: str, t: str) - bool:pointer1, pointer2 len(s) - 1, len(t) - 1 # 标记字符串末尾的位置delete1, delete2 0, 0 # 当前待删除的字符的数量表示从后向前遇到的#数量while pointer1 0 or pointer2 0:# 寻找s中用于比较的当前有效字符while pointer1 0:if s[pointer1] #: # 遇到#delete1 1pointer1 - 1elif delete1 0: # 非#时判断该字符是否要被删除delete1 - 1pointer1 - 1else:break# 寻找t中用于比较的当前有效字符while pointer2 0:if t[pointer2] #: # 遇到#delete2 1pointer2 - 1elif delete2 0: # 非#时判断该字符是否要被删除delete2 - 1pointer2 - 1else:break# 比较当前有效字符if pointer1 0 and pointer2 0:if s[pointer1] ! t[pointer2]:return Falseelse:pointer1 - 1pointer2 - 1elif pointer1 0 and pointer2 0:return Trueelse:return Falsereturn Trueif __name__ __main__:obj Solution()while True:try:in_line input().strip().split()s in_line[1].split(,)[0].strip()[1: -1]t in_line[2].strip()[1: -1]print(obj.backspaceCompare(s, t))except EOFError:break1047. 删除字符串中的所有相邻重复项 1、与“844. 比较含退格的字符串”的处理方式基本一致 2、该类型题目还可以用等价地按照索引而非元素入栈的方式来写这是在考察最长的相邻重复子串的长度问题的解题模板比如接下来的一道题目“32. 最长有效括号” 1047. 删除字符串中的所有相邻重复项
给出由小写字母组成的字符串S重复项删除操作会选择两个相邻且相同的字母并删除它们。
在 S 上反复执行重复项删除操作直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例 1:
输入abbaca
输出ca
解释
例如在 abbaca 中我们可以删除 bb 由于两字母相邻且相同这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 aaca
其中又只有 aa 可以执行重复项删除操作所以最后的字符串为 ca。
题眼排在后面的字母会先删除 与 栈先进后出 的思想一致
思路
class Solution:def removeDuplicates(self, s: str) - str:stk []for ch in s:if len(stk) 0 or stk[-1] ! ch: # 入栈情况stk.append(ch)else: # 出栈情况stk.pop()return .join(stk)# # 按照索引入栈的方式写# stk []# for i in range(len(s)):# if len(stk) 0 or s[stk[-1]] ! s[i]: # 入栈情况# stk.append(i)# else: # 出栈情况# stk.pop()# result # for i in stk:# result s[i]# return resultif __name__ __main__:obj Solution()while True:try:s input().strip()[1: -1]print(obj.removeDuplicates(s))except EOFError:break32. 最长有效括号 该题按照索引而非元素入栈的方式来写将遍历元素是不匹配时把索引全部入栈匹配时进行出栈并计算此时的有效括号的长度更新答案 32. 最长有效括号
给你一个只包含 ( 和 ) 的字符串找出最长有效格式正确且连续括号子串的长度。
示例 1:输入s )()())输出4解释最长有效括号子串是 ()()
题眼括号匹配是使用栈解决的经典问题 —— 后遇到的左括号要先闭合
思路1、这里从字符串里选择 最长的有效括号子串2、因为是求长度所以需要有标志记录 起始位置正好把 压入栈的数据 设置为 不匹配的元素的索引3、遇到匹配出栈时就可以用 遍历元素索引 - 栈顶元素索引 当前有效括号序列长度
class Solution:def longestValidParentheses(self, s: str) - int:# 情况1、字符串为空if not s:return 0# 情况2、用栈判断stk []result 0for i in range(len(s)):# 入栈的情况栈为空、当前元素为、栈顶元素为——不匹配才需要入栈if len(stk) 0 or s[i] ( or s[stk[-1]] ):stk.append(i) # 压入栈的数据 设置为 不匹配的元素的索引else: # 匹配出栈stk.pop()if len(stk) 0: # 此时依然要判断栈是否为空因为可能存在上一步出栈为空了result max(result, i - stk[-1])else:result max(result, i 1) # 栈为空相当于上一个不匹配的位置是-1return resultif __name__ __main__:obj Solution()while True:try:s input().strip().split()[1].strip()[1: -1]print(obj.longestValidParentheses(s))except EOFError:break20. 有效的括号 1、该说不说这题首先先要把题意弄明白 2、该题有两种思路思路1、与本章总结题型的大思路一致充分利用栈的思想在遍历字符串时遇到左括号按照对应的右括号形式添加处理技巧遇到右括号时判断匹配情况思路2、将栈当作一个特殊格式的存储空间将元素全部遍历入栈并总是在栈中去掉成对的括号——更简单直观 20. 有效的括号
给定一个只包括 (){}[]的字符串 s 判断字符串是否有效。
有效字符串需满足1、左括号必须用相同类型的右括号闭合。2、左括号必须以正确的顺序闭合。————这个应该是栈的特点3、每个右括号都有一个对应的相同类型的左括号。
示例 1:输入s ()输出true
题眼括号匹配是使用栈解决的经典问题 —— 后遇到的左括号要先闭合 与 栈先进后出 的思想一致
思路1、充分利用栈的思想在遍历字符串时遇到左括号按照对应的右括号形式添加处理技巧遇到右括号时判断匹配情况
思路2、将栈当作一个特殊格式的存储空间将元素全部遍历入栈并总是在栈中去掉成对的括号——更简单直观
class Solution:def isValid(self, s: str) - bool:# 思路1、充分利用栈的思想在遍历字符串时遇到左括号按照对应的右括号形式添加遇到右括号时判断匹配情况# # 情况1、s长度为奇数# if len(s) % 2 1:# return False# # 情况2、s长度为偶数# stk []# for ch in s:# if ch (:# stk.append())# elif ch [:# stk.append(])# elif ch {:# stk.append(})# else: # 说明到了右括号了# if len(stk) 0: # 右括号多了# return False# elif ch ! stk[-1]: # 左右括号不匹配# return False# else:# stk.pop() # 元素正常出栈# if len(stk) 0:# return False # 左括号多了# return True# 思路2、将栈当作一个特殊格式的存储空间将元素全部遍历入栈并总是在栈中去掉成对的括号——更简单直观stk []for ch in s:stk.append(ch)if len(stk) 2:target .join(stk[-2:])if target () or target [] or target {}:stk[-2:] []if len(stk) 0:return Truereturn Falseif __name__ __main__:obj Solution()while True:try:s input().strip().split()[1].strip()[1: -1]print(obj.isValid(s))except EOFError:break1003. 检查替换后的词是否有效 1、这题把题意弄明白也很重要它和“20. 有效的括号”是一个意思 2、该题也有两种思路思路1、类似“20. 有效的括号”的思路一遍历每个元素分情况讨论入栈、出栈情况思路2、类似“20. 有效的括号”的思路而将栈当作一个特殊格式的存储空间将元素全部遍历入栈并总是在栈中去掉成对的括号——更简单直观 1003. 检查替换后的词是否有效
给你一个字符串 s 请你判断它是否 有效 。
字符串 s 有效 需要满足假设开始有一个空字符串 t 你可以执行 任意次 下述操作将 t 转换为 s
将字符串 abc 插入到 t 中的任意位置。形式上t 变为 tleft abc tright其中 t tleft tright 。注意tleft 和 tright 可能为 空 。
如果字符串 s 有效则返回 true否则返回 false。
示例 1:输入s aabcbc输出true解释 - abc - aabcbc因此aabcbc 有效。
题眼这道题读懂题目很重要它和“20. 有效的括号”是一个意思
思路1、类似“20. 有效的括号”的思路遍历每个元素分情况讨论入栈、出栈情况
思路2、将栈当作一个特殊格式的存储空间将元素全部遍历入栈并总是在栈中去掉目标子串——更简单直观
class Solution:def isValid(self, s: str) - bool:# 思路1、类似“20. 有效的括号”的思路# stk []# for ch in s:# if ch a:# stk.append(ch)# elif ch b:# if len(stk) 0:# return False# elif stk[-1] a:# stk.append(ch)# else:# return False# elif ch c:# if len(stk) 0:# return False# elif stk[-1] b:# stk.pop()# stk.pop()# else:# return False# if len(stk) 0:# return True# return False# 思路2、将栈当作一个特殊格式的存储空间将元素全部遍历入栈并总是在栈中去掉子串abc——更简单直观stk []for ch in s:stk.append(ch)if len(stk) 3:target .join(stk[-3:])if target abc:stk[-3:] []if len(stk) 0:return Truereturn Falseif __name__ __main__:obj Solution()while True:try:s input().strip().split()[1].strip()[1: -1]print(obj.isValid(s))except EOFError:break1910. 删除一个字符串中所有出现的给定子字符串 1、这题是上一题1003. 检查替换后的词是否有效的一般情况 2、该题不适合1003. 检查替换后的词是否有效的思路一了因为没法加判断条件对入栈出栈分情况处理了只能用思路二将栈当作一个特殊格式的存储空间将元素全部遍历入栈并总是在栈中去掉成对的括号——更简单直观 3、官方题解还有一种字符串匹配的思路感觉不如栈的这种方式直观 1910. 删除一个字符串中所有出现的给定子字符串
给你两个字符串 s 和 part 请你对 s 反复执行以下操作直到 所有 子字符串 part 都被删除
找到 s 中 最左边 的子字符串 part 并将它从 s 中删除。
请你返回从 s 中删除所有 part 子字符串以后得到的剩余字符串。
一个 子字符串 是一个字符串中连续的字符序列。
示例 1:输入s daabcbaabcbc, part abc输出dab解释以下操作按顺序执行- s daabcbaabcbc 删除下标从 2 开始的 abc 得到 s dabaabcbc 。- s dabaabcbc 删除下标从 4 开始的 abc 得到 s dababc 。- s dababc 删除下标从 3 开始的 abc 得到 s dab 。此时 s 中不再含有子字符串 abc 。
题眼1003. 检查替换后的词是否有效的一般情况
思路、将栈当作一个特殊格式的存储空间将元素全部遍历入栈并总是在栈中去掉目标子串——更简单直观
class Solution:def removeOccurrences(self, s: str, part: str) - str:# 情况1、s比part长度短if len(s) len(part):return s# 情况2、用栈处理stk []for ch in s:stk.append(ch)if len(stk) len(part):target .join(stk[-len(part): ])if target part:stk[-len(part): ] []return .join(stk)if __name__ __main__:obj Solution()while True:try:in_line input().strip().split()s in_line[1].strip().split(,)[0][1: -1]part in_line[2].strip()[1: -1]print(obj.removeOccurrences(s, part))except EOFError:break
