→ sixB: 不對 完全沒必要 他又沒要找lca== 09/24 09:10
→ sixB: 感覺還是trie一下就好 09/24 09:10
3043.
longest common prefix
數字好多
懶得思考直接開trie==
感覺也可以直接用lca那套
還是等等用BIT試試
class Trie{
public:
vector<Trie*> num;
Trie(){
num = vector<Trie*>(10, nullptr);
}
};
class Solution {
public:
Trie* root = new Trie();
int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {
for(int& i: arr1){
Trie* t = root;
string s = to_string(i);
for(char& c: s){
int idx = c - '0';
if(t->num[idx] == nullptr)
t->num[idx] = new Trie();
t = t->num[idx];
}
}
int maxlen = 0;
for(int& i: arr2){
Trie* t = root;
string s = to_string(i);
int curlen = 0;
for(char& c: s){
int idx = c - '0';
if(t->num[idx] == nullptr) break;
curlen++;
t = t->num[idx];
}
maxlen = max(maxlen, curlen);
}
return maxlen;
}
};
-----
Sent from JPTT on my iPad
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.205.121.194 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1727139894.A.CDF.html