在国外做电商网站,网站建设技术外文,宁波网络营销咨询,网站开发笔记本要多少钱的1. 移动零 题目分析
对于这类数组分块的问题#xff0c;我们应该首先想到用双指针的思路来进行处理#xff0c;因为数组可以通过下标进行访问#xff0c;所以说我们不用真的定义指针#xff0c;用下标即可。比如本题就要求将数组划分为零区域和非零区域#xff0c;我们不…
1. 移动零 题目分析
对于这类数组分块的问题我们应该首先想到用双指针的思路来进行处理因为数组可以通过下标进行访问所以说我们不用真的定义指针用下标即可。比如本题就要求将数组划分为零区域和非零区域我们不妨定义两个指针cur和destcur不断向后遍历dest则指向已处理区间内最后一个非零元素当cur找到一个非零元素时就把dest并交换dest和cur对应的数组元素
那么在处理数组的过程中数组被划分为了三块区域
[0, dest] [dest1, cur] [cur1, n-1]
分别代表非零区域、零区域、未处理区域
当处理结束后只剩下非零区域和零区域了而我们也实现了题目的要求把数组中的所有元素都移动到数组末尾且不改变其他元素的次序
实现代码
class Solution {
public:void moveZeroes(vectorint nums) {int dest -1, cur 0; // 我们一开始并不知道dest的位置暂时定义为-1while(cur nums.size()) {if(nums[cur] 0) {cur;}else if(nums[cur] ! 0) {dest;swap(nums[dest], nums[cur]);cur;}}}
};
2. 复写零 1089. 复写零 - 力扣LeetCode 题目描述
依据题意数组中的零是会被重复写一遍的那么一旦数组中有0数组后面肯定就会有元素被覆盖掉所以我们肯定是不能从前向后进行处理的。
为了保证不漏掉元素我们应该要找到最后一个没有被覆盖的元素然后把这个元素填到数组最后面接着向前遍历如果碰到的元素是非零就填一次如果是零就填两次这样就实现了把所有的零都复写一遍显然这个过程我们还是需要两个指针来帮助我们完成覆盖的操作。
所以我们接下来要实现的就是
1. 找到最后一个“复写”的数
两个指针cur和destcur向后遍历当碰到0时dest向后移动两位否则向后移动一位这样当dest指向数组末尾时cur指向的位置就是数组中最后一个需要复写的元素位置了
2. 从前向后进行复写
在第一步处理之后dest指向了数组末尾cur指向了最后一个要复写的下标cur和dest开始从后往前移动并把cur元素覆盖到dest位置上如果cur元素为0就覆盖两次
3. 边界情况
一般情况下上述的第一步处理中dest是能正常移动到n-1位置的但是存在这样一种情况 当数组内容如上所示时第一步的操作就会出现问题dest指向了数组长度之外的位置我们需要对这种情况进行特殊处理
实现代码
class Solution {
public:void duplicateZeros(vectorint arr) {int cur 0, dest -1;int n arr.size();while(cur n - 1) // 找到最后一个复写元素{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]) arr[dest--] arr[cur--];else{arr[dest--] 0;arr[dest--] 0;cur--;}}}
};
3. 快乐数
202. 快乐数 - 力扣LeetCode 题目分析 依题意对于一个正整数如果每次将其替换为每个位置上数字的平方和那么这个数最终可能为1或进入无限循环。事实上这一点我们是可以证明的首先给大家讲一下鸽巢原理如果有n个巢穴n1只鸽子那么至少有一个巢穴是有两只鸽子的。然后接下来解决本题n的范围如上如果将其最大值替换为每个位置上数字的平方和2^31-1 的值为2,147,483,647就算把这十位数换成9,999,999,999按照这个算法结果也只有810。 也就是说本题n取值范围内的所有数经过处理得到的结果都不超过810所以只要n经过811次变换最后一定至少出现一次重复的元素也就进入了循环。原因是前810次n已经将所有变换的可能结果枚举了一遍第811次的结果必定在前810次变换结果的集合之中所以必定重复。
算法原理 经过上述证明我们清楚了n经过足够多次数的变换只可能进入重复循环或变为1而1的平方和恒为1也算一个循环。所以我们要判断一个数是不是快乐数只需要判断在循环中这个数是不是1即可。 这就要用到快慢指针算法了fast指针一次移动两个单位slow指针一次移动一个单位则一旦fast和slow相遇就说明已经在循环中了此时仅需判断相遇时值是否为1即可。
代码如下:
class Solution {
public:// 进行变换int getsum(int n) {int sum 0;while(n) {int tmp n % 10;sum tmp * tmp;n / 10;}return sum;}bool isHappy(int n) {int fast n, slow n;do {// fast每次移动两个单位slow移动一个单位fast getsum(getsum(fast));slow getsum(slow);} while(fast ! slow);// 最后仅需判断相遇时值是否为1return fast 1;}
};
4. 盛水最多的容器
11. 盛最多水的容器 - 力扣LeetCode 题目解析 根据题目示例我们发现容器高度是由两端的柱子中较短的一根所决定的设其高度为h两根柱子的距离设为l则我们要找的就是h*l最大的组合
算法原理
解法一 暴力解法 从起始位置开始将所有的位置都枚举一遍最后肯定能找到盛水最多的容器时间复杂度是O(n^2)但这样做肯定是会超时的我们必须想一种更优秀的方法 解法二 双指针算法 我们先用一个小区间来举例子在题目解析中我们看出了容器高度由两端中较短的一方决定。在这个例子中如果我们固定较短的柱子移动另一端可以发现容器的容积是在减小的问题在于
1. 向内枚举区间长度是一定减小的
2. 固定了短端移动另一端如果另一端比短端短高度减小就算比短端长高度也不会变大 所以趋势是l一定减小h不变或减小v h * l则容积也必定减小 而如果我们固定较长的柱子移动另一端情况则有不同如果短端找到更长的柱子容器的容积是有可能增大的 所以我们可以定义两个指针left、right在区间的0和n-1位置找到短的一方计算出当前容积移动长的一方这样我们只需要遍历数组一遍就能够找到最大值时间复杂度为O(n)
class Solution {
public:int maxArea(vectorint height) {int l 0, r height.size() - 1;int h, w;int v 0;while(l ! r) {h height[l] height[r] ? height[l] : height[r];w r - l;int tmp h * w;v tmp v ? tmp : v;if(height[l] height[r]) l;else r--;}return v;}
};
5. 有效三角形的个数 611. 有效三角形的个数 - 力扣LeetCode 题意分析 我们都知道三角形的三条边满足任意两条边之和大于第三条边但是还有一个更进一步的结论假设a b c则只要三个数满足a b c就能保证任意两边之和大于第三条边。 因此本题就转化为了找到数组中满足 a b c 且 a b c 的三元组个数。
算法原理
解法一暴力解法 用三层for循环列举出所有的三元组然后判断是否满足构成三角形的条件则时间复杂度3*n^3进行一下优化如果我们先把数组排序那么判断是否满足条件就只需要一次时间复杂度为n*logn n^3显然时间复杂度还是O(n^3)肯定是会超时的我们需要想办法减小时间复杂度。
解法二双指针算法 在前面我们分析过了要找的是满足 a b c 且 a b c 的三元组个数和解法一中的优化一样我们先将数组进行排序则c肯定就在数组的末端找了所以我们不妨先固定c再找符合条件的a、b即可。 可是如果我们还是用遍历的方式去找a和b那时间复杂度根本就没有降低还是O(n^3)所以必须换一个思路既然 a b 我们不妨定义两个指针leftright分别从数组左右端移动与上一道题类似的我们要通过单调性来决定是移动left还是right 如果 a b c因为数组排过序是单调递增的left过程中是始终满足 a b c 的由于本题求的是三元组个数没必要进行left了直接right - left求个数即可。之后我们再进行right--当left right时说明这个c为最长边的情况列举完了接着求下一个c为最长边的情况。 如果 a b c因为数组排过序是单调递增的如果我们让right--a b 只能更小因此只能让left直到 a b c 或 left right。 代码如下
class Solution {
public:int triangleNumber(vectorint nums) {int a, b, c;int max nums.size() - 1;int cnt 0;sort(nums.begin(), nums.end());while(max 1){int left 0, right max - 1;while(left ! right){a nums[left], b nums[right], c nums[max];if(a b c){cnt right - left;right--;}else left;}max--;}return cnt;}
};
文章转载自： http://www.morning.nwqyq.cn.gov.cn.nwqyq.cn http://www.morning.fsrtm.cn.gov.cn.fsrtm.cn http://www.morning.kntsd.cn.gov.cn.kntsd.cn http://www.morning.rfkyb.cn.gov.cn.rfkyb.cn http://www.morning.kcbml.cn.gov.cn.kcbml.cn http://www.morning.jmmz.cn.gov.cn.jmmz.cn http://www.morning.qnhpq.cn.gov.cn.qnhpq.cn http://www.morning.jycr.cn.gov.cn.jycr.cn http://www.morning.pbzlh.cn.gov.cn.pbzlh.cn http://www.morning.pnjsl.cn.gov.cn.pnjsl.cn http://www.morning.xhfky.cn.gov.cn.xhfky.cn http://www.morning.hqrr.cn.gov.cn.hqrr.cn http://www.morning.hyryq.cn.gov.cn.hyryq.cn http://www.morning.pcxgj.cn.gov.cn.pcxgj.cn http://www.morning.tlyms.cn.gov.cn.tlyms.cn http://www.morning.lkcqz.cn.gov.cn.lkcqz.cn http://www.morning.dmldp.cn.gov.cn.dmldp.cn http://www.morning.tpdg.cn.gov.cn.tpdg.cn http://www.morning.yjfzk.cn.gov.cn.yjfzk.cn http://www.morning.dlwzm.cn.gov.cn.dlwzm.cn http://www.morning.qtyfb.cn.gov.cn.qtyfb.cn http://www.morning.qbmpb.cn.gov.cn.qbmpb.cn http://www.morning.jjxnp.cn.gov.cn.jjxnp.cn http://www.morning.ryxgk.cn.gov.cn.ryxgk.cn http://www.morning.xglgm.cn.gov.cn.xglgm.cn http://www.morning.dljujia.com.gov.cn.dljujia.com http://www.morning.wnhgb.cn.gov.cn.wnhgb.cn http://www.morning.mcpdn.cn.gov.cn.mcpdn.cn http://www.morning.lkwyr.cn.gov.cn.lkwyr.cn http://www.morning.xckdn.cn.gov.cn.xckdn.cn http://www.morning.tslwz.cn.gov.cn.tslwz.cn http://www.morning.tnzwm.cn.gov.cn.tnzwm.cn http://www.morning.wpmlp.cn.gov.cn.wpmlp.cn http://www.morning.rxcqt.cn.gov.cn.rxcqt.cn http://www.morning.ttrdr.cn.gov.cn.ttrdr.cn http://www.morning.dhmll.cn.gov.cn.dhmll.cn http://www.morning.jhrkm.cn.gov.cn.jhrkm.cn http://www.morning.rdnkx.cn.gov.cn.rdnkx.cn http://www.morning.kpgbz.cn.gov.cn.kpgbz.cn http://www.morning.hsrpc.cn.gov.cn.hsrpc.cn http://www.morning.hdlhh.cn.gov.cn.hdlhh.cn http://www.morning.fhyhr.cn.gov.cn.fhyhr.cn http://www.morning.gcqdp.cn.gov.cn.gcqdp.cn http://www.morning.mtyhk.cn.gov.cn.mtyhk.cn http://www.morning.srgwr.cn.gov.cn.srgwr.cn http://www.morning.pnbls.cn.gov.cn.pnbls.cn http://www.morning.bwttj.cn.gov.cn.bwttj.cn http://www.morning.qbpqw.cn.gov.cn.qbpqw.cn http://www.morning.sxhdzyw.com.gov.cn.sxhdzyw.com http://www.morning.wblpn.cn.gov.cn.wblpn.cn http://www.morning.cfpq.cn.gov.cn.cfpq.cn http://www.morning.rkdzm.cn.gov.cn.rkdzm.cn http://www.morning.kxyqy.cn.gov.cn.kxyqy.cn http://www.morning.hxxzp.cn.gov.cn.hxxzp.cn http://www.morning.gthc.cn.gov.cn.gthc.cn http://www.morning.qbzdj.cn.gov.cn.qbzdj.cn http://www.morning.kqpsj.cn.gov.cn.kqpsj.cn http://www.morning.pyxtn.cn.gov.cn.pyxtn.cn http://www.morning.tnhqr.cn.gov.cn.tnhqr.cn http://www.morning.fdwlg.cn.gov.cn.fdwlg.cn http://www.morning.tkkjl.cn.gov.cn.tkkjl.cn http://www.morning.qglqb.cn.gov.cn.qglqb.cn http://www.morning.xqknl.cn.gov.cn.xqknl.cn http://www.morning.bxnrx.cn.gov.cn.bxnrx.cn http://www.morning.hbxnb.cn.gov.cn.hbxnb.cn http://www.morning.rqlqd.cn.gov.cn.rqlqd.cn http://www.morning.jtdrz.cn.gov.cn.jtdrz.cn http://www.morning.rqkck.cn.gov.cn.rqkck.cn http://www.morning.btpzn.cn.gov.cn.btpzn.cn http://www.morning.rnwmp.cn.gov.cn.rnwmp.cn http://www.morning.rszt.cn.gov.cn.rszt.cn http://www.morning.xylxm.cn.gov.cn.xylxm.cn http://www.morning.fhykt.cn.gov.cn.fhykt.cn http://www.morning.bmtyn.cn.gov.cn.bmtyn.cn http://www.morning.tkxyx.cn.gov.cn.tkxyx.cn http://www.morning.qhrlb.cn.gov.cn.qhrlb.cn http://www.morning.pfnlc.cn.gov.cn.pfnlc.cn http://www.morning.jkrrg.cn.gov.cn.jkrrg.cn http://www.morning.rqqkc.cn.gov.cn.rqqkc.cn http://www.morning.rmqmc.cn.gov.cn.rmqmc.cn
