给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。

进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？

示例 1：

输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

示例 2：

输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

提示：

• 树上节点的数目在范围 [2, 1000] 内
• -231 <= Node.val <= 231 - 1

题解

关键信息“二叉搜索树”，重点在于二叉搜索树的一个特殊的特性，他的中序遍历的结果是递增的。那么本题就是应该利用这个特性来解决，在中序遍历的时候，对比当前节点和前驱节点的值，如果不是前驱节点小，当前节点大，那么说明这边是顺序有问题的。

注意，这里只能说明是有问题，拿具体的中序遍历结果来示意【1,2,6,4,5,3,7】,这里的6比后面的4大，并不能说明是6和4调换位置了，而是应当继续往后寻找，找到最后一个比当前6小的节点，才是和6调换了位置的节点。此处应当是3节点。

所以，代码：

class Solution {

    TreeNode preNode;
    TreeNode errorNode1;
    TreeNode errorNode2;
    public void recoverTree(TreeNode root) {
        dfs(root);
        int tmp = errorNode2.val;
        errorNode2.val = errorNode1.val;
        errorNode1.val = tmp;
    }
    
    
    private void dfs(TreeNode node){
        if (null == node){
            return;
        }
        dfs(node.left);
        //mid
        if (preNode!=null){
            if (preNode.val > node.val){
                if (errorNode2==null)errorNode2 = preNode;
                errorNode1 = node;
            }
        }

        //更新前序节点
        preNode = node;
        dfs(node.right);
    }
}

当然，最直接的就是像上面分析的那样，把中序遍历结果存下来，然后对这个结果遍历查找到调换了顺序的。也可以就像代码中这样的在中序遍历的时候根据前驱节点的值的情况来记录比较。

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

题解

9月2日每日一题，最常规的解法应该声明一个数组，然后就是遍历链表，记录下每个节点，最后得到总长之后，到数组中找到总长减去k位置的并返回

我这边的第一反应是递归，探底后返回依次加1，加到k的时候记录下这倒数第k个结点。原理类似DFS的后序遍历。

class Solution {
    int k = 0;
    int count = 0;
    ListNode node;
    public ListNode getKthFromEnd(ListNode head, int k) {
        this.k = k;
        func(head);
        return node;
    }


    public void func(ListNode head){
        if (head == null){
            return;
        }
        func(head.next);
        count++;
        if (count == k){
            node = head;
        }
    }
}

另外的一种，双指针，如下，具体思路逻辑详见注释

class Solution {
    ListNode node1;
    ListNode node2;
    public ListNode getKthFromEnd(ListNode head, int k) {
        node1 = head;
        node2 = head;
        //这里初始为1，举例说明 链表【1,2,3】，倒是第一个应当是3，不存在倒数第0个的这种说法
        int count = 1;
        //让node2先跑k步
        while (node2.next != null && count<k){
            node2 = node2.next;
            count++;
        }
        if (count < k){
            //假如链表总长度小于k
            return null;
        }
        //此时node2在node1后面距离k,接下来，node1和node2一起往后跑
        //当node2跑到结尾的时候，node1即为倒数第k个了
        while (node2.next != null){
            node1 = node1.next;
            node2 = node2.next;
        }

        return node1;
    }
}

当然这边也可以再优化下，写到一个while循环里，通过条件判断让node2先跑k个，双指针的思路和上次LeetCode刷题【876】链表的中间结点有点类似，都是通过控制两个指针之间的相对距离，找出链表中间的某个节点。

给你两个版本号 version1 和 version2 ，请你比较它们。

版本号由一个或多个修订号组成，各修订号由一个 '.' 连接。每个修订号由 多位数字 组成，可能包含 前导零 。每个版本号至少包含一个字符。修订号从左到右编号，下标从 0 开始，最左边的修订号下标为 0 ，下一个修订号下标为 1 ，以此类推。例如，2.5.33 和 0.1 都是有效的版本号。

