【2023】字节跳动 10 日心动计划—

这篇具有很好参考价值的文章主要介绍了【2023】字节跳动 10 日心动计划——第六关。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1. 环形链表 II

🔗 原题链接：142. 环形链表 II

用哈希表判重即可。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode*> st;
        while (head) {
            if (st.count(head)) return head;
            st.insert(head);
            head = head->next;
        }
        return nullptr;
    }
};

2. 有序数组中的单一元素

🔗 原题链接：LCR 070. 有序数组中的单一元素

这里介绍两种做法。

方法一：异或。注意到 $x\oplus x=0$ ，因此 $\oplus_{i=1}^nnums[i]$ 就是最终答案。

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int ans = 0;
        for (auto& num: nums) ans ^= num;
        return ans;
    }
};

方法二：二分。注意到数组是有序的，因此我们可以用二分去处理，时间复杂度可以降至 $O(\log n)$ 。

不妨设只出现一次的元素的下标是 $x$ ，由题意可知下标 $x$ 的左右两边各有偶数个元素，从而 $x$ 是偶数，且数组的长度是奇数，不妨设为 $n$ 。

既然要用二分，那我们就需要找到一个性质能够将区间 $[0, n - 1]$ 一分为二。注意到 $\forall i\in[0,x-1]$ ，如果 $n u m s [i] = n u m s [i + 1]$ ，那么 $i$ 一定是偶数； $\forall i\in[x,n-1]$ ，如果 $n u m s [i] = n u m s [i + 1]$ ，那么 $i$ 一定是奇数。

更进一步， $\forall i\in[0,n-1]$ ，如果 $i$ 是偶数，我们判断 $n u m s [i]$ 和 $n u m s [i + 1]$ 是否相等，如果相等，则 $i\in[0,x-1]$ ，否则 $i\in[x,n-1]$ ；如果 $i$ 是奇数，则 $i - 1$ 是偶数，我们判断 $n u m s [i - 1]$ 和 $n u m s [i]$ 是否相等，如果相等，则 $i\in[0,x-1]$ ，否则 $i\in[x,n-1]$ 。

注意到当 $i$ 是偶数时， $i+1=i\oplus1$ ，当 $i$ 是奇数时， $i-1=i\oplus1$ ，从而我们只需要判断 $n u m s [i]$ 和 $nums[i\oplus 1]$ 是否相等。条件 $nums[i]\neq nums[i\oplus1]$ 将区间 $[0, n - 1]$ 分成了两部分： $[0, x)$ 和 $[x, n - 1]$ ，前者不满足这个条件，后者满足这个条件，所以我们可以套用寻找左边界的二分模版。文章来源地址https://www.toymoban.com/news/detail-632595.html

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] != nums[mid ^ 1]) r = mid;
            else l = mid + 1;
        }
        return nums[r];
    }
};