Fork me on GitHub
image frame

EightyNinth

力扣 779. 第K个语法符号

leetcode

思路

0
01
0110
01101001
……

可以看出，每一层前半是上一层的复制，后半是上一层的求反

因此，若k在当前层的前半，就是上一层的值；若k在当前层的后半，就是上一层k-2**(n-1)/2的反值。

解法

1
2
3
4
5
6
7
def kthGrammar(n, k):
    if n == 1:
         return 0
    if k <= 1 << (n -2):
        return kthGrammar(n - 1, k)
    else:
        return kthGrammar(n - 1, k - (1 << (n - 2))) ^ 1

力扣 1700. 无法吃午餐的学生数量

leetcode

模拟1

1
2
3
4
5
6
7
8
9
10
11
def countStudents(students, sandwiches):
    s1 = sum(students)
    s0 = len(students) - s1
    for x in sandwiches:
        if x == 1 and s1:
            s1 -= 1
        elif x == 0 and s0:
            s0 -= 1
        else:
            break
    return s0 + s1

模拟2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def countStudents(students, sandwiches):
    cur, flag = len(sandwiches), True
    while flag:
        for i in range(cur):
            if sandwiches[0] == students[0]:
                sandwiches.pop(0)
                students.pop(0)
            else:
                students.append(students.pop(0))
        if cur == len(sandwiches):
            flag = False
        else:
            cur = len(sandwiches)
    return cur

力扣 902. 最大为N的数字组合

leetcode

数位dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def atMostNGivenDigitSet(digits, n):
    n_s = str(n)
    m, k = len(digits), len(n_s)
    dp = [[0, 0] for _ in range(k + 1)]
    dp[0][1] = 1
    for i in range(1, k + 1):
        for d in digits:
            if d == n_s[i - 1]:
                dp[i][1] = dp[i - 1][1]
            elif d < n_s[i - 1]:
                dp[i][0] += dp[i - 1][1]
            else:
                break
        if i > 1:
            dp[i][0] += m + dp[i - 1][0] * m
    return sum(dp[k])

力扣 300. 最长递增子序列

leetcode

时间复杂度$O(n^2)$

1
2
3
4
5
6
7
8
9
10
def lengthOfLIS(nums):
    #  动态规划
    dp = [1 for _ in range(len(nums))]
    ret = 1
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[j] + 1, dp[i])
        ret = max(ret, dp[i])
    return ret

时间复杂度$O(nlogn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def lengthOfLIS(nums):
    #  动态规划 + 二分查找
    dp = [0 for _ in range(len(nums))]
    ret = 0
    for num in nums:
        i, j = 0, ret
        while i < j:
            m = i + j >> 1
            if dp[m] < num:
                i = m + 1
            else:
                j = m
        dp[i] = num
        if i == ret: ret += 1

    return ret

力扣 297. 二叉树的序列化

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if not root: return "null"
        # 层序遍历
        ret, queue = [], [root]
        while queue:
            for _ in range(len(queue)):
                cur = queue.pop(0)
                if cur == None:
                    ret.append("null")
                    continue
                ret.append(cur.val)
                queue.append(cur.left)
                queue.append(cur.right)
        return " ".join(map(str, ret))


    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        # 层序构建树
        data = data.split(" ")
        if data[0] == "null":
            return None
        head = TreeNode(int(data[0]))
        nodes = [head]
        j = 1
        for node in nodes:
            if node != None:
                node.left = TreeNode(int(data[j])) if data[j] != "null" else None
                nodes.append(node.left)
                j += 1
                if j >= len(data):
                    return head
                node.right = TreeNode(int(data[j])) if data[j] != "null" else None
                nodes.append(node.right)
                j += 1
                if j >= len(data):
                    return head

力扣 287. 寻找重复数

leetcode

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def findDuplicate(nums):
    # 二分查找
    left, right = 1, len(nums) - 1
    while left < right:
        mid = (left + right) >> 1
        count = 0
        for n in nums:
            if n <= mid:
                count += 1
        if count <= mid:
            left = mid + 1
        else:
            right = mid

    return left

双指针

1
2
3
4
5
6
7
8
9
10
11
def findDuplicate(nums):
    # 双指针
    low, fast = nums[0], nums[nums[0]]
    while low != fast:
        low = nums[low]
        fast = nums[nums[fast]]
    fast = 0
    while low != fast:
        low = nums[low]
        fast = nums[fast]
    return fast

力扣 283. 移动零

leetcode

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def moveZeroes(nums):
    """
    Do not return anything, modify nums in-place instead.
    """        
    s, e, L = 0, 0, len(nums)
    while s < L and e < L:
        # 找0值
        while s < e and nums[s] != 0: s += 1
        # 找非0值
        while e < L and nums[e] == 0: e += 1
        if s < L and e < L: 
            nums[s], nums[e] = nums[e], nums[s]
            s += 1
            e += 1

技巧，知识积累，持续更新

校招

堆的构建: 以大根堆为例

参考

  1. 找到堆中最后一个父节点
  2. 对比当前父节点和左右子节点的大小，最大的和较小的交换。
  3. 数组逆序到上一个父节点，执行第二步以后，如果交换的子节点还有子节点，执行第二步到叶节点
  4. 执行到根节点结束

力扣 253. 会议室II

leetcode

由于是会员题目，这里对题目进行描述

题目描述

给定一个会议时间安排的数组，每个会议时间都会包括开始和结束的时间[[s1, e1], [s2,e2], …](si < ei)，为避免会议冲突，同时要考虑充分利用会议室资源，请你计算至少需要多少间会议室，才能满足这些会议安排？

示例1：
input： [[0, 30], [5, 10], [15, 20]]
output：2

示例2：
input： [[7, 10], [2, 4]]
output：1

思路1 优先队列

  1. 按照开始时间对会议进行排序。
  2. 以会议结束时间构建最小堆，判断是否有会议室空着可使用。
    1. 如果空闲，直接开始会议
    2. 如果不空闲，开新房间，加入堆

解法1

1
2
3
4
5
6
7
8
9
10
11
12
import heapq
def minMeetingRooms(intervals):
    if not intervals: return 0
    # 堆
    intervals.sort(key=lambda x: x[0])
    heap = []
    for inter in intervals:
        if heap and heap[0] <= inter[0]:
            heapq.heappop(heap)
        heapq.heappush(heap, inter[1])

    return len(heap)

思路2 双指针

  1. 分别按照开始时间和结束时间对会议进行排序。
  2. 双指针分别指向开始和结束
  3. 会议室会随着开始指针右移一直增加，但如果开始指针大于等于结束指针，会议室数量-1，结束指针后移1位

解法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def minMeetingRooms(intervals):
    if not intervals: return 0
    # 双指针
    start, end = [], []
    for inter in intervals:
        start.append(inter[0])
        end.append(inter[1])
    start.sort()
    end.sort()
    left, right, ret = 0, 0, 0
    while left < len(intervals) and right < len(intervals):
        if start[left] >= end[right]:
            right += 1
            ret -= 1
        ret += 1
        left += 1
    return ret
  • Copyrights © 2022 eightyninth
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信