Yanshi XU
Go back

LeetCode Biweekly Contest 131

·
Edit page

Contest

Q1 Find the XOR of Numbers Which Appear Twice

You are given an array nums, where each number in the array appears either once or twice.

Return the bitwise XOR of all the numbers that appear twice in the array, or 0 if no number appears twice.

Example 1:

Input: nums = [1,2,1,3]

Output: 1

Explanation:

The only number that appears twice in nums is 1.

Example 2:

Input: nums = [1,2,3]

Output: 0

Explanation:

No number appears twice in nums.

Example 3:

Input: nums = [1,2,2,1]

Output: 3

Explanation:

Numbers 1 and 2 appeared twice. 1 XOR 2 == 3.

Constraints:

My solution during the contest

Count the occurrences of every numbers.

class Solution:
    def duplicateNumbersXOR(self, nums: List[int]) -> int:
        ans = 0
        cnt = Counter(nums)
        for num in cnt:
            if cnt[num] == 2:
                ans ^= num
        return ans

Better solution

class Solution:
    def duplicateNumbersXOR(self, nums: List[int]) -> int:
        ans = vis = 0
        for x in nums:
            if vis >> x & 1:
                ans ^= x
            else:
                vis |= 1 << x
        return ans

Q2 Find Occurrences of an Element in an Array

You are given an integer array nums, an integer array queries, and an integer x.

For each queries[i], you need to find the index of the queries[i]th occurrence of x in the nums array. If there are fewer than queries[i] occurrences of x, the answer should be -1 for that query.

Return an integer array answer containing the answers to all queries.

Example 1:

Input: nums = [1,3,1,7], queries = [1,3,2,4], x = 1

Output: [0,-1,2,-1]

Explanation:

Example 2:

Input: nums = [1,2,3], queries = [10], x = 5

Output: [-1]

Explanation:

Constraints:

My solution during the contest

Store every indices of x in x_idx and query.

class Solution:
    def occurrencesOfElement(self, nums: List[int], queries: List[int], x: int) -> List[int]:
        x_idx = []
        for i, num in enumerate(nums):
            if num == x:
                x_idx.append(i)
        ans = [-1] * (n := len(queries))
        for i in range(n):
            if queries[i] <= len(x_idx):
                ans[i] = x_idx[queries[i] - 1]
        return ans

Better solution

class Solution:
    def occurrencesOfElement(self, nums: List[int], queries: List[int], x: int) -> List[int]:
        pos = [i for i, v in enumerate(nums) if v == x]
        return [-1 if q > len(pos) else pos[q - 1] for q in queries]

Q3 Find the Number of Distinct Colors Among the Balls

You are given an integer limit and a 2D array queries of size n x 2.

There are limit + 1 balls with distinct labels in the range [0, limit]. Initially, all balls are uncolored. For every query in queries that is of the form [x, y], you mark ball x with the color y. After each query, you need to find the number of distinct colors among the balls.

Return an array result of length n, where result[i] denotes the number of distinct colors after ith query.

Note that when answering a query, lack of a color will not be considered as a color.

Example 1:

Input: limit = 4, queries = [[1,4],[2,5],[1,3],[3,4]]

Output: [1,2,2,3]

Explanation:

Example 2:

Input: limit = 4, queries = [[0,1],[1,2],[2,2],[3,4],[4,5]]

Output: [1,2,2,3,4]

Explanation:

Constraints:

My solution during the contest

Two hash maps. Color to balls & ball to color.

class Solution:
    def queryResults(self, limit: int, queries: List[List[int]]) -> List[int]:
        ans = [0] * (n := len(queries))
        color = 0
        color_ball = defaultdict(set)
        ball_color = defaultdict(int)
        for i, (x, y) in enumerate(queries):
            if x in ball_color:
                color_ball[ball_color[x]].remove(x)
                if not color_ball[ball_color[x]]:
                    color_ball.pop(ball_color[x])
                    color -= 1
                if y not in color_ball:
                    color += 1
            else:
                if y not in color_ball:
                    color += 1
            color_ball[y].add(x)
            ball_color[x] = y
            ans[i] = color  # len(color_ball.keys())
        return ans

