网站备案幕布要求,精通网站建设 100%全能建站密码pdf,360网站卖东西怎么做,如何做网站结构优化文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴哈希表秦九韶算法一、题目
1、原题链接 2058. 笨拙的手指 2、题目描述 奶牛贝茜正在学习如何在不同进制之间转换数字。 但是她总是犯错误#xff0c;因为她无法轻易的用两…
文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴哈希表秦九韶算法一、题目
1、原题链接 2058. 笨拙的手指 2、题目描述 奶牛贝茜正在学习如何在不同进制之间转换数字。 但是她总是犯错误因为她无法轻易的用两个前蹄握住笔。 每当贝茜将数字转换为一个新的进制并写下结果时她总是将其中的某一位数字写错。 例如如果她将数字 14 转换为二进制数那么正确的结果应为 1110但她可能会写下 0110 或 1111 。 贝茜不会额外添加或删除数字但是可能会由于写错数字的原因写下包含前导 0 的数字。 给定贝茜将数字 N 转换为二进制数字以及三进制数字的结果请 确定 N 的正确初始值十进制表示。 输入格式 第一行包含 N 的二进制表示其中一位是错误的。 第二行包含 N 的三进制表示其中一位是错误的。 输出格式 输出正确的 N 的值。 数据范围 0≤N≤109且存在唯一解。 输入样例 1010
212输出样例 14样例解释 14 在二进制下的正确表示为 1110在三进制下的正确表示为 112。 二、解题报告
1、思路分析 思路来源y总视频讲解 y总yyds 1将数N的二进制表示下可能写错的每种情况的十进制下的数值存入哈希表中。 2将数N的三进制表示下的每种写错的情况的十进制下的数值在哈希表中进行查找如果该数值出现过则该数就是N的十进制表示输出即可。
2、时间复杂度
时间复杂度为O(n)
3、代码详解
使用STL中unordered_set
#include iostream
#include string
#include unordered_set
using namespace std;
//使用秦九韶算法将y进制下的数x转化为十进制
int ten(string x,int y){int ans0;for(int i0;ix.size();i){ansans*yx[i]-0;}return ans;
}
int main(){string n,m;cinnm;unordered_setint s;for(int i0;in.size();i){string tn;t[i]^1; //改变第i位数0变1,1变0if(t[0]0t.size()1) continue; //如果数字存在前导0则不合法直接跳过s.insert(ten(t,2)); //将写错后的数字在十进制下的数值放入哈希表}for(int i0;im.size();i){for(int j0;j3;j){ //枚举第i位数字可能的写错情况然后再在哈希表中查找该数的十进制下数值是否出现过if(m[i]-0!j){ string tmpm;tmp[i]j0;if(tmp[0]0tmp.size()1) continue; //同上if(s.count(ten(tmp,3))){ //如果该数的十进制的值在哈希表存在过直接输出该数就是答案coutten(tmp,3);}}}}return 0;
}手写哈希表
#include iostream
#include string
#include cstring
using namespace std;
const int N103;
int h[N];
//哈希表开放寻址法如果x存在返回x的位置否则返回x应该插入的位置
int find(int x){int t(x%NN)%N;while(h[t]!-1h[t]!x){t;if(tN) t0;}return t;
}
//使用秦九韶算法将y进制下的数x转化为十进制
int ten(string x,int y){int ans0;for(int i0;ix.size();i){ansans*yx[i]-0;}return ans;
}int main(){string n,m;cinnm;memset(h,-1,sizeof h);for(int i0;in.size();i){string tn;t[i]^1; //改变第i位数0变1,1变0if(t[0]0t.size()1) continue; //如果数字存在前导0则不合法直接跳过h[find(ten(t,2))]ten(t,2); //将写错后的数字在十进制下的数值放入哈希表}for(int i0;im.size();i){for(int j0;j3;j){ //枚举第i位数字可能的写错情况然后再在哈希表中查找该数的十进制下数值是否出现过if(m[i]-0!j){ string tmpm;tmp[i]j0;if(tmp[0]0tmp.size()1) continue; //同上if(h[find(ten(tmp,3))]!-1){ //如果该数的十进制的值在哈希表存在过直接输出该数就是答案coutten(tmp,3);}}}}return 0;
}三、知识风暴 哈希表 哈希表的增删改查的时间复杂度为O(1)。C中STL的unordered_set和unordered_map底层就是使用哈希结构实现的。 秦九韶算法 参考百度百科 秦九韶算法是一种多项式的简化算法。 具体做法是将多项式 改写为 先计算内层的数值然后依次由内向外进行拓展。针对本题我们可以使用其来进行计算不同进制转十进制的结果。 例如求二进制1010的十进制 二进制1010转换为10进制的算式可以写成1x230x221x210x20,类比上述多项式2即为多项式中的x二进制的每位数字则是多项式的系数而我们在本题中二进制数是按字符串记为s读入的所以将其每位数字记为s[i]。根据上述算法可知我们最终算的每层均是s[i]*xs[i1]而在计算下一层时上一层的结果更新成了下一层x前面的系数所以我们将上一层的结果记录到临时变量ans中然后按照公式s[i]*xs[i1]依次向外扩展直到遍历完所有数字ans就是多项式的值也就是我们要求的十进制的数值。 所以据此我们可以总结出计算本题将x进制转换为十进制数值的代码 int ans0; //ans存储每层的结果最终ans的值为最外层的值也就是多项式的值
for(int i0;is.size();i){ansans*xs[i]-0; //i可以理解为层数第0层只有第一个数字而最后一层就是整个多项式的值
}
