hot100之双指针
移动0(283)先看代码
class Solution {
public void moveZeroes(int[] nums) {
int idx0 = 0;
for (int idx = 0; idx < nums.length; idx++){
if(nums != 0){
int temp = nums;
nums = nums;
nums = temp;
idx0++;
}
}
}
}
[*]分析
由于仅当 nums == 0 时 idx0和idx间距会扩大 即有idx0 ~idx 间都为0
idx0用于记录0的起始位置, idx 向前移动发现非0 填入idx0idx0 向右移动
[*]感悟
双指针通过停一动一, 将两次遍历融合在一次遍历中, 同时维护两个指针, 处理两个数据
盛最多水的容器(011)
先看代码
class Solution {
public int maxArea(int[] height) {
int res = 0;
int lef = 0;
int rig = height.length - 1;
while (lef < rig){
int area = (rig - lef) * Math.min(height, height);
res = Math.max(res, area);
if (height < height){
lef++;
}else rig--;
}
return res;
}
}
[*]分析
容器盛最多水由短板决定, 显然在相同短板下容器越宽越好 所以让左右板从最边缘开始
增大容器容量只能通过寻找更优最短板(lef++ OR rig--), 此时的 trade off 就是容器变窄
[*]感悟
双指针技巧特别适合需要同时考虑多个值的处理场景
三数之和(015)
先看代码
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
int n = nums.length;
Arrays.sort(nums);
for (int i = 0; i < n; i++){
if (nums > 0) break;
if (i > 0 && nums == nums) continue;
int lef = i+1;
int rig = n-1;
while (lef < rig){
int sum = nums + nums + nums;
if(sum == 0){
res.add(Arrays.asList(nums, nums, nums));
while (lef < rig && nums == nums)lef++;
while (lef < rig && nums == nums)rig--;
lef++;
rig--;
}
else if(sum < 0) lef++;
else if(sum > 0) rig--;
}
}
return res;
}
}
[*]分析
分解问题成定一找二 寻找 nums + nums= - nums且 k < i, j < n-1
nums 要和 (nums + nums) 为异号, 且当 nums > 0 时结束
k < i , j < n-1 可行性分析
因为 nums + nums + nums i, j, k 可相互替换
k 枚举了所有 nums OR nums OR nums< 0的情况
先通过 sort 对原数组排序 →(方便去重 |便于 nums > 0 时结束 )
[*]感悟
写完了两数之和, 第一感觉是要以nums作target , 取nums + nums作两数之和
但分析之后发现 还是用了二分
时间复杂度: 双指针O(n*logn + n²/2 ), hash O(n² + k(n))
双指针有 n²/2 因为只枚举小于0情况, 由实际动态浮动 , 这里就先取个2
k(n)指哈希计算、解决哈希冲突, 及哈希扩容
空间复杂度: 双指针O(1), hash O(n² → 利用hashset去重) 双指针在res中操作, 而hash 还要维护set
另外, hash代码实现比较麻烦 orz
接雨水(042)
先看代码
class Solution {
public int trap(int[] height) {
int res = 0;
int lef = 0;
int rig = height.length-1;
int preMax = 0;
int sufMax = 0;
while (lef < rig){
preMax = Math.max(preMax, height);
sufMax = Math.max(sufMax, height);
res += preMax > sufMax ? sufMax - height : preMax - height;
}
return res;
}
}
[*]分析
通过维护全局两侧最高板, 采用了盛最多水的容器(011)的做法 寻找最优短板
对遍历到的块的接水量进行计算
[*]感悟
暂无
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]