当前位置: 首页> 科技> IT业 > 微信开发者工具快捷键_鞍山最新消息_东莞今天新增加的情况_广告语

微信开发者工具快捷键_鞍山最新消息_东莞今天新增加的情况_广告语

时间:2025/7/11 12:18:18来源:https://blog.csdn.net/2303_80828380/article/details/142467829 浏览次数:0次
微信开发者工具快捷键_鞍山最新消息_东莞今天新增加的情况_广告语

目录

一、快乐数:

二、有效三角形的个数:

三、盛最多水的容器:

四、复写0:

五、三数之和:

总结:


一、快乐数:

题目出处:

202. 快乐数 - 力扣(LeetCode)icon-default.png?t=O83Ahttps://leetcode.cn/problems/happy-number/

题目说明:

输入示例:

如上图所示:

当输入一个数字的时候,经过多次变化,一定会进入一个圆,如果最后是1可以看做一个圆,里面都是1。如果不是1,那么一定会进入一个圆里面。那么会不会出现一个无限不循环的呢?答案是不会的。

证明思路:

首先,正整型最大的是2147483647,那么便于计算将9999999999代替它,那么将9999999999经过题目所给的方式计算后的结果为810,所以经过题目的操作后,其结果肯定在0~810中,所以一个数字经过811次题目所给操作后肯定会有重复的,那么就会进入一个圆

解题思路:

首先定义快慢指针,慢指针指向输入的数,快指针指向进行一次题目操作后的数字,

因为要多次进行题目所给的操作,所以就需要将题目所给操作封装成一个函数,

最后使用循环判断知直到二者相遇就结束循环,最后返回二者之一是否等于1即可

class Solution {
public:int func(int n){int sum = 0;while(n){int t = n % 10;sum += t*t;n /= 10;}return sum;}bool isHappy(int n) {int slow = n, fast = func(n);while(slow != fast){slow = func(slow);fast = func(func(fast));}return slow == 1;}
};

二、有效三角形的个数:

题目出处:

611. 有效三角形的个数 - 力扣(LeetCode)icon-default.png?t=O83Ahttps://leetcode.cn/problems/valid-triangle-number/题目说明:

输入示例:

解题思路:

既然可以包含重复的,那么就不需要进行去重操作。

主要思路是暴力解法(将每一个情况都列举出来,之后通过三角形两边之和大于另一边进行判断),双指针在暴力解法上更加快速:(三角形最短两边之和大于最长的一边)

那么就将整个数组进行排序(因为这样的话就方便使用双指针进行操作)

需要三个变量,一个指向最左边作为短边,一个指向最右边作为最长的一边,另一个在中间的区间进行寻找能够构成三角形的三个数字。

其中两个if判断

一个if

如果最左边left和最右边right所在的值相加比第三边都长的话就证明左边的所有和right相加都比第三边大,这个时候直接进行right-left找到所有情况加到ret返回值即可,

另一个if就是左边最小的值和右边最大的值相加都小于等于最大的max,这样的话就证明left和右边所有相加都不能够构成三角形,left继续++即可

