leetcode 32最长有效括号 34在排序数组中查找元素的第一个和最后一个位置

32. 最长有效括号
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
示例 3：
输入：s = ""
输出：0

题解：通过栈实现

enumerate函数用于将一个可迭代的对象组合为一个索引序列，
同时列出数据和数据下标。在这个例子中，i是索引，j是s中的元素。

python">class Solution:
    def longestValidParentheses(self, s):
        stack = [-1]
        res = 0
        for i,j in enumerate(s):
          """
          enumerate函数用于将一个可迭代的对象组合为一个索引序列，
          同时列出数据和数据下标。在这个例子中，i是索引，j是s中的元素。
          """
            if j == "(":
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    stack.append(i)
                else:
                    res = max(res,i - stack[-1])
        return res

34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。
请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]

题解：可以直接使用二分查找函数 bisect_left, bisect_right 很快解出，这俩个函数具体使用，

参见博客http://t.csdnimg.cn/0H7jg

python">class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        from bisect import bisect_left, bisect_right
        if len(nums)==0:
            return [-1,-1]
        res = [-1,-1]
        left = bisect_left(nums,target)
        if left<len(nums) and nums[left]==target:
            res[0] = left
            res[1] = bisect_right(nums,target)-1
        return res

补充二分查找手搓代码，与之前总结的双指针解法十分类似，望读者进行区分掌握

python">l, r = 0, len(nums) - 1
while l <= r:
    mid = (l + r) // 2 # // 表示只要整数
    if nums[mid] == target:
        return mid
    elif nums[mid] < target:
        l = mid + 1
    else:
        r = mid - 1