简介：机器视觉与深度学习基础知识补漏Week1线性分类器分类器设计总体流程下图是分类器设计总体流程图像表示二值化图像；(0or1)灰度图像；(0 255 单通道)彩色图像；(三通道RGB)分类模型线性分类器：f（x,w）计算分类得分，选取其中最高的分类得分作为分类输出。其中w其实是作为权重矩阵，w表示对图像中特殊部分进行突出显示，b为偏置项。（模板）线性分类器其实就是寻找分类的决策边界。通过决策边界来判断样本的分类情况。### 损失函数损失值：真实值和预测值的差值。一般数据集的损失函数定义：多累支撑向量机损失：其中存在一个+1操作，是为了防止两类误差分类预测值相近，虽然预测正确，但是分类器仍需优化的情况。引入正则损失（对参数的损失，参数平衡）。其中包含一个超参数用来调整数据损失和正则损失的权重关系。优化算法目标旨在：寻找使得损失函数达到最小时的那一组W参数。直接方法：使得损失函数对W求导得0。梯度下降算法：梯度下降的方向以及步长（lr）。具体流程：计算梯度 >更新梯度梯度计算方法：1.按照导数公式求导，(f(x+n) f(x))/n这一套。2.使用解析法，现有的求导公式。随机梯度下降法：相较于梯度下降法，其是随机使用一个样本进行计算梯度，减少了计算量，在大量的数据下其正向优化效果能掩盖噪声带来的负面影响。小批量梯度下降法：每次随机选取m个样本计算梯度。m=1时就是随机梯度下降法。iteration;batch_size;epoch;数据集划分：这里搞清楚了验证集和训练集的区别：训练集只能用俩评估最终模型的性能；验证集是用来判定不同朝参属下的模型的性能，本质上用于选择超参数；训练集用来训练模型里面的参数；K折交叉验证：数据量小的时候使用，分为shuffled和not..数据预处理（去范围，去量纲）：全连接神经网络网络结构激活函数常用的激活函数：损失函数SOFTMAX：将输出分数压缩到0 1内，即一个概率分布。相较于之前的输出分数，这里我们输出的是一个概率。因此对应的损失函数也应该改变。交叉熵损失：对于SOFTMAX预测概率和真实one hot编码的真实值进行损失值计算的方法。这里介绍了三个概念：熵、交叉熵和相对熵；其关系是交叉熵=熵+相对熵。由于在我们的分类任务中，确定分类结果的熵为0，所以我们可以使用交叉熵来代替相对熵来度量两个分布的不相似性。我们再将之前了解的多类支持向量机损失和交叉熵损失进行比较：其计算过程也不同。前者将每一类预测得分 真实值求和；而后者则使用真实的类别预测概率做负对数求损失。举个例子：计算图计算图是一种有向图，它用来表达输入、输出及中间变量的计算关系，图中的每一个节点对应着一种数学运算。计算图可以更好的帮我们表示计算机中表达式运算的过程，尤其是在反向传播中进行求梯度的链式求导的过程。小知识点：计算图的颗粒度。使用计算颗粒度大的门，也就是这个门不仅仅是一个符号，而是一个公式，会大大减小我们的计算量，提高计算效率，但是这种门/公式得需要自己设计。动量法对于SGD，其可能存在山谷问题，导致出现震荡。引入动量法，实际上就是引入了历史梯度信息协同更新梯度。这里引入了动量系数，用以表示历史梯度信息所占的权重（可以理解为摩擦系数）。动量法的另一个优势：通过一个历史梯度能将我们推出鞍点这个范围。另一种方法：自适应梯度法自适应梯度法：本质就是在震荡的方向减小其步长，在平缓的方向增大其步长。而对于如何分辨震荡和平缓，其依据是梯度幅度的平方大小，大的为震荡方向，小的为平缓方向。缺陷就是：随着步数的累计，历史梯度值越来越大，导致整体步长被压制，步长越来越小。为了解决这个缺陷同样引入了一个权值（类似动量），用以控制历史梯度值的影响范围。动量法和自适应梯度法结合：Adam。这里有一个细节：由于在累计梯度和累计平方梯度时，导致一开始的用来更新权值的梯度被缩小（冷启动），模型很难收敛，因此提出了一个修正偏差。其保证了初试的修正动量和修正自适应梯度能保持原有的梯度，在经过一段时间的更新后，缩小当前梯度的影响，放大两者结合的优点（累计梯度和累计平方梯度）。权值初始化首先要避免全0初始化，这样导致输出全为0，并且方向传播时的梯度也一样，最后更新后的权值也全部一样，也就是所有神经元学习到的东西全部一样，等价为1一个神经元，导致无法训练。其次权值随机初始化，保证权值服从N（0，0.01）的高斯分布。但是我们发现在第三个及之后的隐层的输出全为0，也就是前向传播的信息全部丢失了。并且因此在反向传播时局部梯度也为0，反向传播也消失。我们的神经元全部处于饱和阶段，正向传播信息传递过去了，但是在反向传播时局部梯度全部为0（梯度消失）。可以看出我们希望得到一个在正向传播过程和反向传播过程中信息不丢失的初始化方法。Xavier初始化：使得输入与输出分布相同（都为正态分布）通过分析可以知道，我们W的分布要为（0，1/N）时，输入和输出的分布才相同。批归一化解决前向过程中信号消失的问题（输出不至于小到0）。在反向传播中让较小的值回归到0均值1方差左右。下面是归一化的过程最后增加了4.平移缩放，因为0均值1方差不一定是最好的结果，需要根据数据的情况来指定，其中y是对方差的调整，p是对均值的调整都是从数据集中学习而来的。对于单张样本测试时，均值和方差来自于训练中累加的每个批次的均值和方差，最后取平均的结果作为预测时的均值和方差。过拟合模型在训练集上准确率很高，但是在真实场景下识别率很低。最好的解决方案是：增大数据集次优解：正则化：1.调节模型大小2.增加正则项（正则损失），对于大数值权值向量进行惩罚，鼓励更加分散的权重向量，使模型更倾向于用所有输入特征作决策。欠拟合模型训练效果不佳，在训练集上效果就不行，更不提测试集及其泛化能力了。DropoutDropout：让隐层的神经元以一定概率失活（不起作用），需要设置一个比例，将某一层的输出值舍弃（设置为0）。解释Dropout为什么能防止过拟合？1.更新梯度时参与计算的网络参数变少，降低模型容量。2.鼓励权重分散（通正则化）3.模型集成（很像集成学习 投票）细节问题：在dropout之后需要保持训练层和预测层的输出水平一致。超参数调优超参数是人为设计的，在模型设计阶段就需要指定。网格索搜，随机搜索。一般先采用随机搜索确定大致范围再使用网格搜索精细查找。使用标尺空间后，我们在不同量纲下分布比较均衡。

