【LeetCode每日一题合集】2023.9.25-2023.10.1（⭐LFU缓存Java数据流花期内花的数量）

文章目录

460. LFU 缓存⭐（数据结构题）

https://leetcode.cn/problems/lfu-cache/description/?envType=daily-question&envId=2023-09-25

在这里插入图片描述

提示：
1 <= capacity <= 10^4
0 <= key <= 10^5
0 <= value <= 10^9
最多调用 2 * 10^5 次 get 和 put 方法

解法1——平衡树 + 哈希表（TreeSet + HashMap） O ( l o g n ) O(logn) O(logn)

自定义节点维护每个键值对的 time 和 cnt。
用 TreeSet 对节点排序，HashMap 存储 key 和 node 的对应关系。

class LFUCache {
    int capacity, time;
    Map<Integer, Node> keyTable;
    TreeSet<Node> s;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.time = 0;
        keyTable = new  HashMap<>();
        s = new TreeSet<Node>();
    }
    
    public int get(int key) {
        if (!keyTable.containsKey(key)) return -1;
        // 取出旧的
        Node cache = keyTable.get(key);
        s.remove(cache);
        // 修改旧的 并重新放入
        cache.cnt++;
        cache.time = time++;
        s.add(cache);
        keyTable.put(key, cache);
        return cache.value;
    }
    
    public void put(int key, int value) {
        if (!keyTable.containsKey(key)) {
            if (keyTable.size() == capacity) {
                // 删除最近最少使用的
                keyTable.remove(s.first().key);
                s.remove(s.first());
            }
            // 创建新的缓存
            Node cache = new Node(1, time++, key, value);
            keyTable.put(key, cache);
            s.add(cache);
        } else {
            Node cache = keyTable.get(key);
            s.remove(cache);
            cache.cnt++;
            cache.time = time++;
            cache.value = value;
            s.add(cache);
            keyTable.put(key, cache);
        }
    }
}

class Node implements Comparable<Node> {
    int cnt, time, key, value;

    Node(int cnt, int time, int key, int value) {
        this.cnt = cnt;
        this.time = time;
        this.key = key;
        this.value = value;
    }

    public boolean equals(Object anObject) {
        if (this == anObject) return true;
        if (anObject instanceof Node) {
            Node rhs = (Node) anObject;
            return this.cnt == rhs.cnt && this.time == this.time;
        }
        return false;
    }

    public int compareTo(Node rhs) {
        return cnt == rhs.cnt? time - rhs.time: cnt - rhs.cnt;
    }

    public int hashCode() {
        return cnt * 1000000007 + time;
    }
}

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

解法2——双哈希表 + 双向链表 O ( 1 ) O(1) O(1) （LRU缓存的升级版）

一个哈希表存储 key 和 Node 之间的关系。另一个哈希表存储 freq 和 DoublyLinkedList 的对应关系。
每个使用频率对应一个双向链表，双向链表维护了该频次所有节点的先后顺序，头节点是最近被使用的，尾节点是最不常被使用的。（类似LRU缓存那道题）。

同时维护一个变量 minFreq，方便快速确定最低使用的频率。

class LFUCache {
    int minFreq, capacity;
    Map<Integer, Node> keyTable;
    Map<Integer, DoublyLinkedList> freqTable;

    public LFUCache(int capacity) {
        this.minFreq = 0;
        this.capacity = capacity;
        keyTable = new HashMap<Integer, Node>();
        freqTable = new HashMap<Integer, DoublyLinkedList>();
    }
    
