LeetCode_02_BinarySearch笔记总结
摘要
今天主要涉及到的二分查找的一些变型形式，比如在树上，其中涉及到好些知识点，完全二叉树，二分搜索树，还有移位运算的原理等.
正文
1. LC167. Two Sum II - Input array is sorted
题目：
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution and you may not use the same element twice.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
使用公司:
Amazon
难度:
容易
题目与思路分析:
这道题是说给定一个正序排列了的数组，找到两个值要和等于sum,返回这两个数是第几个数(下标+1). 这道题要类比search 2D matrix这个题. 大家会发现特别的相似. 2Dmatrix这个题我们找的点就是行最大点列最小点，这样我们通过移动遍历m+n就可以达到目的.所以向这类型排序数组中找值的题目，都按照这种思路. 回到这个题目, 我们不妨采用两点的形式，left在最左面，right在最右面.这样left只能右走，right只能左走. 也就是说当sum>target的时候，说明值大了，这样不能让left右移动吧，因为left右移动只会将数组变得更大, 所以只能right左移.
直接上代码:
class Solution {
public int[] twoSum(int[] numbers, int target) {
int[] res = new int[2];//结果集
if(numbers.length < 2 || numbers == null){
return res;
}
int left = 0;
int right = numbers.length - 1;
while(left <= right){
int sum = numbers[left] + numbers[right];
if(sum == target){
res[0] = left + 1;//下标+1
res[1] = right + 1;
break;
}
else if(sum > target){
right--;
}else{
left++;
}
}
return res;
}
}2. LC53. Maximum Subarray
题目：
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
使用公司:
Microsoft, Bloomberg, Linkedln
难度:
容易
题目与思路分析:
这道题加上附加的问题的话，应该可以达到中等难度. 首先分析题意, 在一个数组中找到连续的子数组和最大. 这个题目应该是很简单的，维护两个变量，一个不断地往前面加，然后每次和当前数组值进行比较，如果等于或者是小于的话，立马换成当前的值，因为你前面加了那么多都没我现在的多，说明前面的对我当前的值来说就是拉后腿的，所以干掉.循环走完就可以.这样的时间复杂度是O(n). 附加题说要分治法处理一下.这样的话就得知道个思路,怎么分？我们要将这个数组分成三部分去分别chuli : left, mid, right. 左右知道，中间是什么鬼？中间就是要向两边扩散的形式找到包括中间值在内的最大sum. 最后再进行left, right, mid取最大就行了.从代码上进行解析吧.
直接上代码非分治:
class Solution {
public int maxSubArray(int[] nums) {
if(nums.length == 0 || nums == null){
return -1;
}
int res = nums[0];
int sum = nums[0];
for(int i = 1; i < nums.length; i++){
sum = Math.max(sum + nums[i], nums[i]);
res = Math.max(sum, res);
}
return res;
}
}直接上代码分治:
class Solution {
public int maxSubArray(int[] nums) {
if(nums.length == 0 || nums == null){
return -1;
}
return helper(nums, 0, nums.length - 1);
}
private int helper(int[] nums, int left, int right){
if(left >= right){
return nums[left];
//当分到很小的时候就重了，取左右都行
}
int mid = left + (right - left) / 2;
//分
int lmax = helper(nums, left, mid - 1);//左最大
int rmax = helper(nums, mid + 1, right);//右最大
int mmax = nums[mid];//中间最大
int tmp = mmax;
//中间向左右两边靠取包括中间值在内的最大sum
for(int i = mid - 1; i >= left; i--){
tmp += nums[i];
mmax = Math.max(mmax, tmp);
}
tmp = mmax;
for(int i = mid + 1; i <= right; i++){
tmp += nums[i];
mmax = Math.max(mmax, tmp);
}
//三者最后进行比较
return Math.max(mmax, Math.max(lmax, rmax));
}
}3. LC209. Minimum Size Subarray Sum
题目：
Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.
For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.
使用公司:
Facebook
难度:
中等
题目与思路分析:
这道题还是挺有意思的, 和上题稍有类似, 这道题是说让你找出这个数组中最小个数的连续子序列和>=target的subArray长度. 这里有个很巧妙的思路: 首先题目说是要求连续子序列, 那么就是整块迁移，所以right最小下标也是从0开始不断加起来的位置, 如图:
在上面这里发现大于等于了，但是不一定是最短的，所以猜测很有可能远大于7以至于能去除一些元素, left就派上用场了. 首先记录下长度，然后能移动的话一直右移动到sum < target. 这时候记录下的就是right从开始移动最短的长度>= target, 然后循环.
最后注意一下边角问题.
直接上代码:
class Solution {
public int minSubArrayLen(int s, int[] nums) {
if(nums.length == 0 || nums == null){
return 0;
}
int left = 0;
int right = 0;
int len = nums.length;
int subLen = Integer.MAX_VALUE;
//只要right没有到边界就能每轮靠left右移找到最小长度
int sum = 0;
while(right < len){
//只有<s的时候才能继续让right移动
while(right < len && sum < s){
sum += nums[right];
right++;
}
while(sum >= s){
subLen = Math.min(subLen, right - left);
//这里不减1是因为上面r++了
sum -= nums[left];
left++;
}
}
return subLen == Integer.MAX_VALUE ? 0 : subLen;
}
}4. LC222. Count Complete Tree Nodes
题目：
Given a complete binary tree, count the number of nodes.
使用公司:
无
难度:
中等
题目与思路分析:
题目就是让求一个平衡二叉树上的节点个数. 首先，什么是完全二叉树? 简单点就是每个节点的左右节点都是有的(这里不包括叶子节点),并且叶子节点部分，尽量是左靠的. 这样很自然想到一个问题就是一直遍历左节点就能知道整个树的高度. 但是我们不用这个思路,我们的思路是: 以某个结点为root节点的一直左的高度等于一直又的高度，说明这个树肯定是完全bt, 并且是一种满bt. 这种情况下有一个公式2^h - 1就是整个树的高度. 如果不是这样的话，那么我们就分而治之，分到满足这个条件的地方.敢这样分就是因为肯定有左右孩子.我们比较容易的找到h,但是2^h怎么搞，这里就要用到移位运算了：
<<运算规则：按二进制形式把所有的数字向左移动对应的位数，高位移出（舍弃），低位的空位补零。
语法格式：
需要移位的数字 << 移位的次数
例如： 3 << 2，则是将数字3左移2位
计算过程：
3 << 2
首先把3转换为二进制数字0000 0000 0000 0000 0000 0000 0000 0011，然后把该数字高位（左侧）的两个零移出，其他的数字都朝左平移2位，最后在低位（右侧）的两个空位补零。则得到的最终结果是0000 0000 0000 0000 0000 0000 0000 1100，则转换为十进制是12.数学意义：
在数字没有溢出的前提下，对于正数和负数，左移一位都相当于乘以2的1次方，左移n位就相当于乘以2的n次方。
>>运算规则：按二进制形式把所有的数字向右移动对应巍峨位数，低位移出（舍弃），高位的空位补符号位，即正数补零，负数补1.
语法格式：
需要移位的数字 >> 移位的次数
例如11 >> 2，则是将数字11右移2位
计算过程：11的二进制形式为：0000 0000 0000 0000 0000 0000 0000 1011，然后把低位的最后两个数字移出，因为该数字是正数，所以在高位补零。则得到的最终结果是0000 0000 0000 0000 0000 0000 0000 0010.转换为十进制是3.数学意义：右移一位相当于除2，右移n位相当于除以2的n次方。
直接上代码:
class Solution {
public int countNodes(TreeNode root) {
if(root == null){
return 0;
}
//如果以某个结点为root的最左和最右子树的高度一样，节点数2^h - 1
//这个公式只是针对完全二叉树
int leftH = getLeftHight(root);
//这里不能直接传root.left因为如果Left为空呢
int rightH = getRightHight(root);
if(leftH == rightH){
return (2<<(leftH - 1)) - 1;
//这里注意leftH + 1表示前面的数要乘以2的多少次方
}else{
//如果不是那就迭代分别计算左右子树
return countNodes(root.left) +
countNodes(root.right) + 1;
}
}
private int getLeftHight(TreeNode root){
int count = 1;
while(root.left != null){
count++;
root = root.left;
}
return count;
}
private int getRightHight(TreeNode root){
int count = 1;
while(root.right != null){
count++;
root = root.right;
}
return count;
}
}5. LC270. Closest Binary Search Tree Value
题目：
Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.
Note:
Given target value is a floating point.
You are guaranteed to have only one unique value in the BST that is closest to the target.
使用公司:
Google, Microsoft, Snapchat
难度:
容易
题目与思路分析:
题中说给定一个二分查找树，即BST， 找到最接近target的节点，这个taget是个float类型. 这道题就比较简单了,首先要知道什么是二分查找树,就是在二叉树中，如果左子树存在，则一定小于root， 如果右子树存在，则一定大于root.并且不存在重复值，其实就是中序遍历的数组. 这里我们的思路是: 将每个节点都看作是root然后进行比较, 但是为了节省时间复杂度，利用到二分查找，所有每次都判断root和target的值, 小于就把root给了left，然后记录下差的绝对值, 不然就给了right.
直接上代码:
class Solution {
public int closestValue(TreeNode root, double target) {
if(root == null){
return -1;
}
//就判断root就行，把每个点都当做是root
int res = root.val;
double minValue = Double.MAX_VALUE;
while(root != null){
if(Math.abs(root.val - target) < minValue){
minValue = Math.abs(root.val - target);
res = root.val;
}
if(target > root.val){
root = root.right;
}
else if(target < root.val){
root = root.left;
}else{
return root.val;
}
}
return res;
}
}总结
今天的题目有得很有趣，有一些小的技巧在里面，一次不会没事，多去回过头来看看怎么操作这些数组或树. BinarySearch的这类型题目也是很容易出现在公司的面试中.
联系方式: [email protected]