博客主页 🏗️
wy的leetcode刷题记录_Day82
wy的leetcode刷题记录_Day82

Author:

wy-1226

©

Wordage:

共计 12504 字

needs:

约 6 分钟

Popular:

223 ℃

Created:

目 录

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;
    }
};

收获

文章二维码
wy的leetcode刷题记录_Day82
共计 0 条评论,点此发表评论
博客主页 wyのblog I know you are here. 百度统计
鄂ICP备2023003777号-1 本站已运行 324 天 13 小时 25 分 自豪地使用 Typecho 建站,并搭配 MyDiary 主题 Copyright © 2023 ~ 2024. wyのblog All rights reserved.
打赏图
打赏博主
欢迎
搜 索
足 迹
分 类
  • 默认分类
  • Code
  • 日记
  • 音乐
  • 游戏
  • 阅读
  • 计划
  • 图片
  • 旅游
  • 影视