本篇文章根据labuladong的算法小抄介绍部分经典面试题，采用python3实现

快速选择算法

数组中的第K个最大元素，T215

题目：有无序数组nums和正整数k，请计算nums中第k个最大的元素。

⭐法1：二叉堆（优先队列）【建议】

时间O(NlogK)，空间O(K)

def findKthLargest(nums,k):
    pq = []
    for e in nums:
        heapq.heappush(pq,e)
        if len(pq) > k:
            heapq.heappop(pq)
    return heapq.heappop(pq)

法2：快速选择

先介绍一下快速排序：要对nums[lo…hi]排序，先找一个分界点p，通过交换元素使得nums[lo…p-1]都小于等于nums[p]，且nums[p+1…hi]都大于nums[p]，然后递归的在nums[lo…p-1]和nums[p+1…hi]中寻找新的分界点。

def sort(nums):
    #一般在这用洗牌算法将nums打乱，以保证较高的效率
    sort(nums,0,len(nums)-1)
    
def sort(nums,lo,hi):
    if lo >= hi:
        return
    #通过交换元素构建分界点索引p
    p = partition(nums,lo,hi)
    sort(nums,lo,p-1)
    sort(nums,p+1,hi)
    
def partition(nums,lo,hi):
    if lo == hi:
        return lo
    #将nums[lo]作为分界点
    pivot = nums[lo]
    i = lo + 1
    j = hi
    while True:
        while nums[i] < pivot:
            if i == hi:
                break
            i += 1 
        while nums[j] > pivot:
            if j == lo:
                break
            j -= 1 
        if i >= j:
            break
        #如果走到这里：nums[i] >= pivot, nums[j] <= pivot
        nums[i],nums[j] = nums[j],nums[i]
        i += 1
        j -= 1
    nums[j],nums[lo] = nums[lo],nums[j]
    return j

快速选择：

partition可以将nums[p]排到正确位置，那么nums[lo…p-1] < nums[p] < nums[p+1…hi]。那么如果p < len(nums) - k，说明要找的元素在nums[p+1…hi]中；如果p>len(nums) - k，说明要找的元素早nums[lo…p-1]中

def findKthLargest(nums,k):
    lo = 0
    hi = len(nums) - 1
    k = len(nums) - k #要找的元素索引，如果数组按升序排序
    while lo <= hi:
        p = partition(nums,lo,hi)
        if p == k:
            return nums[p]
        elif p < k:
            lo = p + 1
        else:
            hi = p - 1
    return -1

注意：

partition最好情况下每次p都在中间，那么遍历的元素总数就是N+N/2+N/4+N/8+…+1，求极限为2N，时间复杂度为O(N)。最坏情况下p一直都是lo+1或hi-1，那么遍历的元素总数就是N+(N-1)+(N-2)+…+1，时间复杂度为O(N^2)。

为了尽可能防止极端情况发生，需要在算法开始时堆nums进行随机打乱

def shuffle(nums):
    n = len(nums)
    for i in range(n):
        #从i到最后随机选一个元素
        r = random.randint(i,n-1)
        nums[i],nums[r] = nums[r],nums[i]

分治算法

归并排序

def sort(nums):
	def merge_sort(nums,l,r):
        if l == r:
            return
        mid = (l + r) // 2
        merge_sort(nums,l,mid)
        merge_sort(nums,mid+1,r)
        tmp = []
        i = l
        j = mid + 1
        while (i <= mid) or (j <= r):
            if (i > mid) or (j <= r and nums[j] < nums[i]):
                tmp.append(nums[j])
                j += 1
            else:
                tmp.append(nums[i])
                i += 1
        nums[l:r+1] = tmp
    merge_sort(nums,0,len(nums)-1)
    return nums

添加括号的所有方式，T241

题目：给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同结果，你需要给出所有可能的组合的结果。有效运算符号包括+,-,*。

