刷题记录合辑

标题不含题号，题号写在正文与 description 中。

3477. 水果成篮2

思路
代码
题解
尝试1
尝试2

思路
直接模拟即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
```

<!-- tab 不同解法 -->

```python
class Solution:
    def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
        s = defaultDict(int)
        for fruit in fruits:
            for i, cap in enumerate(baskets):
                if i in s or cap < fruit:
                    continue
                else:
                    s.add(i)
        return len(baskets) - len(s)
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
```

{% endtabs %}

**总结**
使用set的defaultDict(int)中间是需要有type的

---

## 454. 四数之和2

{% folding  模板 open:false %}

{% tabs active:2 align:left %}
<!-- tab 思路 -->

**思路**  

尝试1 - 三轮排序+set: 超时 
* 三轮排序以后使用集合

尝试2 - 两轮排序后使用双指针: 超时
* 全部都排序，剩下两个数组分别有一个指针，然后每次移动让和实现较小的增长

题解 - 分别两轮n^2的方法加上dict:

<!-- tab 题解 -->

```python
class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        cnt = Counter(x+y for x in nums1 for y in nums2)
        return sum(cnt[-x-y] for x in nums3 for y in nums4)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        nums1.sort()
        nums2.sort()
        nums3.sort()
        s = set()
        for item in nums4:
            s.add(item)
        res = 0
        for n1 in nums1:
            for n2 in nums2:
                for n3 in nums3:
                    target = 0-n1-n2-n3
                    if target in s:
                        res+=1
        return res
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
class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        nums1.sort()
        nums2.sort()
        nums3.sort()
        nums4.sort()
        s1 = len(nums3)
        s2 = len(nums4)
        res = 0
        for n1 in nums1:
            for n2 in nums2:
                l1, l2 = 0, 0
                while l1 < s1 and l2 < s2:
                    n3 = nums3[l1]
                    n4 = nums4[l2]
                    current_sum = n1+n2+n3+n4
                    if current_sum == 0:
                        res+=1
                    if l1 == s1-1 and l2 == s2-1:
                        break
                    if l1 == s1-1 and l2 < s2-1:
                        l2 += 1
                    if l1 < s1-1 and l2 == s2-1:
                        l1 += 1
                    if l1 < s1-1 and l2 < s2-1:
                        add1 = nums3[l1+1] - nums3[l1]
                        add2 = nums4[l2+1] - nums4[l2]
                        if add1 >= add2:
                            l2+=1
                        else:
                            l1+=1

        return res

总结

1310. XOR查询

思路
代码

思路

尝试1 - 前缀和: 通过 

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        size = len(arr)
        prefix = [0] * (size+1)
        for i in range(1, size+1):
            prefix[i] = prefix^arr[i-1]
        res = []
        for q in queries:
            a, b = q[0], q[1]
            res.append(prefix[a]^prefix[b+1])
        return res

总结

494. 目标和

思路
代码
二分查找

思路

尝试1 - 搜索: 超时后进行一个剪枝后通过

  • 最朴素的搜索， 每个点都加或减进行深搜
  • 如果当前已有值减去所有剩下未选仍大于目标值或者加上所有未选仍小于目标值说明不可能实现，排除

题解1 - 搜索:

题解2 - 动态规划 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        size = len(nums)
        ans = 0
        def dfs(x, current):
            nonlocal ans
            if x == size:
                if current == target:
                    ans += 1
                return 
            dfs(x+1, current+nums[i])
            dfs(x+1, current-nums[i])
            return 
        dfs(0, 0)
        return ans
1
2
3
4
```

<!-- tab 题解 -->
```python

总结

相关题目

*

知识点小结

*

模板

思路
代码
二分查找

思路 

1
        
1
2
3
4
```

<!-- tab 题解 -->
```python

总结

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。