首页 > 其他分享 >力扣刷题之2940.找到Alice和Bob可能相遇的建筑

力扣刷题之2940.找到Alice和Bob可能相遇的建筑

时间:2024-08-13 23:24:39浏览次数:14  
标签:int Alice 查询 力扣 Bob heights 建筑

题干描述

给你一个下标从 0 开始的正整数数组 heights ,其中 heights[i] 表示第 i 栋建筑的高度。

如果一个人在建筑 i ,且存在 i < j 的建筑 j 满足 heights[i] < heights[j] ,那么这个人可以移动到建筑 j 。

给你另外一个数组 queries ,其中 queries[i] = [ai, bi] 。第 i 个查询中,Alice 在建筑 ai ,Bob 在建筑 bi 。

请你能返回一个数组 ans ,其中 ans[i] 是第 i 个查询中,Alice 和 Bob 可以相遇的 最左边的建筑 。如果对于查询 i ,Alice  Bob 不能相遇,令 ans[i] 为 -1 。

示例 1:

输入:heights = [6,4,8,5,2,7], queries = [[0,1],[0,3],[2,4],[3,4],[2,2]]
输出:[2,5,-1,5,2]
解释:第一个查询中,Alice 和 Bob 可以移动到建筑 2 ,因为 heights[0] < heights[2] 且 heights[1] < heights[2] 。
第二个查询中,Alice 和 Bob 可以移动到建筑 5 ,因为 heights[0] < heights[5] 且 heights[3] < heights[5] 。
第三个查询中,Alice 无法与 Bob 相遇,因为 Alice 不能移动到任何其他建筑。
第四个查询中,Alice 和 Bob 可以移动到建筑 5 ,因为 heights[3] < heights[5] 且 heights[4] < heights[5] 。
第五个查询中,Alice 和 Bob 已经在同一栋建筑中。
对于 ans[i] != -1 ,ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左边建筑的下标。
对于 ans[i] == -1 ,不存在 Alice 和 Bob 可以相遇的建筑。

示例 2:

输入:heights = [5,3,8,2,6,1,4,6], queries = [[0,7],[3,5],[5,2],[3,0],[1,6]]
输出:[7,6,-1,4,6]
解释:第一个查询中,Alice 可以直接移动到 Bob 的建筑,因为 heights[0] < heights[7] 。
第二个查询中,Alice 和 Bob 可以移动到建筑 6 ,因为 heights[3] < heights[6] 且 heights[5] < heights[6] 。
第三个查询中,Alice 无法与 Bob 相遇,因为 Bob 不能移动到任何其他建筑。
第四个查询中,Alice 和 Bob 可以移动到建筑 4 ,因为 heights[3] < heights[4] 且 heights[0] < heights[4] 。
第五个查询中,Alice 可以直接移动到 Bob 的建筑,因为 heights[1] < heights[6] 。
对于 ans[i] != -1 ,ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左边建筑的下标。
对于 ans[i] == -1 ,不存在 Alice 和 Bob 可以相遇的建筑。

题干分析

问题解析

        我们有一个数组heights,其中每个元素代表着建筑物的高度。给定一个查询数组queries,每个查询包含两个位置(ai, bi),表示Alice在ai位置,Bob在bi位置。我们的目标是找到一个最左边的位置,使得Alice和Bob都能通过移动到该位置相遇。如果不能相遇,返回-1。

解题思路

        为了解决这个问题我们使用线段树来有效地查找每个位置右侧的最高建筑。这样可以快速判断Alice是否能与Bob相遇。

       这里简单解释一下什么是线段树:线段树是一种数据结构,允许我们在对数时间内找到某个区间的最大值。这非常适合处理需要多次从进行范围查询的问题。

代码步骤

1.构建线段树
  • 目的:构建一棵线段树用于存储每个区间的最大高度。
  • 叶子结点:表示每个建筑物的高度。
  • 内部节点:表示其子节点的最大值,这样可以快速查询某一区间的最大高度。
// 构建线段树,用于存储建筑高度信息
void build(int l, int r, int rt, int heights[], int n, int* zd) {
    if (l == r) {  // 叶子节点:存储heights数组的值
        zd[rt] = heights[l - 1];
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, rt << 1, heights, n, zd);  // 递归构建左子树
    build(mid + 1, r, rt << 1 | 1, heights, n, zd);  // 递归构建右子树
    zd[rt] = (zd[rt << 1] > zd[rt << 1 | 1]) ? zd[rt << 1] : zd[rt << 1 | 1];  // 保存左右子树的最大值
}
 2.查询最左位置

目的:

  • 找到右侧第一个高度大于val的位置。

步骤:

1.如果当前区间的最大高度小于等于val,返回0表示无法找到满足条件的建筑。

  • 解释:如果当前区间的最大高度小于等于val,意味着从这个区间的所有建筑高度都无法满足条件(即高度都小于等于val)。因此,我们返回0表示在这个区间内无法找到合适的建筑。