def diffWaysToCompute(input):
    if expression.isdigit():
        return [int(expression)]
    res = []
    for i in range(len(input)):
        c = input[i]
        if (c == '-') or (c == '*') or (c =='+'):
            #分
            left = diffWaysToCompute(input[0:i]) #0..i-1
            right = diffWaysToCompute(input[i+1:]) #i+1..n-1
            #治
            for a in left:
                for b in right:
                    if c == '+':
                        res.append(a+b)
                    elif c == '-':
                        res.append(a-b)
                    elif c =='*':
                        res.append(a*b)
    return res

区间问题

区间问题的主要技巧：

1. 排序：常见的排序方法就是按照区间起点排序，或者先按照起点升序排序，再按照终点降序排序。
2. 画图。

删除被覆盖区间，T1288

题目：请你删除列表中被其他区间所覆盖的区间。只有当c<=a且b<=d才认为[a,b)被[c,d)覆盖。在完成所有删除操作后，返回列表中剩余区间的数目。

def removeCoveredIntervals(intvs):
    intvs.sort(key = lambda a : (a[0],-a[1]))
    left = intvs[0][0]
    right = intvs[0][1]
    res = 0
    for i in range(1,len(intvs)):
        intv = intvs[i]
        #被完全覆盖
        if intv[1] <= right:
            res += 1
        #部分重合
        elif (intv[0] <= left) and (intv[1] >= right):
            right = intv[1]
        #完全不相交
        elif intv[0] > left:
            left = intv[0]
            right = intv[1]
    return len(intvs) - res

区间合并，T56

题目：合并所有重叠的区间

def merge(intervals):
    if not intervals:
        return []
    intervals.sort(key = lambda a:(a[0],-a[1]))
    res = []
    res.append(intervals[0])
    for i in range(1,len(intervals)):
        cur = intervals[i]
        last = res[-1]
        if curr[0] <= last[1]:
            last[1] = max(last[1],curr[1])
        else:
            res.append(curr)
    return res

区间交集，T986

题目：返回两个区间列表的交集。每个区间列表都是不相交的，且已经排序。

def intervalIntersection(A,B):
    i = 0
    j = 0
    res = []
    while i < len(A) and j < len(B):
        a1,a2 = A[i][0],A[i][1]
        b1,b2 = A[j][0],A[j][1]
        #存在交集
        if b2 >= a1 and b1 <= a2:
            res.append([max(a1,b1),min(a2,b2)])
        if b2 < a2:
            j += 1
        else:
            i += 1
    return res

字符串乘法

字符串相乘，T43

def multiply(num1,num2):
    m = len(num1)
    n = len(num2)
    #结果最多有m+n位
    res = [0 for i in range(m+n)]
    for i in range(m-1,-1,-1):
        for j in range(n-1,-1,-1):
            #乘积
            mul = int(num1[i])*int(num2[j])
            #索引
            p1 = i + j
            p2 = i + j + 1
            #结果
            sum_ = mul + res[p2]
            res[p2] = sum_ % 10
            res[p1] += sum // 10
    #前缀可能有i个0
    res = [str(x) for x in res]
    res = "".join(res)
    return res

二分查找高效判定子序列

判断子序列，T392

如何判定字符串s是否是字符串t的子序列

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        i = 0
        j = 0
        if len(s) == 0:
            return True
        while i < len(s) and j < len(t):
            if s[i] == t[j]:
                i += 1
                if i == len(s):
                    return True
            j += 1
        return False

时间复杂度O(N)

判断子序列列表

题目：给定一系列字符串s1,s2…和字符串t，判断每个s是否是t的子序列。

用二分查找可以提高效率，这里以单个字符串s为例

def isSubsequence(s,t):
    m = len(s)
    n = len(t)
    index = [[] for i in range(128)]
	#index储存，字符：在t中出现的索引
    for i in range(n):
        c = t[i]
        index[ord(c)].append(i)
    j = 0
    for i in range(m):
        c = s[i]
        if not index[ord(c)]:
            return False
        pos = left_bound(index[ord(c)],j)
        if pos == len(index[ord(c)]):
            return False
        j = index[ord(c)][pos] + 1
    return True

最长回文子串

最长回文子串，T5

寻找回文串问题的核心思想：从中间向两边扩散