    public int get(int key) {
        if (capacity == 0) {
            return -1;
        }
        if (!keyTable.containsKey(key)) {
            return -1;
        }
        Node node = keyTable.get(key);
        int val = node.val, freq = node.freq;
        freqTable.get(freq).remove(node);
        // 如果当前链表为空，我们需要在哈希表中删除，且更新minFreq
        if (freqTable.get(freq).size == 0) {
            freqTable.remove(freq);
            if (minFreq == freq) {
                minFreq += 1;
            }
        }
        // 插入到 freq + 1 中
        DoublyLinkedList list = freqTable.getOrDefault(freq + 1, new DoublyLinkedList());
        list.addFirst(new Node(key, val, freq + 1));
        freqTable.put(freq + 1, list);
        keyTable.put(key, freqTable.get(freq + 1).getHead());
        return val;
    }
    
    public void put(int key, int value) {
        if (!keyTable.containsKey(key)) {
            // 缓存已满，需要删除
            if (keyTable.size() == capacity) {
                Node node = freqTable.get(minFreq).getTail();
                keyTable.remove(node.key);
                freqTable.get(minFreq).remove(node);
                if (freqTable.get(minFreq).size == 0) {
                    freqTable.remove(minFreq);
                }
            }
            // 创建新节点
            DoublyLinkedList list = freqTable.getOrDefault(1, new DoublyLinkedList());
            list.addFirst(new Node(key, value, 1));
            freqTable.put(1, list);
            keyTable.put(key, freqTable.get(1).getHead());
            minFreq = 1;
        } else {
            // 与 get 操作基本一致，除了需要更新缓存的值
            Node node = keyTable.get(key);
            int freq = node.freq;
            freqTable.get(freq).remove(node);
            if (freqTable.get(freq).size == 0) {
                freqTable.remove(freq);
                if (minFreq == freq) {
                    minFreq += 1;
                }
            }
            DoublyLinkedList list = freqTable.getOrDefault(freq + 1, new DoublyLinkedList());
            list.addFirst(new Node(key, value, freq + 1));
            freqTable.put(freq + 1, list);
            keyTable.put(key, freqTable.get(freq + 1).getHead());
        }
    }
}

class Node {
    int key, val, freq;
    Node prev, next;

    Node() {
        this(-1, -1, 0);
    }

    Node(int key, int val, int freq) {
        this.key = key;
        this.val = val;
        this.freq = freq;
    }
}

class DoublyLinkedList {
    Node dummyHead, dummyTail;
    int size;

    DoublyLinkedList() {
        dummyHead = new Node();
        dummyTail = new Node();
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
        size = 0;
    }

    public void addFirst(Node node) {
        Node prevHead = dummyHead.next;
        node.prev = dummyHead;
        dummyHead.next = node;
        node.next = prevHead;
        prevHead.prev = node;
        size++;
    }

    public void remove(Node node) {
        Node prev = node.prev, next = node.next;
        prev.next = next;
        next.prev = prev;
        size--;
    }

    public Node getHead() {
        return dummyHead.next;
    }

    public Node getTail() {
        return dummyTail.prev;
    }
}


/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

2582. 递枕头

https://leetcode.cn/problems/pass-the-pillow/?envType=daily-question&envId=2023-09-26
在这里插入图片描述

解法——找数学规律

队列长度是 n，每次循环传递 n - 1 次。
计算传递几次循环，以及最后一次循环完成了几次传递。

class Solution {
    public int passThePillow(int n, int time) {
        int x = time / (n - 1), y = time % (n - 1);
        if (x % 2 == 0) return y + 1;
        return n - y;
    }
}

1333. 餐厅过滤器（简单模拟）

https://leetcode.cn/problems/filter-restaurants-by-vegan-friendly-price-and-distance/description/?envType=daily-question&envId=2023-09-27

在这里插入图片描述
提示：
1 <= restaurants.length <= 10^4
restaurants[i].length == 5
1 <= idi, ratingi, pricei, distancei <= 10^5
1 <= maxPrice, maxDistance <= 10^5
veganFriendlyi 和 veganFriendly 的值为 0 或 1 。
所有 idi 各不相同。

写法1——手动模拟

