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

看板Marginalman作者sustainer123 (caster )時間1年前 (2024/07/27 19:07)推噓3(3推 0噓 5→)

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

※ 引述《oin1104 (是oin的說)》之銘言： : ※ 引述《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; : } : }; 思路: Floyd-Warshall 查了一下先做成i為起點j為終點的圖之後再加入中間點k計算這樣就能找出最短距離新的方法+1 還不錯等等寫昨天的然後這個有重複的超哭然後寫得滿醜的 Python Code: class Solution: def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int: graph = [[float("inf") if i != j else 0 for j in range(26)] for i in range(26)] for i in range(len(original)): graph[ord(original[i])-ord("a")][ord(changed[i])-ord("a")] = min(graph[ord(original[i])-ord("a")][ord(changed[i])-ord("a")], cost[i]) for k in range(26): for i in range(26): for j in range(26): graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]) result = 0 for i in range(len(source)): if graph[ord(source[i])-ord("a")][ord(target[i])-ord("a")] == float("inf"): return -1 result += graph[ord(source[i])-ord("a")][ord(target[i])-ord("a")] return result -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.194.160.111 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722078435.A.B28.html

推

JIWP

07/27 19:22, 1年前 , 1^F

07/27 19:22, 1^F

推

oin1104

07/27 19:28, 1年前 , 2^F

07/27 19:28, 2^F

→

sustainer123

07/27 19:29, 1年前 , 3^F

07/27 19:29, 3^F