网页制作站点,全网整合营销外包,辅料企业网站建设费用,网站建设监理今天#xff0c;带来哈希表相关算法的讲解。文中不足错漏之处望请斧正#xff01;
理论基础点这里 1. 快乐数
分析题意
出题者已经把题意明确告诉我们了:
对于一个正整数#xff0c;每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1带来哈希表相关算法的讲解。文中不足错漏之处望请斧正
理论基础点这里 1. 快乐数
分析题意
出题者已经把题意明确告诉我们了:
对于一个正整数每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1也可能是 无限循环 但始终变不到 1。如果这个过程 结果为 1那么这个数就是快乐数。
题意转化
怎么理解?
如果我们替换平方和的过程中, 发现当前的数字之前已经出现过, 那我们就陷入了无限循环.
如果没有把题意转化过来, 就会手足无措了.
解决思路
那我们只需要不断重复替换平方和的过程, 再同时判断平方和之前是否出现过:
没出现过: 继续重复替换出现过: 陷入无限循环, 结束
编程实现
取每位上的数
关于取十进制数上的每位, 可以再谈谈.
如, 要取1234中的每位数.
1234 % 10 4 //取到最后一位
1234 / 10; //去掉最后一位
123 % 10 3 //取到倒数第二位
123 / 10; //去掉最后一位
12 % 10 4 //取到倒数第三位
12 / 10; //去掉最后一位
1 % 10 4 //取到倒数第四位
1 / 10; //去掉最后一位
//最终1234变为0结束如果是二进制, 八进制, 只需要mod8即可.
class Solution {
public:// 可能替换的过程可能一直循环:// 如果当前得到的数之前已经得到过, 则会无限循环; 反之不会bool isHappy(int n) {unordered_setint appearedNum;while (n ! 1) {int sum getSqureSum(n);// 只要当前的数之前没出现过, 就代表可能这个数能变到1if (appearedNum.find(sum) appearedNum.end()) {appearedNum.insert(sum);} else { // 反之不可能变到1return false;}n sum;}return true;}
private:int getSqureSum(int n) {int sum 0;while (n) {sum pow(n % 10, 2);n / 10;}return sum;}
};2. 两数之和
分析题意
*很好理解, 无需分析.
题意转化
找到 x 和 y, 满足 x y target.
解决思路
一层遍历获取 x, 查找nums内是否有这样的 y 满足 y target - x.
关于查找:
for暴力查找 – O(n)哈希快速查找 – O(1)
查找某个元素在某个集合中是否用过, 这是哈希的绝活; 而且题目要求返回下标. 综合这两点, 我们用 unordered_map, 存储键值对的哈希表.
编程实现
class Solution {
public:// 找到 x 和 y, 满足 x y targetvectorint twoSum(vectorint nums, int target) {unordered_mapint, int numsMap; // value, index// 一层遍历获取 x, 查找nums内是否有这样的 y 满足 y target - xfor (int i 0; i nums.size(); i) {int x nums[i];int y target - x;auto iter numsMap.find(y);if (iter ! numsMap.end()) {int i1 i;int i2 iter-first;return {i, iter-second};} else {numsMap.insert(pairint, int(nums[i], i));}}return {};}
};今天的分享就到这里了感谢您能看到这里。
这里是培根的blog期待与你共同进步