class Solution {
    public List<Integer> filterRestaurants(int[][] restaurants, int veganFriendly, int maxPrice, int maxDistance) {
        List<int[]> ans = new ArrayList<>();
        for (int[] r: restaurants) {
            if (veganFriendly == 1 && r[2] == 0) continue;
            if (r[3] <= maxPrice && r[4] <= maxDistance) {
                ans.add(r);
            }
        }
        Collections.sort(ans, (x, y) -> {
            if (x[1] != y[1]) return y[1] - x[1];
            return y[0] - x[0];
        });
        List<Integer> res = new ArrayList<>();
        for (int[] x: ans) res.add(x[0]);
        return res;
    }
}

写法2——Java数组流处理⭐

class Solution {
    public List<Integer> filterRestaurants(int[][] restaurants, int veganFriendly, int maxPrice, int maxDistance) {
        Stream<int[]> stream = Arrays.stream(restaurants);
        if (veganFriendly == 1) stream = stream.filter(x -> x[2] == 1);
        return stream.filter(x -> x[3] <= maxPrice)
                .filter(x -> x[4] <= maxDistance)
                .sorted((x, y) -> x[1] != y[1]? y[1] - x[1]: y[0] - x[0])
                .map(x -> x[0])
                .collect(Collectors.toList());
    }
}

2251. 花期内花的数目⭐

https://leetcode.cn/problems/number-of-flowers-in-full-bloom/description/?envType=daily-question&envId=2023-09-28

在这里插入图片描述

提示：
1 <= flowers.length <= 5 * 10^4
flowers[i].length == 2
1 <= starti <= endi <= 10^9
1 <= people.length <= 5 * 10^4
1 <= people[i] <= 10^9

解法1——差分数组

由于花期的数据范围很大，所以使用哈希表来代替数组存储差分结果。

代码的重点是差分数组的还原过程。

class Solution {
    public int[] fullBloomFlowers(int[][] flowers, int[] people) {
        Map<Integer, Integer> m = new HashMap<>();  // diff数组
        for (int[] f: flowers) {
            int start = f[0], end = f[1];
            m.merge(start, 1, Integer::sum);
            m.merge(end + 1, -1, Integer::sum);
        }
        // 取出所有的key，从小到大排序
        int[] times = m.keySet().stream().mapToInt(Integer::intValue).sorted().toArray();
        int n = people.length, s = 0;
        int[] ans = new int[n];
        Integer[] idx = IntStream.range(0, n).boxed().toArray(Integer[]::new);
        Arrays.sort(idx, (a, b) -> people[a] - people[b]);
        // 差分数组的还原过程
        for (int i = 0, j = 0; i < n; ++i) {
            while (j < times.length && times[j] <= people[idx[i]]) {
                s += m.get(times[j++]);
            }
            ans[idx[i]] = s;
        }
        return ans;
    }
}

解法2——二分查找

计算出某个人到达之前开花的数量 x 和 花谢的数量 y，那么他对应的答案就是 x - y。这个过程可以用二分查找来做。

class Solution {
    public int[] fullBloomFlowers(int[][] flowers, int[] people) {
        int n = people.length, m = flowers.length;
        int[] ans = new int[n];
        int[] start = new int[m], end = new int[m];
        for (int i = 0; i < m; ++i) {
            start[i] = flowers[i][0];
            end[i] = flowers[i][1];
        }
        Arrays.sort(start);
        Arrays.sort(end);
        for (int i = 0; i < n; ++i) ans[i] = op(start, end, people[i]);
        return ans;
    }

    public int op(int[] start, int[] end, int time) {
        int n = start.length;
        if (start[0] > time || end[n - 1] < time) return 0;
        return bs(start, time) - bs(end, time - 1);
    }

    public int bs(int[] a, int k) {
        int l = -1, r = a.length - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (a[mid] <= k) l = mid;
            else r = mid - 1;
        }
        return l;
    }
}

605. 种花问题（贪心）

https://leetcode.cn/problems/can-place-flowers/description/?envType=daily-question&envId=2023-09-29

