每日5题Day24 - LeetCode 116 - 120

每一步向前都是向自己的梦想更近一步，坚持不懈，勇往直前！

第一题：116. 填充每个节点的下一个右侧节点指针 - 力扣（LeetCode）

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;
    public Node() {}
    public Node(int _val) {
        val = _val;
    }
    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        //题目已经说了是完美的二叉树，所以每一层都是满的
        //我们使用栈来实现
        if(root == null){
            return root;
        }
        Deque<Node> deque = new LinkedList<>();
        //先把第一个放进来
        deque.offerLast(root);
        while(!deque.isEmpty()){
            Node prev = new Node();
            int size = deque.size();
            //对于同一层，不断指向下一个
            for(int i = 0; i < size; i++){
                Node node = deque.pollFirst();
                if(node != null){
                    prev.next = node;
                }
                prev = node;
                if(node.left != null){
                    deque.offerLast(node.left);
                }
                if(node.right != null){
                    deque.offerLast(node.right);
                }
            }
        }
        return root;
    }
}

第二题：117. 填充每个节点的下一个右侧节点指针 II - 力扣（LeetCode）

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        //这不是和上一题是一样的吗？
        if(root == null){
            return root;
        }
        Deque<Node> deque = new LinkedList<>();
        deque.offerLast(root);
        while(!deque.isEmpty()){
            Node prev = new Node();
            int size = deque.size();
            for(int i = 0; i < size; i++){
                Node node = deque.pollFirst();
                if(node != null){
                    prev.next = node;
                }
                prev = node;
                if(node.left != null){
                    deque.offerLast(node.left);
                }
                if(node.right != null){
                    deque.offerLast(node.right);
                }
            }
        }
        return root;
    }
}

第三题：118. 杨辉三角 - 力扣（LeetCode）

class Solution {
    public List<List<Integer>> generate(int numRows) {
        //因为每一行的的长度都不同，所以要使用ArrayList
        List<List<Integer>> dp = new ArrayList<>();
        if(numRows == 0){
            return dp;
        }
        dp.add(new ArrayList<>());
        dp.get(0).add(1);
        //注意这里的 i 是指行数，但是dp是从0开始的
        //所以preRow是i-2
        for(int i = 2; i <= numRows; i++){
            List<Integer> row = new ArrayList<>();
            List<Integer> preRow = dp.get(i-2);
            row.add(1);
            for(int j = 1; j < i-1; j++){
                row.add(preRow.get(j) + preRow.get(j-1));
            }
            row.add(1);
            dp.add(row);
        }
        return dp;
    }
}

第四题：119. 杨辉三角 II - 力扣（LeetCode）

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<List<Integer>> res = new ArrayList<>();
        if (rowIndex == 0) {
            return Arrays.asList(1);
        }
        res.add(new ArrayList<>());
        res.get(0).add(1);
        for (int i = 2; i <= rowIndex + 1; i++) {
            List<Integer> row = new ArrayList<>();
            List<Integer> preRow = res.get(i - 2);
            row.add(1);
            for (int j = 1; j < i - 1; j++) {
                row.add(preRow.get(j) + preRow.get(j - 1));
            }
            row.add(1);
            res.add(row);
        }
        return res.get(res.size() - 1);
    }
}

 第五题：120. 三角形最小路径和 - 力扣（LeetCode）

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        // 如果三角形为空，返回0
        if (triangle.size() == 0) {
            return 0;
        }
        // 如果三角形只有一行，直接返回该行的元素值
        if (triangle.size() == 1) {
            return triangle.get(0).get(0);
        }
        
        // 创建一个数组来存储当前层到达每个位置的最小路径和
        int[] dp = new int[triangle.size() + 1];
        
        // 从倒数第二层开始向上遍历
        for (int i = triangle.size() - 1; i >= 0; i--) {
            // 遍历当前层的每个元素
            for (int j = 0; j < triangle.get(i).size(); j++) {
                // 更新当前位置的最小路径和，当前位置的最小路径和等于下一层相邻两个位置的最小值加上当前位置的值
                dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
            }
        }
        
        // 返回顶部元素的最小路径和，即为最终结果
        return dp[0];
    }
}