Re: [閒聊] 每日leetcode
※ 引述《sixB (6B)》之銘言：
: 標題: Re: [閒聊] 每日leetcode
: 時間: Tue Sep 24 09:04:47 2024
:
: 3043.
:
: longest common prefix
剛剛寫完了
第一次是直接比較
發現TLE了
class Solution {
public:
int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {
int longest_prefix = INT_MIN;
cout << arr1.size() << "\n";
set(arr1.begin(), arr1.end());
set(arr2.begin(), arr2.end());
cout << arr1.size() << "\n";
for(int i : arr1){
for(int j : arr2){
int tmp_l = compare_prefix(i, j);
if(tmp_l > longest_prefix){
longest_prefix = tmp_l;
}
}
}
return longest_prefix;
}
int compare_prefix(int a, int b){
string a_s = to_string(a);
string b_s = to_string(b);
int longest_prefix = 0;
for(int i = 0 ; i < a_s.size() ; i++){
if(a_s[i] != b_s[i]){
break;
}
longest_prefix ++;
}
return longest_prefix;
}
};
因為不會用Trie就去看了一下可以用Hash
用了就過了
我先用Hash存arr1的全部prefix
跟我上面的寫法時間複雜度有差這麼多喔
原本以為差不多
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.248.91.73 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1727158663.A.3E2.html
推
09/24 14:17,
1年前
, 1F
09/24 14:17, 1F
→
09/24 14:23,
1年前
, 2F
09/24 14:23, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 900 之 1554 篇)：