标签： 二分法

今天每日一题，简单，最近几天每日一题题目好像都挺水的…….

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

 

提示：

1. 你可以假设 nums 中的所有元素是不重复的。
2. n 将在 [1, 10000]之间。
3. nums 的每个元素都将在 [-9999, 9999]之间。

没啥太多解释的，就：二分

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        while (left <= right){
            int mid = left + ((right-left) >> 1);
            if (nums[mid] == target){
                return mid;
            }
            if (nums[mid] < target){
                left = mid+1;
            }else{
                right = mid-1;
            }
        }
        return -1;
    }
}

二分的时候取中间值有个小技巧

int mid = left + ((right-left) >> 1);

这个应该成为所有类型解题过程中常规需要考虑到的问题，而不是直接的加起来除以2。

给定一个二叉搜索树 root 和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

 

示例 1：

输入: root = [5,3,6,2,4,null,7], k = 9
输出: true

示例 2：

输入: root = [5,3,6,2,4,null,7], k = 28
输出: false

示例 3：

输入: root = [2,1,3], k = 4
输出: true

示例 4：

输入: root = [2,1,3], k = 1
输出: false

示例 5：

输入: root = [2,1,3], k = 3
输出: true

 

提示:

• 二叉树的节点个数的范围是  [1, 104].
• -104 <= Node.val <= 104
• root 为二叉搜索树
• -105 <= k <= 105

题解

继续还是二叉搜索树，牢记特性，左小右大，中序遍历后是一个有序递增数组。

那么直接一个中序遍历出来，这样题目就转换成在有个有序递增数组中寻找两个数的和能凑成k，是不是有点眼熟，对的，就是LeetCode刷题 【1】两数之和，先不管之前我们是怎么做的。

那么，按照目前最直观的思路，从数组结尾开始的两个数字尝试相加，假设对应索引为index1,index2，如果这两个位置的值相加比目标值k，大，则尝试将前面一个索引往前移动一位，找一个更小的值相加看是否等于k，一直找到索引为0的位置。如果这两个最大的值相加的合比k小，说明不存在相加了能满足k的情况了。尝试过一轮之后，如果找不到合适的值，则将后一位的索引往前移动一位，继续这个过程。

举例:【1,2,3,4,5,6,7,8】数组

先用7+8尝试，如果大于则用6+8、5+8、4+8尝试，直到1+7尝试，如果没有合适的，则进行下一轮用6+7尝试,5+7、4+7依次尝试。

好了，下面是代码：

class Solution1 {
    List<Integer> list = new ArrayList<>();
    public boolean findTarget(TreeNode root, int k) {
        dfs(root);
        int index1 = list.size()-1;
        int index2 = index1-1;

        while (index2>=0){
            if (list.get(index1)+list.get(index2) < k){
                return false;
            }
            while (index2 >= 0 && list.get(index1)+list.get(index2) >= k ){
                if (list.get(index1)+list.get(index2) == k){
                    return true;
                }
                index2--;
            }
            index1--;
            index2=index1-1;
        }
        return false;
    }

    private void dfs(TreeNode node){
        if (null==node)return;
        dfs(node.left);
        list.add(node.val);
        dfs(node.right);
    }

}

而执行的结果告诉了我，问题应该不至于这样

解答成功:
执行耗时:1138 ms,击败了5.24% 的Java用户
内存消耗:39.9 MB,击败了20.04% 的Java用户

所以，回到上面的思路中间的过程看下，两个关键点“有序递增数组”，“在这个有序递增数组中寻找一个特定的值”，是不是很自然的就想到了此处应该可以用二分法来处理，此处后续省略。

重新再看下整个思考的过程，就是一个求解a+b=k的过程，其中k预先已给出，a、b值在对二叉树遍历的时候能知道一个，就是当前节点的值。此时问题就变成了再二叉树的所有节点中找另一个值是否存在。此时问题就转换成了，在二叉树遍历过程中，已知了a,已知了k，再在二叉搜索树中搜索(k-a)这个值是否存在，可利用二叉树的左小右大的特性查找。

