📚
337
分类：
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);
}
};收获前序遍历和中序遍历
362
分类：
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;
}
}
}
};
收获无
360
分类：
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;
}
};收获有点不会说实话
382
分类：
Code
简介：手撕算法系列 Dijkstra单源最短路径前言纯小白手撕一波dijkstra，十分简陋，有问题望指出。理论暂无理论哈哈哈哈（ps：懒得写，主要图好难画，下次一定补上！）给个链接你们看链接代码#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
using namespace std;
#define GRAPH_INFINITY 65535 /* 无穷大 */
#define MAXVEX 5 /*最大图顶点*/
#define MAXEDGE 20 /*最大图边*/
vector<vector<int>> createGraph()
{
vector<vector<int>> graph(MAXVEX,vector<int>(MAXVEX,0));
int n = graph.size();
int m = graph[0].size();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < i+1; j++)
{
graph[i][j] = rand()%10;
if (graph[i][j] == 0) graph[i][j] = 1;
graph[j][i] = graph[i][j];
}
}
return graph;
}
int main()
{
vector<vector<int>> graph = createGraph();
int n = graph.size();
int m = graph[0].size();
graph[0][0] = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cout << graph[i][j] << " ";
}
cout << endl;
}
vector<int> vertex(n,0);
vector<int> distance(n);
queue<int> q;
for (int i = 0; i < n; i++)
{
distance[i] = GRAPH_INFINITY;
}
vertex[0] = 1;
distance[0] = 0;
q.push(0);
while (!q.empty())
{
int q_top = q.front();
q.pop();
int min_val = GRAPH_INFINITY + 1;
for (int i = 0; i < n; i++)
{
if (graph[q_top][i] != 1 && vertex[i] != 1)
{
distance[i] = min(distance[i], graph[q_top][i] + distance[q_top]);
min_val = min(min_val, distance[i]);
}
}
for (int j = 0; j < n; j++)
{
if (min_val == distance[j] && vertex[j] != 1)
{
vertex[j] = 1;
q.push(j);
cout << "本轮选取" << j << endl;
break;
}
}
cout << "distance:" << " ";
for (int i = 0; i < n; i++)
{
cout << distance[i] << " ";
}
cout << endl;
}
//// for (int i = 0; i < n; i++)
// {
// cout << distance[i] << " ";
// }
return 0;
}
