中国建设教育协会的是假网站吗,防红链接在线生成,宜宾网站制作公司,大米包装设计꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好#xff0c;我是xiaoxie.希望你看完之后,有不足之处请多多谅解#xff0c;让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN … ꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好我是xiaoxie.希望你看完之后,有不足之处请多多谅解让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转载还请通知˶⍤⃝˶ 个人主页xiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 系列专栏xiaoxie的刷题系列专栏——CSDN博客●ᴗσσணღ* 我的目标:团团等我( ◡̀_◡́ ҂) ( ⸝⸝⸝›ᴥ‹⸝⸝⸝ )欢迎各位→点赞 收藏⭐️ 留言关注互三必回! 数组篇
1. 在排序数组中查找元素的第一个和最后一个位置
力扣链接 我相信大家一看到这题是有序的数组有点基础的同学们都会想到二分查找法这一题有思路很容易但提交时却老是无法通过这就是因为没有考虑好边界问题了现在博主为大家介绍两种二分查找法
1.普通二分查找法
做好这一题的关键就在于找到边界
题就是查找 target 在 nums 中的区间即查找 target 在 nums 中的左右边界。
仔细想的话要找 target 在 nums 数组中的左右边界无非存在 3 种情况
target 在 nums[0] ~ nums[n-1] 中nums 中存在 target。例如 nums [5,7,7,8,8,10]target 8返回 [34]。 target 在 nums[0] ~ nums[n-1] 中nums 中不存在 target。例如 nums [5,7,7,8,8,10]target 6返回 [-1,-1]。 target nums[0] 或者 target nums[n-1]。例如 nums [5,7,7,8,8,10], target 4返回 [-1,-1]。
用两个二分查找一个二分查找查找左边界另一个查找右边界分情况讨论上述的 3 种情况。 class Solution {public int[] searchRange(int[] nums, int target) {int start lowerBound(nums, target);if (start nums.length || nums[start] ! target)return new int[]{-1, -1};// 如果 start 存在那么 end 必定存在int end lowerBound(nums, target 1) - 1;return new int[]{start, end};}private int lowerBound(int[] nums, int target) {int left 0, right nums.length - 1; // 闭区间 [left, right]while (left right) { // 区间不为空int mid left (right - left) / 2;if (nums[mid] target)left mid 1; // 范围缩小到 [mid1, right]elseright mid - 1; // 范围缩小到 [left, mid-1]}return left; // right1}
2.红蓝二分查找法
相信大家一直对二分查找法的边界问题一直有困扰一般来说二分查找就这些东西在边界和细节上搞人只要每次做题小心点就没啥问题。现在博主就为大家介绍另外一种二分查找方法它不需要考虑那么多问题只要在最后返回值时多多注意就好了
class Solution {public int searchRangeLeft(int[] nums, int target) {int left -1;int right nums.length;while (left 1 ! right) {int mid (left right) / 2;if (nums[mid] target) {left mid;} else {right mid;}}return left;}public int searchRangeRight(int[] nums, int target) {int left -1;int right nums.length;while (left 1 ! right) {int mid (left right) / 2;if (nums[mid] target) {left mid;} else {right mid;}}return right;}public int[] searchRange(int[] nums, int target) {int leftIndex searchRangeLeft(nums, target);int rightIndex searchRangeRight(nums, target);if (leftIndex rightIndex leftIndex nums.length nums[leftIndex] target nums[rightIndex] target) {return new int[] {rightIndex, leftIndex};}return new int[] {-1, -1};}
}开始时L指针和 R指针取在搜索区间界外L首个元素下标−1R末尾元素下标1此时所有元素均未着色 循环条件始终为 L1 R当 LR 时跳出循环此时蓝红区域划分完成所有元素均已着色 M指针取值始终为 M (LR)/2 L指针和 R指针变化的时候直接变为 M指针即对 M 指针所指向元素进行染色无需 1 或者−1 本模板唯一变化的地方是判断目标元素最终落在左边蓝色区域还是右边红色区域。以不变应万变根据情况的不同变换判断条件大大的降低了出错的可能。 这样就找到左下标和右下标啦再因为该题是找不到就返回-1所以还要再判断同时红蓝二分查找法并不只是适用于这题哦它在大部分的题目都适用目前博主还没有遇到不适用的情况所以大家可以放心用在变换判断条件时和普通二分查找法大大的降低了出错的可能。
2. 删除有序数组中的重复项---快慢指针 这是力扣上的一道简单题有的同学可能说了多余的元素删掉不就得了。
要知道数组的元素在内存地址中是连续的不能单独删除数组中的某个元素只能覆盖所以从中我们第一时间想到也是最简单的就是暴力解法
1.暴力解法
这个题目暴力的解法就是两层for循环一个for循环遍历数组元素 第二个for循环更新数组。
public int removeDuplicates(int[] nums) {if (nums.length 0) {return 0;}int k 1; // 记录唯一元素的个数for (int i 1; i nums.length; i) {boolean isDuplicate false;// 检查当前元素是否已经存在于前面的唯一元素中for (int j 0; j k; j) {if (nums[i] nums[j]) {isDuplicate true;break;}}// 如果当前元素是新的唯一元素则加入到唯一元素列表中if (!isDuplicate) {nums[k] nums[i];k;}}return k;
}很明显暴力解法的时间复杂度是O(n^2)这道题目暴力解法在leetcode上是可以过的。但这面试中你写这个解法显然是不能让面试官满意的。博主这有一个使用双指针快慢指针的解法
2.快慢指针
双指针法快慢指针法 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
定义快慢指针
快指针寻找新数组的元素 新数组就是不含有目标元素的数组慢指针指向更新 新数组下标的位置
很多同学这道题目做的很懵就是不理解 快慢指针究竟都是什么含义所以一定要明确含义后面的思路就更容易理解了。要解这题的思路如下
首先我们写记录下数组第一个元素的数值 int val nums[0];
然后我们在定义一个快指针和慢指针指向数组第二个元素然后快指针寻找新数组的元素 新数组就是不含有目标元素的数组慢指针指向更新 新数组下标的位置如下图 public int removeDuplicates(int[] nums) {int val nums[0]; // 记录当前唯一元素的值int slow 1; // 慢指针指向下一个唯一元素应该存放的位置for (int fast 1; fast nums.length; fast) {if (nums[fast] ! val) { // 如果当前元素与前一个唯一元素不相同nums[slow] nums[fast]; // 将当前元素存放到慢指针指向的位置val nums[slow]; // 更新当前唯一元素的值slow; // 慢指针向后移动}}return slow; // 返回唯一元素的个数
}双指针法快慢指针法在数组和链表的操作中是非常常见的很多考察数组、链表、字符串等操作的面试题都使用双指针法写成这样你的代码才可以说达到了面试的高度了所以我们遇到这一类的题型可以多往快慢指针法那边靠靠我相信你多练习多学习一定可以做到更好。
3.长度最小的子数组 这是力扣上的一道中等难度的数组题还是一样看到这一题第一个想到的方法就是用两个for 循环的暴力解法
1.暴力解法
public class Solution {public int minSubArrayLen(int s, int[] nums) {int result Integer.MAX_VALUE; // 最终的结果int sum 0; // 子序列的数值之和int subLength 0; // 子序列的长度for (int i 0; i nums.length; i) { // 设置子序列起点为isum 0;for (int j i; j nums.length; j) { // 设置子序列终止位置为jsum nums[j];if (sum s) { // 一旦发现子序列和超过了s更新resultsubLength j - i 1; // 取子序列的长度result result subLength ? result : subLength;break; // 因为我们是找符合条件最短的子序列所以一旦符合条件就break}}}// 如果result没有被赋值的话就返回0说明没有符合条件的子序列return result Integer.MAX_VALUE ? 0 : result;}
}2.滑动窗口
该如何把两个for循环变成一个呢我想大家想到的一定是双指针对没错使用双指针现在博主来为大家介绍一种双指针方法滑动窗口。所谓滑动窗口就是不断的调节子序列的起始位置和终止位置从而得出我们要想的结果。它一样是使用双指针只不过这种解法更像是一个窗口的移动所以就称为滑动窗口。
在本题中实现滑动窗口主要确定如下三点
窗口内是什么如何移动窗口的起始位置如何移动窗口的结束位置
窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
窗口的起始位置如何移动如果当前窗口的值大于s了窗口就要向前移动了也就是该缩小了。
窗口的结束位置如何移动窗口的结束位置就是遍历数组的指针也就是for循环里的索引。
解题的关键在于 窗口的起始位置如何移动如图所示 代码如下
class Solution {public int minSubArrayLen(int target, int[] nums) {int result Integer.MAX_VALUE;int star 0,end 0;int sum 0;for(;end nums.length; end) {sum nums[end];while(sum target) {int subl end - star1;result Math.min(subl,result);//动态更新数值sum - nums[star];} }return result Integer.MAX_VALUE ? 0 : result;}
}
好了这就是数组篇的全部内容了后续博主还会持续更新链表篇等等内容大家可以点个关注不错过后续精彩内容。感谢您的阅读祝您一天生活愉快
