暂无内容
2024年4月5日
阴 🌷 15℃
来更新咯，也算是小小的上岸了吧，准备先把毕设和论文搞搞，让后开始度假啦！ ୧(๑•̀⌄•́๑)૭
📚
最新
分类：
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);
}
};收获前序遍历和中序遍历
wy的leetcode刷题记录_Day66
简介：wy的leetcode刷题记录_Day66声明本文章的所有题目信息都来源于leetcode如有侵权请联系我删掉!时间：2023 4 10前言@TOC1019. 链表中的下一个更大节点今天的每日一题是：1019. 链表中的下一个更大节点题目介绍给定一个长度为 n 的链表 head对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。示例 1：输入：head = [2,1,5] 输出：[5,5,0] 示例 2：输入：head = [2,7,4,3,5] 输出：[7,0,5,5,0]思路一道简单的模拟题，分析题意下来就是，遍历整个节点，对于当前节点我们向后寻找第一个大于该节点的节点值，并将值放入一个vector，如果没有则放入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:
vector<int> nextLargerNodes(ListNode* head) {
ListNode* curr=head;
ListNode*next=head >next;
vector<int> ans;
while(curr >next)
{
while(next)
{
if(next >val>curr >val)
{
ans.push_back(next >val);
break;
}
else
{
next=next >next;
}
}
if(next==nullptr)
{
ans.push_back(0);
}
curr=curr >next;
next=curr >next;
}
ans.push_back(0);
return ans;
}
};收获简单的模拟题OI WIKIOI WIKI从今天起，开始较为系统的学习算法的一些基础，不再盲目刷题了。
wy的leetcode刷题记录_Day66
简介：wy的leetcode刷题记录_Day66声明本文章的所有题目信息都来源于leetcode如有侵权请联系我删掉!时间：2023 4 10前言@TOC1019. 链表中的下一个更大节点今天的每日一题是：1019. 链表中的下一个更大节点题目介绍给定一个长度为 n 的链表 head对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。示例 1：输入：head = [2,1,5] 输出：[5,5,0] 示例 2：输入：head = [2,7,4,3,5] 输出：[7,0,5,5,0]思路一道简单的模拟题，分析题意下来就是，遍历整个节点，对于当前节点我们向后寻找第一个大于该节点的节点值，并将值放入一个vector，如果没有则放入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:
vector<int> nextLargerNodes(ListNode* head) {
ListNode* curr=head;
ListNode*next=head >next;
vector<int> ans;
while(curr >next)
{
while(next)
{
if(next >val>curr >val)
{
ans.push_back(next >val);
break;
}
else
{
next=next >next;
}
}
if(next==nullptr)
{
ans.push_back(0);
}
curr=curr >next;
next=curr >next;
}
ans.push_back(0);
return ans;
}
};收获简单的模拟题OI WIKIOI WIKI从今天起，开始较为系统的学习算法的一些基础，不再盲目刷题了。
创作：Anson Seabra
评分：
分类：
音乐
标签：
简介：哈哈这是网易云随机推荐给我的一首歌，当Anson Seabra的歌声传入我的耳朵中时，我知道这就是我想要的，这就是“一听钟情”吧？这首歌能让你想起青春里的遗憾嘛？Almost thought we could've been something，Almost thought we could havetried, butIt didn't happen so I need you to get out my life。差点我就觉得我们会有结果了。即使如此，明天我还是想见你。
wy的leetcode刷题记录_Day64
简介：wy的leetcode刷题记录_Day64声明本文章的所有题目信息都来源于leetcode如有侵权请联系我删掉!时间：2023 3 29前言@TOC1641. 统计字典序元音字符串的数目今天的每日一题是：1641. 统计字典序元音字符串的数目题目介绍给你一个整数 n，请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。字符串 s 按 字典序排列 需要满足：对于所有有效的 i，s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。示例 1：输入：n = 1 输出：5 解释：仅由元音组成的 5 个字典序字符串为 ["a","e","i","o","u"] 示例 2：输入：n = 2 输出：15 解释：仅由元音组成的 15 个字典序字符串为["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]。注意，"ea" 不是符合题意的字符串，因为 'e' 在字母表中的位置比 'a' 靠后 示例 3： 输入：n = 33 输出：66045思路归纳总结法：列出表格看图：数学分析法：我们想象有五个盒子，共有n个小球。从左往右盒子编号依次为a、e、i、o、u，我们必须从左往右再拿n个小球出来，每当我们拿出一个小球时，将盒子上的编号填入字符串即可。这样子就转换成这n个小球该如何放入这5个盒子并且盒子可以为空的排列组合问题。我们假设有n+5个球，多出的5个球分别放入a、e、i、o、u，这样剩下n个就可以随便放入了。就是在这n个球中插入四个隔板分成五类，四个隔板在n 1个空中随机分布C（4 n 1）。或者你将n个球盒子不为空和空1个一直到空5个的情况加起来也可以。代码class Solution {
public:
int countVowelStrings(int n) {
vector<vector<int>> dp(n+1,vector<int>(5));
// int dp[n][5];
if(n==1)
return 5;
for(int i=0;i<5;i++)
{
dp[0][i]=1;
}
for(int i=0;i<n+1;i++)
{
dp[i][0]=1;
}
for(int i=1;i<n+1;i++)
{
for(int j=1;j<5;j++)
{
dp[i][j] = dp[i][j 1] + dp[i 1][j];
}
}
return dp[n][4];
}
};class Solution {
public:
int countVowelStrings(int n) {
return (n + 4) * (n + 3) * (n + 2) * (n + 1) / 24;
}
};
收获观察题，最后总结出数学规律。
