Fork me on GitHub
image frame

EightyNinth

力扣 34. 在排序数组中查找元素的第一个和最后一个位置

leetcode

左右二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def searchRange(nums, target):
    # 左右二分
    def search_left(l, r, t):
        while l < r:
            m = l + r >> 1
            if nums[m] < t:
                l = m + 1
            else:
                r = m
        return l

    def search_right(l, r, t): 
        while l < r:
            m = l + r + 1 >> 1
            if nums[m] > t:
                r = m - 1
            else:
                l = m
        return l
    if not nums: return [-1, -1]
    nums_len = len(nums) - 1
    left = search_left(0, nums_len, target)
    right = search_right(0, nums_len, target)

    return [left, right] if nums[left] == target and nums[right] == target else [-1, -1]

力扣 33. 搜索旋转排序树组

leetcode

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def search(nums, target):
    if not nums: return -1
    # 数组是局部有序的
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + right >> 1
        if nums[mid] == target:
            return mid
        # [l, mid - 1] 有序
        if nums[0] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # [mid + 1, right] 有序
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

力扣 32. 最长有效括号

leetcode

动态规划

思想

dp[i] 表示到第i个字符的有效括号数量
初始情况下, 全部初始化为0

  1. s[i - 1], s[i] == “()”
    dp[i] = dp[i - 2] + 2
  2. s[i - 1], s[i] == “…))”
    dp[i] = dp[i - dp[i - 1] - 1] + dp[i - 2] + 2 if s[i - dp[i - 1] - 1] == “(“
    代码还需考虑 i 的范围的事情

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
def longestValidParentheses(s):
    # 动态规划
    s_len = len(s)
    dp, max_sub = [0 for _ in range(s_len)], 0
    for i in range(s_len):
        if s[i] == ")" and i - 1 >= 0:
            if s[i - 1] == "(":
                dp[i] = dp[i - 2] + 2 if i - 2 >= 0 else 2
            elif i - dp[i - 1] > 0 and s[i - dp[i - 1] - 1] == "(":
                dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2
        max_sub = max(max_sub, dp[i])
    # print(dp)
    return max_sub

栈

思想

  1. 对于遇到的每个”(“, 将它的下标放入栈中

  2. 对于遇到的每个”)”, 先弹出栈顶元素表示匹配了当前右括号:

    1. 如果栈为空，说明当前的右括号为没有被匹配的右括号，将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」
    2. 如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def longestValidParentheses(s):
    # 栈
    stack, max_sub = [-1], 0
    for i in range(len(s)):
        if s[i] == "(":
            stack.append(i)
        else:
            stack.pop()
            if stack:
                max_sub = max(max_sub, i - stack[-1])
            else:
                stack.append(i)
    
    return max_sub

贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def longestValidParentheses(s):
    # 贪心
    left, right, max_sub, s_len = 0, 0, 0, len(s)
    for i in range(s_len):
        if s[i] == "(":
            left += 1
        else:
            right += 1
        
        if left == right:
            max_sub = max(max_sub, right * 2)
        elif right > left:
            left, right = 0, 0
    
    left, right = 0, 0
    for i in range(s_len - 1, -1, -1):
        if s[i] == "(":
            left += 1
        else:
            right += 1
        
        if left == right:
            max_sub = max(max_sub, right * 2)
        elif left > right:
            left, right = 0, 0
    
    return max_sub

力扣 224. 基本计算器

leetcode

栈处理op

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def cal(s):
    op = [1]
    sign, res = 1, 0
    i, s_len = 0, len(s)
    while i < s_len:
        if s[i] == " ":
            i += 1
        elif s[i] == "+":
            sign = op[-1]
            i += 1
        elif s[i] == "-":
            sign = -op[-1]
            i += 1
        elif s[i] == "(":
            op.append(sign)
            i += 1
        elif s[i] == ")":
            op.pop()
            i += 1
        else:
            num = 0
            while i < s_len and s[i].isdigit():
                num = num * 10 + ord(s[i]) - ord("0")
                i += 1
            res += sign * num
    
    return res

笔试题 基础计算器

校招

题目描述

实现一个表达式计算, 输入包括: 非负整数, “(“, “)”, “+”, “-“, “*”, “/“, 空格

示例

“2 * ( 6 - 1 ) / 4”

输出

2

思路

实际上是中缀表达式的计算, 中缀转后缀计算

栈 + hash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
def cal(s):
    if not s: return 0
    prior = {"+": 0, "-": 0, "*": 1, "/": 1, "(": -1}
    stack, op = [], []
    num = None
    # 中缀 -> 后缀
    for i in range(len(s)):
        if s[i] != " ":
            if s[i].isdigit():
                num = 10 * num + int(s[i]) if num != None else int(s[i])
            else:
                if num != None:
                    stack.append(num)
                    num = None
                if op:
                    if s[i] != "(" and s[i] != ")":
                        while op and prior[s[i]] <= prior[op[-1]]:
                            stack.append(op.pop())
                        op.append(s[i])
                    elif s[i] == "(":
                        op.append(s[i])
                    else:
                        while op and op[-1] != "(":
                            stack.append(op.pop())
                        op.pop()
                else:
                    op.append(s[i])
    if num != None: stack.append(num)
    while op: stack.append(op.pop())

    # print(stack)
    # 计算后缀
    res = []
    for cur in stack:
        if type(cur) == int:
            res.append(cur)
        else:
            num2, num1 = res.pop(), res.pop()
            if cur == "+":
                tmp = num1 + num2
            elif cur =="-":
                tmp = num1 - num2
            elif cur == "*":
                tmp = num1 * num2
            else:
                tmp = num1 / num2
            res.append(tmp)

    return res[-1]

扩展: 前缀表达式的计算

前缀不需要转换, 利用栈对表达式从右到左扫描计算

力扣 31. 下一个排列

leetcode

类似双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
"""
核心是保证变大的幅度尽可能小
"""
def nextPermutation(nums):
    """
    Do not return anything, modify nums in-place instead.
    """
    if len(nums) <= 1: return
        i = len(nums) - 2
        # 求最靠右的较小数
        while i >= 0 and nums[i] >= nums[i + 1]: i-= 1
        # 求最远离较小数的较大数
        if i>= 0:
            j = len(nums) - 1
            while j > i and nums[j] <= nums[i]: j -= 1
            
            # 交换较大较小数
            nums[i], nums[j] = nums[j], nums[i]
        
        # 保证变大幅度不大的降序反序
        l, r = i + 1, len(nums) - 1
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l += 1
            r -= 1

力扣 23. 合并K个升序链表

leetcode

预置

1
2
3
4
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

队列 + leetcode 21

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def mergeKLists(lists):
    def mergelal(l1, l2):
        if not l1: return l2
        if not l2: return l1
        top = ListNode()
        cur, c1, c2 = top, l1, l2
        while c1 and c2:
            if c1.val <= c2.val:
                cur.next, c1 = c1, c1.next
            else:
                cur.next, c2 = c2, c2.next
            cur = cur.next
        
        if c1: cur.next = c1
        if c2: cur.next = c2
        return top.next
    
    if not lists: return None

    while len(lists) > 1:
        lists.append(mergelal(lists.pop(0), lists.pop(0)))

    return lists[0]

力扣 22. 括号生成

leetcode

回溯思想 + 深度优先遍历(dfs)实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def generateParenthesis(n):
    res, cur = [], ""
    def dfs(cur, left, right):
        if left == 0 and right == 0:
            res.append(cur)
        elif right < left:
            return
        else:
            if left > 0:
                dfs(cur + "(", left - 1, right)
            if right > 0:
                dfs(cur + ")", left, right - 1)
    dfs(cur, n, n) 
    return res

力扣 21. 合并两个有序链表

leetcode

预置

1
2
3
4
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

虚拟头节点 + 链表基础操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def mergeTwoLists(list1, list2):
    if not list1: return list2
    if not list2: return list1
    top = ListNode()
    cur1, cur2, cur = list1, list2, top
    while cur1 and cur2:
        if cur1.val <= cur2.val:
            cur.next, cur1 = cur1, cur1.next
        else:
            cur.next, cur2 = cur2, cur2.next
        cur = cur.next
    
    if cur1: cur.next = cur1
    if cur2: cur.next = cur2
    return top.next

力扣 20. 有效的括号

leetcode

栈 + hash表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def isValid(s):
    if not s: return True 
    pip = {"}": "{",
           ")": "(",
           "]": "["}

    queue = []

    for sign in s:
        if sign in pip.keys():
            if not queue:
                return False
            else:
                cur = queue.pop()
                if pip[sign] != cur:
                    return False
        else:
            queue.append(sign)
        
    
    if not queue:
        return True
    else:
        return False
  • Copyrights © 2022 eightyninth
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信