class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(),nums.end());int ret = 0;int left = 0,right = nums.size()-2,max = nums.size()-1;while(max>left){while(left < right){if(nums[left]+nums[right] > nums[max]){ret += right-left;right--;}else//nums[left]+nums[right] <= nums[max]{left++;}}max--;left = 0;right = max-1;}return ret;}
};

三、盛最多水的容器:

题目出处:

11. 盛最多水的容器 - 力扣(LeetCode)icon-default.png?t=O83Ahttps://leetcode.cn/problems/container-with-most-water/题目说明:

示例:

解题思路:

首先依然是双指针就定义left和right指针指向最左和最右,这里还需要宽度(right-left),高度(left和right所对应的值中小的那一个)最大体积,当前体积(如果比最大体积大就更新最大体积)

之后在循环中使用双指针,

if语句中

如果此时left所在的高度比right所在的高度小,那么就证明left~right中间的所有和此时的left组合成的容器所盛水的体积都比此时要小

所以就将left++;

如果此时left所在的高度比right所在的高度大,那么就证明left~right中间的所有和此时的right组合成的容器所盛水的体积都比此时要小

所以就将right--;

最后更新宽度,高度,此时体积和max体积比较。

循环结束后返回max体积即可

class Solution {
public:int maxArea(vector<int>& height) {int left = 0;int right = height.size() - 1;int wide = right - left;int high = height[left] < height[right] ? height[left] : height[right];int tempval = 0;int maxval = wide*high; while(left < right){if(height[left]<height[right]){left++;}else{right--;}wide--;high = height[left] < height[right] ? height[left] : height[right];tempval = wide*high;if(tempval > maxval){maxval = tempval;}}return maxval;}
};

四、复写0:

题目出处:

1089. 复写零 - 力扣(LeetCode)icon-default.png?t=O83Ahttps://leetcode.cn/problems/duplicate-zeros/题目说明:

解题思路:

首先对于arr数组,复写0,如果从前往后进行复写的时候会发现无论怎样都会覆盖某些值,这样就会丢失数据,那么就需要从后往前进行复写操作。

那么既然是复写,并且数组元素确定,那么肯定这个数组中存在一个数(这个数可能是中间的某个,也可能是最后一个),在进行复写操作后就变为新数组的最后一个数,那么就需要在复写之前找到这个数。 

找到这个数之后就可以进行复写了。

找这个数的思路:

首先依然是定义两个“指针”,一个在数组0位置,另一个在数组-1位置(但是这个位置不会访问,也不能访问)接着往后进行遍历,一般情况下cur在dest的下一个,但是如果cur的位置不是0的话,两个都++,如果cur位置是0的话,就将dest向右移动两位,如果dest到最后的时候,此时cur位置就是要找的这个值。

但是有一个例外情况,就是dest最后+2后越界访问了,这样的话就在确定cur后进行边界检查

最后复写即可:

如果cur位置不是0就直接和dest交换,之后将二者向左移一个位置

如果cur位置是0就将cur和dest交换,之后将二者向左移一个位置,在将此时的dest修改为0,在将dest向左移一个位置。

class Solution {
public:void duplicateZeros(vector<int>& arr) {int cur = 0;int dest = -1;int n = arr.size();while(dest < n - 1){//如果cur位置是0,dest就走两步,不是0就走一步if(arr[cur]){dest++;}else{dest += 2;}if(dest >= n - 1)break;cur++;}if(dest == n){arr[n-1] = 0;cur--;dest-=2;}while(cur>=0){if(arr[cur]){swap(arr[cur--],arr[dest--]);}else{swap(arr[cur--],arr[dest--]);arr[dest--] = 0;}}}
};

五、三数之和:

题目出处:

15. 三数之和 - 力扣(LeetCode)icon-default.png?t=O83Ahttps://leetcode.cn/problems/3sum/description/题目说明:

解题思路:

思路一:

首先进行排序,在进行暴力枚举,最后再利用容器去重

上述方法由于是暴力枚举,在本题中会超时

思路二(“双指针”法):

1、首先依然是进行排序,

2、然后分析题目,要找到三个数相加为0,其实也可以看做两个数的和等于第三个数的相反数。

3、那么就可以首先固定一个数为目标数记为ret,在这个数的后面寻找其余两个数,这两个数的和是-ret即可

注意细节:

1、题目说不能有重复的三元组,那么就需要去重操作。

去重思路:

a、容器去重,直接利用set或者unordered_set进行去重处理

b、每次找到一种结果之后将left和right指针跳过重复元素,当使用完一次双指针之后,也就是在一个ret找完后,ret也要跳过重复元素。

2、要保证不能漏

不漏比较好处理,只需要在每次找到一种结果之后,继续走完当前情况

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(),nums.end());vector<vector<int>> v;int i = 0,n = nums.size();int ret = 0;while(i<n){ret = nums[i];int left = i+1,right = n-1;while(left < right){int sum = -(nums[left] + nums[right]);//-4 -3 -2 -1 0 1 2 3 4 5 6 7 8if(ret < sum) ++left;else if(ret > sum) --right;else{v.push_back({nums[i],nums[left],nums[right]});left++;right--;while(left<right && nums[left] == nums[left-1]) ++left;while(left<right && nums[right] == nums[right+1]) --right;}}i++;while(i<n && nums[i] == nums[i-1]) i++;}return v;}
};

总结:

双指针算法适用于一串有序的数字,能够将暴力枚举的时间复杂度降低一维,n^3->n^2

关键字:微信开发者工具快捷键_鞍山最新消息_东莞今天新增加的情况_广告语

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: