目录
移动零(原题链接)
复写零(原题链接)
快乐数(原题链接)
盛最多水的容器(原题链接)
有效三角形的个数(原题链接)
查找总价格为目标值的两个商品(原题链接)
三数之和(原题链接)
四数之和(原题链接)
移动零(原题链接)
给定一个数组 nums
,编写一个函数将所有 0
移动到数组的末尾,同时保持非零元素的相对顺序。
请注意 ,必须在不复制数组的情况下原地对数组进行操作。
解题思路
- 定义两个指针
cur
和dest
。cur
用于遍历整个数组。dest
指向下一个非零元素应该放置的位置。- 初始化
dest
为-1
,这是因为我们需要在第一次找到非零元素时将其值赋给dest
并且增加dest
的值。
步骤说明
初始化:
cur
从0开始。dest
从-1开始(表示还没有遇到非零元素)。遍历数组:
- 使用循环遍历整个数组
nums
。- 对于数组中的每一个元素
nums[cur]
,检查它是否是非零元素。
- 如果
nums[cur]
不为0,则执行以下操作:
- 将
dest
加1。- 交换
nums[dest]
和nums[cur]
的值。结束条件:
- 当
cur
遍历完整个数组后,循环结束。结果:
- 所有的非零元素都已经被移动到了数组的前半部分,并保持了原有的顺序。
- 所有的0元素都被移动到了数组的后半部分。
具体代码
class Solution { public:void moveZeroes(vector<int>& nums){for (int cur = 0, dest = -1; cur < nums.size(); cur++){if (nums[cur]){swap(nums[++dest], nums[cur]);}}} };
复写零(原题链接)
给你一个长度固定的整数数组 arr
,请你将该数组中出现的每个零都复写一遍,并将其余的元素向右平移。
注意:请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改,不要从函数返回任何东西。
解题思路
初始化变量
预处理:
复制与调整
步骤说明
初始化:
cur
从0开始。dest
从-1开始。n
是数组的长度。预处理:
- 使用循环遍历整个数组
arr
。- 如果
arr[cur]
是0,则dest
增加2;否则,dest
增加1。- 如果
dest
大于等于n-1
,则退出循环。特殊情况处理:
- 如果
dest
等于n
,说明最后一个位置应该是一个复制的0元素,需要将最后一个元素设置为0,并减少dest
的值以确保不会超出数组长度。- 减少
cur
的值以便在接下来的步骤中重新处理这个位置。复制与调整:
- 从
cur
开始向左遍历数组。- 如果
arr[cur]
不为0,则直接将arr[cur]
复制到dest
的位置。- 如果
arr[cur]
为0,则需要复制两次0元素到dest
的位置。- 在每一步之后减少
dest
的值,并且每次循环结束后减少cur
的值。结束条件:
- 当
cur
小于0 时,循环结束。
具体代码
class Solution { public:void duplicateZeros(vector<int>& arr){int cur = 0, dest = -1, n = arr.size();while (cur < n){if (arr[cur])dest++;elsedest += 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--;}}} };
快乐数(原题链接)
编写一个算法来判断一个数 n
是不是快乐数。
「快乐数」 定义为:
- 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1,那么这个数就是快乐数。
如果 n
是 快乐数 就返回 true
;不是,则返回 false
。
首先我们先证明:
对于任意正整数,通过上述过程要么最终变为 1,要么进入一个循环,而不会出现其他情况。(鸽巢原理)
证明过程
有限性:
- 假设初始数为 𝑛n,且 𝑛n 有 𝑑d 位数字。
- 每次迭代产生的新数的最大值是 𝑑×81d×81,这是因为每一位上的数字最大是 9,而 92=8192=81。
- 因此,无论初始数有多大,经过若干次迭代后,得到的数将不会超过 𝑑×81d×81。
循环检测:
- 既然每次迭代产生的数都是有限集合内的一个数,那么随着迭代次数的增加,必然会出现重复的数。
- 当重复出现时,就会形成一个循环,因为一旦出现了一个数,之后的迭代结果将完全由之前的数决定,形成一个闭环。
唯一循环:
- 如果一个数 𝑛n 通过上述过程变成了 1,那么它就是一个快乐数。
- 如果一个数进入了循环,而循环中没有 1,那么这个数就是一个不快乐数。
- 除了 1 之外,所有可能的循环都是有限的,因为生成的数总是有限集合内的一个数。
解题思路
- 定义辅助函数
bitSum
:计算一个数各位数字的平方和。- 使用快慢指针法
isHappy
:通过快慢指针法检测循环,判断是否为快乐数。
步骤说明
- 初始化变量
slow
和fast
:
slow
初始化为n
。fast
初始化为bitSum(n)
,即对n
应用一次bitSum
函数的结果。- 使用快慢指针法检测循环:
- 在
slow
和fast
不相等的情况下,继续执行循环。- 在每次循环中:
- 更新
slow
为bitSum(slow)
,即对slow
应用一次bitSum
函数。- 更新
fast
为bitSum(bitSum(fast))
,即对fast
应用两次bitSum
函数。- 判断是否为快乐数:
- 如果
slow
和fast
最终相等,并且等于 1,则n
是快乐数。- 如果
slow
和fast
最终相等但不等于 1,则n
不是快乐数,因为它进入了循环。
具体代码
class Solution { public:int bitSum(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 = bitSum(n);while(slow != fast){slow = bitSum(slow);fast = bitSum(bitSum(fast));}return slow == 1;} };
盛最多水的容器(原题链接)
给定一个长度为 n
的整数数组 height
。有 n
条垂线,第 i
条线的两个端点是 (i, 0)
和 (i, height[i])
。
找出其中的两条线,使得它们与 x
轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明:你不能倾斜容器。
解题思路
- 双指针法:使用两个指针
left
和right
,分别指向数组的起始位置和结束位置。- 计算面积:每次计算由
left
和right
指向的两条线形成的容器面积。- 更新最大面积:记录每次计算的最大面积。
- 移动指针:根据高度较小的一侧来移动指针,以寻找可能更大的面积。
步骤说明
- 初始化变量
left
和right
分别指向数组的首尾,ret
用于记录最大的面积。- 循环条件:当
left
小于right
时,继续执行循环。- 计算面积:
- 计算当前容器的面积
v
,面积由较短边的高度和两线间的距离决定:v = min(height[left], height[right]) * (right - left)
。- 更新
ret
为当前面积v
和已记录的最大面积ret
中较大的那个值。- 移动指针:
- 如果
height[left]
小于height[right]
,则将left
向右移动一位。- 否则,将
right
向左移动一位。- 循环结束:当
left
不再小于right
时,循环结束。- 返回结果
ret
。
具体代码
class Solution { public:int maxArea(vector<int>& height) {int left = 0, right = height.size() - 1, ret = 0;while(left < right){int v = min(height[left], height[right]) * (right - left);ret = max(ret, v);if(height[left] < height[right])left++;elseright--;}return ret;} };
有效三角形的个数(原题链接)
给定一个包含非负整数的数组 nums
,返回其中可以组成三角形三条边的三元组个数。
解题思路
- 排序:首先对数组进行排序。
- 双指针法:使用两个指针
left
和right
,分别指向数组的起始位置和当前遍历位置的前一个位置。- 遍历:从数组的末尾开始遍历,每次选取一个数作为最长边。
- 条件判断:根据构成三角形的条件,移动
left
和right
指针来寻找所有可能的组合。
步骤说明
排序:
- 使用
sort
函数对输入数组nums
进行升序排序。初始化变量:
ret
用于记录满足条件的组合数量。n
是数组的长度。遍历数组:
- 从数组的末尾开始,即从最长的边开始遍历。
- 使用循环变量
i
从n - 1
开始递减到2
(因为至少需要三个数才能构成三角形)。双指针法:
- 在每次循环中,使用两个指针
left
和right
,分别初始化为 0 和i - 1
。- 使用内部循环,当
left
小于right
时,继续执行循环。- 根据构成三角形的条件(两边之和大于第三边),进行如下操作:
- 如果
nums[left] + nums[right] > nums[i]
,则满足条件,此时所有位于left
和right
之间的数都可以与nums[left]
和nums[i]
构成三角形,因此加上right - left
的数量。- 如果不满足条件,则将
left
向右移动一位,尝试更大的数。- 如果满足条件,则将
right
向左移动一位,尝试较小的数。返回结果:
- 返回
ret
,即满足条件的组合数量。
具体代码
class Solution { public:int triangleNumber(vector<int>& nums) {sort(nums.begin(), nums.end());int ret = 0, n = nums.size();for(int i = n - 1; i >= 2; i--){int left = 0, right = i - 1;while(left < right){if(nums[left] + nums[right] > nums[i]){ret += right - left;right--;}else{left++;}}}return ret;} };
查找总价格为目标值的两个商品(原题链接)
购物车内的商品价格按照升序记录于数组 price
。请在购物车中找到两个商品的价格总和刚好是 target
。若存在多种情况,返回任一结果即可。
解题思路
- 双指针法:使用两个指针
left
和right
,分别指向数组的起始位置和结束位置。- 计算和:每次计算由
left
和right
指向的两个数的和。- 更新指针:根据和与目标值的关系来更新指针。
- 返回结果:如果找到了符合条件的两个数,则返回这两个数;否则,返回
{ -1, -1 }
。
步骤说明
- 初始化变量
left
和right
分别指向数组的首尾。- 循环条件:当
left
小于right
时,继续执行循环。- 计算和:
- 计算当前和
sum
:sum = price[left] + price[right]
。- 更新指针:
- 如果
sum
大于target
,则将right
向左移动一位。- 如果
sum
小于target
,则将left
向右移动一位。- 如果
sum
等于target
,则找到了符合条件的两个数,返回这两个数。- 循环结束:当
left
不再小于right
时,循环结束。- 返回结果:如果没有找到符合条件的两个数,则返回
{ -1, -1 }
。
具体代码
class Solution { public:vector<int> twoSum(vector<int>& price, int target) {int left = 0, right = price.size() - 1;while(left < right){int sum = price[left] + price[right];if(sum > target)right--;else if(sum < target)left++;elsereturn {price[left], price[right]};}return {-1,-1};} };
三数之和(原题链接)
给你一个整数数组 nums
,判断是否存在三元组 [nums[i], nums[j], nums[k]]
满足 i != j
、i != k
且 j != k
,同时还满足 nums[i] + nums[j] + nums[k] == 0
。请你返回所有和为 0
且不重复的三元组。
注意:答案中不可以包含重复的三元组。
解题思路
- 排序:首先对数组进行排序。
- 双指针法:使用两个指针
left
和right
,分别指向数组的当前位置的后一个位置和数组的末尾。- 遍历:从数组的开头开始遍历,每次选取一个数作为第一个数。
- 条件判断:根据和为 0 的条件,移动
left
和right
指针来寻找所有可能的组合。- 去重:在遍历过程中,跳过重复的元素以避免重复的组合。
步骤说明
排序:
- 使用
sort
函数对输入数组nums
进行升序排序。初始化变量:
ret
用于记录满足条件的组合。n
是数组的长度。遍历数组:
- 从数组的开头开始遍历,使用循环变量
i
。- 当
nums[i]
大于 0 时,提前结束遍历(因为之后的组合肯定大于 0)。双指针法:
- 在每次循环中,使用两个指针
left
和right
,分别初始化为i + 1
和n - 1
。- 使用内部循环,当
left
小于right
时,继续执行循环。- 计算和
sum
:sum = nums[left] + nums[right]
。- 根据和与目标值 0 的关系,进行如下操作:
- 如果
sum
大于 0,则将right
向左移动一位。- 如果
sum
小于 0,则将left
向右移动一位。- 如果
sum
等于 0,则将当前组合加入到结果中,并移动指针以寻找下一个可能的组合。- 在找到有效的组合后,需要跳过重复的元素,以避免重复的组合。
返回结果:
- 返回
ret
,即满足条件的组合列表。
具体代码
class Solution { public:vector<vector<int>> threeSum(vector<int>& nums){vector<vector<int>> ret;sort(nums.begin(), nums.end());int n = nums.size();for (int i = 0; i < n; ){if (nums[i] > 0)break;int left = i + 1, right = n - 1, target = -nums[i];while (left < right){int sum = nums[left] + nums[right];if (sum > target)right--;else if (sum < target)left++;else{ret.push_back({ nums[i], nums[right], nums[left] });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 ret;} };
四数之和(原题链接)
给你一个由 n
个整数组成的数组 nums
,和一个目标值 target
。
请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]]
(若两个四元组元素一一对应,则认为两个四元组重复):
0 <= a, b, c, d < n
a
、b
、c
和d
互不相同nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
解题思路
- 排序:首先对数组进行排序。
- 双指针法:使用两个指针
left
和right
,分别指向数组的当前位置的后一个位置和数组的末尾。- 嵌套循环:使用两层嵌套循环,外层循环遍历数组中的两个数,内层使用双指针法寻找另外两个数,使得四数之和等于目标值。
- 去重:在遍历过程中,跳过重复的元素以避免重复的组合。
步骤说明
排序:
- 使用
sort
函数对输入数组nums
进行升序排序。初始化变量:
ret
用于记录满足条件的组合。n
是数组的长度。外层循环:
- 从数组的开头开始遍历,使用循环变量
i
。- 内层循环遍历数组中的第二个数,使用循环变量
j
。双指针法:
- 在每次内外层循环中,使用两个指针
left
和right
,分别初始化为j + 1
和n - 1
。- 使用内部循环,当
left
小于right
时,继续执行循环。- 计算和
sum
:sum = nums[left] + nums[right]
。- 根据和与目标值
target
的关系,进行如下操作:
- 如果
sum
小于target - nums[i] - nums[j]
,则将left
向右移动一位。- 如果
sum
大于target - nums[i] - nums[j]
,则将right
向左移动一位。- 如果
sum
等于target - nums[i] - nums[j]
,则将当前组合加入到结果中,并移动指针以寻找下一个可能的组合。- 在找到有效的组合后,需要跳过重复的元素,以避免重复的组合。
返回结果:
- 返回
ret
,即满足条件的组合列表。
具体代码
class Solution { public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> ret;sort(nums.begin(), nums.end());int n = nums.size();for(int i = 0; i < n; ){for(int j = i + 1; j < n; ){int left = j + 1, right = n - 1;long long aim = (long long)target - nums[i] - nums[j];while(left < right){int sum = nums[left] + nums[right];if(sum < aim)left++;else if(sum > aim)right--;else{ret.push_back({nums[i], nums[j], nums[left], nums[right]});left++, right--;while (left < right && nums[left] == nums[left - 1])left++;while (left < right && nums[right] == nums[right + 1])right--;}}j++;while(j < n && nums[j] == nums[j-1])j++;}i++;while(i < n && nums[i] == nums[i - 1])i++;}return ret;} };