wy的leetcode刷题记录_Day83

声明

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

前言

@TOC

2834. 找出美丽数组的最小和

今天的每日一题是：
2834. 找出美丽数组的最小和

题目介绍

给你两个正整数：n 和 target 。

如果数组 nums 满足下述条件，则称其为美丽数组。

nums.length == n.
nums 由两两互不相同的正整数组成。
在范围 [0, n-1] 内，不存在两个不同下标 i 和 j ，使得 nums[i] + nums[j] == target 。
返回符合条件的美丽数组所可能具备的最小和，并对结果进行取模 109 + 7。

示例 1：
输入：n = 2, target = 3
输出：4
解释：nums = [1,3] 是美丽数组。
nums 的长度为 n = 2 。
nums 由两两互不相同的正整数组成。
不存在两个不同下标 i 和 j ，使得 nums[i] + nums[j] == 3 。
可以证明 4 是符合条件的美丽数组所可能具备的最小和。
示例 2：
输入：n = 3, target = 3
输出：8
解释： nums =[1,3,4] 是美丽数组。
nums 的长度为 n = 3 。
nums 由两两互不相同的正整数组成。
不存在两个不同下标 i 和 j ，使得 nums[i] + nums[j] == 3 。
可以证明 8 是符合条件的美丽数组所可能具备的最小和。
示例 3：
输入：n = 1, target = 1
输出：1
解释：nums = [1]是美丽数组

思路

贪心：本题要求寻找长度为n其中任意两元素之和不等于target的不重复的序列的最小和，对于不重复我们可以按升序寻找，两元素之和不等于target意味着加入a在序列中那么就不能将target-a放入序列，又因为是寻找最小和，那么我们考虑第一段序列为从0到target/2（向下取整），而剩下的序列我们从target+1往后（包括target+1）依次寻找n-target2个即可。

代码

class Solution {
public:
    int minimumPossibleSum(int n, int target) {
        if(n==1)
            return 1;
        long temp=min(n,target/2);
        return (((1+temp)*temp+(n-temp)*(2L*target+n-temp-1))/2)%1000000007;

    }
};

收获

贪心模拟。

328. 奇偶链表

题目介绍

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。

第一个节点的索引被认为是奇数，第二个节点的索引为偶数，以此类推。

请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。

你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

示例 1:

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

示例 2:

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

思路

之前我记得有一道题也是切分链表的题用双链表，其中一个链表要反转最后相互交叉。这道题也是一样的将整个链表切分为两个链表，奇数链表和偶数链表，最后再将奇数链表的表尾指针指向偶数链表的表头即可。

代码

/**
 * 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) {}
 * };
 */
