浙江省城乡和建设厅网站,初中生可做兼职的网站,厦门跨境电商前十,江苏网站seo优化LeetCode 399
给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件#xff0c;其中 equations[i] [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。
另有一些以数组 queries 表示的问题#xff0c;其…LeetCode 399
给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件其中 equations[i] [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。
另有一些以数组 queries 表示的问题其中 queries[j] [Cj, Dj] 表示第 j 个问题请你根据已知条件找出 Cj / Dj ? 的结果作为答案。
返回 所有问题的答案 。如果存在某个无法确定的答案则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串也需要用 -1.0 替代这个答案。
注意输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况且不存在任何矛盾的结果。
示例 1
输入equations [[a,b],[b,c]], values [2.0,3.0], queries [[a,c],[b,a],[a,e],[a,a],[x,x]]
输出[6.00000,0.50000,-1.00000,1.00000,-1.00000]
解释
条件a / b 2.0, b / c 3.0
问题a / c ?, b / a ?, a / e ?, a / a ?, x / x ?
结果[6.0, 0.5, -1.0, 1.0, -1.0 ]示例 2
输入equations [[a,b],[b,c],[bc,cd]], values [1.5,2.5,5.0], queries [[a,c],[c,b],[bc,cd],[cd,bc]]
输出[3.75000,0.40000,5.00000,0.20000]示例 3
输入equations [[a,b]], values [0.5], queries [[a,b],[b,a],[a,c],[x,y]]
输出[0.50000,2.00000,-1.00000,-1.00000]提示
1 equations.length 20equations[i].length 21 Ai.length, Bi.length 5values.length equations.length0.0 values[i] 20.01 queries.length 20queries[i].length 21 Cj.length, Dj.length 5Ai, Bi, Cj, Dj 由小写英文字母与数字组成
思路
Floyd.
可以把这个看成是一个图求两点之间最短距离。
代码
class Solution {
public:vectordouble calcEquation(vectorvectorstring equations, vectordouble values, vectorvectorstring queries) {vectordouble v;int n0;unordered_mapstring,int m;for(int i0;iequations.size();i){if(m.find(equations[i][0])m.end())m[equations[i][0]]n;if(m.find(equations[i][1])m.end())m[equations[i][1]]n;}vectorvectordouble g(n, vectordouble(n, -1.0));for(int i0;iequations.size();i){int am[equations[i][0]],bm[equations[i][1]];g[a][b]values[i];g[b][a]1.0/values[i];}for (int k 0; k n; k) {for (int i 0; i n; i) {for (int j 0; j n; j) {if(g[i][k]0g[k][j]0)g[i][j]g[i][k]*g[k][j];}}}for(int i0;iqueries.size();i){if(m.find(queries[i][0])m.end()||m.find(queries[i][1])m.end()){v.push_back(-1.0);continue;}int am[queries[i][0]],bm[queries[i][1]];v.push_back(g[a][b]);}return v;}
};
LeetCode406
假设有打乱顺序的一群人站成一个队列数组 people 表示队列中一些人的属性不一定按顺序。每个 people[i] [hi, ki] 表示第 i 个人的身高为 hi 前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue 其中 queue[j] [hj, kj] 是队列中第 j 个人的属性queue[0] 是排在队列前面的人。
示例 1
输入people [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释
编号为 0 的人身高为 5 没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 有 2 个身高更高或者相同的人排在他前面即编号为 0 和 1 的人。
编号为 3 的人身高为 6 有 1 个身高更高或者相同的人排在他前面即编号为 1 的人。
编号为 4 的人身高为 4 有 4 个身高更高或者相同的人排在他前面即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 有 1 个身高更高或者相同的人排在他前面即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。示例 2
输入people [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]提示
1 people.length 20000 hi 1060 ki people.length题目数据确保队列可以被重建
思路
先排序高个子排进去后让个子矮的选位置。
代码
class Solution {
public:vectorvectorint reconstructQueue(vectorvectorint people) {vectorvectorint v;sort(people.begin(),people.end(),[](const vectorint v1, const vectorint v2){return v1[0] v2[0] || (v1[0]v2[0]v1[1] v2[1]);});for(int i0;ipeople.size();i){v.insert(v.begin()people[i][1],people[i]);}return v;}
};