在这里插入图片描述
能种就种，比较数量。

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int k = 0, m = flowerbed.length;
        for (int i = 0; i < m; ++i) {
            if (flowerbed[i] == 0) {
                if (i - 1 >= 0 && flowerbed[i - 1] == 1) continue;
                if (i + 1 < m && flowerbed[i + 1] == 1) continue;;
                k++;
                flowerbed[i] = 1;
            }
        }
        return k >= n;
    }
}

2136. 全部开花的最早一天（贪心）

https://leetcode.cn/problems/earliest-possible-day-of-full-bloom/description/?envType=daily-question&envId=2023-09-30

在这里插入图片描述

先种长的慢的。

提示：
n == plantTime.length == growTime.length
1 <= n <= 10^5
1 <= plantTime[i], growTime[i] <= 10^4

class Solution {
    public int earliestFullBloom(int[] plantTime, int[] growTime) {
        Integer[] id = IntStream.range(0, plantTime.length).boxed().toArray(Integer[]::new);
        Arrays.sort(id, (i, j) -> growTime[j] - growTime[i]);
        int ans = 0, day = 0;
        for (int i: id) {
            day += plantTime[i];
            ans = Math.max(ans, day + growTime[i]);
        }
        return ans;
    }
}

这里学习到 IntStream 流创建数组的使用方法——Integer[] id = IntStream.range(0, plantTime.length).boxed().toArray(Integer[]::new);

121. 买卖股票的最佳时机（贪心 | DP）

在这里插入图片描述
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/?envType=daily-question&envId=2023-10-01

解法1——DP

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[] sell = new int[n], buy = new int[n];
        buy[0] = -prices[0];
        for (int i = 1; i < n; ++i) {
            buy[i] = Math.max(buy[i - 1], -prices[i]);
            sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
        }
        return sell[n - 1];
    }
}

解法2——贪心

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length, ans = 0, mn = Integer.MAX_VALUE;
        for (int price: prices) {
            mn = Math.min(mn, price);
            ans = Math.max(ans, price - mn);
        }
        return ans;
    }
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/166331.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

SpringCloud微服务注册中心：Nacos介绍，微服务注册，Ribbon通信，Ribbon负载均衡，Nacos配置管理详细介绍

SpringCloud微服务注册中心：Nacos介绍，微服务注册，Ribbon通信，Ribbon负载均衡，Nacos配置管理详细介绍

微服务注册中心 注册中心可以说是微服务架构中的”通讯录“&#xff0c;它记录了服务和服务地址的映射关系。在分布式架构中&#xff0c;服务会注册到这里&#xff0c;当服务需要调用其它服务时&#xff0c;就这里找到服务的地址&#xff0c;进行调用。 微服务注册中心 服务注…
阅读更多...
LV.12 D18 中断处理 学习笔记

LV.12 D18 中断处理 学习笔记

一、ARM的异常处理机制及工程代码结构 1.1异常概念 处理器在正常执行程序的过程中可能会遇到一些不正常的事件发生 这时处理器就要将当前的程序暂停下来转而去处理这个异常的事件 异常事件处理完成之后再返回到被异常打断的点继续执行程序。 1.2异常处理机制 不同的处…
阅读更多...
2023/11/19总结

2023/11/19总结

项目进度&#xff1a; 地址管理&#xff1a; 显示菜品 购物车相关功能 然后最近在看 支付宝沙盒支付的相关功能&#xff0c;打算把支付给做了 。界面做的不是很好看 &#xff0c;但是后续会改成 手机端的。
阅读更多...
丹麦能源袭击预示着更关键的基础设施成为目标

丹麦能源袭击预示着更关键的基础设施成为目标

5 月&#xff0c;22 个丹麦能源部门组织在与俄罗斯 Sandworm APT 部分相关的攻击中受到损害。 丹麦关键基础设施安全非营利组织 SektorCERT 的一份新报告描述了不同的攻击者群体利用合勤防火墙设备中的多个关键漏洞&#xff08;包括两个零日漏洞&#xff09;侵入工业机械&…
阅读更多...
【Android Jetpack】DataStore的介绍

