哪里专业做网站,海外精品网站建设,上国外网站用什么dns,360网站推广官网授权商双指针 复写零
给你一个长度固定的整数数组 arr #xff0c;请你将该数组中出现的每个零都复写一遍#xff0c;并将其余的元素向右平移。
注意#xff1a;请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改#xff0c;不要从函数返回任何东西。
…双指针 复写零
给你一个长度固定的整数数组 arr 请你将该数组中出现的每个零都复写一遍并将其余的元素向右平移。
注意请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改不要从函数返回任何东西。
示例 1
输入arr [1,0,2,3,0,4,5,0]
输出[1,0,0,2,3,0,0,4]
解释调用函数后输入的数组将被修改为[1,0,0,2,3,0,0,4]示例 2
输入arr [1,2,3]
输出[1,2,3]
解释调用函数后输入的数组将被修改为[1,2,3]提示
1 arr.length 1040 arr[i] 9
题目解析
特别需要注意的是就地
算法原理
代码如下
class Solution
{
public:void duplicateZeros(vectorint arr) {//1.先找到最后一个数int cur0,dest-1,narr.size();while(curn){if(arr[cur]) dest;else dest2;if(destn-1) break;cur;}//2.处理边界情况if(destn){arr[n-1]0;cur--;dest-2;}//3.从后往前进行复写操作while(cur0){if(arr[cur]) arr[dest--]arr[cur--];else{arr[dest--]0;arr[dest--]0;cur--;}}}
};写这类题目的时候不要在脑袋里面空想要动手动笔去思考像下面这样
更详细点来说 如果「从前向后」进⾏原地复写操作的话由于 0 的出现会复写两次导致没有复写的数「被覆 盖掉」。因此我们选择「从后往前」的复写策略。
但是「从后向前」复写的时候我们需要找到「最后⼀个复写的数」因此我们的⼤体流程分两 步
i. 先找到最后⼀个复写的数
ii. 然后从后向前进⾏复写操作。
算法流程
a. 初始化两个指针 cur 0 dest -1
b. 找到最后⼀个复写的数
i. 当 cur n 的时候⼀直执⾏下⾯循环
• 判断 cur 位置的元素:
◦ 如果是 0 的话 dest 往后移动两位
◦ 否则 dest 往后移动⼀位。
• 判断 dest 时候已经到结束位置如果结束就终⽌循环
• 如果没有结束 cur 继续判断。
c. 判断 dest 是否越界到 n 的位置
i. 如果越界执⾏下⾯三步
n - 1 位置的值修改成 0 cur 向移动⼀步dest 向前移动两步。
d. 从 cur 位置开始往前遍历原数组依次还原出复写后的结果数组
i. 判断 cur 位置的值
如果是 0 dest 以及 dest - 1 位置修改成 0 dest - 2 如果⾮零 dest 位置修改成 0 dest - 1
ii. cur-- 复写下⼀个位置。
快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为
对于一个正整数每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1也可能是 无限循环 但始终变不到 1。如果这个过程 结果为 1那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true 不是则返回 false 。
示例 1
输入n 19
输出true
解释
12 92 82
82 22 68
62 82 100
12 02 02 1示例 2
输入n 2
输出false提示
1 n 231 - 1
题目解析
这个题目让我们想到了带环链表
就可以考虑快慢指针来解决
算法原理
这个题目不需要考虑是否遇不到1或者是循环我们可以想到鸽巢原理 联系到这个题目我们可以知道如果哪个数回不到1那么它一定会落到哪个环里
代码如下
class Solution
{int Add(int n){int sum0;while(n){int tn%10;sumt*t;n/10;}return sum;}
public:bool isHappy(int n) {int slow n,fastAdd(n);while(slow!fast){slowAdd(slow);fastAdd(Add(fast));}return slow1;}
};更进一步来说
题⽬分析:
为了⽅便叙述将「对于⼀个正整数每⼀次将该数替换为它每个位置上的数字的平⽅和」这⼀个 操作记为 x 操作
题⽬告诉我们当我们不断重复 x 操作的时候计算⼀定会「死循环」死的⽅式有两种
▪ 情况⼀⼀直在 1 中死循环即 1 - 1 - 1 - 1…
▪ 情况⼆在历史的数据中死循环但始终变不到 1
由于上述两种情况只会出现⼀种因此只要我们能确定循环是在「情况⼀」中进⾏还是在「情 况⼆」中进⾏就能得到结果。
简单证明
a. 经过⼀次变化之后的最⼤值 9^2 * 10 810 ( 2^31-12147483647 。选⼀个更⼤的最 ⼤ 9999999999 )也就是变化的区间在 [1, 810] 之间
b. 根据「鸽巢原理」⼀个数变化 811 次之后必然会形成⼀个循环
c. 因此变化的过程最终会⾛到⼀个圈⾥⾯因此可以⽤「快慢指针」来解决。
解法快慢指针
算法思路
根据上述的题⽬分析我们可以知道当重复执⾏ x 的时候数据会陷⼊到⼀个「循环」之中。
⽽「快慢指针」有⼀个特性就是在⼀个圆圈中快指针总是会追上慢指针的也就是说他们总会 相遇在⼀个位置上。如果相遇位置的值是 1 那么这个数⼀定是快乐数如果相遇位置不是 1 的话那么就不是快乐数。
补充知识如何求⼀个数 n 每个位置上的数字的平⽅和。
a. 把数 n 每⼀位的数提取出来
循环迭代下⾯步骤
i. int t n % 10 提取个位
ii. n / 10 ⼲掉个位
直到 n 的值变为 0
b. 提取每⼀位的时候⽤⼀个变量 sum 记录这⼀位的平⽅与之前提取位数的平⽅和
▪ sum sum t * t
盛水最多的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
**说明**你不能倾斜容器。
示例 1 输入[1,8,6,2,5,4,8,3,7]
输出49
解释图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下容器能够容纳水表示为蓝色部分的最大值为 49。示例 2
输入height [1,1]
输出1提示
n height.length2 n 1050 height[i] 104
算法原理
代码如下
class Solution
{
public:int maxArea(vectorint height) {int left0,rightheight.size()-1,ret0;while(leftright){int vmin(height[left],height[right])*(right-left);retmax(ret,v);//移动指针if(height[left]height[right]) left;else right--;}return ret;}
};进一步来说
解法⼀暴⼒求解会超时
算法思路
枚举出能构成的所有容器找出其中容积最⼤的值。
◦ 容器容积的计算⽅式
设两指针 i , j 分别指向⽔槽板的最左端以及最右端此时容器的宽度为 j - i 。由于 容器的⾼度由两板中的短板决定因此可得容积公式 v (j - i) * min( height[i], height[j])
算法代码
class Solution {
public:int maxArea(vectorint height) {int n height.size();int ret 0;// 两层 for 枚举出所有可能出现的情况for (int i 0; i n; i) {for (int j i 1; j n; j) {// 计算容积找出最⼤的那⼀个ret max(ret, min(height[i], height[j]) * (j - i));}}
return ret;}
};
解法⼆对撞指针
算法思路
设两个指针 left right 分别指向容器的左右两个端点此时容器的容积 :
v (right - left) * min( height[right], height[left])
容器的左边界为 height[left] 右边界为 height[right] 。
为了⽅便叙述我们假设「左边边界」⼩于「右边边界」。
如果此时我们固定⼀个边界改变另⼀个边界⽔的容积会有如下变化形式
◦ 容器的宽度⼀定变⼩。
◦ 由于左边界较⼩决定了⽔的⾼度。如果改变左边界新的⽔⾯⾼度不确定但是⼀定不会超 过右边的柱⼦⾼度因此容器的容积可能会增⼤。
◦ 如果改变右边界⽆论右边界移动到哪⾥新的⽔⾯的⾼度⼀定不会超过左边界也就是不会 超过现在的⽔⾯⾼度但是由于容器的宽度减⼩因此容器的容积⼀定会变⼩的。
由此可⻅左边界和其余边界的组合情况都可以舍去。所以我们可以 left 跳过这个边界继 续去判断下⼀个左右边界。
当我们不断重复上述过程每次都可以舍去⼤量不必要的枚举过程直到 left 与 right 相 遇。期间产⽣的所有的容积⾥⾯的最⼤值就是最终答案
有效三角形的个数
给定一个包含非负整数的数组 nums 返回其中可以组成三角形三条边的三元组个数。
示例 1:
输入: nums [2,2,3,4]
输出: 3
解释:有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3示例 2:
输入: nums [4,2,3,4]
输出: 4提示:
1 nums.length 10000 nums[i] 1000
这道题也是同理不能够用脑袋空想需要动手去梳理逻辑关系
如下图
题目解析 这里需要注意的是不同顺序但是相同的数字也被算作是一种
算法原理 代码如下
class Solution
{
public:int triangleNumber(vectorint nums) {//1.优化sort(nums.begin(),nums.end());//2.利用双指针解决问题int ret0,nnums.size();for(int in-1;i2;i--)//先固定最大的数{//利用双指针快速统计符合要求的三元组的个数int left0,righti-1;while(leftright){if(nums[left]nums[right]nums[i]){retright-left;right--;}else{left;}}}return ret;}};进一步来说 解法⼀暴⼒求解会超时
算法思路
三层 for 循环枚举出所有的三元组并且判断是否能构成三⻆形。
虽然说是暴⼒求解但是还是想优化⼀下
判断三⻆形的优化
▪ 如果能构成三⻆形需要满⾜任意两边之和要⼤于第三边。但是实际上只需让较⼩的两条边 之和⼤于第三边即可。、
▪ 因此我们可以先将原数组排序然后从⼩到⼤枚举三元组⼀⽅⾯省去枚举的数量另⼀⽅ ⾯⽅便判断是否能构成三⻆形。
算法代码
class Solution {
public:int triangleNumber(vectorint nums) {// 1. 排序sort(nums.begin(), nums.end());int n nums.size(), ret 0;// 2. 从⼩到⼤枚举所有的三元组for (int i 0; i n; i) {for (int j i 1; j n; j) {for (int k j 1; k n; k) {// 当最⼩的两个边之和⼤于第三边的时候统计答案if (nums[i] nums[j] nums[k])ret;} }}return ret;}
};解法⼆排序 双指针
算法思路
先将数组排序。
根据「解法⼀」中的优化思想我们可以固定⼀个「最⻓边」然后在⽐这条边⼩的有序数组中找 出⼀个⼆元组使这个⼆元组之和⼤于这个最⻓边。由于数组是有序的我们可以利⽤「对撞指 针」来优化。
设最⻓边枚举到 i 位置区间 [left, right] 是 i 位置左边的区间也就是⽐它⼩的区 间
◦ 如果 nums[left] nums[right] nums[i]
▪ 说明 [left, right - 1] 区间上的所有元素均可以与 nums[right] 构成⽐ nums[i] ⼤的⼆元组
▪ 满⾜条件的有 right - left 种
▪ 此时 right 位置的元素的所有情况相当于全部考虑完毕 right-- 进⼊下⼀轮判断
◦ 如果 nums[left] nums[right] nums[i]
▪ 说明 left 位置的元素是不可能与 [left 1, right] 位置上的元素构成满⾜条件 的⼆元组
▪ left 位置的元素可以舍去 left 进⼊下轮循环
和为s的两个数字
题⽬描述
输⼊⼀个递增排序的数组和⼀个数字 s 在数组中查找两个数使得它们的和正好是 s 。如果有多 对数字的和等于 s 则输出任意⼀对即可。
⽰例 1
输⼊ nums [2,7,11,15], target 9
输出 [2,7] 或者 [7,2] 找 出⼀个⼆元组使这个⼆元组之和⼤于这个最⻓边。由于数组是有序的我们可以利⽤「对撞指 针」来优化。
设最⻓边枚举到 i 位置区间 [left, right] 是 i 位置左边的区间也就是⽐它⼩的区 间
◦ 如果 nums[left] nums[right] nums[i]
▪ 说明 [left, right - 1] 区间上的所有元素均可以与 nums[right] 构成⽐ nums[i] ⼤的⼆元组
▪ 满⾜条件的有 right - left 种
▪ 此时 right 位置的元素的所有情况相当于全部考虑完毕 right-- 进⼊下⼀轮判断
◦ 如果 nums[left] nums[right] nums[i]
▪ 说明 left 位置的元素是不可能与 [left 1, right] 位置上的元素构成满⾜条件 的⼆元组
▪ left 位置的元素可以舍去 left 进⼊下轮循环
