网站开发找哪家好,西安市建设厅网站,珠海网站建设公司哪个好,域名免费注册网站前言
经过前期的基础训练以及部分实战练习#xff0c;粗略掌握了各种题型的解题思路。现阶段开始专项练习。
描述 给你一个下标从 0 开始的正整数数组 heights #xff0c;其中 heights[i] 表示第 i 栋建筑的高度。 如果一个人在建筑 i #xff0c;且存在 i j 的建筑…前言
经过前期的基础训练以及部分实战练习粗略掌握了各种题型的解题思路。现阶段开始专项练习。
描述 给你一个下标从 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 可以相遇的建筑。提示 1 heights.length 5 * 1041 heights[i] 1091 queries.length 5 * 104queries[i] [ai, bi]0 ai, bi heights.length - 1 实现原理与步骤
1.题目意思解析
queries[i][0]和queries[i][1]相等情况下返回queryies[i][0];
queries[i][0]和queries[i][1]不等情况下找到最接近的下标j使得height(j)Math.max(height(queries[i][0]),height(queries[i][1])).
2.本题模拟算法情况下会超时当存在大量queries情况下线段树方法是合理的选择。
3.线段树的构建没什么特殊特殊的是查询条件变了。
原本查询的区间条件left和right变为起点查询条件pos和Math.max(height(queries[i][0]),height(queries[i][1])的val值。
当Math.max(height(queries[i][0]),height(queries[i][1]))大于zd[node]时跳过当前node对应的线段返回0.当posmid时跳过该线段查询由于递归的下标从小到大所以跳过该段查询后下一段最小的序号即为对应最接近的下标j。当startend时返回节点的序号start也就是找到最接近的下标j使得height(j)Math.max(height(queries[i][0]),height(queries[i][1])) 实现代码
class Solution {int[] zd;public int[] leftmostBuildingQueries(int[] heights, int[][] queries) {int n heights.length;zd new int[n * 4];buildTree(heights,0, 0, n-1);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 (a b) {int temp a;a b;b temp;}if (a b || heights[a] heights[b]) {ans[i] b;continue;}int tempRes queryTree(0,0,n-1,b 1, heights[a]);ans[i]tempRes0?-1:tempRes;}return ans;}public void buildTree(int[] nums, int node, int start, int end) {if (start end) {zd[node] nums[start];} else {int mid (start end) / 2;int leftChild 2 * node 1;int rightChild 2 * node 2;buildTree(nums, leftChild, start, mid);buildTree(nums, rightChild, mid 1, end);zd[node] Math.max(zd[leftChild] ,zd[rightChild]);}}private int queryTree(int node, int start, int end, int pos, int val) {if (valzd[node]) {return 0;}if (startend) {return start;}int mid (start end) / 2;int leftChild 2 * node 1;int rightChild 2 * node 2;if(posmid){int res queryTree(leftChild, start, mid, pos, val);if(res!0){return res;}}return queryTree(rightChild, mid 1, end, pos, val);}
}1.QA:
