Day3

1. 爬楼梯问题：

   • 题目：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
   • 题目解析：每次可以爬 1 或 2 个台阶，可以通过动态规划的思想进行解题，具体代码如下：

   class Solution {
       public int climbStairs(int n) {
           int [] climb = new int[n + 1];
   		climb[0] = 1;
   		climb[1] = 1;
           //设定初值，总的方法数即从前 1 阶爬上的方法数和从前 2 阶爬上的方法数
   		for(int i = 2; i <= n; i ++){
   			 climb[i] = climb[i - 1] + climb[i - 2];
   		}
   		return climb[n];
       }
   }
   

2. 二叉树的直径

   题目：给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

   题目解析：较为自然的想到通过递归的方式书写代码（隐含动态规划的思想），但由于递归代码不太习惯书写，最终参考题解。可以通过 力扣递归图解 理解代码。

class Solution {
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        // 空树需要规定返回值为 0
        if(root == null)
            return 0;
        dfs(root);
        return max - 1;
    }
    public int dfs(TreeNode node){
        // max 值和 dfs 深度指明的均是路径上节点的数目
        if(node == null)
            return 0;
        int L = dfs(node.left);
        int R = dfs(node.right);
        // 左右节点数目之和，加 1 表示根节点，注意路径长度最终要等于节点数目减 1
        max = Math.max(L + R + 1, max);
        return Math.max(L,R) + 1;
    }
}

3. 找到所有数组中消失的元素
   • 题目：给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。找到所有在 [1, n] 范围之间没有出现在数组中的数字。不额外使用存储空间同时时间复杂度为 \(O(n)\)
   • 题目解析：由于数组的下标和其中存储的元素是一一对应的关系，减 1 即可，因此，可以遍历完一次数组时给每一个存在下标的元素做一个标记，本代码采用原数的负数作为标记。代码如下：

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < nums.length; i ++)
            //使用负数作为标记，不是负数的下标说明在数组中不存在它的 +1 元素，注意元素都要使用 abs
            nums[Math.abs(nums[i]) - 1] = -Math.abs(nums[Math.abs(nums[i]) - 1]);
        for(int i = 0; i < nums.length; i ++)
            //第二次遍历寻找元素还是整数的下标加 1 即为缺的元素
            if(nums[i] > 0) list.add(i + 1);
        return list;
    }
}