算法和数据结构相关

在刷题之中遇到的好问题与心得

Posted by Haiming on April 2, 2020

此处主要是记录一些自己觉得精彩的LeetCode题解和心得。

1. Tree

预备. AVL 树

AVL树是一种平衡二叉树,其平衡因子(某个节点的左子树的高度减去右子树的高度得到的差值)的绝对值都不超过1。在每次添加或者删除的情况下,其都会进行检验,如果不满足这个条件,就进行相应的左旋和右旋,从而使其满足平衡因子的差值的绝对值不超过1的要求。

那么为什么在许多数据结构之中使用红黑树而不是AVL树呢?

红黑树相比AVL树而言,其更不平衡,这也就意味着其查找时候所需要的时间更多,但是其插入,删除等的所需的再平衡时间更短。我们使用数据结构,大部分情况是要对数据进行改动的,那么这种情况下不使用AVL树而使用红黑树就很显而易见了。

一些解题心得:

  1. 对于树而言,其递归式的解法必定是从上向下的,而且可以操作的也无非就是TreeNode本身, TreeNode.left, TreeNode.right这三个。那么对于一些”从根节点到叶子节点“是否满足某种条件的问题(https://leetcode.com/problems/path-sum/description/),就要拆分成”每一层除了根节点之外是否满足剩下的条件“。
  2. 如果有对于两棵树的检查(https://leetcode.com/problems/merge-two-binary-trees/description/),那么其结束条件要将两棵树都是null,某一棵为null的一共三种条件都作为结束条件才行。
  3. 一开始几乎都是判断null的操作,原因不仅是第一次循环之中如果为null那么直接返回,更重要的是null意味着判断到了最下层的节点,如果判断到了最下层的节点依旧找不到值,那么通常是返回失败。

136.Single Number

https://leetcode.com/problems/single-number/

本题精彩之处在于要求时间复杂度O(n),而且要求不可以使用额外空间,空间复杂度为O(1)。这就断了我们使用排序或者是hashMap来解决的路。本题之中使用二进制异或的性质来完成,所有数字异或之后就是结果。

为什么可以用异或来完成数字之间的比较?

  1. 0和任何数异或都是其本身,那么我们就可以使用0作为函数的初始条件。
  2. 任何数和本身异或都是0, 那么两个相同的数异或之后可以抵消。

先说下这个抵消的问题:

计算机之中都是使用二进制的,我们来做个示例就知道这种抵消效应了:

假设为[6,2,6],那么

6=0110

2=0010

6 ^ 2 = 0100 = 4

0100 ^ 6 = 0100 ^ 0110 = 0010 = 2

你看,回来了不是。

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for(int i :nums){
            result = result ^ i;
        }
        return result;
    }
}

513. Find Bottom Left Tree Value

本题之中我认为最有趣的是其活用了Queue的先入先出后入后出的性质。通过每次入队时候先入右边节点再入左边节点,那么最后剩下的一定是“最底层的最左边的节点”。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        TreeNode node = new TreeNode(root.val);
        while(!queue.isEmpty()){
            node = queue.poll();
            if(node.right!=null) queue.add(node.right);
            if(node.left!=null) queue.add(node.left);
        }
        return node.val;
    }
}

637. Average of Levels in Binary Tree

https://leetcode.com/problems/average-of-levels-in-binary-tree/

本题的亮点在于其不需要另外一个ArrayList来存储每一层之中的节点,而是可以通过控制遍历时候的长度来实现分层的作用。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        ArrayList<Double> list = new ArrayList<>();
        if(root == null) return list;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            double num = 0;
            int length = queue.size();
            for(int i=0;i<length;i++){
                TreeNode item = queue.poll();
                num+=item.val;
                if(item.left!=null) queue.add(item.left);
                if(item.right!=null) queue.add(item.right);
            }
            num = num/length;
            list.add(num);
        }
        
        return list;
    }
}