3001. 捕獲黑皇后需要的最少移動(dòng)次數(shù)
解題思路
從題中簡(jiǎn)要分析可以知道最多就是兩次，最少就是一次，其他情況就是兩次虚汛。兩次的情況最復(fù)雜，于是想辦法找出一次刺桃，剩下就是兩次粹淋。
-
如果在車(chē)同行或同列吸祟，在象的對(duì)角線上那么答案為1瑟慈，其他情況都為2
對(duì)角線原則
func minMovesToCaptureTheQueen(a int, b int, c int, d int, e int, f int) int {
if a == e && (c != e || ok(b,d,f)) || //如果車(chē)跟皇后在同行且象沒(méi)有阻攔，或象并沒(méi)有在車(chē)皇后之間
b == f && (d != f || ok(a,c,e)) || // //如果車(chē)跟皇后在同列且象沒(méi)有阻攔屋匕，或象并沒(méi)有在車(chē)皇后之間
c+d == e+f && (a+b != e+f || ok(c,a,e)) || //從圖中可以看到同對(duì)角線的值都相等
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)
}
解題思路
因?yàn)橐Ａ糇疃嗟脑馗鸨蹋员M量要去除相同的元素。
設(shè)nums1有n個(gè)不同元素过吻，nums2有m個(gè)不同元素进泼，它們的交集有common個(gè)元素。
由于每個(gè)數(shù)組只能選擇n/2個(gè)元素纤虽，且最好選不在交集中的數(shù)乳绕，于是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)
}
