首页 > 其他分享 >2024/08/10 每日一题

2024/08/10 每日一题

时间:2024-08-10 11:50:41浏览次数:11  
标签:10 right return int 08 tree heights 2024 left

LeetCode 2940 找到Alice和Bob可以相遇的建筑

方法1:线段树

class Solution {
    static int[] tree; // 存储区间的最大值
    
    static void build(int o, int left, int right, int[] datas) {
        if(left == right) {
            tree[o] = datas[left - 1];
            return ;
        }
        int mid = (left + right) >> 1;
        build(o << 1, left, mid, datas);
        build(o << 1 | 1, mid + 1, right, datas);
        tree[o] = Math.max(tree[o << 1], tree[o << 1 | 1]);
    } 

    static int query(int start, int val, int o, int left, int right) {
        if(val >= tree[o]) // 当前区间所有值都不大于 val
            return 0; // 直接返回 0 出去后会被 -1
        if(left == right) // 前面条件没有退出 即当前值是第一个满足条件的
            return left;
        int mid = (left + right) >> 1;
        if(start <= mid) { // 当前位置在要求区间内
            int res = query(start, val, o << 1, left, mid);
            if(res > 0) return res;
        }
        // 当前位置不在要求区间内
        return query(start, val, o << 1 | 1, mid + 1, right);
    }

    public int[] leftmostBuildingQueries(int[] heights, int[][] queries) {
        int n = heights.length;
        tree = new int[n << 2];
        build(1, 1, n, heights);  // 建树
        int m = queries.length;
        int[] ans = new int[m];
        for(int i = 0; i < m; i++) {
            int a = queries[i][0];
            int b = queries[i][1];
            if(b < a) { // 保证 b 在 a 的右边
                int temp = a; a = b; b = temp;
            }
            // 在同一位置或者右边的位置比左边高
            if(a == b || heights[a] < heights[b]) {
                ans[i] = b; continue;
            }
            // 查询区间 [b + 1, n] 中高度大于 heights[a] 的下标
            ans[i] = query(b + 1, heights[a], 1, 1, n) - 1;
        }
        return ans;
    }
}
class Solution:
    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:
        n = len(heights); tree = [0] * (n << 2)
        
        def build(o: int, left: int, right: int) -> None:
            if left == right:
                tree[o] = heights[left - 1]
                return
            mid = (left + right) >> 1
            build(o << 1, left, mid)
            build(o << 1 | 1, mid + 1, right)
            tree[o] = max(tree[o << 1], tree[o << 1 | 1])
        
        def query(start: int, val: int, o: int, left: int, right: int) -> int:
            if val >= tree[o]:
                return 0
            if left == right:
                return left
            mid = (left + right) >> 1
            if start <= mid:
                res = query(start, val, o << 1, left, mid)
                if res > 0: return res
            return query(start, val, o << 1 | 1, mid + 1, right)
        
        build(1, 1, n); ans = list()
        for i, (a, b) in enumerate(queries):
            if a > b:
                a, b = b, a
            if a == b or heights[b] > heights[a]:
                ans.append(b); continue
            ans.append(query(b + 1, heights[a], 1, 1, n) - 1)
        return ans

标签:10,right,return,int,08,tree,heights,2024,left
From: https://www.cnblogs.com/XuGui/p/18352122

相关文章

  • 8.10第四周周六学习总结
    1vj团队12补题不错的一个题解https://blog.fishze.com/archives/3011)字符串变化(模拟+找规律)题目:给定一个字符串,给定一个特定操作方式:该字符串前半段+该字符串自己+该字符串后半段求next(每一个字符向后移动一个),组成一个新字符串,求经过10^100次这样的操作后,......
  • AP2402 5-100V 1.5A 外围简单DC-DC降压恒流驱动IC 手电筒与汽车灯方案
    产品描述AP2402是一款PWM工作模式,高效率、外围简单、内置功率管,适用于5-100V输入的高精度降压LED恒流驱动芯片。输出最大功率可达15W,最大电流1.5A。AP2402可实现三段功能切换,通过MODE1/2/3切换三种功能模式:全亮,半亮,爆闪。AP2402工作频率固定在150KHZ左右,同时内置抖......
  • 塔子哥的美食节-阿里淘天2024笔试(codefun2000)
    题目链接塔子哥的美食节-阿里淘天2024笔试(codefun2000)题目内容塔子哥是一位美食评论家,他最近参加了一个美食节,品尝了n种不同的美食,每种美食都有一个特定的人气值。现在,塔子哥想写一篇关于这次美食节的文章,他打算挑选出k种美食,使得文章中能够突出一种特别受欢迎的......
  • 08 Button 组件
    08Button组件Button组件是tkinter中用于创建可交互按钮的组件,它允许用户通过点击按钮来触发特定的事件或执行命令。Button组件是构建交互式图形用户界面的基础。基本用法与可选属性基本用法创建Button组件的基本语法如下:importtkinterastkroot=tk.Tk()......
  • 如何在 Windows 11/10/8/7 中恢复已删除和未保存的记事本文本文件
    很多原因都会导致未保存的记事本文本文件丢失。这些包括意外关闭、系统崩溃或电源故障等。无论丢失文本文件的原因是什么,相关的焦虑都是一样的。如果您遇到这种情况,可以使用以下有效方法在Windows11/10/8/7 中恢复已删除的文本文件。在这篇文章中,我们将分享三种在Windows......
  • 2024牛客暑期多校训练营2
    A.FloorTiles恶心构造,本来构造的方法没有错,因为不小心修改了第一块砖的位置,导致一直过不去,没注意,倒了思路:先把最多曲线的构造出来,就是类似于BAB......
  • 08-08 题解
    08-08题解地址A-CF1420Eluogu翻译更正ifhegivesnomorethatkorders对于至多k次操作,题面没有翻译出来思路怎么算贡献?贡献(被保护)出现在「处在任意两个不同的0的连续段的守卫」之间,而处于同一连续段的守卫之间没有贡献设一共\(cnt\)个\(0\),每个连续......
  • 下载量10w+!大型语言模型:语言理解和生成
    近年来,人工智能在新语言能力方面取得了显著进展,深度学习技术的快速发展推动了语言AI系统在文本编写和理解方面的表现。免费获取:下载量10w+!大型语言模型:语言理解和生成......
  • 08-09 题解
    08-09题解A小水题思路假设我们选定了当前子序列的绝对众数\(x\),那么该序列里最多再放\(num_x-1\)个其他数字为了分出最少的子序列,肯定要让每个子序列在拥有绝对众数的同时能消化尽量多的其他数字由此,可以得到一个贪心策略:每次取出出现次数最多的一个数字,消掉出现......
  • 2024,该放弃框架来实现 Web 布局了
    在这里,我并不想评论CSS框架和库的好坏,但一个不争的现实就是,很多Web开发者很容易在众多的CSS框架库中迷失方向。甚至,每个框架和库都向Web开发者承诺,将提供更简单的样式和更流畅的Web布局。然而,在当下,现代CSS特性提供了更简单和更灵活的方法,你完全可以不依赖任何CSS......