自己做的网站有什么用,个人做网站名称怎么选择,网站新闻页面设计,国内大型网站域名202.快乐数
力扣链接
代码随想录链接
思路
看到这一题没思路#xff0c;直接看题解。
发现其中一个难点在于“无限循环”#xff0c;这个字眼可以转换成退出条件。退出条件就有两种#xff0c;一种是这个数字是快乐数#xff0c;一种是这个数字不是快乐数。
如果是快…202.快乐数
力扣链接
代码随想录链接
思路
看到这一题没思路直接看题解。
发现其中一个难点在于“无限循环”这个字眼可以转换成退出条件。退出条件就有两种一种是这个数字是快乐数一种是这个数字不是快乐数。
如果是快乐数好说判断结果是否为1即可。如果不是呢就需要看无限循环。
无限循环的意思翻译下就是判断之后出现的结果是否在之前的哈希表中存在。如果存在则说明这个数字是快乐数。
另外一个难点就是怎么对其计算出数字之和发现用循环解决的。
伪代码
当结果集合不存在1时得到一个计算结果判断这个结算结果是否存在如果存在说明开始循环了返回false将其放入结果集合中
返回true因为退出循环了代码
int getSum(int n ){int sum 0 ;while(n!0){sum (n%10)*(n%10);n /10;}return sum;
}
bool isHappy(int n) {unordered_setint st;n getSum(n);st.insert(n);while(st.find(1)st.end()){//等于就相当没找到n getSum(n);if(st.find(n)!st.end()){//说明已经有重复的n了return false;}st.insert(n);}//取出数字的每个位置的平方和放入unorderd_set中return true;
}1.两数之和
力扣链接
代码随想录链接
思路
刷力扣第一题刚开始是想暴力循环两轮取出对应的下标。但因为按照代码随想录刷题所以借用它的思想使用哈希表。若使用哈希表则问题转换为看哪个元素在集合中出现过接下来就是这个元素是什么——应该是target-其中一个元素的差。也就是看差是否出现以及出现在哪里。
思路想到这里卡住便去看卡尔讲解视频。
用到了哈希映射如果这个差没有在集合中那么就添加到里面如果在的话就取出来作为返回结果。
此时有几个问题要回答。
①为什么会想到用哈希法
②为什么会想到要用map以及mapunordered-mapmulti-map为什么用第二个
③map的作用是什么
④map的key是用来干什么的为什么key/value不能转换
问题①在看到一道题出现其中一个元素是否存在/出现时就要考虑是否能使用哈希表
对应到这道题目就是在遍历时需要看这个差是否出现过若出现那它的索引是什么。所以根据这个思考过程想到用哈希表。
问题②因为要获取其索引而差其实是数组元素的数值索引是另外一个数据所以需要存储两个元素数值索引。就需要用到map。
为什么用unordered-map因为map和multi-map的底层是红黑树而unordered-map底层是哈希表索引查找会更快。
问题③既然要获取其索引map的作用在这道题中就是存储暂时不是差的元素。
问题④key存放的是数值就是看差是否在map中。如果value存放的是数值key存放的是索引那么无法在map中直接通过差查询而需要遍历差通过value来比对会影响效率。
时间复杂度 O ( n ) O(n) O(n)
空间复杂度 O ( n ) O(n) O(n)
伪代码 //只会存在一个有效答案遍历数组依次查看所需元素是否在map中如果需要的元素在map中则返回当前下标以及对应元素下标如果不在map中则将当前元素存入map中返回空代码
vectorint twoSum(vectorint nums, int target) {mapint , int mp ;vectorint vt;for(int i 0 ; i nums.size(); i){int need_num target - nums[i];mapint, int::iterator map_result mp.find(need_num);if (map_result mp.end()){//这意思就是没找到所需要的元素mp.insert(pairint,int(nums[i],i));}else{//存放进{}中vt.push_back(map_result-second);vt.push_back(i);return vt;}}return vt;
}