比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较 忽略任何前导零后的整数值 。也就是说，修订号 1 和修订号 001 相等 。如果版本号没有指定某个下标处的修订号，则该修订号视为 0 。例如，版本 1.0 小于版本 1.1 ，因为它们下标为 0 的修订号相同，而下标为 1 的修订号分别为 0 和 1 ，0 < 1 。

返回规则如下：

• 如果 version1 > version2 返回 1，
• 如果 version1 < version2 返回 -1，
• 除此之外返回 0。

示例 1：

输入：version1 = "1.01", version2 = "1.001"
输出：0
解释：忽略前导零，"01" 和 "001" 都表示相同的整数 "1"

示例 2：

输入：version1 = "1.0", version2 = "1.0.0"
输出：0
解释：version1 没有指定下标为 2 的修订号，即视为 "0"

示例 3：

输入：version1 = "0.1", version2 = "1.1"
输出：-1
解释：version1 中下标为 0 的修订号是 "0"，version2 中下标为 0 的修订号是 "1" 。0 < 1，所以 version1 < version2

示例 4：

输入：version1 = "1.0.1", version2 = "1"
输出：1

示例 5：

输入：version1 = "7.5.2.4", version2 = "7.5.3"
输出：-1

提示：

• 1 <= version1.length, version2.length <= 500
• version1 和 version2 仅包含数字和 '.'
• version1 和 version2 都是 有效版本号
• version1 和 version2 的所有修订号都可以存储在 32 位整数 中

题解

9月1日的每日一题。好像没啥复杂的。工作中也会有机会用到的一个案例，比如app更新版本号判断，不过一般而言，工作中的版本号格式应该都是固定的，不会出现两个要比较的版本号的分隔符个数不一样的情况。

class Solution {
    public int compareVersion(String version1, String version2) {
        List<Integer> arr1 = versionToArr(version1);
        List<Integer> arr2 = versionToArr(version2);

        int res = 0;
        int i;
        for (i = 0; i < arr1.size() & i < arr2.size(); i++) {
            if (arr1.get(i) < arr2.get(i)){
                return -1;
            }
            if (arr1.get(i) > arr2.get(i)){
                return 1;
            }
        }
        if (arr1.size() < arr2.size()){
            int i1 = i;
            while (i1<arr2.size()){
                if (arr2.get(i1)>0){
                    return -1;
                }
                i1++;
            }
        }
        if (arr1.size() > arr2.size()){
            int i2 = i;
            while (i2<arr1.size()){
                if (arr1.get(i2)>0){
                    return 1;
                }
                i2++;
            }
        }
        return res;
    }

    private List<Integer> versionToArr(String version){
        List<Integer> arr = new ArrayList<>();
        String[] arrStr = version.split("\\.");
        for (String s : arrStr) {
            arr.add(Integer.parseInt(s));
        }
        return arr;
    }

}

有一点小问题就是，下面的while判断一开始没有写，导致提交后

测试用例:"1.0"，"1.0.0"

这个用例过不去，所以这边其实应该有另一个思路：较短版本号的后面不存在的分隔符的部分可以假设为也存在，但是值为零，这样两个版本号的长度（指分隔符的个数）就可以对齐。

好了，有了上面的解法的思路（即，实际是按照分隔符对应比较每段实际数值的大小），和这里不存在的分割断当做0来处理的认知之后，我们可以试试更加简洁的解法。

这里需要结合另一个知识点，字符串转换为数字的方法，从字符串的高位开始遍历相加，每次相加对之前的结果乘以10，这样可以得到实际的数值。即字符串“123”可以按照

((((0+1)*10)+2)*10)+3

这样的方式求和得到

