LeetCode 六月每日一题

*1 你能在你最喜欢的那天吃到你最喜欢的糖果吗（Mid）

解法：前缀和+区间交集

原理：

favoriteDay内吃糖的总数区间 X = [favoriteDay + 1， (favoriteDay + 1) * dailyCap]，即左边界为每天只吃一个，右边界为每天吃到最大

可以吃到favoriteType的区间 Y = [sum[favoriteType - 1] + 1, sum[favoriteType]]，即最少只吃到一个，最多吃到最后一个（吃完）

只要两区间有交集，总有吃法使得在favoriteDay当天吃到favoriteType类的糖。

边界情况：当favoriteType == 0时，Y的左边界为1，即只要吃一个糖就能吃到第0类

class Solution {
public:
    using LL = long long;
    vector<bool> canEat(vector<int>& candiesCount, vector<vector<int>>& queries) {
        vector<LL> sum(candiesCount.size());
        // 1. 前缀和
        sum[0] = candiesCount[0];
        for (int i = 1; i < candiesCount.size(); i++)
        {
            sum[i] = sum[i - 1] + candiesCount[i];
        }
        // 2. 获取queries，比对区间计算ans
        vector<bool> ans;
        for (auto& qr : queries)
        {
            int favType = qr[0], favDay = qr[1], dailyCap = qr[2];

            LL x1 = favDay + 1;
            LL x2 = (LL)(favDay + 1) * dailyCap;    // 需要强转，否则会溢出
            LL y1 = (favType == 0)? 1 : sum[favType - 1] + 1;
            LL y2 = sum[qr[0]];

            ans.push_back(!(x2 < y1 || y2 < x1));	// 判断
        }
        // 3. 返回
        return ans;
    }
};

小结：

时间复杂度$O(n)$，空间复杂度$O(n)$
使用区间交集的解法判断在一定约束条件下能否满足特定取物行为。

2 连续子数组的和（Mid）

523. 连续的子数组和

思路类似May_25中涉及到的题目560. 和为K的子数组

解法：前缀和+哈希

原理

子数组的和可以表示为 sum = pre[i] - pre[j - 1]

要找到 sum = n * k，变换一下等式，即找到 pre[j - 1] = pre[i] - nk

两边同模k，得pre[j - 1] % k = pre[i] % k

因此将前缀和模k作为哈希表的key，最早出现的下标作为value，从左往右遍历查表即可

初始情况：哈希表mp[0] = -1，即最早出现前缀和模k为0的位置是-1（若遍历到i时查到此值，表示从0到i的子数组之和满足题意）

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        if (n < 2)
            return false;
        
        // 1. hash存前缀和%k；2. 查是否存在pre[i]%k的值
        unordered_map<int, int> mp;
        // int pre = nums[0];
        int pre = 0;
        mp[0] = -1;

        for (int i = 0; i < n; i++)
        {
            pre = (pre + nums[i]) % k;
            if (mp.find(pre) != mp.end())
            {
                if (i - mp[pre] >= 2)
                    return true;
            }
            else
                mp[pre] = i;
        }
        return false;
    }
};

3 连续数组（Mid）

525. 连续数组

解法：前缀和+哈希

原理：

将数组中的0替换为-1，则问题转化为：计算和为0的子数组最大长度

令前缀和为pre，只需令[i..j]的前缀和pre[i] - pre[j - 1] = 0，即找到pre[j - 1 = pre[i]

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        // 1. 0替换为-1
        for (auto& x : nums)
        {
            x = (x == 0)? -1 : x;
        }
        // 2. 哈希记录所有前缀和的下标
        unordered_map<int, int> mp;
        int pre = 0;
        mp[0] = -1;
        // 3. 找相等，计算长度
        int maxLen = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            pre += nums[i];
            if (mp.find(pre) != mp.end())
            {
                maxLen = max(i - mp[pre], maxLen);
            }
            else
                mp[pre] = i;
        }
        return maxLen;
    }
};