【Android Jetpack】DataStore的介绍

DataStore Jetpack DataStore是一种数据存储解决方案&#xff0c;允许您使用协议缓冲区存储键值对或类型化对象。DataStore使用Kotlin协程和Flow以异步、一致的事务方式存储数据。 注意&#xff1a;如果您需要支持大型或复杂数据集、部分更新或参照完整性&#xff0c;请考虑使…
阅读更多...
配置iTerm2打开自动执行命令

配置iTerm2打开自动执行命令

打开iTerm2&#xff0c;commado&#xff0c;打开profies->edit profies&#xff0c;点击号&#xff0c;创建一个新的profile 在新的profile中填写 name&#xff1a;随意 command&#xff1a;Login Shell Send text at start&#xff1a;执行脚本的命令&#xff0c;不想写路…
阅读更多...
C# Winform围棋棋盘

C# Winform围棋棋盘

C# Winform简单的围棋棋盘vs2008winform小游戏C#vs2010winform棋盘C#窗体小游戏 这是一个简单的围棋棋盘小游戏&#xff0c;使用C# Winform编写棋盘界面&#xff0c;玩家可以在空白的交叉点上下棋子 项目获取&#xff1a; 项目获取&#xff1a;typora: typora/img (gitee.co…
阅读更多...
【Android Jetpack】Hilt的理解与浅析

【Android Jetpack】Hilt的理解与浅析

文章目录 依赖注入DaggerHiltKoin添加依赖项Hilt常用注解的含义HiltAndroidAppAndroidEntryPointInjectModuleInstallInProvidesEntryPoint Hilt组件生命周期和作用域如何使用 Hilt 进行依赖注入 本文只是进行了简单入门&#xff0c;博客仅当做笔记用。 依赖注入 依赖注入是一…
阅读更多...
SQL基础理论篇（七）：多表关联的连接算法

SQL基础理论篇（七）：多表关联的连接算法

文章目录 简介Nested LoopsMerge JoinHash Join总结参考文献 简介 多表之间基础的关联算法一共有三种&#xff1a; Hash JoinNested LoopsMerge Join 还有很多基于这三种基础算法的变体&#xff0c;以Nested Loops为例&#xff0c;就有用于in和exist的半连接&#xff08;Nes…
阅读更多...
基于Python+OpenCV+Tensorflow图像迁移的艺术图片生成系统

基于Python+OpenCV+Tensorflow图像迁移的艺术图片生成系统

欢迎大家点赞、收藏、关注、评论啦 &#xff0c;由于篇幅有限&#xff0c;只展示了部分核心代码。 文章目录 一项目简介 二、功能三、系统![请添加图片描述](https://img-blog.csdnimg.cn/dbda87069fc14c24b71c1eb4224dff05.png)四. 总结 一项目简介 基于PythonOpenCVTensorfl…
阅读更多...
ARouter出现 there‘s no route matched in group问题排查

ARouter出现 there‘s no route matched in group问题排查

在使用ARouter时候会出现找不到映射路径的问题&#xff0c;这里给兄弟们总结下踩过的坑 所有用到的模块都要有填写依赖 android {defaultConfig {......javaCompileOptions {annotationProcessorOptions {arguments [AROUTER_MODULE_NAME: project.getName()]}}} } ... depe…
阅读更多...
PS学习笔记——移动工具

PS学习笔记——移动工具

文章目录 介绍文档内移动文档间移动 介绍 移动工具&#xff1a;用于移动图层中的对象&#xff0c;并且同一图层中的所有对象都将一起移动 选中移动工具后&#xff0c;选项栏中会出现“显示变换控件”&#xff0c;勾选后即可看见图层中的对象周围出现边框&#xff0c;可以进行缩…
阅读更多...
Dockerfile自定义镜像以及案例分析

