lettcode 题目

• Valid Parentheses
  给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串，判断字符串是否有效。
  有效字符串需满足：
  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合

def isValid(s):
    """
    :type s: str
    :rtype: bool
    """
    length = len(s)
    if length == 0:
        return True
    if length%2 != 0:
        return False
    stack = []
    dic = {"]":"[", "}":"{", ")":"("}
    for char in s:
        if char in dic.values():
            stack.append(char)
        elif char in dic.keys():
            if stack == [] or dic[char] != stack.pop():
                return False
        else:
            return False
    return stack == []

在评论区看到一种比较。。。 的做法，利用字符串的特性，核心代码如下：

while '()' in s or '{}' in s or '[]' in s:
            s = s.replace('{}','').replace('()','').replace('[]','')
return not bool(s)

• Generate Parentheses
  给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
  采用回溯法,left 表示 左括号的个数，right 表示 右括号的个数

def generateParenthesis(n):
    """
    :type n: int
    :rtype: List[str]
    """
    ans = []
    def backtrace(S='', left=0, right=0):
        if len(S) == 2*n:
            ans.append(S)
            return
        if left < n:
            backtrace(S+'(', left+1, right)
        if right < left:
            backtrace(S+')', left, right+1)
    backtrace()
    return ans

• Letter Combinations of a Phone Number
  给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
  给出数字到字母的映射与电话按键相同，1 和 0 不算
  itertools 模块中有一个 product 函数可以做最后的组合，顺便提一句，这个模块有很多实用的函数

import itertools
def letterCombinations(digits):
    """
    :type digits: str
    :rtype: List[str]
    """
    import itertools
    mapping = {"2":"abc", "3":"def", "4":"ghi", "5":"jkl", "6":"mno",
               "7":"pqrs", "8":"tuv", "9":"wxyz"}
    s = [mapping[d] for d in digits if d in mapping]
    return [] if digits == "" else [ "".join(x) for x in itertools.product(*s)]

• Remove Duplicates from Sorted Array
  给定一个排序数组，你需要在原地]除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
  不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

def removeDuplicates(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    n = len(nums)
    if n == 0:
        return 0
    i = 0    # 前一个数字
    for j in range(n):
        if nums[j] != nums[i]:
            i+=1 
            nums[i] = nums[j]
    return i+1

• Remove Element
  给定一个数组 *nums *和一个值 val，你需要原地移除所有数值等于 *val *的元素，返回移除后数组的新长度。
  不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
  元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

def removeElement(nums, val):
    """
    :type nums: List[int]
    :rtype: int
    """
    n = len(nums)
    i = 0    # 前一个数字
    for j in range(n):
        if nums[j] != val:
            nums[i] = nums[j]
            i += 1
    return i

• Implement strStr()
  实现 strStr() 函数。
  这个函数与 Python 中字符串的 find 函数相同，所以可以直接使用 a.find(b)
  给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。地下这种方法也很有趣，利用了切分原理

if haystack == "" and needle == "":
            return 0
        if needle == "":
            return 0
        if haystack == "" or needle == "" or len(haystack.split(needle)) == 1:
            return -1
        return len(haystack.split(needle)[0])

• Next Permutation
  实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
  如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
  必须原地修改，只允许使用额外常数空间。
  以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
  1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

def nextPermutation(nums):
    """
    :type nums: List[int]
    :rtype: void Do not return anything, modify nums in-place instead.
    """
    if not nums: return nums
    l = len(nums)
    i, j = l-2, l-1
    while i>=0 and nums[i] >= nums[i+1]:
        i -= 1
    while j >i and nums[j] <= nums[i]:
        j -= 1
    nums[i], nums[j] = nums[j], nums[i]
    nums[i+1:] = sorted(nums[i+1:])

放一张动画图片更好理解

来自 lettcode

• Search in Rotated Sorted Array
  假设按照升序排序的数组在预先未知的某个点上进行了旋转。
  ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
  搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
  你可以假设数组中不存在重复的元素。
  你的算法时间复杂度必须是 O(log n) 级别。

# 利用二分查找 注意链式比较
def search(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: int
    """
    lo, hi = 0, len(nums)-1
    while lo < hi:
        mid = (lo+hi) / 2
        if nums[mid] == target:
            return mid
        if nums[lo] < nums[mid]:
            if nums[lo] <= target <= nums[mid]:
                hi = mid - 1
            else:
                lo = mid +1
        else:
            if nums[mid] <= target <= nums[hi]:
                low = mid+1
            else:
                high = mid - 1
    return -1

• Search for a Range
  给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
  你的算法时间复杂度必须是 O(log n) 级别。
  如果数组中不存在目标值，返回 [-1, -1]。

# 它是 O(n) 级别的
def searchRange(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    # 从左边开始，先找出第一个下标
    for i in range(len(nums)):
        if nums[i] == target:
            left_idx = i
            break
    else:
        return [-1, -1]
    # 从右边开始找出 第一个下标
    for j in range(len(nums)-1, -1, -1):
        if nums[j] == target:
            right_idx = j
            break
    return [left_idx, right_idx]

可以使用 bisect 模块

import bisect
def search_range(nums, target):
    lo = bisect.bisect_left(nums, target)
    return [lo, bisect.bisect(nums, target)-1] if target in nums[lo:lo+1] else [-1, -1]

• Search Insert Position
  给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

def searchInsert(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: int
    """
    import bisect
    a = bisect.bisect(nums, target)
    if nums[a-1] == target:
        return a-1
    else:
        return a
    # 一句代码
    # return len([x for x in nums if x<target])