最小公共值

【雙指針】分離雙指針，O(1)空間復雜度。

使數(shù)組中所有元素相等的最小操作數(shù) II

【遍歷】令a[i]=nums1[i]-nums2[i]，則問題變成把每個a變成0的最小操作次數(shù)。k!=0時，得讓所有a[i]變成0，每個a[i]必須是k的倍數(shù)。

最大子序列的分數(shù)

【堆】把nums1和nums2組合起來，按照nums2[i]從大到小排序，枚舉nums2[i]作為序列的最小值，那么nums1只能在下標≤i的數(shù)中選，要選最大的k個數(shù)。

判斷一個點是否可以到達

【位運算】考慮從終點(x, y)到起點(1,1),當x或y是偶數(shù),可以變成奇數(shù),x和y都是奇數(shù)時,如果x=y,則不能將x和y減少,此時x=y=1則到起點。x≠y時,由于x和y是奇數(shù),x+y是偶數(shù),可以將其中較大的坐標值減少,如果x>y,則(x,y) →(x +y, y)→(x+y/2, y),由于y < x+y/2 < x可以將橫坐標減少。x<y時,(x,y) →(x, x + y)→(x, x + y/2),由于x < x+y/2 < y可以將橫坐標減少。當x和y都是奇數(shù)且x≠y時,根據(jù)最大公約數(shù)的性質,gcd(x, y)=gcd(x+y, y)=gcd(x+y/2, y)=gcd(x, x+y) =gcd(x, x+y/2) ,因此上述操作之后,橫坐標與縱坐標的最大公約數(shù)不變。當?shù)竭_(1,1)時,橫坐標與縱坐標的最大公約數(shù)是1,如果可以經過反向操作從(x,y)到達(1,1),則必有gcd(x,y)=1。當x和y都是奇數(shù)且x≠y時,如果gcd(x,y)=1,由于上述操作總是可以較大的坐標值減少,因此一定可以經過反向操作從(x,y)到達(1,1)根據(jù)上述分析可以得到,當x和y都是奇數(shù)且x≠y時,可以經過反向操作從(x,y)到達(1,1)等價于gcd(c,y)=1。當x和y中可能存在偶數(shù)時,由于總是可以將偶數(shù)除以2直到變成奇數(shù),因此可以經過反向操作從(x,y)到達(1,1)等價于gcd(x,y)=2^t,其中t為非負整數(shù)。divisor為2的整數(shù)次冪，等價于divisor&(divisor - 1)的結果是0。