沙漠风网站开发怎样,住房和城乡建设部网站下载,普通话手抄报简单又漂亮,中国智慧城市建设门户网站优选算法
双指针
202. 快乐数
链接#xff1a;. - 力扣#xff08;LeetCode#xff09; 【思路】
第一个实例是快乐数#xff0c;因为会变为1且不断是1的循环 第二个实例不可能为1#xff0c;因为会陷入一个没有1的循环 根据两个实例和鸽巢原理可以发现不断的平方和最…优选算法
双指针
202. 快乐数
链接. - 力扣LeetCode 【思路】
第一个实例是快乐数因为会变为1且不断是1的循环 第二个实例不可能为1因为会陷入一个没有1的循环 根据两个实例和鸽巢原理可以发现不断的平方和最终都会形成环所以我们可以联想到用快慢指针慢指针走一步快指针走两步最终会在环相遇判断相遇时是否为1。 //‘平分和’操作int squareSum(int num){int sum 0;while(num){int unit num % 10;num / 10;sum unit*unit;}return sum;}bool isHappy(int n) {//快慢指针int fast n, slow n;//相遇才停下do {//慢指针操作一次slow squareSum(slow);//快指针操作两次fast squareSum(squareSum(fast));} while(fast ! slow);//相遇的值等于1才行return slow 1;} 11. 盛最多水的容器
链接. - 力扣LeetCode 【思路】 容量 底(下标相减) * 高(数组元素较小值)
如图我们先算出最左边(1)和最右边(7)围起来的容量然后7不动1继续和7的左边384...遍历算出容量你会发现底是不断缩短的同时高一直都是1因为高只有两种情况比它小或和它相等所以1和7左边的值算出来的容量都是比1和7的容量小的因为底在不断变小同时高可能不变也可能变小。
所以可以得出结论每次算完容量后元素较小的直接移动不用遍历其他结果。 int maxArea(vectorint height) {int head 0, tail height.size() - 1;int final_cap 0;while(head tail){//计算容量,保留较大值int capacity (tail - head) * min(height[head], height[tail]); final_cap max(final_cap, capacity);//思路的推断移动高度小的一方if(height[head] height[tail]){head;}else{--tail;}}return final_cap;} 611. 有效三角形的个数
链接. - 力扣LeetCode 【思路】
判断三角形最长边小于其它边之和。
先排序获取单调性配合双指针解决问题。
先固定最长边然后先从剩下的区间两端作为另外两条边2910同时因为单调性left的右边都比left大所以right和左边任意一条组合都大于10计算完组合后, right--继续找下一条边此时2510因为单调性right的左边都比right小所以left和right左边的任意一条组合都小于10排除leftleft, 继续找下一条边这样一个区间找完就视为完成一次最大边的固定需要固定下一条最大边直到固定完所有最大边最后一条最大边是倒数第三条因为还剩最后两条构不成三角形。 int triangleNumber(vectorint nums) {//排序获取单调性sort(nums.begin(), nums.end());//固定一个最大边int ret 0;for(int i nums.size() - 1; i 2; --i){//将区间两端作为两条边不断缩小int left 0, right i - 1;while(left right){if(nums[left] nums[right] nums[i]){ret right - left;--right;}else{left;}}}return ret;}
