月度归档： 2021年9月

给你二叉搜索树的根节点 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;
    }

}

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