7.4号刷题

第一题 632. Smallest Range

题目描述

给定k组递增排列的整数。求最小范围，使得每组数中至少有一个包含在其中。

算法

利用数据结构Element记录下对应数据的行数和index, 并利用PriorityQueue进行排序。每次循环弹出最小的答案，最后用max - min对答案进行更新

public class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        PriorityQueue<Element> pq = new PriorityQueue<Element>(new Comparator<Element>() {
            @Override
            public int compare(Element o1, Element o2) {
                return o1.val - o2.val;
            }
        });

        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.size(); i++) {
            int num = nums.get(i).get(0);
            Element e = new Element(num, 0, i);
            pq.offer(e);
            max = Math.max(max, num);
        }

        int range = Integer.MAX_VALUE;
        int start = -1, end = -1;
        while (pq.size() == nums.size()) {
            Element e = pq.poll();
            if (max - e.val < range) {
                range = max - e.val;
                start = e.val;
                end = max;
            }

            if (e.index + 1 < nums.get(e.row).size()) {
                e.index += 1;
                int newNum = nums.get(e.row).get(e.index);
                e.val = newNum;
                pq.offer(e);
                max = Math.max(max, newNum);
            }

        }
        return new int[] {start, end};
    }

    class Element {
        int val;
        int index;
        int row;
        public Element (int v, int i, int r) {
            this.val = v;
            this.index = i;
            this.row = r;
        }
    }
}

第二题 635. Design Log Storage System

题目描述

给定以二元组(id, 时间戳)表示的日志，时间戳格式为Year:Month:Day:Hour:Minute:Second

设计系统支持日志存储，并支持在年，月，日，时，分，秒粒度时间范围内查询日志ID列表

算法

public class LogSystem635 {
    List<String[]> timestamps;
    List<String> units;
    int[] indices;

    public LogSystem635() {
        timestamps = new ArrayList<>();
        units = Arrays.asList("Year", "Month", "Day", "Hour", "Minute", "Second");
        indices = new int[]{4, 7, 10, 13, 16, 19};
    }

    public void put(int id, String timestamp) {
        timestamps.add(new String[] {String.valueOf(id), timestamp});
    }

    public List<Integer> retrieve(String s, String e, String gra) {
        List<Integer> res = new ArrayList<>();
        int index = indices[units.indexOf(gra)];

        for (String[] timestamp : timestamps) {
            if (timestamp[1].substring(0, index).compareTo(s.substring(0, index)) >= 0
                    && timestamp[1].substring(0, index).compareTo(e.substring(0, index)) <= 0)
                res.add(Integer.valueOf(timestamp[0]));
        }
        return res;
    }
}

第三题 617. Merge Two Binary Trees

题目描述

合并两棵二叉树。

算法

回溯

public class mergeTrees617 {

    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        TreeNode root;
        if (t1 == null && t2 == null) {
            return null;
        } else if (t1 == null) {
            int val = t2.val;
            root = new TreeNode(val);
            root.left = mergeTrees(t2.left, null);
            root.right = mergeTrees(null, t2.right);
        } else if (t2 == null) {
            int val = t1.val;
            root = new TreeNode(val);
            root.left = mergeTrees(t1.left, null);
            root.right = mergeTrees(null, t1.right);
        } else {
            int val = t1.val + t2.val;
            root = new TreeNode(val);
            root.left = mergeTrees(t1.left, t2.left);
            root.right = mergeTrees(t1.right, t2.right);
        }
        return root;
    }
}

第四题 513. Find Bottom Left Tree Value

题目描述

给定二叉树，返回末尾行的最左元素。

注意：你可以假设树非空。

算法

public class findBottomLeftValue513 {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            root = queue.poll();
            if (root.right != null) {
                queue.add(root.right);
            }
            if (root.left != null) {
                queue.add(root.left);
            }
        }
        return root.val;
    }
}