wy的leetcode刷题记录_Day82

声明

本文章的所有题目信息都来源于leetcode
如有侵权请联系我删掉!
时间：2024-3-6

前言

@TOC

2917. 找出数组中的 K-or 值

今天的每日一题是：2917. 找出数组中的 K-or 值

题目介绍

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

nums 中的 K-or 是一个满足以下条件的非负整数：

• 只有在 nums 中，至少存在 k 个元素的第 i 位值为 1 ，那么 K-or 中的第 i 位的值才是 1 。

返回 nums 的 K-or 值。

注意 ：对于整数 x ，如果 (2i AND x) == 2i ，则 x 中的第 i 位值为 1 ，其中 AND 为按位与运算符。

示例 1：

输入：nums = [7,12,9,8,9,15], k = 4
输出：9
解释：nums[0]、nums[2]、nums[4] 和nums[5] 的第 0 位的值为 1 。
nums[0] 和 nums[5] 的第 1 位的值为 1 。
nums[0]、nums[1]和 nums[5] 的第 2 位的值为 1 。
nums[1]、nums[2]、nums[3]、nums[4] 和 nums[5] 的第 3 位的值为 1 。
只有第 0 位和第 3 位满足数组中至少存在 k 个元素在对应位上的值为 1 。
因此，答案为 2^0 + 2^3 = 9。

示例 2：
输入：nums = [2,12,1,11,4,5], k = 6
输出：0
解释：因为 k == 6 == nums.length，所以数组的 6-or 等于其中所有元素按位与运算的结果。
因此，答案为 2 AND 12 AND 1 AND 11 AND 4 AND 5= 0 。

示例 3：

输入：nums = [10,8,5,9,11,6,8], k = 1
输出：15
解释：因为 k == 1 ，数组的 1-or等于其中所有元素按位或运算的结果。因此，答案为 10 OR 8 OR 5 OR 9 OR 11 OR 6 OR 8 = 15 。

思路

简单的模拟枚举：首先简历一个长度为32哈希表count（对应32位数），然后遍历nums，统计每一个num的二进制位然后count对应的二进制位自增，最后遍历count中的值与k的值计算得出答案。

代码

class Solution {
public:
    int findKOr(vector<int>& nums, int k) {
        int n=nums.size();
        vector<int> count(32,0);
        int ans=0;

        for(auto num:nums)
        {
            int i=0;
            while(num!=0)
            {
                if(num&1==1)
                {
                    count[i]++;
                }
                i++;
                num=num>>1;
            }
        }
        for(int i=0;i<32;i++)
        {
            if(count[i]>=k)
            {
                ans+=1<<i;
            }
        }
        return ans;
    }
};

收获

对于整数 x ，如果 (2i AND x) == 2i ，则 x 中的第 i 位值为 1 ，其中 AND 为按位与运算符。快速判断二进制位。

143. 重排链表

143. 重排链表

题目介绍

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

输入：head = [1,2,3,4]
输出：[1,4,2,3]

示例 2：

输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]

思路

我的想法是，将链表拆成前半段和后半段，然后反转后半段链表，最后将这俩个链表拼接起来即可。反转链表在前几天已经做了几次了这里就不多说，拆分链表的话也是用我们的老朋友快慢指针，慢指针走一步快指针走两步，当快指针走到尾部时，慢指针刚好处于链表中间，将链表分为两部分。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverse(ListNode* head)
    {
        ListNode* pre=nullptr;
        ListNode* cur=head;
        while(cur)
        {
            ListNode* temp=cur->next;

            cur->next=pre;
            pre=cur;
            cur=temp;
        }
        return pre;
    }

    void reorderList(ListNode* head) {
        ListNode* slow=head;
        ListNode* fast=head;
        while(fast->next!=nullptr&&fast->next->next!=nullptr)
        {
            slow=slow->next;
            fast=fast->next->next;
        }

        ListNode* newHead=slow->next;
        slow->next=nullptr;
        newHead=reverse(newHead);

        while(newHead)
        {
            ListNode* temp=newHead->next;
            newHead->next=head->next;
            head->next=newHead;
            head=newHead->next;
            newHead=temp;
        }

    }
};

收获

无

146. LRU 缓存

146. LRU 缓存

题目介绍

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入:
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出:
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释 :
LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

思路

本题需要维护一个队列，俩个哈希表。一个int变量sum用来保存当前队列中不同元素的个数，队列Q用来记录在超出缓存之前进行get和put操作的元素key值，哈希表count用来记录某一个元素get和put操作的次数，哈希表val表示kv关系。每次替换发生的时机在put一个元素并进行检查时sum>capacity，这个时候我们需要对队列进行清空，每弹出一个元素则需要对应count[key]递减，直到某一个key的count变为0说明他最近用的少，最后用新元素替换该key。

