刷题日记(6)

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

解题思路

从题中简要分析可以知道最多就是两次，最少就是一次，其他情况就是两次。两次的情况最复杂，于是想办法找出一次，剩下就是两次。

• 如果在车同行或同列，在象的对角线上那么答案为1，其他情况都为2

  
  
  对角线原则

func minMovesToCaptureTheQueen(a int, b int, c int, d int, e int, f int) int {
    if a == e && (c != e || ok(b,d,f)) ||  //如果车跟皇后在同行且象没有阻拦，或象并没有在车皇后之间
       b == f && (d != f || ok(a,c,e)) || // //如果车跟皇后在同列且象没有阻拦，或象并没有在车皇后之间
        c+d == e+f && (a+b != e+f || ok(c,a,e)) ||  //从图中可以看到同对角线的值都相等
        c-d == e-f && (a-b != e-f || ok(c,a,e)){
            return 1
        }
        return 2
}

func ok(l,m,r int)bool{
    return m < min(l,r) || m > max(l,r)
}

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

解题思路

因为要保留最多的元素，所以尽量要去除相同的元素。

• 设nums1有n个不同元素，nums2有m个不同元素，它们的交集有common个元素。

• 由于每个数组只能选择n/2个元素，且最好选不在交集中的数，于是c1 = min(n-common,n/2)，同理c2 = min(m-common,n/2)。

• 若c1+c2 < n，那么还可以从common中选，于是答案变成c1+c2+min(n-c1-c2,common) = min(n,c1+c2+common)

func maximumSetSize(nums1, nums2 []int) int {
    set1 := map[int]bool{}
    for _, x := range nums1 {
        set1[x] = true
    }
    set2 := map[int]bool{}
    for _, x := range nums2 {
        set2[x] = true
    }
    m := len(nums1)/2
    common := 0
    for x := range set1 {
        if set2[x] {
            common++
        }
    }
    c1 := min(m,len(set1)-common)
    c2 := min(m,len(set2)-common)

    return min(len(nums1),c1+c2+common)
}