Re: [閒聊] 每日leetcode已回收

看板Marginalman作者oin1104 (是oin的說)時間1年前 (2024/07/27 18:01)推噓1(2推 1噓 5→)

留言8則, 5人參與討論串575/1548 (看更多)

※ 引述《enmeitiryous (enmeitiryous)》之銘言： : 　 : 2976. minium cost to convert string 1 : 題目:給你兩個string source, target，目標是要將source convert to target : 並給你兩個array: original, changed其中original[i],changed[i]配對代表你 : 可以將char: original[i]變換成changed[i]並花費另一個array: cost[i]的花費 : ，回傳將source轉換成target所需的最小花費，如果無法轉換則回傳-1。 : 　 : 思路: 原本想說是不是用dp寫的可是想了想 dp的話必須搭配dfs或是其他東西才能在那些裡找到對的變化方式所以想了想發現字母只有26個所以建圖然後直接套著用比較快建圖的方式是對每個字做Dijkstra's 然後姆咪姆咪就好ㄌ幹你娘: 我剛剛解完覺得我無敵了跟鬼一樣就去看這題的第二題就是hard難度的這題好像就要用dp加上圖了看了看不會果斷放棄吃晚餐嘍 class Solution { public: long long minimumCost(string source, string target, vector<char>& original, vector<char>& changed, vector<int>& cost) { int len = original.size(); unordered_map<char, vector<pair<char,int>> > save; vector<vector<int>> paper(26,vector<int>(26,INT_MAX)); for(int i = 0 ; i < len ; i ++) { save[original[i]].push_back({changed[i],cost[i]}); } queue<char> find; for(int i = 0 ; i < 26 ; i ++) { paper[i][i] = 0; find.push(i+'a'); while(!find.empty()) { char nowfind = find.front(); for(auto k : save[nowfind]) { int jiwp = paper[i][nowfind-'a'] + k.second; if(jiwp < paper[i][k.first-'a']) { paper[i][k.first-'a'] = jiwp; find.push(k.first); } } find.pop(); } } long long res = 0; int slen = source.size(); for(int i = 0 ; i < slen ; i ++) { if(paper[source[i]-'a'][target[i]-'a'] == INT_MAX)return -1; res += paper[source[i]-'a'][target[i]-'a']; } return res; } }; -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.12.21.240 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722074505.A.AE0.html

→

digua

07/27 18:04, 1年前 , 1^F

07/27 18:04, 1^F

噓

dustsstar79

07/27 18:08, 1年前 , 2^F

07/27 18:08, 2^F

→

dustsstar79

07/27 18:08, 1年前 , 3^F

07/27 18:08, 3^F