编程导航算法村第九关 | 二分查找
- LeetCode852.这个题的要求有点啰嗦,核心意思就是在数组中的某位位置i开始,从0到i是递增的,从i+1 到数组最后是递减的,让你找到这个最高点。
详细要求是:符合下列属性的数组 arr 称为山脉数组 :arr.length >= 3存在 i(0 < i < arr.length - 1)使得:
●
arr[0] < arr[1] < … arr[i-1] < arr[i]
●
arr[i] > arr[i+1] > … > arr[arr.length - 1] - 思路:
- 使用二分查找:
- 首先确定左右边界
- 因为必然不是第一个与最后一个,取值范围便是1,length-2
- 分三种情况讨论
- 左边递增区域
- 右边递增区域
- 找见最大值
- 使用二分查找:
public int peakIndexInMountainArray(int[] arr) {
int left = 1;
int right = arr.length - 2;
while (left < right) {
int mid = left + ((right - left) >> 1);
// 符合条件的情况
if (arr[mid - 1] < arr[mid] && 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;
}
旋转数字的最小数字
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]
public int findMin(int[] nums) {
// 如果最小值在中间
// 最小值在左边开端、右边开端
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] < nums[right]) {
right = mid;
}
else {
left = mid + 1;
}
}
return nums[left];
}
找缺失数字
剑指offer题目: 一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。
- 思路:
- 找出第一个num[i]!=i的值就是返回值
public int missingNumber(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] == mid) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
优化求平方根
剑指offer题目
实现函数 int sqrt(int x).计算并返回x的平方根这个题的思路是用最快的方式找到n*n=x的n。这里涉及到四舍五入,所以采用折半进行比较:文章来源:https://www.toymoban.com/news/detail-634759.html
- 思路:在此处需要使用除法,如果使用乘法则可能会导致越界的问题
public int mySqrt(int x) {
int left = 1;
int right = x;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (x / mid > mid) {
left = mid + 1;
} else if (x / mid < mid) {
right = mid - 1;
} else if (x / mid == mid) {
return mid;
}
}
return right;
}
二叉搜索树
2.1 二叉搜索树中搜索特定值
LeetCode 700.给定二叉搜索树(BST)的根节点和一个值。文章来源地址https://www.toymoban.com/news/detail-634759.html
public TreeNode searchBST(TreeNode root, int val) {
if (root == null) {
return null;
}
if (root.val == val) {
return root;
}
// if (root.left != null && root.right != null) {
return searchBST(root.val > val ? root.left : root.right,val);
// }
}
验证二叉搜索树
- LeetCode98.给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
- 需要按照中序遍历,判断左子树是否是二叉搜索树,记录当前节点的值,要保证后面节点的值要大于前面所有节点的值
private long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
if (!isValidBST(root.left)) {
return false;
}
if (root.left != null) {
if (root.val <= root.left.val) {
return false;
}
}
if (root.right != null) {
if (root.val >= root.right.val) {
return false;
}
}
if (root.val <= pre) {
return false;
}
pre = root.val;
if (!isValidBST(root.right)) {
return false;
}
return true;
}
到了这里,关于编程导航算法村第九关 | 二分查找的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!