网站开发合同有效期,omeka wordpress对比,wordpress跨境平台,网站备案查询工信部官网编程导航算法村第九关 | 二分查找
LeetCode852.这个题的要求有点啰嗦#xff0c;核心意思就是在数组中的某位位置i开始#xff0c;从0到i是递增的#xff0c;从i1 到数组最后是递减的#xff0c;让你找到这个最高点。 详细要求是#xff1a;符合下列属性的数组 arr 称为山…编程导航算法村第九关 | 二分查找
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]思路 使用二分查找 首先确定左右边界因为必然不是第一个与最后一个取值范围便是1length-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的递增排序数组中的所有数字都是唯一的并且每个数字都在范围0n-1之内。在范围0n-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*nx的n。这里涉及到四舍五入所以采用折半进行比较
思路在此处需要使用除法如果使用乘法则可能会导致越界的问题 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的根节点和一个值。 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;}
