手机软件制作平台_最新新闻事件今天国内视频_磁力搜索引擎哪个好_汕头疫情最新消息

1、移动零

https://leetcode.cn/problems/move-zeroes/
题目链接

题目解析

这道题的意思就是然我们将所有的0都移到数组最后面，非零元素前移，并且只能在原数组中移动，这道题难度比较低我就简单的说一下。

思路实现（我的建议是大家可以现在大脑中思考一下，如果有自己的解法可以与我的思路相比较一下，如果更优就直接下一题，如果没有思路再来看）

首先这道题我们采用的是双指针的算法，双指针广泛运用于数组中元素的操作类题目。

思路：刚开始有如图下面两个指针，现在让我们的cur扫描整个数组，如果cur所对应的元素为0则cur++即可，如果cur所对应的元素非零先让dest++再交换两个位置的值，然后cur++。当cur超过数组大小就结束

完成代码

class Solution {
public:void moveZeroes(vector<int>& nums) {int cur=0;int dst=-1;while(cur<nums.size()){if(nums[cur]!=0){dst++;swap(nums[cur],nums[dst]);}cur++;}}
};

2、复写零

https://leetcode.cn/problems/duplicate-zeros/
题目链接

题目解析

这道题虽然是简单题，但我认为就地这个题目要求增加了不少难度，可以表为中等。
题目意思简单的来说就是将0元素复写，然后0后面的元素右移。

思路实现

首先我们来看一下这道题的异地算法：

简单来说就是开辟一个一样大小的数组，然后cur为扫描原数组的指针，dest为操作copy数组的指针，如果cur位置处的元素不为0，则dest的位置等于cur位置处元素，如果cur处元素为0，则操作两次dest位置为0.

但是这里我们是不能够异地的那我们就需要想办法让其在原数组中实现。

我们可以先找出最后复写的位置，然后像上面异地复写一样执行复写操作。
那我们如何找到我们最后复写的位置呢？
再来一次双指针

这里就是让cur移动，如果cur位置非0，则两指针都++，如果为0，则cur++，dest+=2；
但是这里有个特殊情况：

这种情况我们直接单独考虑即可：让数组最后一个位置为0，cur–，dest-=2.

总结一下：
第一步：找到最后复写位置
第二步：处理特殊情况
第三步：复写操作

完成代码

class Solution {
public:void duplicateZeros(vector<int>& arr) {int cur=0;int dest=-1;//找到最后复写位置while(cur<arr.size()){if(arr[cur]!=0)dest++;elsedest+=2;if(dest>=arr.size()-1)break;cur++;}//判断是否出现越界的情况if(dest==arr.size()){arr[dest-1]=0;dest-=2;cur--;}//开始复写while(cur>=0){if(arr[cur]==0){arr[dest--]=0;arr[dest--]=0;}else{arr[dest--]=arr[cur];}cur--;}}
};

3、快乐数

题目链接
https://leetcode.cn/problems/happy-number/

题目解析

这道题如果没有第二个条件，难度我认为能到困难级别。
题目的意思是给我们一个数，每一次求各个位置的平方和，最后看其是否为1

根据条件二我们可以知道这个数字的平方和求到最后一定循环

这里为了拓展，我们来讲一下为什么循环

为什么一定出现重复？
就算1-810每种情况均只出现一次，到第811次运算也会有一次重复。

思路实现

上面我们讲到了这个数在运算过程中一定会重复（1也算重复）

最后我们可以得到一个我们熟悉的结构，循环链表，不同的是这个循环结构里，快乐数一定是1，非快乐数一定不为1,。

所以最后问题简化为求循环链表的相交节点是否为1，双指针不言而喻了吧，但是有些同学说这里没有节点啊，怎么用双指针，我想说的是这里不要被双指针给迷惑了，指针它可以是一个值，指针++的过程可以理解成计算一次求各个位置平方和。

完成代码

class Solution {
public:bool isHappy(int n) {int slow = n;slow = sop(n);int fast = n;fast = sop(n);fast = sop(fast);while (slow != fast){slow = sop(slow);fast = sop(fast);fast = sop(fast);}return slow==1;}int sop(int n)//计算每位数字平方求和{int add = 0;while (n){int m = n % 10;add += m * m;n /= 10;}return add;}
};

4、盛最多水的容器

题目链接
https://leetcode.cn/problems/container-with-most-water/

题目解析

总算这里来了一道中等题，题目的意思很明确，以下标之差为宽，以对应位置元素为高，求所围成的面积最大。

思路实现

这道题是存在暴力解法的，就是用两层循环算出每一种情况，最后找到最大的即可，但是时间复杂度为（N^2）过不了，有没有简单一点的思路呢？

这里我们只需要将左右端点作为我们的left与right，然后求出面积v1然后移动最大的点，算出v2重复操作，直至left与right相遇，然后找出面积最大的那个即可。

完成代码

class Solution {
public:int maxArea(vector<int>& height) {int left=0,right=height.size()-1;vector<int> volume;while(left<=right){int minheight=height[left]<height[right]?left:right;int vol=(right-left)*height[minheight];volume.push_back(vol);if(minheight==left)left++;elseright--;}int max=volume[0];for(int i=0;i<volume.size();i++){if(max<volume[i])max=volume[i];}return max;}
};