LCP 18. 早餐组合

已知两个数组，求在两个数组中分别取一个数，它们的和小于x的个数。
力扣：LCP 18. 早餐组合

示例

输入：staple = [10,20,5], drinks = [5,5,2], x = 15
输出：6

方法：排序+双指针

先对两个数组分别进行排序；
用第一个指针left从下标0开始遍历第一个数组，第二个指针right从下表n-1开始逆向遍历第二个数组；
则每次满足条件的个数为 right+1；
最后对个数求和并取余返回。

代码

class Solution:
    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:
        staple.sort()
        drinks.sort()
        m, n = len(staple), len(drinks)
        left, right = 0, n-1
        ans = 0
        while left < m and right >= 0:
            if staple[left] + drinks[right] <= x:
                left += 1
                ans = ans + right + 1
            else:
                right -= 1
        return int(ans % (1e9 + 7))
1
2
3
4
5
6
7
8
9
10
11
12
13
14

剑指 Offer II 079. 所有子集

给定一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

方法

方法一：位运算符
方法二：DFS枚举

代码一

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans = []
        mask = 0
        while mask < (1 << n):
            res = []
            for i in range(n):
                if mask & (1 << i):
                    res.append(nums[i])
            ans.append(res)
            mask += 1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13

代码二

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        res = []
        n = len(nums)
        def dfs(i):
            if i == n:
                ans.append(list(res))
                return
            res.append(nums[i])
            dfs(i+1)
            res.pop()
            dfs(i+1)
        dfs(0)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

77.组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。

示例

输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

方法

DFS枚举

代码

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        ans = []
        res = []
        def dfs(i):
            if len(res) == k:
                ans.append(list(res))
                return
            if i == n + 1:
                return
            res.append(i)
            dfs(i + 1)
            res.pop()
            dfs(i + 1)
        dfs(1)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

求和为1的个数

给定两个数组，对应位置相除，求组合为1的个数。

示例

a = [1, 1, 1], b = [2, 2, 2]
则输出为 3

方法

DFS枚举+除法特殊处理

代码

class Solution:
    def combine(self, a, b):
        ans = []
        res_a = []
        res_b = []
        def sums(x, y):  # 数组和特殊处理
            if not x:
                return 0
            if len(x) == 1:
                return x[0]/y[0]
            if len(x) == 2:
                return (x[0] * y[1] + x[1] * y[0]) / (y[0] * y[1])
            if len(x) > 2:
                c = [x.pop(), x.pop()]
                d = [y.pop(), y.pop()]
                x.append(c[0] * d[1] + c[1] * d[0])
                y.append(d[0] * d[1])
                return sums(x, y)
        def dfs(i):   # DFS枚举
            if sums(list(res_a), list(res_b)) == 1:
                ans.append(res_a)
                return
            if i == len(a):
                return
            res_a.append(a[i])
            res_b.append(b[i])
            dfs(i+1)
            res_a.pop()
            res_b.pop()
            dfs(i+1)
        dfs(0)
        return len(ans)

if __name__ == '__main__':
    print(Solution().combine([1, 1, 1], [2, 2, 2]))
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