Dockerfile自定义镜像以及案例分析

文章目录 一、Dockerfile自定义镜像1.1 镜像结构1.2 Dockerfile语法 二、构建Java项目三、基于java8构建java四、小结 一、Dockerfile自定义镜像 常见的镜像在DockerHub就能找到&#xff0c;但是我们自己写的项目就必须自己构建镜像了。 而要自定义镜像&#xff0c;就必须先了…
阅读更多...
单张图像3D重建：原理与PyTorch实现

单张图像3D重建：原理与PyTorch实现

近年来&#xff0c;深度学习&#xff08;DL&#xff09;在解决图像分类、目标检测、语义分割等 2D 图像任务方面表现出了出色的能力。DL 也不例外&#xff0c;在将其应用于 3D 图形问题方面也取得了巨大进展。 在这篇文章中&#xff0c;我们将探讨最近将深度学习扩展到单图像 3…
阅读更多...
“新KG”视点 | 知识图谱与大语言模型协同模式探究

“新KG”视点 | 知识图谱与大语言模型协同模式探究

OpenKG 大模型专辑 导读 知识图谱和大型语言模型都是用来表示和处理知识的手段。大模型补足了理解语言的能力&#xff0c;知识图谱则丰富了表示知识的方式&#xff0c;两者的深度结合必将为人工智能提供更为全面、可靠、可控的知识处理方法。在这一背景下&#xff0c;OpenKG组织…
阅读更多...
容斥 C. Strange Function改编题

容斥 C. Strange Function改编题

补题&#xff1a; 题目详情 - 9.段坤爱取模%%% - SUSTOJ 本题或许是参考 Problem - C - Codeforces 根据题意&#xff0c;f(i)就是不能被整除的最小的一个质因子。 打表发现&#xff0c;当15个质因子相乘后&#xff0c;长度就大于18。 因此可以知道小于等于1e16内的正整数x…
阅读更多...
LeetCode【92】翻转链表II

LeetCode【92】翻转链表II

题目&#xff1a; 思路&#xff1a; https://blog.csdn.net/DarkAndGrey/article/details/122146216 public ListNode reverseBetween(ListNode head, int left, int right) {if(head null || right left){return head;// 头节点为null&#xff0c;链表为空&#xff0c;反…
阅读更多...
我又开始贩卖焦虑了，机器视觉兄弟们，打工这生意盘不活了？让人逃离北上广深，是毒鸡汤吗？

我又开始贩卖焦虑了，机器视觉兄弟们，打工这生意盘不活了？让人逃离北上广深，是毒鸡汤吗？

我想大多数人和我想的一样&#xff0c;不要质疑自己的出身&#xff0c;也不必用一生去改变出身而获得融入感&#xff0c;思想富足这是我们留给自己一生最珍贵的礼物。也许一线城市容不下肉身&#xff0c;二三线城市容不下灵魂。那我回到生我养我的十八线小县城&#xff0c;这不…
阅读更多...
Linux虚拟机中网络连接的三种方式

Linux虚拟机中网络连接的三种方式

Linux 虚拟机中网络连接的三种方式 先假设一个场景&#xff0c;在教室中有三个人&#xff1a;张三、李四和王五&#xff08;这三个人每人有一台主机&#xff09;&#xff0c;他们三个同处于一个网段中&#xff08;192.169.0.XX&#xff09;&#xff0c;也就是说他们三个之间可…
阅读更多...
Vue3+Vite实现工程化，事件绑定以及修饰符

Vue3+Vite实现工程化，事件绑定以及修饰符

我们可以使用v-on来监听DOM事件&#xff0c;并在事件触发时执行对应的Vue的Javascript代码。 用法&#xff1a;v-on:click "handler" 或简写为 click "handler"vue中的事件名原生事件名去掉 on 前缀 如:onClick --> clickhandler的值可以是方法事件…
阅读更多...
最新文章

Copyright @ 2022~2023