博客主页 🏗️
文章

Count:

计 45 篇
81
机器视觉与深度学习基础知识补漏Week1
无标签
机器视觉与深度学习基础知识补漏Week1
分类: 默认分类
简介:机器视觉与深度学习基础知识补漏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之后需要保持训练层和预测层的输出水平一致。超参数调优超参数是人为设计的,在模型设计阶段就需要指定。网格索搜,随机搜索。一般先采用随机搜索确定大致范围再使用网格搜索精细查找。使用标尺空间后,我们在不同量纲下分布比较均衡。
198
武汉植物园~ 武汉植物园~ 武汉植物园~ 武汉植物园~
无标签
武汉植物园~
📚
182
wy的leetcode刷题记录_Day89
无标签
wy的leetcode刷题记录_Day89
分类: Code
简介:wy的leetcode刷题记录_Day89声明本文章的所有题目信息都来源于leetcode如有侵权请联系我删掉!时间:2024 3 18前言@TOC303. 区域和检索 数组不可变今天的每日一题是:303. 区域和检索 数组不可变题目介绍给定一个整数数组 nums,处理以下类型的多个查询:计算索引 left 和 right (包含 left 和 right)之间的 nums 元素的 和 ,其中 left <= right实现 NumArray 类:NumArray(int[] nums) 使用数组 nums 初始化对象int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ,包含left 和 right 两点(也就是 nums[left] + nums[left + 1] + ... + nums[right] )示例 1:输入: ["NumArray", "sumRange", "sumRange", "sumRange"] [[[ 2, 0, 3, 5,2, 1]], [0, 2], [2, 5], [0, 5]] 输出: [null, 1, 1, 3]解释:NumArray numArray = new NumArray([ 2, 0, 3, 5, 2, 1]);numArray.sumRange(0, 2); // return 1 (( 2) + 0 + 3)numArray.sumRange(2, 5); // return 1 (3 + ( 5) + 2 + ( 1)) numArray.sumRange(0, 5); // return 3 (( 2) + 0 + 3 + ( 5) + 2 + ( 1))思路竟然被我一眼看出来了。。直接用前缀和,但这里题目要求的是左闭右闭区间,需要注意下即可。代码class NumArray { private: vector<int> a; public: NumArray(vector<int>& nums) { a.assign(nums.begin(),nums.end()); int n=nums.size(); for(int i=1;i<n;i++) { a[i]+=a[i 1]; } } int sumRange(int left, int right) { if(left==0) return a[right]; return a[right] a[left 1]; } }; /** * Your NumArray object will be instantiated and called as such: * NumArray* obj = new NumArray(nums); * int param_1 = obj >sumRange(left,right); */收获无230. 二叉搜索树中第K小的元素230. 二叉搜索树中第K小的元素题目介绍给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 个最小元素(从 1 开始计数)。示例 1: 输入:root = [3,1,4,null,2], k = 1 输出:1 示例 2:输入:root = [5,3,6,2,4,null,null,1], k = 3 输出:3思路这道题思路也是一想就出来了哈,最简单的:大家都知道二叉搜索树的中序遍历一定是升序序列,那么我就用中序遍历获得这个升序序列,然后直接返回第k个元素即可。这里使用了递归和递推两种方式。代码/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) * TreeNode(int x) : val(x), left(nullptr), right(nullptr) * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) * }; */ class Solution { private: vector<int> a; public: void dfs(TreeNode* node) { if(!node) return ; dfs(node >left); a.emplace_back(node >val); dfs(node >right); } int kthSmallest(TreeNode* root, int k) { if(!root) return 0; dfs(root); int n=a.size(); if(k>n) return 0; return a[k 1]; } };/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) * TreeNode(int x) : val(x), left(nullptr), right(nullptr) * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) * }; */ class Solution { public: int kthSmallest(TreeNode* root, int k) { vector<int> a; stack<TreeNode*> stk; while(root!=nullptr||!stk.empty()) { while(root!=nullptr) { stk.push(root); root=root >left; } root=stk.top(); stk.pop(); a.emplace_back(root >val); root=root >right; } return a[k 1]; } };收获无199. 二叉树的右视图199. 二叉树的右视图题目介绍给定一个二叉树的 根节点 root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。示例 1:输入: [1,2,3,null,5,null,4] 输出: [1,3,4] 示例 2:输入: [1,null,3] 输出: [1,3] 示例 3:输入: [] 输出: []思路也是一道比较简单的题,如图所知,我们只需要返回二叉树每一层的最右边的元素,那么我们使用层序遍历返回每层的最后的元素即可。代码/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) * TreeNode(int x) : val(x), left(nullptr), right(nullptr) * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) * }; */ class Solution { public: vector<int> rightSideView(TreeNode* root) { vector<int> ans; if(!root) return ; queue<TreeNode*> q; q.push(root); // ans.emplace_back(root >val); while(!q.empty()) { int n=q.size(); for(int i=0;i<n;i++) { TreeNode* node=q.front(); q.pop(); if(node >left) q.push(node >left); if(node >right) q.push(node >right); if(i==n 1) ans.emplace_back(node >val); } } return ans; } };收获巩固层序遍历114. 二叉树展开为链表114. 二叉树展开为链表题目介绍给你二叉树的根结点 root ,请你将它展开为一个单链表:展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。展开后的单链表应该与二叉树 先序遍历 顺序相同。示例 1:输入:root = [1,2,5,3,4,null,6] 输出:[1,null,2,null,3,null,4,null,5,null,6]示例 2:输入:root = [] 输出:[] 示例 3:输入:root = [0] 输出:[0]思路这道题还是蛮复杂的,仔细观察你会发现其实就是对于一个节点我们要将其左子树接到该节点与其右子树之间,对于接入的细节我们先判断是否有左子树,其次寻找到左子树的最右节点,然后再将其连接,最后置该节点左子树为空即可。题解中还有一种解法很想后续遍历,右中左,首先我们的思路跟上一题一样,但是如果使用递归进行修改节点的话原节点的右子树会丢失,那么我们反过来想,从最后一个节点开始链接元素那么其右子树就不会丢失了。代码/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) * TreeNode(int x) : val(x), left(nullptr), right(nullptr) * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) * }; */ class Solution { public: vector<int> rightSideView(TreeNode* root) { vector<int> ans; if(!root) return ; queue<TreeNode*> q; q.push(root); // ans.emplace_back(root >val); while(!q.empty()) { int n=q.size(); for(int i=0;i<n;i++) { TreeNode* node=q.front(); q.pop(); if(node >left) q.push(node >left); if(node >right) q.push(node >right); if(i==n 1) ans.emplace_back(node >val); } } return ans; } };收获对树的结构有了新的认识,不仅可以常规的三种遍历,也可以自己定义从后开始遍历。105. 从前序与中序遍历序列构造二叉树105. 从前序与中序遍历序列构造二叉树题目介绍给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。示例 1:输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出:[3,9,20,null,null,15,7]示例 2:输入: preorder = [ 1], inorder = [ 1] 输出: [ 1]思路前序遍历:中左右,中序遍历:左右中,所以我们可以根据前序遍历寻找到根节点,再根据根节点在中序序列中寻找到左子树和右子树再根据左子树的大小可以在前序序列中寻找到左子树和右子树的根节点,以此类推写个递归就可以了。代码/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) * TreeNode(int x) : val(x), left(nullptr), right(nullptr) * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) * }; */ class Solution { public: unordered_map<int,int> index; TreeNode* build(vector<int> preorder,vector<int> inorder,int preLeft,int preRight,int inLeft,int inRight) { if(preLeft>preRight) return nullptr; int pre_root=preLeft; int in_root=index[preorder[pre_root]];//中序根的下标 TreeNode* root=new TreeNode(preorder[pre_root]); int left_size=in_root inLeft; root >left=build(preorder,inorder,preLeft+1,preLeft+left_size,inLeft,in_root 1); root >right=build(preorder,inorder,preLeft+left_size+1,preRight,in_root+1,inRight); return root; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { int n=preorder.size(); for(int i=0;i<n;i++) { index[inorder[i]]=i; } return build(preorder,inorder,0,n 1,0,n 1); } };收获前序遍历和中序遍历
205
wy的leetcode刷题记录_Day86
wy的leetcode刷题记录_Day86
分类: Code
简介:wy的leetcode刷题记录_Day86声明本文章的所有题目信息都来源于leetcode如有侵权请联系我删掉!时间:2024 3 13前言@TOC2864. 最大二进制奇数今天的每日一题是:2864. 最大二进制奇数题目介绍给你一个 二进制 字符串 s ,其中至少包含一个 '1' 。你必须按某种方式 重新排列 字符串中的位,使得到的二进制数字是可以由该组合生成的 最大二进制奇数 。以字符串形式,表示并返回可以由给定组合生成的最大二进制奇数。注意 返回的结果字符串 可以 含前导零。示例 1:输入:s = "010" 输出:"001" 解释:因为字符串 s 中仅有一个 '1' ,其必须出现在最后一位上。所以答案是 "001" 。示例 2:输入:s = "0101" 输出:"1001" 解释:其中一个 '1' 必须出现在最后一位上。而由剩下的数字可以生产的最大数字是 "100"。所以答案是 "1001"思路统计长度为n字符串s中1的个数num1,0的个数就为n num1,于是对于返回的字符串我们令高num1 1位位1接下来的n num1位为0,最低位为1即可。代码class Solution { public: string maximumOddBinaryNumber(string s) { int num1=0; int n=s.size(); int min_odd=9; string ans=""; for(int i=0;i<n;i++) { if((s[i] '0')==1) { num1++; } } for(int i=0;i<num1 1;i++) { ans+="1"; } for(int i=0;i<n num1;i++) { ans+="0"; } ans+="1"; return ans; } };官方题解:简介代码class Solution { public: string maximumOddBinaryNumber(string s) { int cnt = count(s.begin(), s.end(), '1'); return string(cnt 1, '1') + string(s.length() cnt, '0') + '1'; } }; 收获count统计字符串中字符的个数,以及巩固了string的构建函数。3. 无重复字符的最长子串3. 无重复字符的最长子串题目介绍给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。示例 1:输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。 示例 2:输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。 示例 3:输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。 请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。思路模拟滑动窗口,使用一个哈希表来记录当前窗口内的元素,如果滑动窗口向后扩张时下一个元素已存在于哈希表中,代表窗口内即将有冲突,这时候我们要将窗口前端的元素进行丢弃直到可以容纳下一个元素为止,在滑动窗口扩张的过程中我们维护最长长度即可得到答案。代码class Solution { public: int lengthOfLongestSubstring(string s) { int front=0,rear=0; int n=s.size(); if(n==0) return 0; unordered_map<char,int> hash; int ans=0; while(rear<n) { if(hash[s[rear]]) { while(hash[s[rear]]) { hash[s[front]] ; front++; } } ans=max(ans,rear front+1); hash[s[rear]]++; rear++; } return ans; } };收获复习滑动窗口。438. 找到字符串中所有字母异位词438. 找到字符串中所有字母异位词题目介绍给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。示例 1:输入: s = "cbaebabacd", p = "abc" 输出: [0,6] 解释: 起始索引等于 0 的子串是 "cba", 它是"abc" 的异位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。 示例 2:输入: s = "abab", p = "ab" 输出: [0,1,2] 解释: 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。 起始索引等于 2 的子串是 "ab", 它是 "ab"的异位词。思路跟上一题相同本题也可以使用哈希表来保存滑动窗口内的不同元素对应的个数,但在上题中我们使用的是set类型的哈希表那是因为上一题明确无重复的字符,而本题有重复的字符只能使用map来映射,这里因为字母固定26位我才用vector(26)来进行保存。代码class Solution { public: vector<int> findAnagrams(string s, string p) { int n=s.size(); int m=p.size(); if(n<m) return vector<int>(); vector<int> s1(26),p1(26); vector<int> ans; for(int i=0;i<m;i++) { s1[s[i] 'a']++; p1[p[i] 'a']++; } if(p1==s1) { ans.emplace_back(0); } for(int i=0;i<n m;i++) { s1[s[i] 'a'] ; s1[s[i+m] 'a']++; if(s1==p1) { ans.emplace_back(i+1); } } return ans; } };收获一般滑动窗口需要配合哈希表来统计窗口内部的数据。560. 和为 K 的子数组560. 和为 K 的子数组题目介绍给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。示例 1:输入:nums = [1,1,1], k = 2 输出:2 示例 2:输入:nums = [1,2,3], k = 3 输出:2思路方法一:暴力解法:枚举所有的起点,在每个起点中再枚举重点计算和是否等于k方法二:前缀和+哈希表:前缀和可以是我们计算子数组之和的时间复杂度降低,哈希表记录前缀和出现的次数,后面的思路看下题解(只可意会不可言传)...代码class Solution { public: int subarraySum(vector<int>& nums, int k) { int count = 0; for (int start = 0; start < nums.size(); ++start) { int sum = 0; for (int end = start; end >= 0; end) { sum += nums[end]; if (sum == k) { count++; } } } return count; } }; class Solution { public: int subarraySum(vector<int>& nums, int k) { unordered_map<int,int> hash; hash[0]=1; int count=0,pre=0; int n=nums.size(); if(n==1) return nums[0]==k?1:0; for(auto x:nums) { pre+=x; if(hash.count(pre k)) count+=hash[pre k]; hash[pre]++; } return count; } };收获emmm头晕了。53. 最大子数组和53. 最大子数组和题目介绍给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。子数组是数组中的一个连续部分。示例 1:输入:nums = [ 2,1, 3,4, 1,2,1, 5,4] 输出:6 解释:连续子数组 [4, 1,2,1] 的和最大为 6 。示例 2:输入:nums = [1] 输出:1 示例 3:输入:nums = [5,4, 1,7,8] 输出:23思路动态规划:我先放上原文(讲的巨好)。我自己的理解就是dp[i]表示前i个元素的最大和,而前i+1个元素的最大和与dp[i]和nums[i+1]有关。代码class Solution { public: int maxSubArray(vector<int>& nums) { int ans= 10000; int n=nums.size(); for(int start=0;start<n;start++) { int sum=0; for(int end=start;end<n;end++) { sum+=nums[end]; ans=max(ans,sum); } } return ans; } };优化空间:class Solution { public: int maxSubArray(vector<int>& nums) { int n=nums.size(); int pre=0; int ans=nums[0]; for(int i=0;i<n;i++) { pre=max(pre+nums[i],nums[i]); ans=max(ans,pre); } return ans; } };收获动态规划全忘完咯!56. 合并区间56. 合并区间题目介绍以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。示例 1:输入:intervals = [[1,3],[2,6],[8,10],[15,18]] 输出:[[1,6],[8,10],[15,18]]解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].示例 2:输入:intervals = [[1,4],[4,5]] 输出:[[1,5]] 解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。思路emm说实话我一开始没思路,看了一眼评论区才有思路。先用排序(根据起点开始排序),然后将第i个区间的右边界与排序后的第i+1个区间的左边界进行比较,如果大于则相交,否则不相交。相交将较小的左边界与较大的有边界装入新的ans中,再与下一个区间进行比较。代码class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { int n=intervals.size(); if(n==0) return intervals; sort(intervals.begin(),intervals.end()); vector<vector<int>> ans; for(int i=0;i<n;i++) { if(!ans.size()||ans.back()[1]<intervals[i][0])//不相交 { ans.push_back({intervals[i][0],intervals[i][1]}); } else { ans.back()[1]=max(ans.back()[1],intervals[i][1]); } } return ans; } };收获无。189. 轮转数组189. 轮转数组题目介绍给定一个整数数组 nums,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。示例 1:输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右轮转 3 步: [5,6,7,1,2,3,4]示例2:输入:nums = [ 1, 100,3,99], k = 2 输出:[3,99, 1, 100] 解释: 向右轮转 1 步: [99, 1, 100,3] 向右轮转 2 步: [3,99, 1, 100]思路方法一:反转数组,样例1:1234567.。我们先整体反转7654321,再将前k个和剩余n k个反转得5671234,即可实现。方法二:使用额外数组来保存原数组反转后的位置,原数组的每个元素计算其在新数组中的位置然后赋值即可。代码class Solution { public: void reverse(vector<int>& nums,int start,int end) { while(start<end) { swap(nums[start],nums[end]); start++; end ; } } void rotate(vector<int>& nums, int k) { k=k%nums.size(); reverse(nums,0,nums.size() 1); reverse(nums,0,k 1); reverse(nums,k,nums.size() 1); } };class Solution { public: void rotate(vector<int>& nums, int k) { int n=nums.size(); k%=n; vector<int> a(n); for(int i=0;i<n;i++) { a[(i+k)%n]=nums[i]; } nums.assign(a.begin(),a.end()); } };收获巩固了反转数组和数组的一些赋值操作,vector.assigin(iterator,iterator)。238. 除自身以外数组的乘积238. 除自身以外数组的乘积题目介绍给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。请 不要使用除法,且在 O(n) 时间复杂度内完成此题。示例 1:输入: nums = [1,2,3,4] 输出: [24,12,8,6] 示例 2:输入: nums = [ 1,1,0, 3,3] 输出: [0,0,9,0,0]思路可恶啊,本来记录所有元素的乘积然后除以对应元素就可以得到答案,可恶的出题人不让用除法。这里我使用两个数组left和right分别记录i左边的乘积和和i右边的乘积和,left[i]*right[i]即为所求。代码class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { int n=nums.size(); vector<int> left(n,0),right(n,0); left[0]=1; right[n 1]=1; for(int i=1;i<n;i++) { left[i]=nums[i 1]*left[i 1]; } for(int i=n 2;i>=0;i ) { right[i]=nums[i+1]*right[i+1]; } for(int i=0;i<n;i++) { nums[i]=left[i]*right[i]; } return nums; } };收获无73. 矩阵置零73. 矩阵置零题目介绍给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。示例 1:输入:matrix = [[1,1,1],[1,0,1],[1,1,1]] 输出:[[1,0,1],[0,0,0],[1,0,1]] 示例2:输入:matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]输出:[[0,0,0,0],[0,4,5,0],[0,3,1,0]]思路直观的想法,分别用两个HashSet来保存需要清0的行和列,对整个矩阵进行遍历后得到hashset对hashset选中的行列进行清0即可。题解中给出了另外两种空间上优化解法,这里我只说第一种优化的,剩下那个没看....,我们一开始使用了两个HashSet来记录需要清0的空间,这里我们不需要额外的空间使用二维矩阵的第0行和第0列来表示是否需要对该行或者该列进行清空,这是我们丢失了原本第0行和第0列的信息,所以我们需要两个O(1)的变量来记录是否需要对第0行和第0列进行清空即可。代码class Solution { public: void setZeroes(vector<vector<int>>& matrix) { unordered_set<int> row,col; int n=matrix.size(); int m=matrix[0].size(); for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(matrix[i][j]==0) { row.insert(i); col.insert(j); } } } for(auto i:col) { for(int j=0;j<n;j++) { matrix[j][i]=0; } } for(auto i:row) { for(int j=0;j<m;j++) { matrix[i][j]=0; } } } };class Solution { public: void setZeroes(vector<vector<int>>& matrix) { int m = matrix.size(); int n = matrix[0].size(); int flag_col0 = false, flag_row0 = false; for (int i = 0; i < m; i++) { if (!matrix[i][0]) { flag_col0 = true; } } for (int j = 0; j < n; j++) { if (!matrix[0][j]) { flag_row0 = true; } } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (!matrix[i][j]) { matrix[i][0] = matrix[0][j] = 0; } } } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (!matrix[i][0] || !matrix[0][j]) { matrix[i][j] = 0; } } } if (flag_col0) { for (int i = 0; i < m; i++) { matrix[i][0] = 0; } } if (flag_row0) { for (int j = 0; j < n; j++) { matrix[0][j] = 0; } } } }; 收获无
203
wy的leetcode刷题记录_Day84
无标签
wy的leetcode刷题记录_Day84
分类: Code
简介:wy的leetcode刷题记录_Day84声明本文章的所有题目信息都来源于leetcode如有侵权请联系我删掉!时间:2024 3 10前言@TOC299. 猜数字游戏今天的每日一题是:299. 猜数字游戏题目介绍你在和朋友一起玩 猜数字(Bulls and Cows)游戏,该游戏规则如下:写出一个秘密数字,并请朋友猜这个数字是多少。朋友每猜测一次,你就会给他一个包含下述信息的提示:猜测数字中有多少位属于数字和确切位置都猜对了(称为 "Bulls",公牛),有多少位属于数字猜对了但是位置不对(称为 "Cows",奶牛)。也就是说,这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字。给你一个秘密数字 secret 和朋友猜测的数字 guess ,请你返回对朋友这次猜测的提示。提示的格式为 "xAyB" ,x 是公牛个数, y 是奶牛个数,A 表示公牛,B 表示奶牛。请注意秘密数字和朋友猜测的数字都可能含有重复数字。示例 1:输入:secret = "1807", guess = "7810" 输出:"1A3B"示例 2:输入:secret = "1123", guess = "0111" 输出:"1A1B"注意,两个不匹配的 1中,只有一个会算作奶牛(数字猜对位置不对)。通过重新排列非公牛数字,其中仅有一个 1 可以成为公牛数字。思路第一个想到的就是用哈希表来解决,主要思路就是:首先将secret和guess中同时存在的字符串(不管位置是否相同)算出来b,最后枚举secret和guess找到位置相同元素也相同的数目a,最后b a就是位置不同但元素相同的个数。代码class Solution { public: string getHint(string secret, string guess) { int n=secret.size(); int a_num=0; int b_num=0; unordered_map<char,int> hash; for(int i=0;i<n;i++) { if(!hash.count(secret[i])) hash[secret[i]]=1; else { if(hash[secret[i]]<0) { b_num++; } hash[secret[i]]++; } if(!hash.count(guess[i])) hash[guess[i]]= 1; else { if(hash[guess[i]]>0) { b_num++; } hash[guess[i]] ; } } for(int i=0;i<n;i++) { if(secret[i]==guess[i]) { a_num++; } } b_num=b_num a_num; string ans=to_string(a_num)+"A"+to_string(b_num)+"B"; return ans; } };收获哈希表的应用430. 扁平化多级双向链表430. 扁平化多级双向链表题目介绍你会得到一个双链表,其中包含的节点有一个下一个指针、一个前一个指针和一个额外的 子指针 。这个子指针可能指向一个单独的双向链表,也包含这些特殊的节点。这些子列表可以有一个或多个自己的子列表,以此类推,以生成如下面的示例所示的 多层数据结构 。给定链表的头节点 head ,将链表 扁平化 ,以便所有节点都出现在单层双链表中。让 curr 是一个带有子列表的节点。子列表中的节点应该出现在扁平化列表中的 curr 之后 和 curr.next 之前 。返回 扁平列表的 head 。列表中的节点必须将其 所有 子指针设置为 null 。示例 1:输入:head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]输出:[1,2,3,7,8,11,12,9,10,4,5,6] 解释:输入的多级列表如上图所示。 扁平化后的链表如下图:示例 2:输入:head = [1,2,null,3] 输出:[1,3,2] 解释:输入的多级列表如上图所示。 扁平化后的链表如下图:示例 3:输入:head = []输出:[] 说明:输入中可能存在空列表。思路DFS:本题旨在将child插入在当前节点与下一节点的中间,因此我们需要当前节点和下一节点以及子链头节点以及子链的尾节点。具体细节如下:当前节点无child的时那么继续向下遍历;当前节点有child时,那么通过dfs也就是当前函数继续寻找child的下一个节点(若中途也有child则继续child)直至尾节点,最后连接。代码/* // Definition for a Node. class Node { public: int val; Node* prev; Node* next; Node* child; }; */ class Solution { public: Node* dfs(Node* head) { Node* cur=head; Node* last=nullptr; while(cur) { Node* nextt=cur >next; if(cur >child) { Node* child_last=dfs(cur >child); cur >next=cur >child; cur >child >prev=cur; if(nextt) { child_last >next=nextt; nextt >prev=child_last; } cur >child=nullptr; last=child_last; } else { last=cur; } cur=nextt; } return last; } Node* flatten(Node* head) { dfs(head); return head; } };先序遍历/* // Definition for a Node. class Node { public: int val; Node* prev; Node* next; Node* child; }; */ class Solution { public: Node* flatten(Node* head) { //BFS Node* newHead=head; // if(head==nullptr) // return head; for (; head;head = head >next) { if(head >child) { Node* node=head;//记录当前节点 Node* nexxt=head >next; if(nexxt) nexxt >prev=nullptr; head >next=head >child; head >child >prev=head; head >child=nullptr; while(node >next) { node=node >next; } node >next=nexxt; if(nexxt) { nexxt >prev=node; } } } return newHead; } };收获DFS在链型树上的应用445. 两数相加 II445. 两数相加 II题目介绍给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。你可以假设除了数字 0 之外,这两个数字都不会以零开头。示例1:输入:l1 = [7,2,4,3], l2 = [5,6,4] 输出:[7,8,0,7] 示例2:输入:l1 = [2,4,3], l2 = [5,6,4] 输出:[8,0,7] 示例3:输入:l1 = [0], l2 = [0] 输出:[0]思路方法一:先将两个链表反转,最后相加,使用一个用头插法建立的新链表来保存。细节:每10进1,使用一个flag来表示是否需要进位,最高位进位需要单独判断。(ps:我写的巨丑的代码)方法二:题解用的两个栈,先将两个链表元素分别入栈,然后出栈一一相加。其中细节做的比我好太多了:对于进位的处理使用carry=(a+b+carry)/10来判断(不需要用flag,其实计组里面的加法器也讲过这样的逻辑结构),其次在循环内部就判断了较长和较短在遍历完相同长度剩下多余长度时的情况。代码/** * 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; while(head) { ListNode* next=head >next; head >next=pre; pre=head; head=next; } return pre; } ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { l1=reverse(l1); l2=reverse(l2); ListNode* head=new ListNode(0); int flag=0; //将长度相等的部分先加起来 while(l1!=nullptr&&l2!=nullptr) { ListNode* node=new ListNode(0); node >val=l1 >val+l2 >val; if(flag==1) { flag=0; node >val=node >val+1; } if(node >val>=10) { flag=1; node >val=node >val%10; } l1=l1 >next; l2=l2 >next; node >next=head >next; head >next=node; } //统一判断l1 if(l2) l1=l2; //剩余部分加起来 while(l1) { ListNode* node=new ListNode(l1 >val); if(flag==1) { flag=0; node >val=node >val+1; } if(node >val>=10) { flag=1; node >val=node >val%10; } l1=l1 >next; node >next=head >next; head >next=node; } //最高位的进位情况 if(flag==1) { ListNode* node=new ListNode(1); node >next=head >next; head >next=node; } return head >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* addTwoNumbers(ListNode* l1, ListNode* l2) { stack<int>s1,s2; while(l1) { s1.push(l1 >val); l1=l1 >next; } while(l2) { s2.push(l2 >val); l2=l2 >next; } ListNode* head=new ListNode(0); int carry=0; while(!s1.empty()|| !s2.empty()||carry!=0) { int a=s1.empty()?0:s1.top(); int b=s2.empty()?0:s2.top(); if(!s1.empty()) s1.pop(); if(!s2.empty()) s2.pop(); int cur=a+b+carry; carry=cur/10; cur%=10; ListNode* node=new ListNode(cur); node >next=head >next; head >next=node; } return head >next; } };收获自己写的话巩固了反转链表以及对两个链表进行操作的熟练度,看了题解后发现,像这种反向或者从底部开始的操作可以使用栈来操作。面试题 02.01. 移除重复节点面试题 02.01. 移除重复节点题目介绍编写代码,移除未排序链表中的重复节点。保留最开始出现的节点。示例1:输入:[1, 2, 3, 3, 2, 1] 输出:[1, 2, 3] 示例2:输入:[1, 1, 1, 1, 2] 输出:[1, 2]思路方法一:遍历链表时使用哈希表来保存已经出现过的元素,如果出现重复的则删掉,否则加入哈希表。方法二:来自题解中的挑战部分,不适用额外空间来记录,但是需要提升时间复杂度。使用双重循环枚举元素,外层循环枚举需查重的元素,内层循环进行遍历,若相同则删除。代码/** * Definition for singly linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) * }; */ class Solution { public: ListNode* removeDuplicateNodes(ListNode* head) { ListNode* newHead=head; ListNode* pre=nullptr; unordered_map<int,int> hash; while(head) { if(!hash.count(head >val)) { hash[head >val]=1; pre=head; head=head >next; } else { pre >next=head >next; head=head >next; } } return newHead; } };class Solution { public: ListNode* removeDuplicateNodes(ListNode* head) { ListNode* ob = head; while (ob != nullptr) { ListNode* oc = ob; while (oc >next != nullptr) { if (oc >next >val == ob >val) { oc >next = oc >next >next; } else { oc = oc >next; } } ob = ob >next; } return head; } }; 收获简单题1171. 从链表中删去总和值为零的连续节点1171. 从链表中删去总和值为零的连续节点题目介绍给你一个链表的头节点 head,请你编写代码,反复删去链表中由 总和 值为 0 的连续节点组成的序列,直到不存在这样的序列为止。删除完毕后,请你返回最终结果链表的头节点。你可以返回任何满足题目要求的答案。(注意,下面示例中的所有序列,都是对 ListNode 对象序列化的表示。)示例 1:输入:head = [1,2, 3,3,1] 输出:[3,1] 提示:答案 [1,2,1] 也是正确的。 示例 2:输入:head = [1,2,3, 3,4] 输出:[1,2,4] 示例 3:输入:head = [1,2,3, 3, 2]输出:[1]思路前缀和+Hash:为了确保某一连续的子串满足某种条件我们一般使用前缀和。本题我们以前缀和为key,对于的value为node,二次遍历链表时重新计算前缀和,并以此为key在hash表中寻找,寻找到的就是对应子串和为0的末尾节点。代码/** * 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* removeZeroSumSublists(ListNode* head) { ListNode* newHead=new ListNode(0,head); int sum=0; unordered_map<int,ListNode*> hash; head=newHead; while(head) { sum+=head >val; hash[sum]=head; head=head >next; } sum=0; head=newHead; while(head) { sum+=head >val; head >next=hash[sum] >next; head=head >next; } return newHead >next; } };收获熟练了前缀和的应用283. 移动零283. 移动零题目介绍给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。请注意 ,必须在不复制数组的情况下原地对数组进行操作。示例 1:输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0]示例 2:输入: nums = [0] 输出: [0]思路方法一:使用两个指针,a指针用来寻找0,b指针用来寻找1。这里非0值我统称为1若a寻找到0,b寻找到1那么交换值,a++,b++;若a未寻找到0,b寻找到1,同样的a++,b++,因为通常a在b后面,而在a之前的所有元素都是1;若a寻找到0,b未寻找到1,b++继续寻找1,这些情况违反了上述的通常情况一般是000开头这样的数组;若a未寻找到0,b未寻找到1同样的a++,b++;方法二:同样时双指针,指针j统计0的个数,第一次遍历时将前几个元素值为非零元素,第二次遍历将后j个元素置为0即可。代码class Solution { public: void moveZeroes(vector<int>& nums) { int n=nums.size(); int a=0,b=1; while(a<n&&b<n) { if(nums[a]==0&&nums[b]!=0) { int temp=nums[a]; nums[a]=nums[b]; nums[b]=temp; a++; b++; } else if(nums[a]==0&&nums[b]==0) { b++; } else if(nums[a]!=0&&nums[b]!=0) { a++;b++; } else if(nums[a]!=0&&nums[b]==0) { a++;b++; } } } };class Solution { public: void moveZeroes(vector<int>& nums) { // int a=0,b=0; int n=nums.size(); int j=0; for(int i=0;i<n;i++) { if(nums[i]!=0) { nums[j++]=nums[i]; } } for(int i=j;i<n;i++) { nums[i]=0; } } };收获简单模拟。11. 盛最多水的容器11. 盛最多水的容器题目介绍给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明:你不能倾斜容器。示例 1:输入:[1,8,6,2,5,4,8,3,7] 输出:49 解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。 示例 2:输入:height = [1,1] 输出:1思路方法一(时间超限):暴搜,直接嵌套两个循环维护一个最大面积变量即可。ans=max(ans,min(height[i],height[j])*(j i));方法二:双指针,分别从开头和末尾开始遍历,取水的面积取决于较小的高度,每次更新两个指针中最短的并维护最大面积即可。代码class Solution { public: int maxArea(vector<int>& height) { int ans=0; int n=height.size(); for(int i=0;i<n;i++) { for(int j=i;j<n;j++) { ans=max(ans,min(height[i],height[j])*(j i)); } } return ans; } };class Solution { public: int maxArea(vector<int>& height) { int ans=0; int n=height.size(); int a=0,b=n 1; while(a<b) { ans=height[a]<height[b]?max(ans,(b a)*height[a++]):max(ans,(b a)*height[b ]); } return ans; } };收获无15. 三数之和15. 三数之和题目介绍给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。注意:答案中不可以包含重复的三元组。示例 1:输入:nums = [ 1,0,1,2, 1, 4] 输出:[[ 1, 1,2],[ 1,0,1]] 解释: nums[0] + nums[1] + nums[2] = ( 1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0+ 1 + ( 1) = 0 。 nums[0] + nums[3] + nums[4] = ( 1) + 2 + ( 1) = 0 。 不同的三元组是 [ 1,0,1] 和 [ 1, 1,2] 。 注意,输出的顺序和三元组的顺序并不重要。 示例 2:输入:nums = [0,1,1] 输出:[] 解释:唯一可能的三元组和不为 0 。示例 3:输入:nums = [0,0,0] 输出:[[0,0,0]] 解释:唯一可能的三元组和为 0 。思路一开始可以用三重循环但是效率太低了,参照题解发现第三重循环其实可以优化跟第二重循环平行,因为第三重循环找的c本身就大于b只需要在b的左边找,所以在找b的时候顺便就把c给找了。代码class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { int n=nums.size(); sort(nums.begin(),nums.end()); vector<vector<int>> ans; for(int first=0;first<n;first++) { if(first>0&&nums[first]==nums[first 1]) { continue;//与上一个数字相同不要 } int third=n 1;//c对应的指针在数组最右端开始遍历 int target= nums[first]; //b for(int second=first+1;second<n;second++) { //同fitst不能与上一个数相同 if(second>first+1&&nums[second]==nums[second 1]) { continue; } while(second<third&&nums[second]+nums[third]>target)//保证third在second右边 { third; } if(second==third) break; if(nums[second]+nums[third]==target) { ans.push_back({nums[first],nums[second],nums[third]}); } } } return ans; } };收获有点不会说实话
博客主页 wyのblog I know you are here. 百度统计
鄂ICP备2023003777号-1 本站已运行 324 天 13 小时 22 分 自豪地使用 Typecho 建站,并搭配 MyDiary 主题 Copyright © 2023 ~ 2024. wyのblog All rights reserved.
打赏图
打赏博主
欢迎
搜 索
足 迹
分 类
  • 默认分类
  • Code
  • 日记
  • 音乐
  • 游戏
  • 阅读
  • 计划
  • 图片
  • 旅游
  • 影视