标签： 数据结构

目标

你有一个只支持单个标签页的 浏览器 ，最开始你浏览的网页是 homepage ，你可以访问其他的网站 url ，也可以在浏览历史中后退 steps 步或前进 steps 步。

请你实现 BrowserHistory 类：

• BrowserHistory(string homepage) ，用 homepage 初始化浏览器类。
• void visit(string url) 从当前页跳转访问 url 对应的页面 。执行此操作会把浏览历史前进的记录全部删除。
• string back(int steps) 在浏览历史中后退 steps 步。如果你只能在浏览历史中后退至多 x 步且 steps > x ，那么你只后退 x 步。请返回后退 至多 steps 步以后的 url 。
• string forward(int steps) 在浏览历史中前进 steps 步。如果你只能在浏览历史中前进至多 x 步且 steps > x ，那么你只前进 x 步。请返回前进 至多 steps步以后的 url 。

示例：

输入：
["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]
输出：
[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]

解释：
BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com");       // 你原本在浏览 "leetcode.com" 。访问 "google.com"
browserHistory.visit("facebook.com");     // 你原本在浏览 "google.com" 。访问 "facebook.com"
browserHistory.visit("youtube.com");      // 你原本在浏览 "facebook.com" 。访问 "youtube.com"
browserHistory.back(1);                   // 你原本在浏览 "youtube.com" ，后退到 "facebook.com" 并返回 "facebook.com"
browserHistory.back(1);                   // 你原本在浏览 "facebook.com" ，后退到 "google.com" 并返回 "google.com"
browserHistory.forward(1);                // 你原本在浏览 "google.com" ，前进到 "facebook.com" 并返回 "facebook.com"
browserHistory.visit("linkedin.com");     // 你原本在浏览 "facebook.com" 。 访问 "linkedin.com"
browserHistory.forward(2);                // 你原本在浏览 "linkedin.com" ，你无法前进任何步数。
browserHistory.back(2);                   // 你原本在浏览 "linkedin.com" ，后退两步依次先到 "facebook.com" ，然后到 "google.com" ，并返回 "google.com"
browserHistory.back(7);                   // 你原本在浏览 "google.com"， 你只能后退一步到 "leetcode.com" ，并返回 "leetcode.com"

说明：

• 1 <= homepage.length <= 20
• 1 <= url.length <= 20
• 1 <= steps <= 100
• homepage 和 url 都只包含 '.' 或者小写英文字母。
• 最多调用 5000 次 visit， back 和 forward 函数。

思路

设计一个浏览器历史记录管理器，记录在同一个标签页的浏览历史，允许前进/后退 steps 步（不能超出浏览记录的范围）。如果打开新页面，当前页面记录会覆盖前进的记录。

使用栈模拟，记录 cur 与 tail 两个指针，前进取 Math.min(tail, cur + steps)，后退取 Math.max(0, cur - steps)，访问新页面 ++cur; tail = cur;。

代码

/**
 * @date 2025-02-26 8:48
 */
class BrowserHistory {

    String[] history = new String[5000];
    int tail = 0;
    int cur = 0;

    public BrowserHistory(String homepage) {
        history[0] = homepage;
    }

    public void visit(String url) {
        history[++cur] = url;
        tail = cur;
    }

    public String back(int steps) {
        cur = Math.max(0, cur - steps);
        return history[cur];
    }

    public String forward(int steps) {
        cur = Math.min(tail, cur + steps);
        return history[cur];
    }
}

性能

目标

一个王国里住着国王、他的孩子们、他的孙子们等等。每一个时间点，这个家庭里有人出生也有人死亡。

这个王国有一个明确规定的王位继承顺序，第一继承人总是国王自己。我们定义递归函数 Successor(x, curOrder) ，给定一个人 x 和当前的继承顺序，该函数返回 x 的下一继承人。

Successor(x, curOrder):
    如果 x 没有孩子或者所有 x 的孩子都在 curOrder 中：
        如果 x 是国王，那么返回 null
        否则，返回 Successor(x 的父亲, curOrder)
    否则，返回 x 不在 curOrder 中最年长的孩子

比方说，假设王国由国王，他的孩子 Alice 和 Bob （Alice 比 Bob 年长）和 Alice 的孩子 Jack 组成。

1. 一开始， curOrder 为 ["king"].
2. 调用 Successor(king, curOrder) ，返回 Alice ，所以我们将 Alice 放入 curOrder 中，得到 ["king", "Alice"] 。
3. 调用 Successor(Alice, curOrder) ，返回 Jack ，所以我们将 Jack 放入 curOrder 中，得到 ["king", "Alice", "Jack"] 。
4. 调用 Successor(Jack, curOrder) ，返回 Bob ，所以我们将 Bob 放入 curOrder 中，得到 ["king", "Alice", "Jack", "Bob"] 。
5. 调用 Successor(Bob, curOrder) ，返回 null 。最终得到继承顺序为 ["king", "Alice", "Jack", "Bob"] 。

通过以上的函数，我们总是能得到一个唯一的继承顺序。

请你实现 ThroneInheritance 类：

• ThroneInheritance(string kingName) 初始化一个 ThroneInheritance 类的对象。国王的名字作为构造函数的参数传入。
• void birth(string parentName, string childName) 表示 parentName 新拥有了一个名为 childName 的孩子。
• void death(string name) 表示名为 name 的人死亡。一个人的死亡不会影响 Successor 函数，也不会影响当前的继承顺序。你可以只将这个人标记为死亡状态。
• string[] getInheritanceOrder() 返回 除去 死亡人员的当前继承顺序列表。

示例：

输入：
["ThroneInheritance", "birth", "birth", "birth", "birth", "birth", "birth", "getInheritanceOrder", "death", "getInheritanceOrder"]
[["king"], ["king", "andy"], ["king", "bob"], ["king", "catherine"], ["andy", "matthew"], ["bob", "alex"], ["bob", "asha"], [null], ["bob"], [null]]
输出：
[null, null, null, null, null, null, null, ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"], null, ["king", "andy", "matthew", "alex", "asha", "catherine"]]

解释：
ThroneInheritance t= new ThroneInheritance("king"); // 继承顺序：king
t.birth("king", "andy"); // 继承顺序：king > andy
t.birth("king", "bob"); // 继承顺序：king > andy > bob
t.birth("king", "catherine"); // 继承顺序：king > andy > bob > catherine
t.birth("andy", "matthew"); // 继承顺序：king > andy > matthew > bob > catherine
t.birth("bob", "alex"); // 继承顺序：king > andy > matthew > bob > alex > catherine
t.birth("bob", "asha"); // 继承顺序：king > andy > matthew > bob > alex > asha > catherine
t.getInheritanceOrder(); // 返回 ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"]
t.death("bob"); // 继承顺序：king > andy > matthew > bob（已经去世）> alex > asha > catherine
t.getInheritanceOrder(); // 返回 ["king", "andy", "matthew", "alex", "asha", "catherine"]

说明：

• 1 <= kingName.length, parentName.length, childName.length, name.length <= 15
• kingName，parentName， childName 和 name 仅包含小写英文字母。
• 所有的参数 childName 和 kingName 互不相同。
• 所有 death 函数中的死亡名字 name 要么是国王，要么是已经出生了的人员名字。
• 每次调用 birth(parentName, childName) 时，测试用例都保证 parentName 对应的人员是活着的。
• 最多调用 10^5 次birth 和 death 。
• 最多调用 10 次 getInheritanceOrder 。

思路

首先要弄清皇位继承顺序，国王孩子中最大的先继承，如果他也有后代同样按照长幼继承，然后才轮到国王的次子继承。刚开始以为是先在老一辈里面按顺序继承，然后才轮到孩子辈的。国王生的孩子直接按顺序加入，如果国王死了就将继承国王的后代加入继承序列。

继承顺序可以有两种处理方式，一个是在出生与死亡的时候维护，另一个是在调用继承顺序方法的时候根据现有的状态生成。

动态维护的算法不容易实现，死亡的时候需要从继承序列中删除，出生时需要在特定位置插入，在哪插？

根据状态生成更容易实现，每次都是从开国的国王开始，按照继承规则遍历即可。写的时候也没有意识到这其实就是多叉树的前序遍历。

代码

/**
 * @date 2024-04-07 8:42
 */
public class ThroneInheritance1600 {

    private final Map<String, List<String>> children;

    private final Set<String> dead;

    private final String originator;

    public ThroneInheritance1600(String kingName) {
        originator = kingName;
        children = new HashMap<>();
        dead = new HashSet<>();
    }

    public void birth(String parentName, String childName) {
        children.computeIfAbsent(parentName, k -> new ArrayList<>()).add(childName);
    }

    public void death(String name) {
        dead.add(name);
    }

    public List<String> getInheritanceOrder() {
        List<String> curOrder = new ArrayList<>();
        if (!dead.contains(originator)) {
            curOrder.add(originator);
        }
        successor(originator, curOrder);
        return curOrder;
    }

    public void successor(String name, List<String> curOrder) {
        if (children.get(name) != null && children.get(name).size() != 0) {
            for (String child : children.get(name)) {
                if (!dead.contains(child)) {
                    curOrder.add(child);
                }
                successor(child, curOrder);
            }
        }
    }

    public static void main(String[] args) {
        ThroneInheritance1600 main = new ThroneInheritance1600("king");
        System.out.println(main.getInheritanceOrder());
        main.birth("king", "logan");
        main.birth("logan", "hosea");
        main.birth("king", "leonard");
        main.death("king");
        main.birth("logan", "carl");
        main.death("hosea");
        main.birth("leonard", "ronda");
        main.birth("logan", "betty");
        System.out.println(main.getInheritanceOrder());
    }
}

性能

目标

请你设计并实现一个能够对其中的值进行跟踪的数据结构，并支持对频率相关查询进行应答。

实现 FrequencyTracker 类：

• FrequencyTracker()：使用一个空数组初始化 FrequencyTracker 对象。
• void add(int number)：添加一个 number 到数据结构中。
• void deleteOne(int number)：从数据结构中删除一个 number 。数据结构 可能不包含 number ，在这种情况下不删除任何内容。
• bool hasFrequency(int frequency): 如果数据结构中存在出现 frequency 次的数字，则返回 true，否则返回 false。

示例 1：

输入
["FrequencyTracker", "add", "add", "hasFrequency"]
[[], [3], [3], [2]]
输出
[null, null, null, true]

解释
FrequencyTracker frequencyTracker = new FrequencyTracker();
frequencyTracker.add(3); // 数据结构现在包含 [3]
frequencyTracker.add(3); // 数据结构现在包含 [3, 3]
frequencyTracker.hasFrequency(2); // 返回 true ，因为 3 出现 2 次

示例 2：

输入
["FrequencyTracker", "add", "deleteOne", "hasFrequency"]
[[], [1], [1], [1]]
输出
[null, null, null, false]

解释
FrequencyTracker frequencyTracker = new FrequencyTracker();
frequencyTracker.add(1); // 数据结构现在包含 [1]
frequencyTracker.deleteOne(1); // 数据结构现在为空 []
frequencyTracker.hasFrequency(1); // 返回 false ，因为数据结构为空

示例 3：

输入
["FrequencyTracker", "hasFrequency", "add", "hasFrequency"]
[[], [2], [3], [1]]
输出
[null, false, null, true]

解释
FrequencyTracker frequencyTracker = new FrequencyTracker();
frequencyTracker.hasFrequency(2); // 返回 false ，因为数据结构为空
frequencyTracker.add(3); // 数据结构现在包含 [3]
frequencyTracker.hasFrequency(1); // 返回 true ，因为 3 出现 1 次

说明：

• 1 <= number <= 10^5
• 1 <= frequency <= 10^5
• 最多调用 add、deleteOne 和 hasFrequency 共计 2 * 10^5 次

思路

这道题要我们写一个数据结构，能够实时追踪已保存数字的出现频率。我们可以很方便地使用Map记录数字出现的频率，但是无法直接判断频率是否存在。只能遍历EntrySet一个一个找。

于是考虑再记录一个以频率为Key，相应频率的数字个数为value的Map，以便直接判断是否存在相应的频率。

那么第一个Map是否可以省略呢？当然不行，因为数字新增或删除后，相应的频率也会发生变化。如果不记录的话，无法更新第二个Map。

当数字出现频率增加，除了要累加第一个Map相应数字的频率，还要同时将第二个Map原频率对应数字的个数减1，新频率对应数字的个数加1。

当数字出现频率减少，除了要减小第一个Map相应数字的频率，还要同时将第二个Map原频率对应数字的个数减1，新频率对应数字的个数加1。

代码

/**
 * @date 2024-03-21 8:57
 */
public class FrequencyTracker2671 {

    class FrequencyTracker {
        private final Map<Integer, Integer> elements;
        private final Map<Integer, Integer> fRecord;

        public FrequencyTracker() {
            elements = new HashMap<>();
            fRecord = new HashMap<>();
        }

        public void add(int number) {
            Integer f = elements.get(number) == null ? 0 : elements.get(number);
            if (f != 0) {
                fRecord.put(f, fRecord.get(f) - 1);
            }
            elements.merge(number, 1, Integer::sum);
            fRecord.merge(++f, 1, Integer::sum);
        }

        public void deleteOne(int number) {
            Integer f = elements.get(number) == null ? 0 : elements.get(number);
            if (f != 0) {
                elements.put(number, f - 1);
                fRecord.put(f, fRecord.get(f) - 1);
                fRecord.merge(--f, 1, Integer::sum);
            }
        }

        public boolean hasFrequency(int frequency) {
            return fRecord.get(frequency) != null && fRecord.get(frequency) > 0;
        }
    }

性能

有网友写的变长数组性能更高一些，如果是直接根据题目最大范围创建数组，针对这些测试案例性能反而不好。