代码：省略

接下来再进一步，在a+b=k的求解过程中，查找b能否进一步优化呢？答案是可以的，遍历每个节点的时候把值存储到一个hash表中，这样查找b是否存在就可以从原来的搜索二叉树查找转换成hash查找，时间复杂度直接降为O(1)。

class Solution {
    HashSet<Integer> hashSet = new HashSet<>();
    boolean result = false;
    public boolean findTarget(TreeNode root, int k) {
        dfs(root,k);
        return result;
    }

    private void dfs(TreeNode node, int k){
        if (null==node || result)return;
        dfs(node.left,k);
        if (!result){
            if (hashSet.contains(k-node.val)){
                result = true;
            }
        }
        hashSet.add(node.val);
        dfs(node.right,k);
    }

}

结果

执行耗时:3 ms,击败了83.09% 的Java用户
内存消耗:39.2 MB,击败了79.23% 的Java用户

再看看我们之前第一题是怎么做的，LeetCode刷题 【1】两数之和，是不是回到了一样的解法上了。

本题难度设定的是简单题，嗯，本质上就是在原来第一题两数之和的基础上嵌套了一个二叉树遍历。

另外做这题的时候想到的一个点，二叉平衡搜索树的查找搜索过程，和二分法数组查找搜索，这两个算法，本质上是一样的。

给定一个正整数数组 w ，其中 w[i] 代表下标 i 的权重（下标从 0 开始），请写一个函数 pickIndex ，它可以随机地获取下标 i，选取下标 i 的概率与 w[i] 成正比。

例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。

也就是说，选取下标 i 的概率为 w[i] / sum(w) 。

 

示例 1：

输入：
["Solution","pickIndex"]
[[[1]],[]]
输出：
[null,0]
解释：
Solution solution = new Solution([1]);
solution.pickIndex(); // 返回 0，因为数组中只有一个元素，所以唯一的选择是返回下标 0。

示例 2：

输入：
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
输出：
[null,1,1,1,1,0]
解释：
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // 返回 1，返回下标 1，返回该下标概率为 3/4 。
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 0，返回下标 0，返回该下标概率为 1/4 。

由于这是一个随机问题，允许多个答案，因此下列输出都可以被认为是正确的:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
诸若此类。

 

提示：

• 1 <= w.length <= 10000
• 1 <= w[i] <= 10^5
• pickIndex 将被调用不超过 10000 次

题解

8月30日 每日一题

class Solution {

    int[] preSum;
    public Solution(int[] w) {
        for (int i = 1; i < w.length; i++) {
            w[i] = w[i]+w[i-1];
        }
        preSum = w;
    }
    
    public int pickIndex() {
        int randNum = (int)(Math.random() * preSum[preSum.length-1])+1;
        int left = 0;
        int right = preSum.length-1;
        while (left < right){
            int mid = (left + right) >> 1;
            if (preSum[mid] < randNum){
                left = mid+1;
            }else{
                right = mid;
            }
        }
        System.out.println(left);
        return left;
    }
}

大致思路，比如数组[1,2,3]，要求值对应概率的话，最直观的就会想到创建一个集合，里面放入1个“1”，放入两个“2”，方式3个“3”，然后随机取一个值，这个取到的概率满足1的几率是1/6，2的几率是2/6，3的几率是3/6，找到这个值在原数组中的下标即可。

有了这样一个思路之后，我们看下生成后的数组[1,2,2,3,3,3]，每一位上的概率相等，所以应当是生成一个1<=x<=6的随机整数，而这个6对应的也是原数组[1,2,3]所有值之合，所以就变成了新的关系

【1】=》1，【2,3】=》2，【4,5,6】=》3

这样是不是大概就可以看出来了，此处前缀和的方式比较合适，把原来的[1,2,2,3,3,3]的数组，压缩成为[1,3,6]的数组，随机了一个1到6之间的值之后，在这个数组中找到对应的索引，就是原来数组[1,2,3]对应的索引值，返回即可。查找的这个过程一般来说用二分查找，不过看数据量，直接遍历查找也可以。