Leetcode热题100(双指针篇)
题目出自Leetcode热题100：Leetcode热题100
文章目录
- 283. 移动零
- 思路
- 代码
- C++
- Java
- Python
- 11. 盛最多水的容器
- 思路
- 代码
- C++
- Java
- Python
- 15. 三数之和
- 思路
- 代码
- C++
- Java
- Python
- 42. 接雨水
- 思路
- 代码
- C++
- Java
- Python
- 总结
283. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
思路
必须在不复制数组的情况下原地对数组进行操作，这是题目要求。
如果我把这个要求去掉呢？是不是就可以再开一个数组，然后从头开始遍历这两个数组，遍历原数组时，遇到非0元素就把该元素插入到新数组中，最后在补0。
那么推广一下，把这个过程放放到原数组中，既然两个数组分别用一个指针来遍历，那么现在在原数组上可以用两个指针来模拟开始的过程。
cur表示遍历到当前元素，prev表示第一个的0的位置。
解题过程
先创建两个初始变量，cur和prev。
开始遍历数组，当cur指向的元素为0时如果prev没有指向0，那么就把prev移过来。
当cur指向的元素为非0时，如果prev已经指向0了那么可以开始交换了。
代码
C++
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int cur = 0,prev = 0;
while(cur<nums.size())
{
if(nums[cur] == 0&&nums[prev]!=0)
{
prev = cur;
}
else if(nums[cur]!=0&&nums[prev]==0)
{
swap(nums[prev],nums[cur]);
prev++;
}
cur++;
}
}
};
Java
class Solution {
public void moveZeroes(int[] nums) {
int cur = 0,prev = 0;
while(cur<nums.length){
if(nums[cur]==0&&nums[prev]!=0){
prev = cur;
}
else if(nums[cur]!=0&&nums[prev]==0){
int tmp = nums[cur];
nums[cur] = nums[prev];
nums[prev] = tmp;
prev++;
}
cur++;
}
}
}
Python
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
cur = 0
prev = 0
while cur<len(nums):
if nums[cur]==0 and nums[prev]!=0:
prev = cur
elif nums[cur]!=0 and nums[prev]==0:
nums[cur],nums[prev] = nums[prev],nums[cur]
prev+=1
cur+=1
"""
Do not return anything, modify nums in-place instead.
"""
11. 盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
思路
容器盛水的面积为底乘高，如果使用暴力的做法，把所有的子数组都枚举一遍肯定会超时的。那么怎么优化？
在暴力遍历的过程中，底在增加，高不确定，也就导致了面积是变大还是变小是不确定的。
那么是否可以让底减小，选择性的控制左右边界。
因为底变小了，只有在高上下功夫，如果左边界小于右边界，就把左边界向右移动，反之移动右边。
这是因为，无论移动左边还是右边底都是不变的，为此需要保留高边，是为了获得更高边的机会。
那么把底推广来整个数组，用left指向0，right指向n-1。根据上面的思路来移动left和right。
代码
C++
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0,right = height.size()-1,ans = 0;
while(left<right)
{
ans = max(ans,(right-left)*min(height[left],height[right]));
if(height[left]<height[right]) left++;
else right--;
}
return ans;
}
};
Java
class Solution {
public int maxArea(int[] height) {
int left = 0,right = height.length-1,ans = 0;
while(left<right){
ans = Math.max(ans,(right-left)*Math.min(height[left],height[right]));
if(height[left]<height[right]) left++;
else right--;
}
return ans;
}
}
Python
class Solution:
def maxArea(self, height: List[int]) -> int:
left = 0
right = len(height)-1
ans = 0
while left<right:
ans = max(ans,(right-left)*min(height[right],height[left]))
if(height[left]<height[right]):
left+=1
else:
right-=1
return ans
15. 三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
思路
考虑到三数之和为a+b+c ==0。移动一位就可以变成a = = -(b+c)
不就是b+c == -a的二数之和吗？
那么就可以枚举固定数组元素充当a，在剩下的元素中寻找二数之和。二数之和因为这里不同力扣的第一题是返回下标，所以可以对数组进行排序，初始时b在左端，c在右端。
如果b+c<-c，那么b就往右移动，如果b+c>-c，c就往左移动，直到匹配。完成后将a往右移动一位，重复操作。
解决重复问题
考虑到可能存在多个重复的数组造成答案重复，可以再添加一个去重循环。以a为例，设a为nums[i].如果nums[i]==nums[i-1]就++i。
代码
C++
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
int n = nums.size();
vector<vector<int>> ans;
for(int i = 0;i<n;++i)
{
if(i>0&&nums[i]==nums[i-1]) continue;
for(int j = i+1,k = n-1;j<k;)
{
if(nums[i]+nums[j]+nums[k]<0) j++;
else if(nums[i]+nums[j]+nums[k]>0) k--;
else
{
ans.push_back({nums[i],nums[j],nums[k]});
j++;
while(nums[j]==nums[j-1]&&j<k)j++;
}
}
}
return ans;
}
};
Java
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
int n = nums.length;
for(int i = 0;i<n;++i){
if(i>0&&nums[i]==nums[i-1]) continue;
for(int j = i+1,k= n-1;j<k;){
if(nums[i]+nums[j]+nums[k]<0) j++;
else if(nums[i]+nums[j]+nums[k]>0) k--;
else{
ans.add(Arrays.asList(nums[i],nums[j],nums[k]));
j++;
while(j<k&&nums[j]==nums[j-1]) j++;
k--;
while(j<k&&nums[k]==nums[k+1]) k--;
}
}
}
return ans;
}
}
Python
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
n = len(nums)
ans = list()
for i in range(0,n):
if(i>0 and nums[i]==nums[i-1]): continue
j = i+1
k = n-1
while j<k:
if nums[i]+nums[j]+nums[k]<0: j+=1
elif nums[i]+nums[j]+nums[k]>0: k-=1
else:
ans.append([nums[i],nums[j],nums[k]])
j+=1
while nums[j]==nums[j-1] and j<k:j+=1
k -= 1
while j < k and nums[k] == nums[k + 1]:
k -= 1
return ans
42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
思路
通过对题目的理解，我们可以发现当后面的柱子高度比前面的低时，是无法接着雨水的。
这也就导致，在出现比前面柱子高的柱子前，前面的柱子都是递减状态。那么我们是不是就可以使用单调递减栈来解决问题呢？
利用单调栈解决问题：
当我们在遍历数组时会遇到3种情况：
1.栈为空
直接将当前元素入栈
2.栈不为空，且当前遍历元素小于栈顶元素
直接将当前元素入栈
3.栈不为空，但是当前遍历元素大于等于栈顶元素
这种情况就可以接着雨水了，那么我们也要开始操作了。
雨水区域的右边r指的是当前遍历的下标i
因为遇到了更大的元素，我们需要对其进行出栈，不过在此前我们还要利用top来保存一下啊。
左边的l 就是新的栈顶st.top(要确保左边存在)
这样的话，雨水的区域也就确定下来了，水坑的高度就是左右两边更低的一边减去底部，宽度就是左右之间。
最后使用乘法计算面积。
代码
C++
class Solution {
public:
int trap(vector<int>& arr) {
int ans = 0;
stack<int> st;
int n = arr.size();
for(int i = 0;i<n;++i){
while(!st.empty()&&arr[i]>arr[st.top()]){
int top = st.top();
st.pop();
if(st.empty()){
break;
}
int left = st.top();
int wid = i-left-1;
int height = min(arr[left],arr[i])-arr[top];
ans+=(height*wid);
}
st.push(i);
}
return ans;
}
};
Java
class Solution {
public int trap(int[] height) {
int ret = 0;
Stack<Integer> st = new Stack<>();
for(int i = 0;i<height.length;++i){
while(!st.empty()&&height[i]>height[st.peek()]){
int top = st.pop();
if(st.empty()){
break;
}
int left = st.peek();
int high = Math.min(height[i],height[left])-height[top];
ret+=high*(i-left-1);
}
st.push(i);
}
return ret;
}
}
Python
class Solution:
def trap(self, height: List[int]) -> int:
arr = []
ret = 0
for i in range(len(height)):
while(len(arr)!=0 and height[i]>height[arr[-1]]):
top = arr[-1]
arr.pop()
if len(arr) == 0:
break
left = arr[-1]
high = min(height[left],height[i])-height[top]
ret+=high*(i-left-1)
arr.append(i)
return ret
总结
双指针在实际的算法中，大多数还是依靠经验，当你接触过这种题型，下次碰到就会显得游刃有余了。
此篇章记录我的刷图历程