代码

class LRUCache {
public:
const int maxn = 2e5 + 5;
    queue<int> Q;
    vector<int> count,val;
    int sum=0,cap=0;

    LRUCache(int capacity) {
        cap=capacity;
        count=vector(maxn,0);
        val=vector(maxn,0);
    }
    
    int get(int key) {
        if(count[key]>0)
        {
            count[key]++;
            Q.push(key);
            return val[key];
        }
        else
        {
            return -1;
        }
    }
    
    void put(int key, int value) {
        if(count[key]==0) sum++;
        val[key]=value;
        
        Q.push(key);
        count[key]++;
        
        if(sum>cap)
        {
            while(1)
            {
                int temp=Q.front();
                Q.pop();
                if(--count[temp]==0)
                {
                    sum--;
                    break;
                }
            }
        }

    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

收获

很难，这题看别人的思路才写得出来，而且很多bug，耗费时间也很长，希望二刷的时候能真正自己快速写出来。

147. 对链表进行插入排序

147. 对链表进行插入排序

题目介绍

给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。

插入排序 算法的步骤:

• 1.插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
• 2.每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
• 3.重复直到所有输入数据插入完为止。

下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。

对链表进行插入排序。

示例 1：

输入: head = [4,2,1,3]
输出: [1,2,3,4]

示例 2：

输入: head = [-1,5,3,4,0]
输出: [-1,0,3,4,5]

思路

相信大家都一定了解插入排序，类似抽牌一样，每次插入前都是有序的数列保证插入后也是有序的数列。根据这个理念我们来实现具体细节，其中我们需要一个哑节点来保证能返回原来的链表（因为头节点可能发生变化），其次我们需要一个节点temp来保存当前排序到的位置，即temp前排序完成，temp后待排序。然后在temp后进行搜寻的时候我们同样需要一个pre和一个cur来将选中节点从原链表中取出最终拆入到temp后面即可。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode *dummy=new ListNode(0,head);
        ListNode *temp=dummy;
        int n=0;
        while(head)
        {
            head=head->next;
            n++;
        }
        for(int i=0;i<n-1;i++)
        {
            ListNode* pre=temp;
            if(temp->next==nullptr)
                break;
            head=temp->next;
            int minVal=head->val;
            while(head)
            {
                minVal=min(minVal,head->val);
                head=head->next;
            }

            head=temp->next;

            while(head)
            { 
                if(head->val==minVal)
                {
                    pre->next=head->next;
                    head->next=temp->next;
                    temp->next=head;
                    break;
                }
                pre=head;
                head=head->next;
            }
            temp=temp->next;
        }
        return dummy->next;
    }
};

收获

熟练了链表的操作，温故了插入排序。

160. 相交链表

160. 相交链表

题目介绍

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

• intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
• listA - 第一个链表
• listB - 第二个链表
• skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
• skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA= 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。 在 A 中，相交节点前有 2个节点；在 B 中，相交节点前有 3 个节点。 — 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例 2：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。 由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。 这两个链表不相交，因此返回 null 。

思路

我直接用傻瓜做法：计算俩个链表的长度之差c，让较长的链表先遍历c步，然后同时遍历两个链表判断是否指向同一个节点即可。

代码

/**
 * 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) {
        int a=0,b=0;
        ListNode* temp=headA;
        while(temp)
        {
            a++;
            temp=temp->next;
        }
        temp=headB;
        while(temp)
        {
            b++;
            temp=temp->next;
        }
        int c=abs(b-a);
        if(b>a)
        {
            while(c--)
            {
                headB=headB->next;
            }
        }
        else
        {
            while(c--)
            {
                headA=headA->next;
            }
        }
        while(headA!=headB&&headA!=nullptr)
        {
            headA=headA->next;
            headB=headB->next;
        }
        if(headA)
            return headA;
        return nullptr;
        
    }
};

收获

无

203. 移除链表元素

203. 移除链表元素

题目介绍

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1
输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

思路

双指针，一个指针用来遍历，另一个指针用来保存遍历节点的上一个节点以方便进行删除。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummy=new ListNode(-1,head);
        ListNode* pre=dummy;
        while(head)
        {
            if(head->val==val)
            {
                pre->next=head->next;
                head=head->next;
            }
            else
            {
                pre=head;
                head=head->next;
            }

        }
        return dummy->next;
    }
};

收获

无