6016. Excel 表中某个范围内的单元格
题意
思路
模拟就可，要注意第一层循环的是字母，第二层循环的是数字，范围就是题目里给出字符串的第一个和第二个单元格的范围。每次将组合后的答案保存到vector里。
代码
class Solution { public: vector<string> cellsInRange(string s) { vector<string>ans; for(int j=s[0]-'A';j<=s[3]-'A';j++){ for(int i=s[1]-'0';i<=s[4]-'0';i++){ string now=""; char t=(j+'A'); now=now+t; t=(i+'0'); now=now+t; ans.push_back(now); } } return ans; } };
6017. 向数组中追加 K 个整数
题意
给你一个整数数组 nums 和一个整数 k 。请你向 nums 中追加 k 个 未 出现在 nums 中的、互不相同 的 正 整数，并使结果数组的元素和 最小 。
返回追加到 nums 中的 k 个整数之和。
思路
基本思路就是判判断当前数跟前一个数中间有多少个数，能加小的先加小的。
对于第一个数，跟1比较。
如果遍历完所有的数，还没有加够k个数的话，就从最后开始继续加。
求和的话用等差数列求和公式。
代码
class Solution { public: long long minimalKSum(vector<int>& nums, int k) { long long ans=0; sort(nums.begin(),nums.end()); int n=nums.size()-1; /*for(int i=0;i<=n;i++){ cout<<i<<"==="<<nums[i]<<endl; }*/ for(int i=0;i<nums.size();i++){ long long sum=0; int tmp; if(i==0){ if(nums[i]!=1){ ///5 //1 2 3 4 tmp=nums[i]-1; if(k>=tmp){ k-=tmp; sum=1ll*tmp*(1+tmp)/2; ans=ans+sum; } else{ tmp=k; sum=1ll*tmp*(1+tmp)/2; ans=ans+sum; k=0; } } } else{ if(nums[i]!=nums[i-1]+1&&nums[i]!=nums[i-1]){ tmp=nums[i]-nums[i-1]-1; ///3 6 // 4 5 if(k>=tmp){ k-=tmp; sum=1ll*tmp*(nums[i-1]+1+nums[i]-1)/2; ans+=sum; } else{ tmp=k; sum=1ll*tmp*(nums[i-1]+1+nums[i-1]+1+tmp-1)/2; ans+=sum; k=0; } } } if(k==0) break; // cout<<i<<" "<<nums[i]<<" "<<tmp<<" "<<sum<<endl; } if(k>0){ long long sum=1ll*k*(nums[n]+1+k-1+nums[n]+1)/2; ans=ans+sum; } return ans; } };
6018. 根据描述创建二叉树
题意
思路
首先找到根，根就是当过父亲节点，没有当过子节点的。所以先遍历一遍，存储父亲节点跟子节点是否出现过。
在遍历的过程中，同时存储每个节点的子节点。我用的是vector套pair保存的，所以用哈希离散化了下值，方便保存。
然后dfs进行构造，从根节点开始构造，构造的时候判断是否有左右子节点，然后递归构造。
代码
/** * 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<vector<pair<int,int>>>v; map<int,int>mp; unordered_map<int,bool>parent; unordered_map<int,bool>child; TreeNode* dfs(vector<vector<int>>& descriptions,int root){ TreeNode* res=new TreeNode(root); if(mp.find(root)==mp.end()){ return res; } int u=mp[root]; int siz=v[u].size(); if(siz!=0){ for(pair<int,int>t2:v[u]){ int cc=t2.first,ll=t2.second; if(ll==1){ res->left=dfs(descriptions,cc); } else{ res->right=dfs(descriptions,cc); } } } return res; } TreeNode* createBinaryTree(vector<vector<int>>& descriptions) { int n=descriptions.size(); parent.clear(); child.clear(); for(int i=0;i<n;i++){ vector<pair<int,int>>tmp; v.push_back(tmp); } for(int i=0;i<n;i++){ vector<pair<int,int>>tmp; int pp=descriptions[i][0]; int cc=descriptions[i][1]; int ll=descriptions[i][2]; if(mp.find(pp)==mp.end()){ mp[pp]=i; // cout<<pp<<"***"<<i<<endl; tmp.push_back({cc,ll}); v[i]=tmp; parent[pp]=true; child[cc]=true; } else{ int tt=mp[pp]; // cout<<pp<<"***"<<tt<<endl; tmp=v[tt]; tmp.push_back({cc,ll}); v[tt]=tmp; parent[pp]=true; child[cc]=true; } } /* for(int i=0;i<n;i++){ for(pair<int,int>t:v[i]){ cout<<i<<" "<<t.first<<" "<<t.second<<endl; } }*/ int root=0; for(auto it:parent){ int val=it.first; if(child.find(val)==child.end()){ root=val;break; } } // cout<<root<<endl; TreeNode* ans=dfs(descriptions,root); return ans; } }; /* [50,20,80,15,17,19] */
6019. 替换数组中的非互质数
题意
思路
每次替换都相当于减少一个数，然后暴力维护一下就行了，时间复杂度O(n)
具体地，维护答案vector，遍历一遍数组，然后不断地判断vector的最后一个数和当前数是否互质，不互质的话就令当前数等于lcm，并且将vector的最后一个数弹出。最后将当前数放入vector里。
代码
class Solution { public: int gcd(int a,int b){ return b==0?a:gcd(b,a%b); } int lcm(int x,int y){ return x/gcd(x,y)*y; } vector<int> replaceNonCoprimes(vector<int>& nums) { vector<int>ans; for(int i=0;i<nums.size();i++){ int t=nums[i]; while(!ans.empty()){ int now=ans.back(); if(gcd(t,now)>1){ int sum=lcm(t,now); ans.pop_back(); t=sum; } else break; } ans.push_back(t); } return ans; } };