但是上述代码存在缺陷：修改了传入的数组，根据题解思路进行优化，只在计算时替换数值：

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        // 哈希记录所有前缀和的下标
        unordered_map<int, int> mp;
        int pre = 0;
        mp[0] = -1;

        // 找相等，计算长度
        int maxLen = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            pre += (nums[i] == 0)? -1 : 1;  // **计算前缀和时进行替换
            if (mp.find(pre) != mp.end())
            {
                maxLen = max(i - mp[pre], maxLen);
            }
            else
                mp[pre] = i;
        }
        return maxLen;
    }
};

小结：

时间复杂度$O(n)$，空间复杂度$O(n)$
前缀和+哈希刻进了DNA里

4 相交链表（Easy）

160. 相交链表

解法一：提前步进

原理

假设两个链表长度分别为len1，len2且有len1 > len2，令长的一方先走len1 - len2步，此时双方同时前进，到达相同位置即为相交点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // 1 区分长和短方
        int lenA = 0, lenB = 0;
        for (auto p = headA; p != NULL; p = p->next, lenA++);
        for (auto p = headB; p != NULL; p = p->next, lenB++);

        // 2 计算长度差delta，长的一方提前走delta步
        ListNode *p, *q;
        int delta;

        if (lenA > lenB)
        {
            delta = lenA - lenB;
            for (p = headA; delta > 0; p = p->next, delta--);
            q = headB;
        }
        else if (lenA < lenB)
        {
            delta = lenB - lenA;
            for (p = headB; delta > 0; p = p->next, delta--);
            q = headA;
        }
        else
        {
            p = headA;
            q = headB;
        }
        // 3 双方同时步进并比较
        while (p != NULL && q != NULL)
        {
            if (p == q)
                return p;
            p = p->next; q = q->next;
        }
        return NULL;
    }
};

时间复杂度$O(n)$，空间复杂度$O(1)$

解法二（题解）：双指针

做法：

每步操作需要同时更新指针pA 和 pB；

如果指针pA不为空，则将指针pA移到下一个节点；如果指针pB不为空，则将指针pB移到下一个节点。

如果指针pA为空，则将指针pA移到链表headB的头节点；如果指针pB为空，则将指针pB移到链表 headA的头节点。

当指针pA和pB指向同一个节点或者都为空时，返回它们指向的节点或者null。

原理：

设链表A和B不同的部分分别为a，b，相同的部分为c

若A和B相交，pA走过的部分为a+c+b，pB走过的部分为b+c+a，此时pA和pB都会走到相交点的位置；

若A和B不相交，pA走过a+b，pB走过b+a，二者都会到达链表尾，返回NULL

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == NULL || headB == NULL)
            return NULL;

        ListNode *pA = headA, *pB = headB;
        while (pA != pB)
        {
            pA = (pA == NULL)? headB : pA->next;
            pB = (pB == NULL)? headA : pB->next;
        }
        return pA;
    }
};

时间复杂度$O(n)$，空间复杂度$O(1)$。

5 移除链表元素（Easy）

203. 移除链表元素

解法一：迭代+哑结点

原理：

哑结点是head前的一个辅助结点，使用哑结点就不用考虑删除head的特殊情况了

从哑结点开始遍历，寻找待删除结点的前一个结点p，由 p.next = p.next.next 即可删除

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // 1 插入哑结点
        ListNode *dummy = new ListNode(0, head);

        // 2 遍历
        auto p = dummy;
        
        while (p->next != nullptr)
        {
            if (p->next->val == val)
            {
                auto q = p->next;
                p->next = q->next;	// 软删除
                delete(q);		// 硬删除
            }
            else
                p = p->next;
        }
        // 3 更新头
        head = dummy->next;
        delete(dummy);		// 删除哑结点
        return head;
    }
};

小结：

时间复杂度$O(n)$，空间复杂度$O(1)$
哑结点yyds！！

解法二（题解）：递归

原理：

利用链表的递归性质，先操作 head->next，再判断 head。递归边界为 head == nullptr

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if (head == nullptr) {
            return head;
        }
        head->next = removeElements(head->next, val);
        return head->val == val ? head->next : head;
    }
};

小结

时间复杂度$O(n)$，空间复杂度$O(n)$（递归调用栈最多n层）

*1 你能在你最喜欢的那天吃到你最喜欢的糖果吗（Mid）

2 连续子数组的和（Mid）

3 连续数组 （Mid）

4 相交链表（Easy）

5 移除链表元素（Easy）

3 连续数组（Mid）