简介：wy的leetcode刷题记录_Day83声明本文章的所有题目信息都来源于leetcode如有侵权请联系我删掉!时间：2024 3 8前言@TOC2834. 找出美丽数组的最小和今天的每日一题是：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. 奇偶链表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. 设计推特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. 链表随机节点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(); // 返回 2solution.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. 字母异位词分组49. 字母异位词分组题目介绍给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的所有字母得到的一个新单词。示例 1:输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [["bat"],["nat","tan"],["ate","eat","tea"]] 示例 2:输入: strs = [""] 输出: [[""]] 示例 3:输入: strs = ["a"] 输出: [["a"]]思路看了题目我也是一头雾水，怎么比较两个相同字母组成的异位词，于是我看了评论区一个大佬的解法，就想通了：我们都知道质数的因子只有自己和本身，使用质数来代表26个字母，将每个单词的字母所代表的质数相乘的出来的值，只有拥有相同个数的同种字母才能得到也就是异位词。代码收获128. 最长连续序列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的使用。

简介：wy的leetcode刷题记录_Day82声明本文章的所有题目信息都来源于leetcode如有侵权请联系我删掉!时间：2024 3 6前言@TOC2917. 找出数组中的 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 相交的起始节点的值。如果不存在相交节点，这一值为 0listA 第一个链表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刷题记录_Day81声明本文章的所有题目信息都来源于leetcode如有侵权请联系我删掉!时间：2024 3 4前言@TOC232. 用栈实现队列今天的每日一题是：232. 用栈实现队列题目介绍请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：实现 MyQueue 类：void push(int x) 将元素 x 推到队列的末尾int pop() 从队列的开头移除并返回元素int peek() 返回队列开头的元素.boolean empty() 如果队列为空，返回 true ；否则，返回 false说明：你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。示例 1：输入： ["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2],[], [], []] 输出： [null, null, null, 1, 1, false] 解释： MyQueue myQueue = new MyQueue(); myQueue.push(1); // queue is: [1]myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2]myQueue.empty(); // return false思路本题是一道简单的题，我们只需要使用俩个栈一个输入栈一个输出栈，输入栈用来存贮push到队列中的元素，输出栈用来保存队列。push时将队列元素输入到输入栈，pop时将输入栈中所有元素pop到输出栈中保存，此时输出栈的pop顺序就是队列顺序。代码class MyQueue { public: stack<int> stk_in; stack<int> stk_out; MyQueue() { } void push(int x) { stk_in.push(x); } int pop() { if(stk_out.empty()) { while(!stk_in.empty()) { int x=stk_in.top(); stk_in.pop(); stk_out.push(x); } } int x=stk_out.top(); stk_out.pop(); return x; } int peek() { if(stk_out.empty()) { while(!stk_in.empty()) { int x=stk_in.top(); stk_in.pop(); stk_out.push(x); } } return stk_out.top(); } bool empty() { return stk_in.empty()&&stk_out.empty(); } }; /** * Your MyQueue object will be instantiated and called as such: * MyQueue* obj = new MyQueue(); * obj >push(x); * int param_2 = obj >pop(); * int param_3 = obj >peek(); * bool param_4 = obj >empty(); */收获一道非常简单且基础的题。138. 随机链表的复制138. 随机链表的复制题目介绍给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。例如，如果原链表中有 X 和 Y 两个节点，其中 X.random > Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random > y 。返回复制链表的头节点。用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：val：一个表示 Node.val 的整数。random_index：随机指针指向的节点索引（范围从 0 到 n 1）；如果不指向任何节点，则为 null 。你的代码 只 接受原链表的头节点 head 作为传入参数。示例 1：输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]输出：[[7,null],[13,0],[11,4],[10,2],[1,0]] 示例 2：输入：head = [[1,1],[2,1]] 输出：[[1,1],[2,1]]示例 3：输入：head = [[3,null],[3,0],[3,null]] 输出：[[3,null],[3,0],[3,null]]思路正常的链表深拷贝就仅仅只需要将节点的值以及节点的后续指针拷贝即可，本题的难点就在节点还包含一个随机指针指向随机的一个节点。假设在我们一个一个深拷贝检点时深拷贝一个节点的随机指针时，这个随即指针指向的新节点并未创建那么就会造成指向不明的后果。所以对于每一个节点，我们将递归的深拷贝其后续指针和随即指针，并使用哈希表将原节点与新节点相映射。代码/* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val = _val; next = NULL; random = NULL; } }; */ class Solution { public: unordered_map<Node*,Node*> cacheNode; Node* copyRandomList(Node* head) { if(head==nullptr) { return nullptr; } if(!cacheNode.count(head)) { Node* newHead=new Node(head >val); cacheNode[head]=newHead; newHead >next=copyRandomList(head >next); newHead >random=copyRandomList(head >random); } return cacheNode[head]; } };另一种解法请参考题解：class Solution { public: Node* copyRandomList(Node* head) { if (head == nullptr) { return nullptr; } for (Node* node = head; node != nullptr; node = node >next >next) { Node* nodeNew = new Node(node >val); nodeNew >next = node >next; node >next = nodeNew; } for (Node* node = head; node != nullptr; node = node >next >next) { Node* nodeNew = node >next; nodeNew >random = (node >random != nullptr) ? node >random >next : nullptr; } Node* headNew = head >next; for (Node* node = head; node != nullptr; node = node >next) { Node* nodeNew = node >next; node >next = node >next >next; nodeNew >next = (nodeNew >next != nullptr) ? nodeNew >next >next : nullptr; } return headNew; } }; 收获递归的使用大大简化了代码。141. 环形链表141. 环形链表题目介绍给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ，则返回 true 。 否则，返回 false 。示例 1：输入：head = [3,2,0, 4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。 示例 2：输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。 示例 3：输入：head = [1], pos = 1 输出：false 解释：链表中没有环。思路快慢指针，使用步长不等的指针进行遍历，如果俩个指针重新相遇说明存在换否则不存在。代码/** * Definition for singly linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) * }; */ class Solution { public: bool hasCycle(ListNode *head) { if(head==nullptr||head >next==nullptr) return false; ListNode* low=head; ListNode* high=head >next; while(low!=high) { if(high==nullptr||high >next==nullptr) return false; low=low >next; high=high >next >next; } return true; } };收获双指针的应用。142. 环形链表 II142. 环形链表 II题目介绍给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。示例 1：输入：head = [3,2,0, 4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。示例 2：输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。 示例3：输入：head = [1], pos = 1 输出：返回 null 解释：链表中没有环。思路本题很巧去看题解！题解代码/** * Definition for singly linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) * }; */ class Solution { public: ListNode *detectCycle(ListNode *head) { if(head==nullptr||head >next==nullptr) return nullptr; ListNode* low=head; ListNode* high=head; while(low!=high) { if(high==nullptr||high >next==nullptr) return nullptr; low=low >next; high=high >next >next; } high=head; while(low!=high) { low=low >next; high=high >next; } return high; } };收获双指针的应用。

简介：wy的leetcode刷题记录_Day79声明本文章的所有题目信息都来源于leetcode如有侵权请联系我删掉!时间：2024 3 1前言@TOC2369. 检查数组是否存在有效划分今天的每日一题是：2369. 检查数组是否存在有效划分题目介绍给你一个下标从 0 开始的整数数组 nums ，你必须将数组划分为一个或多个 连续 子数组。如果获得的这些子数组中每个都能满足下述条件 之一 ，则可以称其为数组的一种 有效 划分：1.子数组 恰 由 2 个相等元素组成，例如，子数组 [2,2] 。2.子数组 恰 由 3 个相等元素组成，例如，子数组 [4,4,4] 。3.子数组 恰 由 3 个连续递增元素组成，并且相邻元素之间的差值为 1 。例如，子数组 [3,4,5] ，但是子数组 [1,3,5] 不符合要求。如果数组 至少 存在一种有效划分，返回 true ，否则，返回 false 。示例 1：输入：nums = [4,4,4,5,6] 输出：true 解释：数组可以划分成子数组 [4,4] 和 [4,5,6] 。这是一种有效划分，所以返回 true 。 示例 2：输入：nums = [1,1,1,2] 输出：false 解释：该数组不存在有效划分。思路动态规划，令数组的长度为n，它至少存在一个有效的划分取决于它的子状态：1.前(n 2)个元素存在有效的划分，并且后俩个元素相等2.前(n 2)3个元素存在有效的划分，并且后三个元素相等或者后三个元素呈递增于是我们使用一个数组dp[n+1]来记录前n个元素是否存在有效划分。初始化全为false，dp[0]为true。状态转移方程为 bool euqal=(nums[i 1]==nums[i 2])&(nums[i 1]==nums[i 3]);//判断相等 bool continuous=(nums[i 1] nums[i 2]==1)&(nums[i 2] nums[i 3]==1);//判断递增 dp[i]=(dp[i 2]&(nums[i 2]==nums[i 1]))||(dp[i 3]&&(euqal||continuous));代码class Solution { public: bool validPartition(vector<int>& nums) { int n=nums.size(); vector<bool> dp(n+1,false); dp[0]=true; for(int i=1;i<=n;i++) { if(i>=2) { dp[i]=dp[i 2]&(nums[i 2]==nums[i 1]); } if(i>=3) { bool euqal=(nums[i 1]==nums[i 2])&(nums[i 1]==nums[i 3]); bool continuous=(nums[i 1] nums[i 2]==1)&(nums[i 2] nums[i 3]==1); dp[i]=dp[i]||(dp[i 3]&&(euqal||continuous)); } } return dp[n]; } };收获稳固了动态规划的知识。61. 旋转链表61. 旋转链表题目介绍给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。示例 1：输入：head = [1,2,3,4,5], k = 2 输出：[4,5,1,2,3] 示例 2：输入：head = [0,1,2], k = 4 输出：[2,0,1]思路本题其实跟博主以前做过的题有点类似，就是数组循环右移，不过换成了链表，同样也是老套路。首先我们先得到链表长度为n，然后根据k%n得到实际上所需的右移次数k（节省了多余重复的移动），然后从头遍历链表n k 1次得到新链表的尾节点，而其下一个节点就是新链表的头节点。此时我们将原链表的尾指针指向原链表的头节点，再将新链表的头节点记录下来最后置新链表的尾节点为空即可。代码/** * 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* rotateRight(ListNode* head, int k) { int count=0; ListNode* temp=head; ListNode* tail=nullptr; ListNode* newHead=nullptr; while(temp) { if(temp >next==nullptr) tail=temp; count++; temp=temp >next; } if(count==0) return head; k=k%count; if(k==0) return head; k=count k 1; temp=head; for(int i=0;i<k;i++) { temp=temp >next; } newHead=temp >next; temp >next=nullptr; tail >next=head; return newHead; } };收获无82. 删除排序链表中的重复元素 II82. 删除排序链表中的重复元素 II题目介绍给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。示例 1：输入：head = [1,2,3,3,4,4,5] 输出：[1,2,5] 示例 2：输入：head = [1,1,1,2,3] 输出：[2,3]思路本题其实最关键的就是使用一个哑节点类似书上没有用处的头节点一样，这里称呼它为哑节点。一般用这种情况是因为第一个节点可能会被删掉。首先建立一个指向第一个节点的哑节点newHead，然后使用一个指针cur从newHead来遍历整个链表，在遍历的过程中要判断相邻的俩个节点是否相同（只需判断每一组相同数的子链表前俩个），若相同的话则记录此时节点的值，然后将链表中与这个值相同的节点全部删掉，直到出现相邻的节点值不同；若不同的话则可以将cur置于该节点上使用cur >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* deleteDuplicates(ListNode* head) { if(!head) { return head; } ListNode* newHead=new ListNode(0,head); ListNode* cur=newHead; while(cur >next&&cur >next >next) { if(cur >next >val==cur >next >next >val) { int x=cur >next >val; while(cur >next&&cur >next >val==x) { cur >next=cur >next >next; } } else { cur=cur >next; } } return newHead >next; } };收获哑节点的使用很巧妙，极大程度上的能符合我的逻辑思维且减少我的代码复杂程度。86. 分隔链表86. 分隔链表题目介绍给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。你应当 保留 两个分区中每个节点的初始相对位置。示例 1：输入：head = [1,4,3,2,5,2], x = 3 输出：[1,2,2,4,3,5] 示例 2：输入：head = [2,1], x = 2 输出：[1,2]思路这题也巧借哑节点的思路，因为头节点不确定是否仍能保持其头节点的地位（如果他大于x那么他就不再是头节点）。这道题我们使用俩个哑节点分别存储按链表顺序分别大于x和小于x的节点，最后再将这两个链表合并即得到所需链表。代码/** * 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* partition(ListNode* head, int x) { ListNode* small=new ListNode(0); ListNode* large=new ListNode(0); ListNode* smallHead=small; ListNode* largeHead=large; while(head) { if(head >val<x) { small >next=head; small=small >next; } else { large >next=head; large=large >next; } head=head >next; } small >next=largeHead >next; large >next=nullptr; return smallHead >next; } };收获巩固了哑节点的使用，对于链表类的题，其中对于首节点的处理往往都用到了哑节点的方法。