2.如果当前区间是一个叶子节点,返回这个叶子结点的索引。

  • 解释:如果当前区间已经是一个叶子节点(即只包含一个建筑),那么如果这个建筑高度大于val,我们找到了满足条件的建筑,返回这个建筑的索引。

3.否则递归查询左子区间;如果左子区间没有找到合适的位置,继续查询右子区间。

  • 解释:我们需要检查左子区间是否存在满足条件的建筑。如果左子区间找到了符合条件的建筑,我们可以你直接返回结果。
  • 如果左子区间没有找到合适的位置,则继续查询右子区间。这个步骤的关键是确保我们找到的建筑是最左侧的(即最早可以相遇的位置)。

4.为什么这么做?

       当Alice和Bob分别在建筑ai和bi时,我们需要找到从bi开始向右,第一个高度大于heights[ai]的建筑,以便于确定他们能否相遇。

       如果heights[bi]<heights[ai],Alice不能直接移动到Bob所在的建筑。因此,我们需要找到Bob右侧第一个比heights[ai]高的建筑,这样Alice才能移动到这个为止,从而满足相遇的条件。

// 查询给定值val的第一个可达位置
int query(int pos, int val, int l, int r, int rt, int* zd) {
    if (val >= zd[rt]) {
        return 0;  // 如果查询值大于等于区间最大值,返回0表示无法到达
    }

    if (l == r) {
        return l;  // 如果到达叶子节点,返回该位置
    }

    int mid = (l + r) >> 1;
    if (pos <= mid) {
        int res = query(pos, val, l, mid, rt << 1, zd);  // 先查询左子区间
        if (res != 0) {
            return res;  // 如果左子区间有结果,直接返回
        }
    }
    return query(pos, val, mid + 1, r, rt << 1 | 1, zd);  // 查询右子区间
}
3.处理查询

目的:

  • 根据每个查询(ai,bi)找出Alice和Bob能相遇的最左侧建筑。

步骤: 

  • 如果a == b,Alice和Bob已经相遇,直接返回b。
  • 如果heights[a] < heights[b],Alice可以直接移动到Bob的位置。
  • 否则,通过线段树查询从b+1开始,第一个高度大于heights[a]的位置。
  • 将结果存入ans数组。
// 主函数,处理查询并返回结果数组
int* leftmostBuildingQueries(int* heights, int heightsSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
    int n = heightsSize;
    int zd[n * 4];
    memset(zd, 0, sizeof(zd));
    build(1, n, 1, heights, n, zd);  // 构建线段树

    int* ans = (int*)malloc(queriesSize * sizeof(int));
    for (int i = 0; i < queriesSize; i++) {
        int a = queries[i][0];
        int b = queries[i][1];
        if (a > b) {  // 保证a小于b
            int temp = a;
            a = b;
            b = temp;
        }
        if (a == b || heights[a] < heights[b]) {
            ans[i] = b;  // 如果a和b相等或a位置高度小于b位置高度,b即为答案
            continue;
        }
        ans[i] = query(b + 1, heights[a], 1, n, 1, zd) - 1;  // 查询b右侧高度大于a位置高度的最左位置
    }
    *returnSize = queriesSize;
    return ans;
}

完整代码如下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 构建线段树,用于存储建筑高度信息
void build(int l, int r, int rt, int heights[], int n, int* zd) {
    if (l == r) {  // 叶子节点:存储heights数组的值
        zd[rt] = heights[l - 1];
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, rt << 1, heights, n, zd);  // 递归构建左子树
    build(mid + 1, r, rt << 1 | 1, heights, n, zd);  // 递归构建右子树
    zd[rt] = (zd[rt << 1] > zd[rt << 1 | 1]) ? zd[rt << 1] : zd[rt << 1 | 1];  // 保存左右子树的最大值
}

// 查询给定值val的第一个可达位置
int query(int pos, int val, int l, int r, int rt, int* zd) {
    if (val >= zd[rt]) {
        return 0;  // 如果查询值大于等于区间最大值,返回0表示无法到达
    }

    if (l == r) {
        return l;  // 如果到达叶子节点,返回该位置
    }

    int mid = (l + r) >> 1;
    if (pos <= mid) {
        int res = query(pos, val, l, mid, rt << 1, zd);  // 先查询左子区间
        if (res != 0) {
            return res;  // 如果左子区间有结果,直接返回
        }
    }
    return query(pos, val, mid + 1, r, rt << 1 | 1, zd);  // 查询右子区间
}

