老河口网站建设,wordpress数据库没有填写,美丽深圳微信公众号二维码,如何制作公司app文章目录 leetcode202. 快乐数基本思路AC-code leetcode1. 两数之和基本思路AC-code 454.四数相加II基本思路AC-code leetcode202. 快乐数
链接
基本思路
实际上题目隐藏着一个小细节#xff0c;就是告诉你会发生无限循环#xff0c;那我们该如何跳出这个无限循环就是一个… 文章目录 leetcode202. 快乐数基本思路AC-code leetcode1. 两数之和基本思路AC-code 454.四数相加II基本思路AC-code leetcode202. 快乐数
链接
基本思路
实际上题目隐藏着一个小细节就是告诉你会发生无限循环那我们该如何跳出这个无限循环就是一个需要想通的点而在这个过程中我们通过几次样例的测试或者根据常识的判断最后发生无限循环的原因就是存在了出现相同的数导致陷入了局部无限循环。所以自然而然可以想得到要使用set/vector探索是否会出现相同的数以此退出无限循环。
AC-code
class Solution {
public://传入n得到新的nint happy(int n){int sum 0;int tail;while(n){tail n % 10;n / 10;sum tail*tail;}return sum;}bool isHappy(int n) {//题目提示说了可能会出现无限循环潜台词就是告诉我们对应的n会不断出现循环的值。所以根据题目的意思我们跳出无限循环的条件就是判断n是否已经出现过了出现了就可以跳出没有出现就继续循环知道为1.//定义一个set用于储存结果如果结果出现了相同的值就进行一个跳出循环没有就继续训话 。unordered_setintset_n;while(n ! 1){//当找到了就直接推出无限循环返回失败if(set_n.find(n) ! set_n.end())return false;//插入未出现的数据set_n.insert(n);//进行新一轮运算n happy(n);}return true;}
};leetcode1. 两数之和
链接
基本思路
首先这道题正常人的想法肯定是直接进行两层for循环进行暴力遍历但时间复杂度是O(n2)所以可以进行稍微的修改。
实际上算法的思想就是一层for循环遍历做两种事情也就是我们取出对应数组的元素然后拿target-当前对应数组的元素将其与与之前所寻找到的元素进行作比较如果存在就是返回正确答案不存在就继续循环。
接下来需要明确两点
map用来做什么 map中key和value分别表示什么 map目的用来存放我们访问过的元素因为遍历数组的时候需要记录我们之前遍历过哪些元素和对应的下标这样才能找到与当前元素相匹配的也就是相加等于target
接下来是map中key和value分别表示什么。
这道题 我们需要 给出一个元素判断这个元素是否出现过如果出现过返回这个元素的下标。
那么判断元素是否出现这个元素就要作为key所以数组中的元素作为key有key对应的就是valuevalue用来存下标。
AC-code
暴力的代码
class Solution {
public:vectorint twoSum(vectorint nums, int target) {vectorint result(2,0);for(auto i1 nums.cbegin() ; i1!nums.cend() ; i1){int flag 0;for(auto i2 i11 ; i2!nums.cend() ; i2){if(*i1*i2target){flag 1;result[0] i1-nums.begin();result[1] i2-nums.begin();break;}}if(flag)break;}return result;}
};使用map的代码
class Solution {
public:vectorint twoSum(vectorint nums, int target) {//定义哈希数组用于存储已经遍历过的numsunordered_mapint,int map_nums;//定义一个temp用于存储减值int temp 0;//for循环遍历nums并且判断target-num对应的数据是否在map当中出现过如果出现过就返回没出现过就继续。for(int i 0; i ! nums.size(); i){temp target - nums[i];//判断temp在map当中是否出现过if(map_nums.find(temp) ! map_nums.end())return vectorint{map_nums[temp],i};//如果没找到map_nums.insert(make_pair(nums[i],i));}return vectorint{};}
};454.四数相加II
链接
基本思路
本题正常想法肯定是直接四层for循环进行判断但这种时间复杂度就是O(n4),那有没有一种方法可以减小时间复杂度呢答案是有的实际上就是使用哈希表存储ab的值并在循环遍历cd的时候去哈希表当中寻找是否出现了对应的相反数如果存在就是满足条件不是加上出现的次数好好想想为什么不存在就继续循环。
首先定义 一个unordered_mapkey放a和b两数之和value 放a和b两数之和出现的次数。遍历大A和大B数组统计两个数组元素之和和出现的次数放到map中。 定义int变量count用来统计 abcd 0 出现的次数。在遍历大C和大D数组找到如果 0-(cd) 在map中出现过的话就用count把map中key对应的value也就是出现次数统计出来。最后返回统计值 count 就可以了
AC-code
class Solution {
public:int fourSumCount(vectorint nums1, vectorint nums2, vectorint nums3, vectorint nums4) {//创建哈希表存储nums1nums2,并且使用mapvalue就是对应的出现的次数unordered_mapint,intmap_num;//定义result为出现的次数int result 0;//循环遍历nums1和nums2统计出现的次数以及值for(auto i : nums1)for(auto j : nums2)map_num[ij];//遍历nums3和nums4并且查询是否出现过出现过就对应的次数for(auto i : nums3){for(auto j : nums4){//如果找到了if(map_num.find(0-i-j) ! map_num.end()){result map_num[0-i-j];}}}return result;}
};
