0產出的一天 明天meeting gg
題目: 3043. Find the Length of the Longest Common Prefix
給你兩個int vector: arr1, arr2求出arr1中的整數在arr2中整數最長的prefix len
思路:
先用arr2中的數字做trie，然後拿arr1中的整數一個個下去掃prefix len每次確定需不
需要更新最大值，利用轉成字串再一個個digit下去做overall複雜度是arr1和arr2中的
digit數總和，排名前面的做法雖然複雜度一樣但是幾乎都是直接用整數的乘除操作完成
感覺直接用整數operator下去做會比轉成字串這個行為快?
class trie{
public:
vector<trie*> t;
trie(){
t=vector<trie*>(10,nullptr);
}
};
class Solution {
public:
int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {
trie* pre_ans= new trie();
int ans=0;
for(auto k:arr2){
trie* temp=pre_ans;
string s=to_string(k);
for(auto j:s){
if(!temp->t[j-'0']){
temp->t[j-'0']=new trie();
}
temp=temp->t[j-'0'];
}
}
for(auto k:arr1){
string s=to_string(k);
trie* temp=pre_ans;
int cur=0;
for(auto g:s){
if(!temp->t[g-'0']){
break;
}
else{
cur++;
temp=temp->t[g-'0'];
}
}
ans=max(cur,ans);
}
return ans;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.227.252.3 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1727194624.A.160.html