力扣 LeetCode 2196. 根据描述创建二叉树 - 力扣（LeetCode） 2196. 根据描述创建二叉树 - 给你一个二维整数数组 descriptions ，其中 descriptions[i] = [parenti, childi, isLefti] 表示 parenti 是 childi 在 二叉树 中的 父节点，二叉树中各节点的值 互不相同 。此外： * 如果 isLefti == 1 ，那么 childi 就是 parenti 的左子节点。 * 如果 isLefti == 0 ，那么 childi 就是 parenti 的右子节点。 请你根据... 思路 比较常规的建树题，因为每个节点值各不相同，因此节点值可以当作每个节点的唯一标识。用哈希表维护节点值到树节点的映射，以及每个节点是否有前驱节点（没有前驱节点的节点就是根节点）。 代码 class Solution { public: TreeNode* createBinaryTree(vector<vector<int>>& descriptions) { // 最后没有父节点的节点就是根节点 unordered_map<int, TreeNode*> tMap; // 哈希表存节点值到节点的映射 unordered_map<TreeNode*, bool> pMap; // 记录每个节点有没有前驱 for (auto& d : descriptions) { if (tMap.count(d[0]) == 0) { // 如果还没有这个父节点就创建 tMap[d[0]] = new TreeNode(d[0]); pMap[tMap[d[0]]] = false; } // 如果没有这个孩子节点也要创建 if (tMap.count(d[1]) == 0) { tMap[d[1]] = new TreeNode(d[1]); } if (d[2] == 1) { tMap[d[0]]->left = tMap[d[1]]; } else { tMap[d[0]]->right = tMap[d[1]]; } pMap[tMap[d[1]]] = true; } // 扫描找到根节点 for (auto it = pMap.begin(); it != pMap.end(); it++) { if (!it->second) { return it->first; } } return nullptr; } }; 1 个帖子 - 1 位参与者 阅读完整话题
力扣 LeetCode 3161. 物块放置查询 - 力扣（LeetCode） 3161. 物块放置查询 - 有一条无限长的数轴，原点在 0 处，沿着 x 轴 正 方向无限延伸。 给你一个二维数组 queries ，它包含两种操作： 1. 操作类型 1 ：queries[i] = [1, x] 。在距离原点 x 处建一个障碍物。数据保证当操作执行的时候，位置 x 处 没有 任何障碍物。 2. 操作类型 2 ：queries[i] = [2, x, sz] 。判断在数轴范围 [0, x] 内是否可以放置一个长度为 sz 的物块，这个物块需要 完全 放置在范围 [0,... 力扣我真得控制你了，昨天给把糖，今天直接来一巴掌。这题挺有难度，看了题解才磨出来。 综合考察了二分查找和常见线段树（单点修改、区间查询）。 思路 1. 新增与查询 题目中主要是两个操作，新增一个障碍物，或者查询一个障碍物 左边最长的空闲段长度 是否 \ge sz 。 每次 [1, x] 在 x 位置 新增 障碍物，都会把一段空闲区间切分为两段。 而每次 [2, x, sz] 进行查询时，我们只在意 [0, x] 区间中 最大的空闲区间长度 是否至少为 sz 。 对于第 2 点，我们会进行多次的单点修改，且需要查询一个区间的最大值，因此可以用到常见的 单点修改、区间查询线段树 。 对于第 1 点，为了方便后续查询以及进一步的障碍物插入，我们每次插入肯定要知道 x 左边和右边的障碍物位置。这里就可以用 有序集合 来维护。 2. 线段树维护的内容 我们在查询的时候只在意某个位置 x 的 左边最大的空闲区间长度 ，也就是说查询时希望能查出 [0, x] 区间的最大值。但注意， 查询的这个 x 不一定是障碍物 。 题目中插入的是障碍物，为了方便起见，线段树中修改的点位也应该都是障碍物，没有经历过任何修改的点位值置为 0，说明此处没有障碍物。 查询已经知道了，线段树中单个节点其实表示的就应该是： 这个障碍物节点对应的区间内，所有以障碍物为结束端点的空闲段长度的最大值 。 叶子节点值就表示某个障碍物距离左边相邻障碍物的长度（ 即某个障碍物位置左边相邻的空闲段长度 ），单点修改，其实修改的就是这个值。 如果值为 0，则表示这个位置没有障碍物。 3. 线段树的更新 每次插入新的障碍物 x 时，设其左边和右边相邻的障碍物位置为 prev 和 next ， x 会把 [prev, next] 劈开成 [prev, x] 和 [x, next] 。 上面已经提到我们单点修改修改的是叶结点值，而叶节点值表示某个位置左侧相邻的空闲段长度，因此这里涉及 x 和 next 两个障碍物端点的修改。 显然修改后的值分别为 x-prev , next-x 。 修改完后上推更新树的非叶节点。 4. 查询 查询时题目给出 [2, x, sz] ，我们只需要找到 [0, x] 区间内最长的空闲段长度，看看是不是 \ge sz 即可。 但是要注意，这里不能直接用线段树，从上面第 2 节可以看到线段树是根据 障碍物位置 来更新的，查询的 x 位置不一定是障碍物。 因此我们要先找到 x 的左边相邻障碍物位置 prev ，在线段树中查询 [0, prev] ，然后再计算 x-prev 这个空闲段长度，最后再在二者中取最大值和 sz 比较。 显然 x 位置为障碍物时， x-prev=0 代码 class SegmentTree{ private: int n; vector<int> tree; // 为了方便，下标从 1 开始 public: SegmentTree(int n){ this->n=n; // 线段树预留 4N 空间，因为这里下标从 1 开始，所以 N=n+1，留 4*(n+1) // 初始全为 0，表示没有障碍物 tree.resize(n*4+4,0); } // 单点更新 // idx 为新加入的障碍物下标 // dist 为新障碍物 idx 距离其左边上一个障碍物 prev 的距离 // node 为树中结点下标，从 1 开始 // l, r 表示 node 结点对应的区间 void update(int idx,int dist,int node,int l, int r){ if(l==r){ // 单个点 tree[node]=dist; return; } int mid=l+((r-l)>>1); if(idx<=mid){ // 下标在区间左侧，进入左半边树 update(idx,dist,node<<1,l,mid); }else{ // 否则进入右半边树 update(idx,dist,(node<<1)+1,mid+1,r); } // 上推更新区间最大值 tree[node]=max(tree[node<<1],tree[(node<<1)+1]); } // 重载函数，作为更简便的入口 void update(int idx,int dist){ update(idx,dist,1,0,n); } // 查询区间 int query(int queryL,int queryR,int node,int l, int r){ if(queryL>queryR){ // 区间不合法 return 0; } if(queryL<=l&&r<=queryR){ // [l, r] 已经在 [queryL, queryR] 区间内，返回 [l, r] 区间最大值 return tree[node]; } int mid=l+((r-l)>>1); int res=0; // [queryL, queryR] 拆为两半处理 if(queryL<=mid){ res=max(res,query(queryL,queryR,node<<1,l,mid)); } if(queryR>mid){ res=max(res,query(queryL,queryR,(node<<1)+1,mid+1,r)); } // 取最大值作为查询结果 return res; } // 重载函数，作为更简便的入口 int query(int queryL,int queryR){ return query(queryL,queryR,1,0,n); } }; class Solution { public: vector<bool> getResults(vector<vector<int>>& queries) { // 肯定要用到线段树，应该是单点修改区间查询 // // 1. 每次新增障碍物，都会把一段空闲区间切成两段 // 对于插入操作 [1, x]，需要知道插入 x 时 x 左边、右边最近的障碍物在哪 // // 2. 而查询 [2, x, sz] 时，我们只在意 [0, x] 区间**最大**的空闲长度是否至少为 sz // // 对于第 1 点可以用有序集合 // 第 2 点的话就要用线段树来维护**区间最大值**了 // // 线段树中叶子节点值表示**某个障碍物**左边相邻空闲区间的长度 // // 注意线段树维护的是障碍物为结束端点的区间最大值，但我们查询时的点并不一定是障碍物 // 因此查询 x 时需要： // 1. 找到距离 x 左边最近的障碍物 prev，线段树查询 [0, prev] 最大值 // 2. 计算 x-prev （因为查询的 x 并不一定是障碍物，不在线段树中，这段距离得补上） // 二者取最大值 int maxX=0; // 找到涉及的 x 最大值，用于开树 for(auto&q:queries){ maxX=max(maxX,q[1]); } // 用有序集合维护障碍物位置 set<int> obs; // 添加哨兵，0 和 maxX+1 这个位置都可以算障碍物，方便后面查询 prev 和 next obs.insert(0); obs.insert(maxX+1); maxX++; // 开树 SegmentTree tree(maxX); vector<bool> res; // 处理查询 for(auto& q:queries){ int x=q[1]; // 要查询 / 插入的 x if(q[0]==1){ // 插入障碍物 x，保证插入时这里没有障碍物 // 先利用 C++ 标准库的二分 upper_bound 算法找到 x 位置的下一个障碍物 auto nextIt=obs.upper_bound(x); // nextIt 的上一个位置就是 x 的上一个障碍物 auto prevIt=std::prev(nextIt); int next=*nextIt; int prev=*prevIt; // 把 x 插入有序集合（插入新障碍物） obs.insert(x); // 插入新障碍物后要上推更新线段树 // 插入 x 后，[prev, next] 被截为 [prev, x], [x, next] // 线段树维护的是某个障碍物左边的最大空闲区间长度，因此这里要更新 x 和 next 两个端点 tree.update(next,next-x); // next 端点，左边空闲区间长度变成 next-x tree.update(x,x-prev); // x 端点，左边空闲区间长度变成 x-prev }else{ // 查询 int sz=q[2]; // 注意线段树只维护障碍物 // 查询时 x 不一定是障碍物，因此要先找到 prev auto nextIt=obs.upper_bound(x); int prev=*(std::prev(nextIt)); // obs 存的是障碍物，所以 prev 肯定是障碍物，我们可以查询 [0, prev] int prevMaxLen=tree.query(0,prev); // x 相邻的还有一段 x-prev，如果 x 是障碍物，显然 x-prev=0 int adjMaxLen=x-prev; res.emplace_back(max(prevMaxLen,adjMaxLen)>=sz); } } return res; } }; [!WARNING] 这里最开始我还踩了个坑导致 TLE（时间超限），最开始我用的是 C++ <algorithm> 头中的 upper_bound 二分找上界方法。 但是其主要适用于能随机访问的容器，如 vector ，对于无法随机访问的 set ，其时间复杂度会退化到 O(n) 。 解决方式就是用 set 自己的成员函数 upper_bound 来实现红黑树结构上的近似二分查找。 TLE 版本代码 （点击了解更多详细信息） 2 个帖子 - 2 位参与者 阅读完整话题
力扣 LeetCode 1559. 二维网格图中探测环 - 力扣（LeetCode） 1559. 二维网格图中探测环 - 给你一个二维字符网格数组 grid ，大小为 m x n ，你需要检查 grid 中是否存在 相同值 形成的环。 一个环是一条开始和结束于同一个格子的长度 大于等于 4 的路径。对于一个给定的格子，你可以移动到它上、下、左、右四个方向相邻的格子之一，可以移动的前提是这两个格子有 相同的值 。 同时，你也不能回到上一次移动时所在的格子。比方说，环 (1, 1) -> (1, 2) -> (1, 1) 是不合法的，因为从 (1, 2) 移动到 (1, 1)... 思路 比较典型的无向图判环题，常用的思想有 DFS / BFS / 并查集，这里咱就用并查集来做了。 先注意题目中两个条件： 走回头路不算环路，也就不能往回走。 环路径的长度要 \ge 4 才算。其实 在第 1 点条件的限制下这点是必然成立的 ，最小的环必须要有四个格子组成。 所以这题只需要保证不走回头路，进行判环即可。 用并查集判环，要不走回头路的话，我们在扫描网格时从上至下、从左至右，对于每个格子可以 只尝试合并其右方或者下方的格子 ，按这样的逻辑处理必然是不会有回头路滴。 如此扫描直至某个网格与其右边或者下边的网格在同一个集合中，则满足题目要求，返回 true 。 代码 class Solution { public: bool containsCycle(vector<vector<char>>& grid) { // 比较重要的是这种环路的长度还必须 >=4 才算 // 其实不难，可以用并查集来执行合并和判环，如果有环就看对应块中元素数量是不是 >=4 // 要构成环，最小的环必然是四个方格组成的 int m=grid.size(),n=grid[0].size(); // 初始化并查集 vector<int> parents(m*n,-1),sizes(m*n,1); auto find=[&](auto&& self, int x) -> int { // 带路径压缩的查找 return parents[x]==-1 ? x : parents[x]=self(self, parents[x]); }; // 合并，返回是否执行了合并 auto merge=[&](int x1,int x2) -> bool { int root1=find(find,x1),root2=find(find,x2); if(root1==root2){ // 已经合并 return false; } // 否则启发式合并，小树并入大树 if(sizes[root1]<sizes[root2]){ swap(root1,root2); } parents[root2]=root1; sizes[root1]+=sizes[root2]; return true; }; // 获得集合大小 // auto getSize=[&](int x){ // return sizes[find(find,x)]; // }; // 扫描数组执行判环 int drcts[][2]={ {0,1}, {1,0}, }; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ // 为了防止走回头路，对于每个方格我们只往右或者往下合并 for(auto& d:drcts){ int newI=i+d[0],newJ=j+d[1]; if(newI>=m||newJ>=n||grid[newI][newJ]!=grid[i][j]){ // 越界或者字母不相同 continue; } // 尝试执行合并 if(!merge(i*n+j,newI*n+newJ)/*&&getSize(i*n+j)>=4*/){ // 如果没有执行合并，说明遇到已经在并查集里的了，有环 // 这个时候判断，如果集合中有 >=4 个元素就可以结束 // 其实在不走回头路的前提下，只要有环，必然路径长度 >=4 return true; } } } } return false; } }; 2 个帖子 - 2 位参与者 阅读完整话题