Leetcode (14) - Hot 100 热门 100 题
# 32 最长有效括号
# 问题
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
2
3
4
5
6
7
8
9
# 思路
本题的几个思路详见该题的leetcode官方题解 (opens new window)，还有示例动图说明。
暴力法 。就是从每一个位置开始，向后检查，找到从该位置出发的最长有效括号，更新max长度。复杂度在 n^2 级别。判断是否有效，通过栈的方式来判断。由于括号的成对出现，所以长度一定是偶数的，固定起始位置i之后，子串的结尾位置j以2为步长扩展。另外就是只有 （的位置可以是有效起始位置i，所以无需判断）为起始位置的情况。
动态规划法。定义dp数组，其中下标i的元素，表示以下标i处的字符结尾的最长有效括号的长度。显然，如果字符是 （的话，长度为0，只有）才能作为有效结尾。
定义状态转移：
（1）如果i位置的字符是），且i-1位置是 （，则说明刚好凑了一对儿，所以dp[i] = dp[i-2] + 2.
(2)如果i位置的是），且 i-1位置的是），且i-dp[i-1]-1位置是左括号，则说明是 yyyy((xxx))的情况，那么此时有 dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2。dp[i-1]是 (xxx)的长度，dp[i-dp[i-1]-2] 是 yyyy部分的长度，+2则是因为多了i位置的这对括号。
有了上面这个难想到的状态转移，就可以从前往后用dp来做了。dp的复杂度是n。
栈。这是一种巧妙的解法，使用一个栈来处理。
遇到左括号，就把它的下标加入栈中。
遇到右括号，则说明完成一次配对，则从栈中弹出栈顶元素，并将当前元素下标和弹出后余下的栈顶元素的下标做差，得到当前有效括号字符串的长度。以此计算，记录最大长度。
这种方法的复杂度是n，而且感觉比dp容易理解。但是也需要记录一点细节，比如说一开始要把-1入栈，因为按照上面的逻辑，如果一开始就是 （）这种情况的话，当遇到）时，执行 1 - （-1）= 2 得到长度，如果不把-1预先入栈的话这种情况就会出错。另外是当遇到右括号，且栈弹出了之后栈空了，或者栈已经空了，要把这个右括号的下标入栈，相当于标记下这个位置之前的已经fail了，之后不再考虑。
扫描两遍。思路是利用两个计数器left和right，先从左到右遍历字符串，遇到左括号，增加left计数，遇到右括号，增加right计数。如果left和right相等了，则right-left得到当前一个有效串的长度，并更新最大长度。如果right比left大了，则说明目前串作废，将left和right同时归0，继续往后扫。
但这是不够的，还需要从右到左再扫一遍，以便于处理()((())这样的情况，如果只从左到右的话，最长长度为2，但是从右到左也来一遍的话，最长长度为4。
# 代码
按栈的方法来做。代码竟是如此简洁……
class Solution:
def longestValidParentheses(self, s: str) -> int:
max_ans = 0
stack = []
stack.append(-1)
for i in range(0, len(s)):
if s[i] == '(':
stack.append(i)
else:
stack.pop(-1)
if not stack:
stack.append(i)
else:
max_ans = max(max_ans, i - stack[-1])
return max_ans
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 33 搜索旋转排序数组
# 问题
假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。 你的算法时间复杂度必须是 O(log n) 级别。
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
2
3
# 思路
看到logn就想到要二分查找。可以首先找到旋转的两部分的分界点，也就是数组中最小的元素，然后判断要找的元素在哪一半，在这一半中继续进行二分查找。
如果加上稍微复杂点的分析，可以直接进行查找，无需分两步，只不过判断取左右两边的判断条件要调整。不妨来想一下，何时我们需要取左半部分。
（1）如果是 nums[0] <= target <= nums[mid]，说明0-mid是递增的，不含转折点，且target在这块区间中，所以应该取左半部分。
（2）如果是 target <= nums[mid] < nums[0]，说明0-mid这块当中包含了转折点，而target位于转折点到mid区间内，此时仍然应该取左半部分。
（3）如果是nums[mid] < nums[0] <= target，说明0-mid这块当中包含转折点，且target位于0-转折点区间内，这块仍然应该取左半部分。
以上就是应当取左半部分的三种情况，其他情况下，我们取右半部分。
# 代码
class Solution:
def search(self, nums: List[int], target: int) -> int:
return self.binary(nums, 0, len(nums)-1, target)
def binary(self, nums, l, r, target):
if l > r:
return -1
mid = (l + r) // 2
if nums[mid] == target:
return mid
if (nums[l] <= target <= nums[mid]) or (target <= nums[mid] < nums[0]) or (nums[mid] < nums[l] <= target):
return self.binary(nums, l, mid-1, target)
return self.binary(nums, mid+1, r, target)
2
3
4
5
6
7
8
9
10
11
12
13
14
# 34 排序数组中查找元素的第一个和最后一个位置
# 问题
升序的数组nums和目标值target，找出目标值在数组中的开始和结束位置下标，要求复杂度在 logn级别。如果不存在目标值，返回[-1, -1]。
# 思路
通过二分查找的方法来找左右下标，这个有点类似33题，应用二分查找的思路，但需要想清楚取左右两半的具体条件是啥。
下面代码中的写法虽然简洁，但需要注意一下一些细节的处理。
假如要找左边界，此时is left为True，需要注意 r是右边界的后一个位置。先看mid，如果target比mid位置的值小，则向左，如果相等，此时也需要向左（假如当前mid是左边界了的话，后续left会一直向右，直到l=r，return的还是mid值，所以这样是ok的），如果大，则向右。
假如要找右边界，如果target比mid小，则向左，如果相等或者大，则向右。假如mid已经是右边界了的话，由于l=mid+1，最终会return在边界+1位置，所以下面right_idx又做了-1。
# 代码
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
left_idx = self.find(nums, target, True)
if left_idx == len(nums) or nums[left_idx] != target:
return [-1, -1]
right_idx = self.find(nums, target, False) - 1 # 注意这里减1了
return [left_idx, right_idx]
def find(self, nums, target, is_left):
l, r = 0, len(nums)
while l < r:
mid = (l + r) // 2
if target < nums[mid] or (target == nums[mid] and is_left):
r = mid
else:
l = mid + 1
return l
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 39 组合总和
# 问题
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
示例 1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
示例 2:
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16