网站建设的基本步奏,记事本做网站,中国建设银行官方招聘网站,扬州做网站的公司一、双指针
1.1移动零
链接#xff1a;283. 移动零 - 力扣#xff08;LeetCode#xff09; 给定一个数组 nums#xff0c;编写一个函数将所有 0 移动到数组的末尾#xff0c;同时保持非零元素的相对顺序。请注意 #xff0c;必须在不复制数组的情况下原地对数组进行操…一、双指针
1.1移动零
链接283. 移动零 - 力扣LeetCode 给定一个数组 nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。请注意 必须在不复制数组的情况下原地对数组进行操作。 示例 1: 输入: nums [0,1,0,3,12]输出: [1,3,12,0,0] 解法 通过两个指针并非是真的指针只是数组的下标dest和cur将长度为n的数组划分为三个部分 [0,dest]cur已经遍历过的地方处理过不为0的部分 [dest1,cur-1]cur已经遍历过的地方处理过为0的部分 [cur,n-1]cur未遍历的地方 第一种情况 cur指向数组元素为0 [0,dest]部分是处理过并且元素不为0的部分cur指向0所以处理后[0,dest]不变 [dest1,cur-1]部分是处理过为0的部分所以处理后[dest1,cur-1]长度加一 [cur,n-1]部分长度减一 第二种情况 cur指向数组元素不为0 [0,dest]部分是处理过并且元素不为0的部分cur指向1所以处理后[0,dest]长度加一dest往后移一位用来存放1 [dest1,cur-1]部分是处理过为0的部分所以处理后[dest1,cur-1]长度不变 [cur,n-1]部分长度减一 dest往后移一位dest指向为0的部分只需要将此时的dest指向和cur指向元素交换即可之后cur 初始状态dest-1cur0 1.nums[cur]为0cur 2.nums[cur] 不为0dest后在交换nums[dest]和nums[cur]; c解法
class Solution {
public:void moveZeroes(vectorint nums) {for(int dest-1,cur0; curnums.size(); cur){if(nums[cur])swap(nums[cur], nums[dest]);}}
};
c语言解法
void moveZeroes(int* nums, int numsSize)
{for(int dest-1,cur0; curnumsSize; cur){if(nums[cur]){ int temp 0;temp nums[dest];nums[dest] nums[cur];nums[cur] temp;}}
} 1.2复写零 链接1089. 复写零 - 力扣LeetCode 给你一个长度固定的整数数组 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]解法 在不用额外的数组情况下从前往后复写会造成数据覆盖的影响因此需要从后往前复写 但从什么位置从后向前进行复写需要额外确定 1.找出从后往前开始复写的位置 2.从后往前复写 初始状态 1.cur指向的元素不为0dest往后移一位 2.cur指向的元素为0dest往后移两位 初始状态cur指向1dest cur再往后移一位指向元素为0 dest往后移两位 当dest移动到最后一位时停止移动记录此刻cur的位置 特殊情况 当cur指向元素0时dest往后移动两位此刻dest越界 手动将数组最后一位将其元素改为0 cur往前移动一位dest往前移两位 从此刻开始复写 1.arr[cur]不为0arr[dest] arr[cur] 2. arr[cur]为0arr[dest] arr[dest-1] 0 直到cur0 c实现
class Solution {
public:void duplicateZeros(vectorint arr) {int cur 0, dest -1;int n arr.size();for(cur0,dest-1; destn-1; cur){if(arr[cur])dest;elsedest 2;}if(dest n){arr[n-1] 0;dest - 2;cur--;}cur--;for(; cur0; cur--){if(arr[cur]){arr[dest] arr[cur];dest--;}else{arr[dest] 0;arr[dest-1] 0;dest - 2;}}}
}; 1.3 快乐数
链接202. 快乐数 - 力扣LeetCode 「快乐数」 定义为 对于一个正整数每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1也可能是 无限循环 但始终变不到 1。如果这个过程 结果为 1那么这个数就是快乐数。 如果 n 是 快乐数 就返回 true 不是则返回 false 。 示例 1 输入n 19
输出true
解释
1^2 9^2 82
8^2 2^2 68
6^2 8^2 100
1^2 0^2 0^2 1
示例 2
输入n 2
输出false对应两种情况 1.重复操作最后结果会变成1 例如19经过4步操作后变为1 2.重复一定操作步骤后陷入无限循环中 例如2平方后变成4又经过几次操作后又出现了4所以会一直陷入循环中 上述两种情况都会进入 一个循环第一种进入的循环全为1第二种循环中不会出现1根据此判断是否为快乐数; 快慢指针可以解决是否是环形链式结构只需判断出slow指针和fast指针相遇时的值是否为1即可slowfast2 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;}
}; 1.4 盛最多水的容器
链接11. 盛最多水的容器 - 力扣LeetCode 给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。说明你不能倾斜容器。 输入[1,8,6,2,5,4,8,3,7]
输出49
解释图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下容器能够容纳水表示为蓝色部分的最大值为 49。解法1暴力解法 0-10-2...0-8 1-21-3...1-8 ... 7-8找出他们中的最大值 解法2 选取两个边5和7所盛水的体积,高度为min(5,7)5,底为4v高×底 20 1.因数1×因数2 乘积1 因数1减小因数2不变乘积1减小 2.因数1×因数2 乘积2 因数1减小因数2减小乘积2减小 下图 固定较矮的一侧移动较高的一侧 1.固定左边蓝色条右边蓝色条移动向左移动一位右边蓝色条高度变为3比左边蓝色条高因此此刻高不变仍为1底减小容积变小 容积最大时为初始状态下标0-8向里缩只会减小 上述较矮的一方向里侧移动左侧蓝色条向右移动一位后如下图所示。 1.固定右边蓝色条左边蓝色条移动向右移动一位右边蓝色条高度变为6比右边蓝色条矮因此此刻高减小为6底减小容积变小 容积最大时为初始状态下标1-8向里缩只会减小 重复上述操作 class Solution
{
public:int maxArea(vectorint height) {int left 0, right height.size()-1, ret 0;while(leftright){int v min(height[left],height[right]) * (right - left);if(ret v)ret v;if(height[left] height[right])left;elseright--;}return ret;}
};
