leetcode麻烦又易忘记题目
一,双指针
同种思路的相向双指针方法
有序数组的平方 做到 O(n)
找到 K 个最接近的元素
数组中的 K 个最强值 用双指针解决
两数之和 II - 输入有序数组
平方数之和
统计和小于目标的下标对数目
采购方案 同 2824 题
三数之和https://leetcode.cn/problems/3sum/description/
最接近的三数之和
四数之和https://leetcode.cn/problems/4sum/description/
有效三角形的个数
数的平方等于两数乘积的方法数 用双指针实现
三数之和的多种可能 1711
1, 四数之和
排序 + 双指针方法。 实现On3时间复杂度
思路:
穷举第一个数
再穷举第二个数
剩下两个数就转为了使用相向双指针寻找恰好让四个数和为target的方法
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
int n = nums.length;
for(int i = 0; i < n - 3; ++i){
long outi = nums[i];
if(i > 0 && outi == nums[i - 1]) continue;
for(int j = i + 1; j < n - 2; ++j){
long outj = nums[j];
//这里用例中虽然溢出了,不担心int强转溢出问题是因为这个用例刚好没有符合条件的组合
if(j > i + 1 &&outj== nums[j - 1]) continue;
int left = j + 1;
int right = n - 1;
while(left < right){
long sum = outi + outj + nums[left] + nums[right];
if(sum > target){
-- right;
}else if(sum < target){
++ left;
}else{
ans.add(List.of((int)outi,(int)outj,nums[left],nums[right]));
for(left++; left < right && nums[left] == nums[left - 1]; ++ left);
for(right --; left < right && nums[right] == nums[right + 1]; -- right);
}
}
}
}
return ans;
}
}
木桶原理
1,盛最多水的容器
https://leetcode.cn/problems/container-with-most-water/description/
class Solution {
public int maxArea(int[] height) {
//这个题就是移动短边
//从题意上,假设以第一个数为左侧边,然后应该穷举右侧边直到最后一个数
//然后再假设以第二个数为左侧边,穷举右侧边直到最后一个数。
//依次类推,暴力。On2
//但是双指针可以实现On的复杂度,同时借助left和right只移动短边
//就代表它所匹配的另一侧的长边,当前的面积是最大值。
//例如:1,8,6,2,5,4,8,3,7
//第一次left的1最短,因为right-left已经是最大,1不管匹配对侧的长边
//包括8,6,2,5,4,8,3这些都不用再遍历了,因为1和7对应的right-left最大
//此时面积就是这些中最大的
int left = 0;
int right = height.length - 1;
int ans = 0;
while(left < right){
int area = (right - left) * Math.min(height[left], height[right]);
ans = Math.max(ans, area);
if(height[left] < height[right]){
++ left;
}else{
-- right;
}
}
return ans;
}
}
2,接雨水
https://leetcode.cn/problems/trapping-rain-water/
class Solution {
public int trap(int[] height) {
//应该把数组每一个位置当作一个桶,这个桶由左侧和右侧组成
//而当前的数值大小,可以认为是在这个桶上填满了heigth[i]的石头
//这个桶剩余的大小才是雨水的。
//而这个桶的大小取决于左侧边,右侧边中较小的那个,短板
//而left和right两个桶,根据lmax和rmax的大小比较,优先计算已经确定较小边的那个
//例如:对于8,0,10,6这个序列。
//left对应的8已经确定左侧边最小是8,但是它的右侧边此时只知道最小是6,在8到6中间数组数据中有没有比6更大的,不确定
//而right对应的6右侧最小边是确定的了,但是左侧边不确定,现在只知道至少有个8了。但是有这个8就够了,因为即使8和6之间有一个10,但是桶取决于最小边6. 那如果有一个比6 更小的呢,例如3,那这个不影响当前的right这个桶啊,因为这个桶右侧必然是6了,同时左侧已经确定至少有一个8了,3即使比6小,但他不可能作为当前这个right这个桶两个边。
int left = 0;
int right = height.length - 1;
int lmax = 0;
int rmax = 0;
int ans = 0;
while(left <= right){
lmax = Math.max(lmax, height[left]);
rmax = Math.max(rmax, height[right]);
if(lmax <= rmax){
ans += lmax - height[left];
++ left;
}else{
ans += rmax - height[right];
-- right;
}
}
return ans;
}
}
同向双指针
1,删除最短的子数组使剩余数组有序
https://leetcode.cn/problems/shortest-subarray-to-be-removed-to-make-array-sorted/description/
class Solution {
public int findLengthOfShortestSubarray(int[] arr) {
//同向双指针
//思路:既然要找非递减序列,虽然含有等值部分,下面以递增相称。
//第一:找一个最长的递增子序列起始点,所以从右侧遍历
int n = arr.length;
int right = n - 1;
while(right >= 1 && arr[right - 1] <= arr[right]){
-- right;
}
//经过while寻找后,是右侧最长递增子序列起始点。
if(right == 0) return 0; //right 都等于0了,说明整个数组就是递增的,不需要删除子数组
//第二:如果不是全部递增的,左侧部分 + 右侧部分组合可能也是递增的,这时
//删除的子数组可能更短。
int ans = right; //默认删除左侧的全部数的子数组
int left = 0;
while(left == 0 || arr[left - 1] <= arr[left]){
while(right < n && arr[left] > arr[right]){
++ right;
}
ans = Math.min(ans, right-left-1); // 注意这个right-left-1是只删除left和right之间的数,例如:2,5,3,只是删除5这个数的长度
++ left;
}
//第三:为什么上面的while可以考虑到所有的删除子数组情况呢??
//因为题目要求只删除一个,注意是一个连续子数组,所以最简单的思考方式是
//让left 和 right两侧尽可能长, 中间部分就是那个删除的最短的子数组
//那为什么不让 中间部分 + right串最长呢? 不可能,会超过一个
//那为什么不让 left串 + 中间部分串最长呢? 不可能,会超过一个
return ans;
}
}
其他
1,分割两个字符串得到回文串
class Solution {
public boolean checkPalindromeFormation(String a, String b) {
//左右寻找到不匹配的部分
//中间剩余的left 到 right部分的串如果是回文的了
//那么 apre1+bsuf1 或者 apre2+bsuf2有一个就是能够拼接成回文的串。
//必须 a 和 b的check都有,一个acheck表示的以 a为前缀, b为后缀的两种情况
//第二个bcheck,表示以b为前缀,a为后缀的两种情况
return check(a, b) || check(b, a);
}
//a和b必须都检查是不是中间剩余串可以符合回文串
//如果只判断a的中间剩余串不是回文串,就认为不能拼接成回文串,
//这是漏掉了b的中间串是回文串, a的前缀 + b含这个b的中间串的后缀串可以拼接成回文串的情况
public boolean check(String a, String b){
int left = 0;
int right = b.length() - 1;
while(left < right && a.charAt(left) == b.charAt(right)){
++ left;
-- right;
}
return isPalindrome(a, left, right) || isPalindrome(b, left, right);
}
public boolean isPalindrome(String s, int i, int j){
while(i < j){
if(s.charAt(i) == s.charAt(j)){
++ i;
-- j;
}else{
return false;
}
}
return true;
}
}