动态规划

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
            return s
        dp = [[False for i in range(n)] for j in range(n)]
        for i in range(n):
            dp[i][i] = True
        start = 0
        length = 1
        for i in range(n-2,-1,-1):
            for j in range(i+1,n):
                if s[i] != s[j]:
                    dp[i][j] = False
                else:
                    if j - i < 2:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i+1][j-1]
                if dp[i][j] and j - i + 1 > length:
                    length = j - i + 1
                    start = i
        return s[start:start+length]

中心扩展：

def expandCenter(s,left,right):
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return left + 1,right - 1

def longestPalindrome(s):
    start = 0
    end = 0
    for i in range(len(s)):
        left1,right1 = expandCenter(s,i,i)
        left2,right2 = expandCenter(s,i,i+1)
     	if right1 - left1 > end - start:
            start,end = left1,right1
        if right2 - left2 > end - start:
            start,end = left2,right2
    return s[start:end+1]

接雨水

接雨水，T42

暴力解法：

def trap(height):
    n = len(height)
    res = 0
    for i in range(1,n-1):
        l_max = 0
        r_max = 0
        for j in range(0,i):
            l_max = max(l_max,height[j])
        for j in range(i+1,n):
            r_max = max(r_max,height[j])
        if height[i] <= l_max or height[i] <= r_max:
            res += min(l_max,r_max) - height[i]
    return res

时间O(N^2)，空间O(1)

备忘录优化：

def trap(height):
    n = len(height)
    if n < 3:
        return 0
    res = 0
    l_max = [0 for i in range(n)]
    r_max = [0 for i in range(n)]
    #从左往右计算l_max
    l_max[0] = height[0]
    for i in range(1,n):
        l_max[i] = max(height[i],l_max[i-1])
    #从右往左计算r_max
    r_max[n-1] = height[n-1]
    for i in range(n-2,-1,-1):
        r_max[i] = max(r_max[i+1],height[i])
    for i in range(1,n-1):
        res += min(l_max[i],r_max[i]) - height[i]
    return res

时间O(N)，空间O(N)

双指针：

def trap(height):
    left = 0
    right = len(height) - 1
    l_max = 0
    r_max = 0
    res = 0
    while left < right:
        l_max = max(l_max,height[left])
        r_max = max(r_max,height[right])
        res += min(l_max,r_max) - height[i]
    return res

盛最多水的容器，T11

def maxArea(height):
    left = 0
    right = len(height) - 1
    res = 0
    while left < right:
        cur_area = min(height[right],height[left]) * (right - left)
        res = max(res,cur_area)
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return res

括号相关问题

有效的括号，T20

def isValid(s):
    left = []
    pairs = {'(':')','[':']','{':'}'}
    for c in s:
        if c in pairs:
            left.append(c)
        else: #是右括号
            if left and c == pairs[left[-1]]:
                left.pop()
            else:
                return False
    return not left

使括号有效的最少添加，T921

题目：给定一个由 '(' 和 ')' 括号组成的字符串 S，我们需要添加最少的括号（ '(' 或是 ')'，可以在任何位置），以使得到的括号字符串有效。

def minAddToMakeValid(s):
    #添加几次左括号
    res = 0
    #需要多少右括号
    need = 0
    for i in range(len(s)):
        if s[i] == '(':
            need += 1
        else:
            need -= 1
            if need == -1:
                need = 0
                res += 1
    return res + need

平衡括号字符串的最少插入次数，T1541

题目：给你一个括号字符串s，只包含’(‘和’)’，一个括号字符串被称为平衡的，当它满足：

（1）’(‘对应两个连续的右括号’))’

（2）’(‘必须在’))'之前

请返回让s平衡的最少插入次数

括号生成，T22

题目：生成n对有效括号，列举所有可能

def generateParenthesis(n):
    def backtrack(left,right,track,res):
        if left > right:
            return
        if (left < 0) or (right < 0):
            return
        if (left == 0) and (right == 0):
            res.append(track[:])
            return
        track.append('(')
        backtrack(left-1,right,track,res)
        track.pop()
        
        track.append(')')
        backtrack(left,right-1,track,res)
        track.pop()
    res = []
    track = []
    backtrack(n,n,track,res)
    for i in range(len(res)):
        res[i] = ''.join(res[i])
    return res

