思维题 | lc379 补题Q2 Q3

发表于 分类于 阅读次数：

Q2 3001. 捕获黑皇后需要的最少移动次数

题意

给你一个 8 x 8的棋盘，上面有一个白色车(a, b)和一个白色象(c, d)，以及一个黑皇后(e, f)，只移动白色棋子，求吃掉黑皇后的最少移动次数。

题解

首先，答案最大为2，无论何种情况总能由车移动两步吃掉皇后，被象挡住的情况下，把象移走，再让车吃掉皇后即可。

有4种情况答案能为1：

  • 1、皇后和车在一条线方向上，且象不在两者中间

    象不在两者中间的情况

    • 1.1、象在这条线上，但不在两者中间
    • 1.2、象不在这条线上，肯定不在两者中间

  • 2、皇后和象在一个对角线方向上，且车不在两者中间

    车不在两者中间的情况

    • 2.1、车在此对角线方向上，但不在两者中间
    • 2.2、车不在此对角线方向上，肯定不在两者中间

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def minMovesToCaptureTheQueen(self, a: int, b: int, c: int, d: int, e: int, f: int) -> int:
        # x y z
        # y不在x和z中间可以用
        # (x-y)*(z-y) > 0 或者
        # y < min(x,z) or y > max(x,z) 判断
        if a == e and (c!=e or (b-d)*(f-d)>0) or \
           b == f and (d!=f or (a-c)*(e-c)>0) or \
           e+f == c+d and (a+b != c+d or (e-a)*(c-a)>0) or \
           e-f == c-d and (a-b != c-d or (e-a)*(c-a)>0):
           return 1
        return 2

Q3 3002. 移除后集合的最多元素数

题意

给你两个整数数组nums1和nums2，长度都是偶数n，要求从nums1和nums2中分别移除一半的元素，再将这两数组中剩下的元素放入集合中，求集合中最大能包含多少元素。

题解

set1和set2分别为set(nums1)和set(nums2)，n1、n2、n3分别为各个区域的元素个数，具体看代码

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def maximumSetSize(self, nums1: List[int], nums2: List[int]) -> int:
        s1 = set(nums1)
        s2 = set(nums2)
        n = len(nums1)
        m = n // 2
        ls1 = len(s1)
        ls2 = len(s2)
        n2 = len(s1&s2)
        n1 = ls1 - n2
        n3 = ls2 - n2
        ans = 0
        if n1 >= m:
            ans += m
            ans += min(n3+n2, m)
        else:
            if n1+n2 >= m:
                n2 -= m - n1
                ans += m
                ans += min(n2+n3, m)
            else:
                ans += n1+n2
                ans += min(n3, m)
        return ans

小结

这次的周赛本来没有参加的，后面打模拟发现Q2和Q3都不会，Q4更是计分以来的最高分(3039)的一道题，以目前自己的这个水平索性就不补了，留着以后来做。另外，本来应该是上个月的补题笔记，这个月才开始写，惭愧惭愧，不过这次回头重新做Q3时，发现能做了，水平还是有在进步，还是很高兴的。