A. Determine if Two Events Have Conflict (opens new window)

Determine if two segments overlap.

DETAILS

def haveConflict(self, E1: List[str], E2: List[str]) -> bool:
        return not (E1[1] < E2[0] or E1[0] > E2[1])

B. Number of Subarrays With GCD Equal to K (opens new window)

Brute Force is okay. Start from each index i and calculate the common gcd from nums[i] all the way to its right until gcd is smaller than k. During the iteration, if gcd equals k, it means we find one such valid subarray.

Can be improved using two pointers.

DETAILS

def subarrayGCD(self, nums: List[int], k: int) -> int:
        res, n = 0, len(nums)
        for i in range(n):
            tmp = nums[i]
            for j in range(i, n):
                tmp = gcd(nums[j], tmp)
                res += int(tmp == k)
        return res

C. Minimum Cost to Make Array Equal (opens new window)

Prefix sum.

The value that makes the minimum cost must be one of the value in N. Thus we just need to try every possible values in N, use prefix sum of unit cost to simplify the calculation time.

DETAILS

def minCost(self, N: List[int], C: List[int]) -> int:
        A, n = sorted([n, c] for n, c in zip(N, C)), len(C)
        pre = [0] * n
        pre[0] = A[0][1]
        for i in range(1, n): pre[i] = A[i][1] + pre[i - 1]
        
        cur = 0
        for i in range(1, n): cur += A[i][1] * (A[i][0] - A[0][0])
        ans = cur
        
        for i in range(1, n):
            gap = A[i][0] - A[i - 1][0]
            if gap > 0:
                cur += pre[i - 1] * gap
                cur -= gap * (pre[n - 1] - pre[i - 1])
                ans = min(cur, ans)
        return ans

D. Minimum Number of Operations to Make Arrays Similar (opens new window)

Please refer to This LC Discussion (opens new window) for my solution in English.

贪心法。

• 每次操作，数字的改变量的都是2的倍数，一定是奇数变奇数，偶数变偶数
• 从N到T，要用最少的操作，所以一定是排序后，最小的N变成最小的T，以此类推。

因此，把两个数组按照【奇偶】和【大小】排序。

每次操作会把总差距减少4，所以只需要算出排序后N，T之间的所有差距，除以4即可。

DETAILS

def makeSimilar(self, N: List[int], T: List[int]) -> int:
        N.sort(key=lambda x: [x % 2, x])
        T.sort(key=lambda x: [x % 2, x])
        return sum(abs(n - t) for n, t in zip(N, T)) // 4