LeetCode两个数组的交集-跳跃游戏- 最长有效括号

两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2]
示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[9,4] 解释：[4,9] 也是可通过的

class Solution:def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:d=[]for i in range(len(nums1)):for j in range(len(nums2)):if nums1[i]==nums2[j]:if nums1[i] not in d:d.append(nums1[i])else:continuereturn d

55. 跳跃游戏

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3> 步到达最后一个下标。

class Solution:def canJump(self, nums: List[int]) -> bool:max_i = 0       #初始化当前能到达最远的位置for i, jump in enumerate(nums):   #i为当前位置，jump是当前位置的跳数if max_i>=i and i+jump>max_i:  #如果当前位置能到达，并且当前位置+跳数>最远位置max_i = i+jump  #更新最远能到达位置return max_i>=i

32. 最长有效括号

给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度

示例 1：

输入：s = “(()” 输出：2 解释：最长有效括号子串是 “()”

对于遇到的每个 ‘(’ ，我们将它的下标放入栈中
对于遇到的每个 ‘)’ ，我们先弹出栈顶元素表示匹配了当前右括号：
如果栈为空，说明当前的右括号为没有被匹配的zuo括号，我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」
如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」

class Solution:def longestValidParentheses(self, s: str) -> int:d=[-1]maxx=0for i in range(len(s)):# d.append(s[i])if s[i]=="(":d.append(i)else:d.pop()if len(d)==0:d.append(i)else:maxx=max(maxx,i-d[-1])return maxx

20. 有效的括号

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = “()” 输出：true
示例 2：

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

输入：s = “(]” 输出：false

class Solution:def isValid(self, s: str) -> bool:re=Falsedd={'(':')','[':']','?':'?','{':'}'}d=['?']for i in s:if i in dd:d.append(i)elif dd[d.pop()]!=i:re=Falsebreakelse:re=Trueif len(d)//2==1 :re=False#最后堆栈长度为奇数，没有对应括号return re