Better solution

class Solution:
    def queryResults(self, _: int, queries: List[List[int]]) -> List[int]:
        ans = []
        color = {}
        cnt = defaultdict(int)
        for x, y in queries:
            if x in color:
                c = color[x]
                cnt[c] -= 1
                if cnt[c] == 0:
                    del cnt[c]
            color[x] = y
            cnt[y] += 1
            ans.append(len(cnt))
        return ans

Q4 Block Placement Queries

There exists an infinite number line, with its origin at 0 and extending towards the positive x-axis.

You are given a 2D array queries, which contains two types of queries:

  1. For a query of type 1, queries[i] = [1, x]. Build an obstacle at distance x from the origin. It is guaranteed that there is no obstacle at distance x when the query is asked.
  2. For a query of type 2, queries[i] = [2, x, sz]. Check if it is possible to place a block of size sz anywhere in the range [0, x] on the line, such that the block entirely lies in the range [0, x]. A block cannot be placed if it intersects with any obstacle, but it may touch it. Note that you do not actually place the block. Queries are separate.

Return a boolean array results, where results[i] is true if you can place the block specified in the ith query of type 2, and false otherwise.

Example 1:

Input: queries = [[1,2],[2,3,3],[2,3,1],[2,2,2]]

Output: [false,true,true]

Explanation:

For query 0, place an obstacle at x = 2. A block of size at most 2 can be placed before x = 3.

Example 2:

Input: queries = [[1,7],[2,7,6],[1,2],[2,7,5],[2,7,6]]

Output: [true,true,false]

Explanation:

Constraints:

My solution during the contest

class Solution:
    def getResults(self, queries: List[List[int]]) -> List[bool]:
        pass

Better solution

平衡树+线段树

from sortedcontainers import SortedList

class Solution:
    def getResults(self, queries: List[List[int]]) -> List[bool]:
        m = max(q[1] for q in queries) + 1
        t = [0] * (2 << m.bit_length())

        # 把 i 处的值改成 val
        def update(o: int, l: int, r: int, i: int, val: int) -> None:
            if l == r:
                t[o] = val
                return
            m = (l + r) // 2
            if i <= m:
                update(o * 2, l, m, i, val)
            else:
                update(o * 2 + 1, m + 1, r, i, val)
            t[o] = max(t[o * 2], t[o * 2 + 1])

        # 查询 [0,R] 中的最大值
        def query(o: int, l: int, r: int, R: int) -> int:
            if r <= R:
                return t[o]
            m = (l + r) // 2
            if R <= m:
                return query(o * 2, l, m, R)
            return max(t[o * 2], query(o * 2 + 1, m + 1, r, R))

        sl = SortedList([0, m])  # 哨兵
        ans = []
        for q in queries:
            x = q[1]
            i = sl.bisect_left(x)
            pre = sl[i - 1]  # x 左侧最近障碍物的位置
            if q[0] == 1:
                nxt = sl[i]  # x 右侧最近障碍物的位置
                sl.add(x)
                update(1, 0, m, x, x - pre)    # 更新 d[x] = x - pre
                update(1, 0, m, nxt, nxt - x)  # 更新 d[nxt] = nxt - x
            else:
                # 最大长度要么是 [0,pre] 中的最大 d，要么是 [pre,x] 这一段的长度
                max_gap = max(query(1, 0, m, pre), x - pre)
                ans.append(max_gap >= q[2])
        return ans
Edit page
Share this post:
Share this post on Whatsapp Share this post on Facebook Share this post on X Share this post on Telegram Share this post on Pinterest Share this post via email
Previous Post
用友技术笔试-友新星实习项目-Java
Next Post
HSBC Summer 24 Coding Test