门户网站功能清单,crm系统排行榜,重庆论坛建站模板,大兴安岭地网站seo第三题#xff1a;快乐数
. - 力扣#xff08;LeetCode#xff09;. - 备战技术面试#xff1f;力扣提供海量技术面试资源#xff0c;帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/happy-number/算法思想#xff1a;
1.每个…第三题快乐数
. - 力扣LeetCode. - 备战技术面试力扣提供海量技术面试资源帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/happy-number/算法思想
1.每个节点的值是唯一的因为会形成环所以用节点的值充当指针。
2.快指针走两步慢指针走一步下次相遇时在环内。
3.如果是快乐数则环中的数字全是1否则都不是1因为1的下一个就是1直接判定相遇时节点的值即可。
4.一定会形成环这里就不证明了因为题目条件给了。就算不给也是一定成环的。
代码实现
class Solution {
public:int next(int n) {int res0;while(n) {res(n%10)*(n%10);n/10;}return res;}bool isHappy(int n) {int slown,fastn;do {fastnext(fast);fastnext(fast);slownext(slow);}while(fast!slow);if(fast1) return true;return false;}
}; 第四题盛水最多的容器
. - 力扣LeetCode. - 备战技术面试力扣提供海量技术面试资源帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/container-with-most-water/
算法思想
V Height* WidthHeight取较小的那一个
取两头对于当中较短的边这已经是最好的情况了此时宽度取最大区间长度高度也取最大自己本身将其计入后就不用再考虑了。现在区间缩小了。
如此循环下去区间比1小时lr即可退出。
代码实现
class Solution {
public:int maxArea(vectorint height) {int l0,rheight.size()-1,res0;while(lr) {int NewResmin(height[l],height[r])*(r-l);if(NewResres) resNewRes;if(height[l]height[r]) --r;else l;}return res;}
};
第五题有效三角形之和
. - 力扣LeetCode. - 备战技术面试力扣提供海量技术面试资源帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/valid-triangle-number/算法思想
1.排序使数组单调递增。
2.固定最大的数下标最小是2否则凑不到三个数然后从该数组左边的区间取剩下的两个数字。
3.取小区间的两头一个最小(l)一个最大(r)
如果这两个数足够大max太大了min都能带动其他的更能带的动resr-l; --r;r已经计算完了
如果这两个数不够大min太小了max都带不动l; l 太小了没有利用价值了
当l与r相遇时这个大数就计算完了
4.计算下一个大数一直循环到最后一个
代码实现
class Solution {
public:int triangleNumber(vectorint nums) {sort(nums.begin(),nums.end());int res0,sizenums.size();for(int i2;isize;i) {int l0,ri-1;while(lr) {if(nums[l]nums[r]nums[i]) {resr-l; --r; }else l;}}return res;}
};
第六题两数之和
. - 力扣LeetCode. - 备战技术面试力扣提供海量技术面试资源帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/算法思想
取区间的两头一个最小(l)一个最大(r)
如果这两个数大了max太大了带上最小的数还是超过了target所以min无用 --r;
如果这两个数小了min太小了带上了最大的数都够不到target所以max无用l;
如果相等就找到了走人 每一次行动都会让区间宽度减1如果减没了也就是两指针相遇还没找到那就是没有了。
class Solution {
public:vectorint twoSum(vectorint price, int target) {int l0,rprice.size()-1;while(lr){if(price[l]price[r]target) return {price[l],price[r]};else if(price[l]price[r]target) --r;else l;}return {};}
}; 第七题三数之和
. - 力扣LeetCode. - 备战技术面试力扣提供海量技术面试资源帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/3sum/算法思想
排序双指针
注意去重
1.固定一个数然后在他右边因为本思路左边的数都计完了的区间利用双指针解决两数之和问题。
运行双指针时去重
对于l如果加加完了数值不变则继续加加一直到数值变化
对于r如果减减完了数值不变则接着减减一直到数值变化
2.固定第一个在固定下一个将数组遍历一遍。
遍历时去重如果加加完了数值不变则继续加加一直到数值变化
在连续加加减减时要注意越界问题。
解决方案在连续加加减减时每变化一次判定一次
代码实现
class Solution {
public:vectorvectorint threeSum(vectorint nums) {sort(nums.begin(),nums.end());vectorvectorint res;int sizenums.size();for(int i0;isize;) {if(nums[i]0) break;int ji1,ksize-1;while(jk) {if(nums[i] nums[j]nums[k]0) --k;else if(nums[i]nums[j]nums[k]0) j;else {res.push_back({nums[i],nums[j],nums[k]});j; --k;while(jknums[j-1]nums[j]) j;while(jknums[k]nums[k1]) --k;}}i;while(isize-2nums[i]nums[i-1]) i;}return res;}
}; 第八题四数之和
算法思想
排序双指针
注意去重
1.从左到右轮流固定每一个数然后在他右边的区间利用双指针解决三数之和问题。
2.去重问题和三数之和类似此处略。
代码实现
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {sort(nums.begin(),nums.end());vectorvectorint res;int size nums.size();for(int i0;isize-3;) {for(int ji1;jsize-2;) {int kj1,rsize-1;while(kr) {if((long)nums[i]nums[j]nums[k]nums[r]target) k;else if((long)nums[i]nums[j]nums[k]nums[r]target) --r;else if((long)nums[i]nums[j]nums[k]nums[r]target) {res.push_back({nums[i],nums[j],nums[k],nums[r]});k; --r;while(krnums[k]nums[k-1]) k;while(krnums[r]nums[r1]) --r;}}j;while(jsize-2nums[j]nums[j-1]) j;}i;while(isize-3nums[i]nums[i-1]) i;}return res;}
};
