Re: [閒聊] 每日leetcode

看板Marginalman作者sixB (6B)時間11月前 (2024/12/23 23:47)推噓0(0推 0噓 0→)

要去洗澡等等再來看solution怎麼寫的 class Solution { public: vector<int> leftmostBuildingQueries(vector<int>& H, vector<vector<int>>& Q) { // range: val [1, mx] // get min idx int n = H.size(), m = Q.size(); // seperate H vector<int> sp(n); for(int i = 0; i < n; i++){ sp[i] = i; } ranges::sort(sp, [&](int& a, int& b){return H[a] < H[b]; }); int cur = -1, cnt = 1; for(int& i: sp){ if(H[i] == cur) H[i] = cnt; else{ cur = H[i]; cnt++; H[i] = cnt; } } int mx = cnt * 4 + 1; vector<int> tree(mx + 1, INT_MAX); vector<int> order(m), res(m, -1); // Q[i][1] order for(int i = 0; i < m; i++){ if(Q[i][0] > Q[i][1]) swap(Q[i][0], Q[i][1]); order[i] = i; } ranges::sort(order, [&](int& a, int& b){ return Q[a][1] < Q[b][1]; }); for(int i = n-1, oi = m-1; i >= 0, oi >= 0; i--){ // H: i, order: oi //cout << i << ": \n"; while(oi >= 0 and Q[ order[oi] ][1] >= i){ //cout << oi << " " << Q[ order[oi] ][1] << " "; int &ai = Q[ order[oi] ][0], &bi = Q[ order[oi] ][1]; if(ai == bi or H[ai] < H[bi] ){ res[order[oi]] = bi; //cout << "no q: " << bi << '\n'; } else{ int q = query(tree, 1, H[ai], 0, cnt); if(q != INT_MAX) res[order[oi]] = q; //cout << "q: " << q << '\n'; } oi--; } update(tree, 1, H[i], i, 0, cnt); } return res; } void update(vector<int>& tree, int pos, int& val, int& idx, int tl, int tr){ // root pos = 1 if(val < tl || tr < val) return; if(val == tl ){ tree[pos] = idx; } else{ int mid = (tl + tr) / 2; update(tree, pos*2, val, idx, tl, mid); update(tree, pos*2 +1, val, idx, mid+1, tr); tree[pos] = min(tree[pos*2], tree[pos*2 +1]); } } int query(vector<int>& tree, int pos, int& val, int tl, int tr){ // (val, inf] if(tree[pos] == INT_MAX or tr <= val) return INT_MAX; int idx = INT_MAX; if(val < tl){ idx = min(idx, tree[pos]); } else{ int mid = (tl + tr) / 2; idx = min(idx, query(tree, pos*2, val, tl, mid)); idx = min(idx, query(tree, pos*2 +1, val, mid+1, tr)); } return idx; } }; ※ 引述《sixB (6B)》之銘言： : 2940. : 昨天寫不出來 : 今天邊寫邊吐 : 想這個樹怎麼建想好久 : 寶可夢直接+20勝== : 動態開點MLE : 看hint不知道怎麼用BIT建 : 改smart pointer還是MLE : 最後改成先離散化再開點才過的 : 要離散化的話 : 應該不要動態開點更快ㄅ : 但是我腿了：（ : class Solution { : public: : // segment tree : class Node{ : public: : int idx; : Node *l, *r; : Node(){ : idx = INT_MAX; : l = nullptr; : r = nullptr; : }; : Node(int i){ : idx = i; : l = nullptr; : r = nullptr; : }; : }; : class Segment_tree{ : public: : Node* root; : int idx; : Segment_tree(){ : root = new Node(); : idx = INT_MAX; : } : Segment_tree(int i){ : root = new Node(i); : idx = i; : } : void update(Node* nd, int& val, int& idx, int tl = 0, int tr = 1e9){ : if(val < tl || tr < val) return; : if(val == tl ){ : nd->idx = idx; : } : else{ : int mid = (tl + tr) / 2; : if(nd->l == nullptr){ : nd->l = new Node(); : } : if(nd->r == nullptr){ : nd->r = new Node(); : } : update(nd->l, val, idx, tl, mid); : update(nd->r, val, idx, mid+1, tr); : nd->idx = min(nd->l->idx, nd->r->idx); : } : } : int query(Node* nd, int& val, int tl = 0, int tr = 1e9){ : // (val, inf] : if(nd == nullptr or tr <= val) return INT_MAX; : int idx = INT_MAX; : if(val < tl){ : idx = min(idx, nd->idx); : } : else{ : int mid = (tl + tr) / 2; : idx = min(idx, query(nd->l, val, tl, mid)); : idx = min(idx, query(nd->r, val, mid+1, tr)); : } : return idx; : } : }; : vector<int> leftmostBuildingQueries(vector<int>& H, vector<vector<int>>& Q : ) { : // range: val [1, 1e9] : // get min idx : Segment_tree tree; : int n = H.size(), m = Q.size(); : // seperate H : vector<int> sp(n); : for(int i = 0; i < n; i++){ : sp[i] = i; : } : ranges::sort(sp, [&](int& a, int& b){return H[a] < H[b]; }); : int cur = -1, cnt = 0; : for(int& i: sp){ : if(H[i] == cur) H[i] = cnt; : else{ : cur = H[i]; : cnt++; : H[i] = cnt; : } : } : int mx = cnt * 4; : vector<int> order(m), res(m, -1); : // Q[i][1] order : for(int i = 0; i < m; i++){ : if(Q[i][0] > Q[i][1]) swap(Q[i][0], Q[i][1]); : order[i] = i; : } : ranges::sort(order, [&](int& a, int& b){ return Q[a][1] < Q[b][1]; }); : for(int i = n-1, oi = m-1; i >= 0, oi >= 0; i--){ : // H: i, order: oi : //cout << i << ": \n"; : while(oi >= 0 and Q[ order[oi] ][1] >= i){ : //cout << oi << " " << Q[ order[oi] ][1] << " "; : int &ai = Q[ order[oi] ][0], &bi = Q[ order[oi] ][1]; : if(ai == bi or H[ai] < H[bi] ){ : res[order[oi]] = bi; : //cout << "no q: " << bi << '\n'; : } : else{ : int q = tree.query(tree.root, H[ai], 0, mx); : if(q != INT_MAX) res[order[oi]] = q; : //cout << "q: " << q << '\n'; : } : oi--; : } : tree.update(tree.root, H[i], i, 0, mx); : } : return res; : } : }; : ※ 引述《dont (dont)》之銘言： : : 2940. Find Building Where Alice and Bob Can Meet : : ## 思路 : ----- : Sent from JPTT on my iPad ----- Sent from JPTT on my iPad -- 很姆的咪姆之咪 http://i.imgur.com/5sw7QOj.jpg