class Solution {
    public int compareVersion(String version1, String version2){
        int index1 = 0,index2 = 0,num1,num2;
        while (index1< version1.length() || index2 < version2.length()){
            num1=0;
            num2=0;
            //一直往后取，取到分隔符的点。注意越界
            while (index1< version1.length() && version1.charAt(index1)!='.'){
                num1 += num1*10 + (version1.charAt(index1)-'0');
                index1++;
            }
            //同num1的
            while (index2 < version2.length() && version2.charAt(index2)!='.'){
                num2 += num2*10 + (version2.charAt(index2)-'0');
                index2++;
            }
            if (num1<num2){
                return -1;
            }
            if (num2< num1){
                return 1;
            }

            //往后进一位，当前位置为分隔符，假如没有越界的话，越界也没关系，上面的求和之前有判断了越界
            index2++;
            index1++;
        }
        return 0;
    }

}

这样是不是一下子就出来了

这里有 n 个航班，它们分别从 1 到 n 进行编号。

有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。

请你返回一个长度为 n 的数组 answer，其中 answer[i] 是航班 i 上预订的座位总数。

示例 1：

输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]
解释：
航班编号        1   2   3   4   5
预订记录 1 ：   10  10
预订记录 2 ：       20  20
预订记录 3 ：       25  25  25  25
总座位数：      10  55  45  25  25
因此，answer = [10,55,45,25,25]

示例 2：

输入：bookings = [[1,2,10],[2,2,15]], n = 2
输出：[10,25]
解释：
航班编号        1   2
预订记录 1 ：   10  10
预订记录 2 ：       15
总座位数：      10  25
因此，answer = [10,25]

提示：

• 1 <= n <= 2 * 104
• 1 <= bookings.length <= 2 * 104
• bookings[i].length == 3
• 1 <= firsti <= lasti <= n
• 1 <= seatsi <= 104

题解

一看题目啊，emmm，这不简单嘛，直接遍历循环套循环，好处理的嘛

public int[] corpFlightBookings(int[][] bookings, int n) {
    int [] res = new int[n];
    for (int[] booking : bookings) {
        plus(res, booking[0]-1,booking[1]-1,booking[2]);
    }

    return res;
}


public void plus(int[] arr, int start, int end, int count){
    while (start <= end){
        arr[start] += count;
        start++;
    }
}

你看这不还过了

解答成功:
执行耗时:879 ms,击败了29.46% 的Java用户
内存消耗:53.5 MB,击败了44.81% 的Java用户	

但是想一下这中间的过程，应该没那么简单。以官方给出的示例来分析

输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
解释：
航班编号        1   2   3   4   5
预订记录 1 ：   10  10
预订记录 2 ：       20  20
预订记录 3 ：       25  25  25  25
总座位数：      10  55  45  25  25

通过分析这份数据我们可以知道，在1航站新增了10名旅客，直到2航站才下机，所以到3航站的时候这10名旅客就不在了。

2航站有两批数据，一匹是20 一匹是25，一共新增了45名乘客，加上之前1航站的10名乘客一共是有55名。那么在4航站的时候就有20名下机了，而另外25名可以认为直到一个不存在的6才下机或者不处理也可以。

那么实际的逻辑就应该是在1的位置新增了10，这个10需要再3的位置减去，在2的位置新增了20、25，分别在4位置和不存在6位置减去。

所以用一个新的数组保存每个的变更情况，如果为0，则说明没有变更，则需要继承前一个位置的值，如果为正则说有净增加，需要由前一个位置的值加上这个值，如果为负数，则说明有净减少，需要由前一个位置的值减去对应的值。

思路对应代码

class Solution {

    public int[] corpFlightBookings(int[][] bookings, int n) {
        int [] res = new int[n];
        for (int[] booking : bookings) {
            res[booking[0]-1] += booking[2];
            if (booking[1]<n){
                res[booking[1]] -= booking[2];
            }
        }
        for (int i = 1; i < res.length; i++) {
            res[i] += res[i-1];
        }
        return res;
    }
}

提交下，可以，没毛病

解答成功:         
执行耗时:2 ms,击败了100.00% 的Java用户         
内存消耗:53.3 MB,击败了67.00% 的Java用户