实现计算器

要实现的功能：

1. 输入字符串，包括+,-,*,/，数字，括号，空格，返回运算结果
2. 复合运算法则，括号优先级最高，先乘除后加减
3. 除号是整数除法，无论正负都向0取整
4. 假定输入一定合法，且不会出现整型溢出，除数为0的情况

一、字符串转整数

s = '458'
n = 0
for i in range(len(s)):
    c = s[i]
    n = 10 * n + (ord(c) - ord('0'))

二、处理加减法

def calculate(s):
    stk = []
    num = 0
    sigh = '+'
    for i in range(len(s)):
        c = s[i]
        if c.isdigit():
            num = 10 * num + (ord(c) - ord('0'))
        if (not c.isdigit()) or (i == len(s) - 1):
            if sign == '+':
                stk.append(num)
            elif sign == '-':
                stk.append(-num)
            sign = c
            num = 0
    return sum(stk)

三、处理乘除法和空格

for i in range(len(s)):
    c = s[i]
    if c == ' ':
        continue
    if c.isdigit():
        num = 10 * num + (ord(c) - ord('0'))
    if (not c.idigit()) or (i == len(s) - 1):
        if sign == '+':
            stk.append(num)
        elif sign == '-':
            stk.append(-num)
        elif sigh == '*':
            pre = stk.pop()
            stk.push(pre * num)
        elif sign == '/':
            pre = stk.pop()
            stk.push(pre // num)
        sign = c
        num = 0

四、处理括号

def calculate(s):
    def helper(s):
        stack = []
        sigh = '+'
        num = 0
        while len(s) > 0:
            c = s.pop(0)
            if c == '(':
                num = helper(s)
            if c.isdigit():
                num = 10 * num + int(c)
            if (not c.isdigit() and c != ' ') or len(s) == 0:
                if sign == '+':
                    stack.append(num)
                elif sign == '-':
                    stack.append(-num)
                elif sign == '*':
                    stack[-1] = stack[-1] * num
                elif sign == '/':
                    stack[-1] = int(stack[-1] / float(num))
                num = 0
                sign = c
            if c == ')':
                break
        return sum(stack)
    return helper(collections.deque(s))

基本计算器，T224

class Solution:
    def calculate(self, s: str) -> int:
        def helper(s):
            stack = []
            num = 0
            sign = '+'
            while len(s) > 0:
                c = s.popleft()
                if c == '(':
                    num = helper(s)
                if c.isdigit():
                    num = 10 * num + int(c)
                if (not c.isdigit() and c != ' ') or len(s) == 0:
                    if sign == '+':
                        stack.append(num)
                    elif sign == '-':
                        stack.append(-num)
                    num = 0
                    sign = c
                if c == ')':
                    break
            return sum(stack)
        return helper(collections.deque(s))

基本计算器Ⅱ，T227

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        sign = '+'
        s = collections.deque(s)
        num = 0
        while len(s) > 0:
            c = s.popleft()
            if c.isdigit():
                num = 10 * num + int(c)
            if (not c.isdigit() and c != ' ') or len(s) == 0:
                if sign == '+':
                    stack.append(num)
                elif sign == '-':
                    stack.append(-num)
                elif sign == '*':
                    stack[-1] = stack[-1] * num
                elif sign == '/':
                    stack[-1] = int(stack[-1] / num)
                num = 0
                sign = c
        return sum(stack)

最后

以上就是粗暴小兔子为你收集整理的[Leetcode]其它经典面试题——python版本快速选择算法分治算法区间问题字符串乘法二分查找高效判定子序列最长回文子串接雨水括号相关问题实现计算器的全部内容，希望文章能够帮你解决[Leetcode]其它经典面试题——python版本快速选择算法分治算法区间问题字符串乘法二分查找高效判定子序列最长回文子串接雨水括号相关问题实现计算器所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。