/**
 * 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* oddEvenList(ListNode* head) {

        if(head==nullptr||head->next==nullptr)
            return head;
    
        ListNode* odd=head;
        ListNode* even=head->next;
        ListNode* evenHead=head->next;
        while(even!=nullptr&&even->next!=nullptr)
        {
            
            odd->next=even->next;
            odd=odd->next;
            even->next=odd->next;
            even=even->next;    
        }
        // if(odd->next->next)
        // {
        //     odd->next=odd->next->next;
        //     odd=odd->next;
        // }   
        // even->next=nullptr;
        odd->next=evenHead;

        return head;

    }
};

收获

简单题

355. 设计推特

题目介绍

设计一个简化版的推特(Twitter)，可以让用户实现发送推文，关注/取消关注其他用户，能够看见关注人（包括自己）的最近 10 条推文。

实现 Twitter 类：

Twitter() 初始化简易版推特对象
void postTweet(int userId, int tweetId) 根据给定的 tweetId 和 userId 创建一条新推文。每次调用此函数都会使用一个不同的 tweetId 。
List getNewsFeed(int userId) 检索当前用户新闻推送中最近 10 条推文的 ID 。新闻推送中的每一项都必须是由用户关注的人或者是用户自己发布的推文。推文必须按照时间顺序由最近到最远排序。
void follow(int followerId, int followeeId) ID 为 followerId 的用户开始关注 ID 为 followeeId 的用户。
void unfollow(int followerId, int followeeId) ID 为 followerId 的用户不再关注 ID 为 followeeId 的用户。

示例：
输入:
["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"] [[], [1, 5], [1], [1, 2],[2, 6], [1], [1, 2], [1]]
输出:
[null, null, [5], null, null, [6, 5],null, [5]]
解释 :
Twitter twitter = new Twitter(); twitter.postTweet(1, 5); // 用户 1发送了一条新推文 (用户 id = 1, 推文 id = 5)
twitter.getNewsFeed(1); // 用户 1 的获取推文应当返回一个列表，其中包含一个 id 为 5 的推文
twitter.follow(1, 2); // 用户 1 关注了用户 2 twitter.postTweet(2, 6); // 用户 2 发送了一个新推文 (推文 id = 6)
twitter.getNewsFeed(1); // 用户 1 的获取推文应当返回一个列表，其中包含两个推文，id 分别为 -> [6, 5] 。推文 id 6 应当在推文 id 5 之前，因为它是在 5 之后发送的 twitter.unfollow(1, 2); // 用户 1 取消关注了用户 2 twitter.getNewsFeed(1); // 用户 1 获取推文应当返回一个列表，其中包含一个 id 为 5 的推文。因为用户 1 已经不再关注用户 2

思路

借鉴题解一位老哥很规范的设计模式。

代码

int global_Time=0;
//推文类
class Tweet{
   public:
   int id;
   int time;
   Tweet *next;
   Tweet(int id)
   {
       this->id=id;
       this->time=global_Time++;
       next=nullptr;
   } 
};

//用户类
class User
{
public:
    int id;
    Tweet *tweet;//该用户发布的推文链表
    unordered_set<int> follows;//该用户关注的用户

    User(int id)
    {
        this->id=id;
        tweet=nullptr;
    }

    void follow(int followee)
    {
        if(followee==this->id)    return;
        follows.insert(followee);
    }

    void unfollow(int followee)
    {
        if(followee==this->id)    return;
        follows.erase(followee);
    }

    void post(int tweetID)
    {
        Tweet * newTweet=new Tweet(tweetID);
        newTweet->next=tweet;//头插法
        tweet=newTweet;
    }
};

class Twitter{
    private:
        unordered_map<int,User*> user_map;//所有用户
        bool contain(int id )
        {
            return user_map.find(id)!=user_map.end();
        }

    public:
        Twitter(){
            user_map.clear();//init
        }
        void postTweet(int UserID,int tweetID)
        {
            if(!contain(UserID))
            {
                user_map[UserID]=new User(UserID);
            }
            user_map[UserID]->post(tweetID);
        }

        vector<int> getNewsFeed(int UserID)
        {
            if(!contain(UserID))    return {};

            struct cmp{
                bool operator()(const Tweet *a,const Tweet *b)
                {
                    return a->time<b->time;
                }
            };

            //大顶堆
            priority_queue<Tweet* ,vector<Tweet*>,cmp> q;
            //自己的推文
            if(user_map[UserID]->tweet)
            {
                q.push(user_map[UserID]->tweet);
            }
            //关注的推文
            for(auto followeeId:user_map[UserID]->follows)
            {
                if(!contain(followeeId))
                {
                    continue;
                }
                Tweet *head=user_map[followeeId]->tweet;
                if(head==nullptr)   continue;
                q.push(head);
            }
            vector<int> rs;
            while (!q.empty()) {//优先队列实现大顶堆
                Tweet *t = q.top(); 
                q.pop();
                rs.push_back(t->id);
                if (rs.size() == 10) return rs;
                if (t->next) {
                    q.push(t->next);
                }
            }
            return rs;

        }

        // 用户followerId 关注 用户followeeId.
        void follow(int followerId, int followeeId) {
            if (!contain(followerId)) {
                user_map[followerId] = new User(followerId);
            }
            //面向对象
            user_map[followerId]->follow(followeeId);
        }
        
        // 用户followerId 取关 用户followeeId.
        void unfollow(int followerId, int followeeId) {
            if (!contain(followerId)) return;
            //面向对象
            user_map[followerId]->unfollow(followeeId);
        }

};

收获

优先队列最近遇到好多，也算是了解了一些。这道题的优先队列用于实现大顶堆，而这种分类的设计模式也是好久没写过了，之前还是大二的时候上C++的时候有机会去写一写，现在压根不看...

382. 链表随机节点

题目介绍

给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点被选中的概率一样。
实现 Solution 类：

Solution(ListNode head) 使用整数数组初始化对象。
int getRandom() 从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。

示例：
输入:
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"] [[[1, 2, 3]], [], [], [], [], []]
输出:
[null, 1, 3, 2, 2,3]
解释 :
Solution solution = new Solution([1, 2, 3]);
solution.getRandom();// 返回 1
solution.getRandom(); // 返回 3
solution.getRandom(); // 返回 2
solution.getRandom(); // 返回 2
solution.getRandom(); // 返回 3
//getRandom() 方法应随机返回 1、2、3中的一个，每个元素被返回的概率相等。

思路

emmmm，说实话这道题很难评，乍一看真没看懂，啥随机返回。奥搞了半天调用个随机函数然后随机返回第几位的节点。然后我就用了最直接的方法（笨蛋解法），用一个数组保存链表然后再用随机函数生成下标，最后返回即可。这样操作时间复杂度O(1)，空间复杂度O(n)。

代码

/**
 * 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:
    int n = 0;
    vector<int> list1;
    Solution(ListNode* head) {
        ListNode* temp=head;
        while(temp)
        {
            n++;
            list1.push_back(temp->val);
            temp=temp->next;
        }


    }
    
    int getRandom() {
        int count=rand()%n;
        return list1[count];
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(head);
 * int param_1 = obj->getRandom();
 */

收获

无

49. 字母异位词分组

题目介绍

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

字母异位词是由重新排列源单词的所有字母得到的一个新单词。

示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]

思路

看了题目我也是一头雾水，怎么比较两个相同字母组成的异位词，于是我看了评论区一个大佬的解法，就想通了：我们都知道质数的因子只有自己和本身，使用质数来代表26个字母，将每个单词的字母所代表的质数相乘的出来的值，只有拥有相同个数的同种字母才能得到也就是异位词。

代码

收获

128. 最长连续序列

题目介绍

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

思路

这道题同样也参考了题解：首先使用set将原数组中重复的元素筛只剩一个，然后遍历整个数组，要判断一个数是否是一个最长连续序列的第一个元素（否则造成冗余计算），只需要判断set中是否存在当前元素-1即可，最后维护最大程度即可。

代码

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> sett;
        for(auto num:nums)
        {
            sett.insert(num);
        }
        int longgest=0;

        for(int num:nums)
        {
            if(!sett.count(num-1))
            {
                int curNum=num;
                int curLen=1;
                while(sett.count(curNum+1))
                {
                    curNum++;
                    curLen++;
                }
                longgest=max(longgest,curLen);
            }
        }

        return longgest;
    }
};

收获

set的使用。