力扣小记 1710、129、515

1710.卡车上的最大单元数

https://leetcode.cn/problems/maximum-units-on-a-truck

思路:
先对numberOfUnitsPerBoxi从大到小排序, 每次取最大的数量, 然后truckSize减去numberOfBoxesi，尽可能的装多, 当truckSize为0得出答案, 这道题贪心算法直接可以过

func maximumUnits(boxTypes [][]int, truckSize int) (result int) {
    sort.Slice(boxTypes, func(i, j int) bool {
        return boxTypes[i][1] > boxTypes[j][1]
    })
    for _, box := range boxTypes {
        result += box[1] * min(truckSize, box[0])
        truckSize -= box[0]
        if truckSize <= 0 {
            break
        }
    }
    return
}

func min(i, j int) int {
    if i > j {
        return j
    }
    return i
}

129.求根节点到叶子节点数字之和

https://leetcode.cn/problems/sum-root-to-leaf-numbers

思路:
记录每一个节点的值, 当遍历到叶子节点便往res添加值

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumNumbers(root *TreeNode) int {
    return traverse(root, 0)
}

func traverse(root *TreeNode, cur int) int {
    if root == nil {
        return 0
    }
    cur = cur*10 + root.Val
    if root.Left == nil && root.Right == nil {
        return cur
    }
    return traverse(root.Left, cur) + traverse(root.Right, cur)
}

515.在每个数行中找最大值

https://leetcode.cn/problems/find-largest-value-in-each-tree-row

思路:
对二叉树做层序遍历, 将最大值记录起来

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < size; i++) {
                TreeNode cur = q.poll();
                max = Math.max(max, cur.val);
                if (cur.left != null) {
                    q.offer(cur.left);
                }
                if (cur.right != null) {
                    q.offer(cur.right);
                }
            }
            res.add(max);
        }
        return res;
    }
}