上海市建设安全协会网站一360,界面设计包括哪三个方面,律师网站建设模板,网站设计与建设word设计理念关卡名 逢试必考的二分查找 我会了✔️ 内容 1.山脉数组的峰顶索引 ✔️ 2.旋转数字的最小数字 ✔️ 3.寻找缺失数字 ✔️ 4.优化求平方根 ✔️ 5.中序与搜索树原理 ✔️ 6.二叉搜索树中搜索特定值 ✔️ 7.验证二叉搜索树 ✔️
基于二分查找思想#xff0c;可以拓展出很… 关卡名 逢试必考的二分查找 我会了✔️ 内容 1.山脉数组的峰顶索引 ✔️ 2.旋转数字的最小数字 ✔️ 3.寻找缺失数字 ✔️ 4.优化求平方根 ✔️ 5.中序与搜索树原理 ✔️ 6.二叉搜索树中搜索特定值 ✔️ 7.验证二叉搜索树 ✔️
基于二分查找思想可以拓展出很多算法问题的而且很多都是考察的热门 这里我们整理了几道经典的问题。 二分在算法中的应用非常多也是很多大厂钟爱的考察类型感兴趣的同学可以继续研究一下
CC150面试题53在排序数组中查找数字要求统一几个数字在排序数组中出现的次数例如输入排序数组{1,2,3,3,3,3,4,5}和数字3由于3在数组中出现了4次因此输出4。leetcode 34. 在排序数组中查找元素的第一个和最后一个位置LeetCode875.爱吃香蕉的珂珂LeetCode29.两数相除
在前面我们发现很多题使用前序、后序或者层次遍历都可以解决但几乎没有中序遍历的。这是因为中序与前后序相比有不一样的特征例如中序可以和搜索树结合在一起但是前后序则不行。 在理解了二分搜索之后我们会发现中序搜索与二分查找简直就是一个娘养的实在太像了。这里我们就来研究一下中序搜索的问题。
1.基于二分查找的拓展问题
1.1 山脉数组的峰顶索引
LeetCode852.这个题的要求有点啰嗦核心意思就是在数组中的某位位置i开始从0到i是递增的从i1 到数组最后是递减的让你找到这个最高点。 详细要求是符合下列属性的数组 arr 称为山脉数组 arr.length 3存在 i0 i arr.length - 1使得
arr[0] arr[1] ... arr[i-1] arr[i]arr[i] arr[i1] ... arr[arr.length - 1]
给你由整数组成的山脉数组 arr 返回任何满足 arr[0] arr[1] ... arr[i - 1] arr[i] arr[i 1] ... arr[arr.length - 1] 的下标 i 。 这个题其实就是前面找最小值的相关过程而已最简单的方式是对数组进行一次遍历。 当我们遍历到下标i时如果有arr[i-1]arr[i]arr[i1],那么i就是我们需要找出的下标。 其实还可以更简单一些因为是从左开始找的开始的时候必然是arr[i-1]a[i],所以只要找到第一个arr[i]arr[i1]的位置即可。代码就是
public int peakIndexInMountainArray(int[] arr) {int n arr.length;int ans -1;for (int i 1; i n - 1; i) {if (arr[i] arr[i 1]) {ans i;break;}}return ans;
}
这个题能否使用二分来优化一下呢当然可以。 对于二分的某一个位置 midmid 可能的位置有3种情况:
mid在上升阶段的时候满足arr[mid]a[mid-1] arr[mid]arr[mid1]mid在顶峰的时候满足arr[i]a[i-1] arr[i]arr[i1]mid在下降阶段满足arr[mid]a[mid-1] arr[mid]arr[mid1]
因此我们根据 mid 当前所在的位置调整二分的左右指针就能找到顶峰。
public int peakIndexInMountainArray(int[] arr) {if (arr.length 3)return 1;int left 1, right arr.length - 2;while(left right) {int mid left ((right - left)1);if (arr[mid] arr[mid - 1] arr[mid] arr[mid 1])return mid;if (arr[mid] arr[mid 1] arr[mid] arr[mid - 1])left mid 1;if (arr[mid] arr[mid 1] arr[mid] arr[mid - 1])right mid - 1;}return left;
}
1.2. 旋转数字的最小数字
我们说刷算法要按照专题来刷这样才能看清很多题目的内在关系二分查找也是如此很多题目看似与二分无关但是就是在考察二分查找我们一起看一下。 LeetCode153 已知一个长度为 n 的数组预先按照升序排列经由1到n次旋转后得到输入数组。例如原数组 nums [0,1,2,4,5,6,7] 在变化后可能得到
若旋转 4 次则可以得到 [4,5,6,7,0,1,2]若旋转 7 次则可以得到 [0,1,2,4,5,6,7]
注意数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。 示例1 输入nums [4,5,1,23] 输出1 解释原数组为 [1,2,3,4,5] 旋转 3 次得到输入数组。 示例2 输入nums [4,5,6,7,0,1,2] 输出0 解释原数组为 [0,1,2,4,5,6,7] 旋转 4 次得到输入数组。 本部分都摘自LeetCode一个不包含重复元素的升序数组在经过旋转之后可以得到下面可视化的折线图 其中横轴表示数组元素的下标纵轴表示数组元素的值。图中标出了最小值的位置是我们需要查找的目标。 我们考虑数组中的最后一个元素 x在最小值右侧的元素不包括最后一个元素本身它们的值一定都严格小于 x而在最小值左侧的元素它们的值一定都严格大于 x。因此我们可以根据这一条性质通过二分查找的方法找出最小值。 在二分查找的每一步中左边界为 low右边界为 high区间的中点为 pivot最小值就在该区间内。我们将中轴元素 nums[pivot] 与右边界元素 nums[high] 进行比较可能会有以下的三种情况 第一种情况是nums[pivot]nums[high]。如下图所示这说明nums[pivot] 是最小值右侧的元素因此我们可以忽略二分查找区间的右半部分。 第二种情况是 nums[pivot]nums[high]。如下图所示这说明nums[pivot] 是最小值左侧的元素因此我们可以忽略二分查找区间的左半部分。 由于数组不包含重复元素并且只要当前的区间长度不为 1pivot 就不会与high 重合而如果当前的区间长度为 1这说明我们已经可以结束二分查找了。因此不会存在 nums[pivot]nums[high] 的情况。 当二分查找结束时我们就得到了最小值所在的位置。
public int findMin(int[] nums) {int low 0;int high nums.length - 1;while (low high) {int pivot low ((high - low) 1);if (nums[pivot] nums[high]) {high pivot;} else {low pivot 1;}}return nums[low];
}
这里你是否注意到high pivot;而不是我们习惯的high pivot-1呢这是为了防止遗漏元素例如[3,1,2]执行的时候nums[pivot]1小于nums[high]2此时如果highpivot-1则直接变成了0。所以对于这种边界情况很难解释清楚最好的策略就是多写几种场景测试一下看看。这也是二分查找比较烦的情况一般来说解释比较困难也不容易理解清楚所以写几个典型的例子试一下面试的时候大部分case能过就能通过。 我们可以再拓展一下如果在上面的基础上存在重复元素会怎么样呢感兴趣的同学可以研究一下LeetCode154这道题。
1.3 找缺失数字
public int missingNumber (int[] a) {int left 0;int right a.length-1;while(left right){int mid (leftright)/2;if(a[mid]mid){left mid1;}else{right mid;}}return left;
}
1.4 优化求平方根
剑指offer题目 实现函数 int sqrt(int x).计算并返回x的平方根这个题的思路是用最快的方式找到n*nx的n。 如果整数没有平方根一般采用向下取整的方式得到结果。采用折半进行比较的实现过程是
public int sqrt (int x) {int l1,rx;while(l r){int mid l ((r - l)1);if(x/mid mid){l mid 1;} else if(x / mid mid){r mid - 1;} else if(x/mid mid){return mid;}}return r;
} 这种优化思想要记住凡是在有序区间查找的场景都可以用二分查找来优化速度。 如果有序区间是变化的那就每次都针对这个变化的区间进行二分查找。这种题目在LeetCode中特别多的。
2 中序与搜索树原理
在前面我们发现很多题使用前序、后序或者层次遍历都可以解决但几乎没有中序遍历的。这是因为中序与前后序相比有不一样的特征例如中序可以和搜索树结合在一起但是前后序则不行。 二叉搜索树是一个很简单的概念但是想说清楚却不太容易。简单来说就是如果一棵二叉树是搜索树则按照中序遍历其序列正好是一个递增序列。比较规范的定义是
若它的左子树不空则左子树上所有节点的值均小于它的根节点的值;若它的右子树不空则右子树上所有节点的值均大于它的根节点的值;它的左、右子树也分别为二叉排序树。下面这两棵树一个中序序列是{3,6,9,10,14,16,19}一个是{3,6,9,10}因此都是搜索树 搜索树的题目虽然也是用递归但是与前后序有很大区别主要是因为搜索树是有序的就可以根据条件决定某些递归就不必执行了这也称为“剪枝”。
2.1 二叉搜索树中搜索特定值
LeetCode 700.给定二叉搜索树BST的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在则返回 NULL。例如
target为2给定二叉搜索树: 4/ \2 7/ \1 3 你应该返回如下子树: 2 / \ 1 3
本题看起来很复杂但是实现非常简单递归
如果根节点为空 root null 或者根节点的值等于搜索值 val root.val返回根节点。如果 val root.val进入根节点的左子树查找 searchBST(root.left, val)。如果 val root.val进入根节点的右子树查找 searchBST(root.right, val)。
public TreeNode searchBST(TreeNode root, int val) {if (root null || val root.val) return root;return val root.val ? searchBST(root.left, val) : searchBST(root.right, val);
}
如果采用迭代方式也不复杂
如果根节点不空 root ! null 且根节点不是目的节点 val ! root.val如果 val root.val进入根节点的左子树查找 root root.left。如果 val root.val进入根节点的右子树查找 root root.right。
public TreeNode searchBST(TreeNode root, int val) {while (root ! null val ! root.val)root val root.val ? root.left : root.right;return root;
}
2.2 验证二叉搜索树
LeetCode98.给你一个二叉树的根节点 root 判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下
节点的左子树只包含 小于 当前节点的数。节点的右子树只包含 大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。
示例 示例1 输入root [2,1,3] 输出true 示例2 输入root [5,1,4,null,null,3,6] 输出false 解释根节点的值是 5 但是右子节点的值是 4 。 根据题目给出的性质我们可以进一步知道二叉搜索树「中序遍历」得到的值构成的序列一定是升序的在中序遍历的时候实时检查当前节点的值是否大于前一个中序遍历到的节点的值即可。
递归法
long pre Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {if (root null) {return true;}// 如果左子树下某个元素不满足要求则退出if (!isValidBST(root.left)) {return false;}// 访问当前节点如果当前节点小于等于中序遍历的前一个节点说明不满足BST返回 false否则继续遍历。if (root.val pre) {return false;}pre root.val;// 访问右子树return isValidBST(root.right);
}
迭代法 /*** 迭代实现** param root* return*/public static boolean isValidBST2(TreeNode root) {DequeTreeNode stack new LinkedListTreeNode();double inorder 0;while (!stack.isEmpty() || root ! null) {while (root ! null) {stack.push(root);root root.left;}root stack.pop();// 如果中序遍历得到的节点的值小于等于前一个 inorder说明不是二叉搜索树if (root.val inorder) {return false;}inorder root.val;root root.right;}return true;} 如果这个题理解了可以继续研究LeetCode530.二叉搜索树的最小绝对差和LeetCode501.二叉搜索树中的众数两个题。
