专注徐州网站建设,岳阳汨罗网站建设,如何做静态网页,网络广告投放的主要方式有基于二分查找的拓展问题
1.山脉数组的峰顶索引
思路#xff1a;二分查找
山峰有三种状态#xff1a;需要注意数组边界
1.顶峰#xff1a;arr[mid]arr[mid1]arr[mid]arr[mid-1]
2.上坡#xff1a;arr[mid]arr[mid1]
3.下坡#xff1a;arr[mid]…基于二分查找的拓展问题
1.山脉数组的峰顶索引
思路二分查找
山峰有三种状态需要注意数组边界
1.顶峰arr[mid]arr[mid1]arr[mid]arr[mid-1]
2.上坡arr[mid]arr[mid1]
3.下坡arr[mid] arr[mid-1]
class Solution {public int peakIndexInMountainArray(int[] arr) {int left 0;int right arr.length-1;while(leftright){int mid left ((right - left)1);if(mid 0 mid arr.length-1){return -1;}if(arr[mid]arr[mid1]arr[mid]arr[mid-1]){return mid;}else if(arr[mid]arr[mid1]){left mid 1;}else if(arr[mid] arr[mid-1]){right mid - 1;}}return -1;}
}
2.寻找旋转排序数组中的最小值 思路抓住目标值nums[mid]一定是小于等于nums[high] class Solution {public int findMin(int[] nums) {int l 0;int r nums.length - 1;int mid 0;while(lr){mid l ((r-l)1);if(nums[mid]nums[r]){l mid 1;}else if(nums[mid]nums[r]){r mid;}}return nums[l];}
}
3.寻找旋转排序数组中的最小值II 思路
本题含有重复的元素
[1,3,3]这种情况就不能单纯的判断nums[mid]nums[high]就舍弃当前mid左区间
但是还是抓住nums[mid]一定是小于等于nums[high]关键也就是一定在high左边
当nums[mid]nums[high]high--缩小范围
class Solution {public int findMin(int[] nums) {int l 0;int r nums.length - 1;int mid 0;while(lr){mid l ((r-l)1);if(nums[mid]nums[r]){l mid 1;}else if(nums[mid]nums[r]){r mid;}else{r - 1;}}return nums[l];}
} 4.缺失的数字 思路 二分查找思路递增数组
一般情况nums[mid]mid说明缺失值在mid右侧
nums[mid]mid说明缺失值在mid左侧
class Solution {public int missingNumber(int[] nums) {int low 0;int high nums.length - 1;while(lowhigh){int mid low ((high - low)1);if(nums[mid]mid){high mid-1;}else if(nums[mid]mid){low mid1;}}return low;}
}
5.x的平方根 思路二分思想需要注意超过int范围的情况不能直接乘
class Solution {public int mySqrt(int x) {if(x 1){return x;}int low 0;int high x;while(lowhigh){int mid low ((high - low)1);if(x/mid mid){return mid;}else if(x/midmid){high mid;}else{low mid1;}}return low-1;}
}
中序和搜索树
二叉搜索树左结点小于根结点右结点大于根结点
二叉搜索树的中序遍历从小到大递增
1.二叉搜索树中的搜索 思路很简单与根结点比较小于往左大于往右等于返回 。
二叉树递归方法参考二叉树经典算法题
按照递归三部曲写出递归函数迭代也是可以的。
class Solution {public TreeNode searchBST(TreeNode root, int val) {if(root null){return null;}if(root.val val){return searchBST(root.left,val);}if(root.val val){return searchBST(root.right,val);}return root;}
}
2.验证二叉搜索树 思路利用搜索树中序遍历递增的特性如果出现小于前一个值的情况就返回false
class Solution {long pre Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if(root null){return true;}boolean left isValidBST(root.left);if(root.valpre){return false;}pre root.val;boolean right isValidBST(root.right);return leftright;}
}