// 主函数,处理查询并返回结果数组
int* leftmostBuildingQueries(int* heights, int heightsSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
    int n = heightsSize;
    int zd[n * 4];
    memset(zd, 0, sizeof(zd));
    build(1, n, 1, heights, n, zd);  // 构建线段树

    int* ans = (int*)malloc(queriesSize * sizeof(int));
    for (int i = 0; i < queriesSize; i++) {
        int a = queries[i][0];
        int b = queries[i][1];
        if (a > b) {  // 保证a小于b
            int temp = a;
            a = b;
            b = temp;
        }
        if (a == b || heights[a] < heights[b]) {
            ans[i] = b;  // 如果a和b相等或a位置高度小于b位置高度,b即为答案
            continue;
        }
        ans[i] = query(b + 1, heights[a], 1, n, 1, zd) - 1;  // 查询b右侧高度大于a位置高度的最左位置
    }
    *returnSize = queriesSize;
    return ans;
}

// 测试代码
int main() {
    int heights[] = { 10, 12, 5, 14, 15 };
    int heightsSize = sizeof(heights) / sizeof(heights[0]);
    int queriesSize = 2;
    int queriesColSize[] = { 2, 2 };
    int* queries[] = { (int[]) { 1, 3 }, (int[]) { 4, 2 } };
    int returnSize;

    int* result = leftmostBuildingQueries(heights, heightsSize, queries, queriesSize, queriesColSize, &returnSize);
    for (int i = 0; i < returnSize; i++) {
        printf("%d\n", result[i]);
    }
    free(result);

    return 0;
}

标签:int,Alice,查询,力扣,Bob,heights,建筑
From: https://blog.csdn.net/m0_75213259/article/details/141144732

相关文章

  • 算法力扣刷题记录 七十七【63. 不同路径 II】
    前言动态规划第6篇。记录七十七【63.不同路径II】一、题目阅读一个机器人位于一个mxn网格的左上角(起始点在下图中标记为“Start”)。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。现在考虑网格中有障碍物。那......
  • 力扣第五十七题——插入区间
    内容介绍给你一个 无重叠的 ,按照区间起始端点排序的区间列表 intervals,其中 intervals[i]=[starti,endi] 表示第 i 个区间的开始和结束,并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval=[start,end] 表示另一个区间的开始和结束。在......
  • 力扣面试经典算法150题:移除元素
    移除元素今日的题目依旧是力扣面试经典算法150题中数组相关的题目:移除元素题目链接:https://leetcode.cn/problems/remove-element/description/?envType=study-plan-v2&envId=top-interview-150题目描述给定一个排序数组nums和一个值val,需要在原地移除数组中所有等......
  • 151. 反转字符串中的单词【 力扣(LeetCode) 】
    一、题目描述  给你一个字符串s,请你反转字符串中单词的顺序。  单词是由非空格字符组成的字符串。s中使用至少一个空格将字符串中的单词分隔开。  返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。注意:输入字符串s中可能会存在前导空格、尾......
  • 力扣第五十题——Pow(x,n)
    内容介绍实现 pow(x, n) ,即计算 x 的整数 n 次幂函数(即,xn )。示例1:输入:x=2.00000,n=10输出:1024.00000示例2:输入:x=2.10000,n=3输出:9.26100示例3:输入:x=2.00000,n=-2输出:0.25000解释:2-2=1/22=1/4=0.25提示:-100.0<x<100.0-2......
  • 力扣1.给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值
    1.给定一个整数数组nums和一个整数目标值target,请你在该数组中找出和为目标值target的那两个整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。letnums=[1,2,4,5,3,2,4,6......
  • 算法力扣刷题记录 六十八【131.分割回文串】
    前言回溯章节第六篇。切割问题。记录六十八【131.分割回文串】。一、题目阅读给你一个字符串s,请你将s分割成一些子串,使每个子串都是回文串。回文串指字符串从前读和从后读一样。返回s所有可能的分割方案。示例1:输入:s="aab"输出:[["a","a","b"],["aa","b"]]......
  • 力扣每日一题2024.8.5
    600.不含连续1的非负整数(困难)给定一个正整数n,请你统计在[0,n]范围的非负整数中,有多少个整数的二进制表示中不存在连续的1。示例1:输入:n=5输出:5解释:下面列出范围在[0,5]的非负整数与其对应的二进制表示:0:01:12:103:114:1005:101......
  • leetcode力扣第29题:两数相除
    这题看似简单,实则一点也不难(不是),实则还是比较困难。最简单的做法是直接用减法,不停循环计数,最后统计减多少次能成。如果被除数是2^31-1或差不多大小的数,而除数是1差不多大小的数,那循环减法要执行的次数太多,一定会超时。所以一定要有更好的思路(1)通过二分法查找可能的商(2)对于......
  • day32【LeetCode力扣】541. 反转字符串 II
    day32【LeetCode力扣】541.反转字符串II1.题目描述给定一个字符串s和一个整数k,从字符串开头算起,每计数至2k个字符,就反转这2k字符中的前k个字符。如果剩余字符少于k个,则将剩余字符全部反转。如果剩余字符小于2k但大于或等于k个,则反转前k个字符,其余字符......