给定一个正整数数组 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]对应的索引值，返回即可。查找的这个过程一般来说用二分查找，不过看数据量，直接遍历查找也可以。

给你一个字符串 s ，逐个翻转字符串中的所有 单词 。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。

说明：

• 输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
• 翻转后单词间应当仅用一个空格分隔。
• 翻转后的字符串中不应包含额外的空格。

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

输入：s = "  hello world  "
输出："world hello"
解释：输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括。

示例 3：

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，将翻转后单词间的空格减少到只含一个。

示例 4：

输入：s = "  Bob    Loves  Alice   "
输出："Alice Loves Bob"

示例 5：

输入：s = "Alice does not even like bob"
输出："bob like even not does Alice"

提示：

• 1 <= s.length <= 104
• s 包含英文大小写字母、数字和空格 ' '
• s 中 至少存在一个 单词

进阶：

• 请尝试使用 O(1) 额外空间复杂度的原地解法。

public String reverseWords2(String s) {
        String[] arr = s.split(" ");
        if (arr.length == 1){
            return arr[0];
        }
        StringBuilder sb = new StringBuilder();
        sb.append(arr[arr.length-1]);
        int i = arr.length-2;
        while (i >= 0) {
            if (arr[i].length()>0){//判空很重要
                sb.append(" ").append(arr[i]);
            }
            i--;
        }
        return sb.toString();
    }

O（1）空间的java里面应该是实现不了，如果哪位大神有啥思路的可以提供下，我就整出来个char[]上原地翻转实现的，而且最后还是的new String ,再trim()实现

思路是这样的，先把String型的字符转成char[]，在这过程中需要把中间重复的空格去掉，或者说是挪到char[]的结尾部分。写了一个moveRedundantSpace方法，把中间多余的空格去除掉，或者说挪到数组结尾。

然后对char[]数组从头到整体翻转，然后再次遍历，根据空格判断单词分割，分别对每个单词重新翻转，这样单个单词的字符顺序就翻转回来了。代码里面这边的单词翻转部分是在写去除重复空格之前写的，所以还保留了之前有重复空格时候的do/while判断。

  class Solution {
    public String reverseWords(String s) {
        char[] arr = s.toCharArray();
        moveRedundantSpace(arr);
        int left = 0;
        int right = arr.length-1;
        reverse(arr,left,right);

        //挨个单词翻转
        int index1;
        int index2;
        int i = 0;
        while (i <= arr.length-1){
            if (arr[i] != ' ') {
                index1 = i;
                do {
                    i++;
                } while (i <= arr.length - 1 && arr[i] != ' ');
                index2 = i-1;
                reverse(arr,index1,index2);
            }
            i++;
        }
        return (new String(arr)).trim();
    }

    public void reverse(char[] arr, int left ,int right){
        while (left < right){
            char tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
            left++;
            right--;
        }
    }

    public void moveRedundantSpace(char[] arr){
        int cur = 1;
        for (int index = 1;index < arr.length; index++){
            while (cur < arr.length && arr[cur] == ' ' && arr[cur-1] == ' '){
                cur++;
            }
            if (cur < arr.length){
                arr[index] = arr[cur];
            }else{
                arr[index] = ' ';
            }
            cur++;
        }
    }
}

给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i]) 。

请返回 nums 的动态和。

示例 1：

输入：nums = [1,2,3,4]
输出：[1,3,6,10]
解释：动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4] 。
示例 2：

输入：nums = [1,1,1,1,1]
输出：[1,2,3,4,5]
解释：动态和计算过程为 [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1] 。
示例 3：

输入：nums = [3,1,2,10,1]
输出：[3,4,6,16,17]
 

提示：

1 <= nums.length <= 1000
-10^6 <= nums[i] <= 10^6

题解

8月28每日一题

class Solution {
    public int[] runningSum(int[] nums) {
        int i = 1;
        while(i <= nums.length-1){
            nums[i] = nums[i] + nums[i-1];
            i++;
        }
        return nums;
    }
}

求前序合基本操作