秋招突击——算法练习——复习{双指针：移动零、盛最多的水、三数之和}——新作{接雨水}
引言
- 这段时间还是很迷茫的，秋招到了一个阶段，但是收获并不是很多，基本上都在泡池子，没有意向。也就没有在坚持刷题，只是整理一些专门的知识点。
- 现在也想明白了，还是得好好刷题，继续找工作，总归能找到的，急也没用。一个一个面，一个一个总结吧！
- 把hot100再过一遍！
复习
移动零
class Solution {
public void moveZeroes(int[] nums) {
int zeroIdx= 0;
for(int i = 0;i < nums.length;i ++){
if(nums[i] != 0){
nums[zeroIdx ++] = nums[i];
}
}
while(zeroIdx < nums.length) nums[zeroIdx ++] = 0;
}
}
盛最多的水
- 这个怎么证明的，又忘记了，想想看！只记得怎么移动左右指针，然后具体的推导就不知道了。
- 具体的数学推论还是有点混乱，不过大概的思路还是好记得，因为影响最终结果的始终是那个较短的边，直接移动短边就行了！
class Solution {
public int maxArea(int[] height) {
int l = 0;
int r = height.length - 1;
int res = 0;
while (l <= r) {
res = Math.max(res, Math.min(height[l], height[r]) * (r - l ));
if ( height[l] < height[r])
l++;
else
r--;
}
return res;
}
}
三数之和
-
有点丢人了，这个题目已经做了四五遍，还是出了问题
-
出现了元素的重复，是因为双指针，左右指针不应该相交，左指针应该始终小于右指针。
-
修改完之后
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (i != 0 && nums[i] == nums[i - 1])
continue;
for (int l = i + 1, r = nums.length - 1; l < r; l++) {
if (l != i + 1 && nums[l] == nums[l - 1])
continue;
while (r -1 > l && nums[l] + nums[r - 1] + nums[i] >= 0)
r--;
if (nums[l] + nums[r] + nums[i] == 0) {
res.add(Arrays.asList(nums[i], nums[l], nums[r]));
}
}
}
return res;
}
}
新作
接雨水
个人实现
思路分析
- 找到坑，先是单调递减序列，然后再试单调递增序列。
- 没有任何思路，还是看题解
参考实现
- 下面是逐个弹出元素后的计算过程
- 计算对应的区域A的面积
- 弹出第二个元素，然后在计算区域B的面积
- 在往后移动一个元素，然后在弹出新的元素，具体如下如，计算区域C的面积
- 这里使用单调栈实现，每一次弹出元素的时候，更新一下对应的元素
具体逻辑如下
- 如果当前元素小于栈顶元素或者栈为空
- 直接入栈
- 如果当前元素大于等于栈顶元素
- 弹出一个元素，计算一下邻接面积，宽度是当前元素减去左边界，高度是栈顶元素减去已经计算的last面积
- 然后last在更新
class Solution {
public int trap(int[] height) {
Deque<Integer> stk = new ArrayDeque<>();
int resVol = 0;
for(int i = 0 ;i < height.length;i ++){
int last = 0;
// 循环中的代码计算的是A区域的面积
while(!stk.isEmpty() && height[i] >= height[stk.peek()])
{
resVol += (height[stk.peek()] - last) * (i - stk.peek() - 1);
last = height[stk.peek()];
stk.pop();
}
// 计算的是区域B的代码，也就是更新之后的代码，当前元素小于栈顶的元素
if(!stk.isEmpty()) resVol += (i - stk.peek() - 1) * (height[i] - last) ;
stk.push(i);
}
return resVol;
}
}
总结
- 继续准备面试吧，目前还是0offer，有点焦虑了，继续准备吧！
- 准备得那么久了，难受呀！不过还是继续冲吧！
原文地址：https://blog.csdn.net/Blackoutdragon/article/details/142619480
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！