Verilmiş Təchizat LeetCode Həllindən Bütün Mümkün Reseptləri tapın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur googleBaxılıb 31

Problem bəyanat

Verilmiş Təchizatlardan Bütün Mümkün Reseptləri Tapın LeetCode Həll adlı bu problemdə bizdən sətirlərin vektoru kimi verilən təchizatlardan istifadə etməklə hazırlana biləcək reseptləri tapmaq tələb olunur. Bizə həmçinin hazırlamaq üçün lazım olan reseptlər və onlara lazım olan müvafiq maddələr verilir.

Verilmiş Təchizatlardan Bütün Mümkün Reseptləri Tapmaq üçün Nümunələr və İzahat LeetCode Həll

Misal 1:

Input: recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast","flour","corn"]
Output: ["bread"]
Explanation:
We can create "bread" since we have the ingredients "yeast" and "flour".

Misal 2:
Input: recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]], supplies = ["yeast","flour","meat"]
Output: ["bread","sandwich"]
Explanation:
We can create "bread" since we have the ingredients "yeast" and "flour".
We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread".

Misal 3:
Input: recipes = ["bread","sandwich","burger"], ingredients = [["yeast","flour"],["bread","meat"],["sandwich","meat","bread"]], supplies = ["yeast","flour","meat"]
Output: ["bread","sandwich","burger"]
Explanation:
We can create "bread" since we have the ingredients "yeast" and "flour".
We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread".
We can create "burger" since we have the ingredient "meat" and can create the ingredients "bread" and "sandwich".

Yanaşma

Bu problem çox oxşardır leetcode-da kurs planlaşdırma problemi. Bu həll, onların müvafiq reseptlərinə yönəldilmiş inqrediyentlərin qrafikində topoSort üçün Kahn alqoritmindən istifadə edir, yəni resept üçün tələb olunan bütün inqrediyentlər həmin reseptə yönəldiləcəkdir. Qrafik qurulduqdan sonra asanlıqla edə bilərik sətirləri çap edin topoSort istifadə edin və inqrediyentlər istisna olmaqla topoSort-u qaytarın.

Aşağıdakı şəkil təsvir edir nümunə 3 qovşaqların dərəcələri ilə birlikdə qrafik

 

Verilmiş Təchizat LeetCode Həllindən Bütün Mümkün Reseptləri tapınPin

Şərhlər

  • bütün təchizatların 0 kimi dərəcəsi olacaq
  • resept[i] hazırlandıqdan sonra biz onu tədarük kimi qəbul edirik və beləliklə resepti[i] növbəyə itələyirik.
  • Hansı reseptləri hazırlamalı olduğumuzu yoxlamaq üçün xəritəni saxlayın və reseptləri yalnız inqrediyentlər kimi deyil, cavab olaraq saxlayın

Kodu

Verilmiş Təchizatlardan Bütün Mümkün Reseptləri Tapmaq üçün C++ proqramı

class Solution {
    map<string, vector<string>> adj;
    map<string, int> indegree;
    map<string, int> recipesAvl;
    vector<string> res;
public:
    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
        int n = recipes.size();
        for(int i=0; i<n; i++) {
            for(int j=0; j<ingredients[i].size(); j++) {
                adj[ingredients[i][j]].push_back(recipes[i]);
                indegree[recipes[i]]++;
                recipesAvl[recipes[i]]=1;
            }
        }
        // to print the graph
        // for(auto it:adj) {
        //     cout<<it.first<<"--->";
        //     for(auto itr:it.second) cout<<"->"<<itr;
        //     cout<<"\n";
        // }
        
        queue<string> q;
        for(string s: supplies) q.push(s);
        
        while(!q.empty()) {
            string u = q.front();
            q.pop();
            // cout<<u<<" ";
            if(recipesAvl[u]) {
                res.push_back(u);
            }
            for(string v: adj[u]) {
                if(--indegree[v]==0) {
                    q.push(v);
                }
            }
        }
        
        
        // cout<<"\n";
        return res;
    }
};

Java proqramı üçün Verilmiş Təchizatlardan Bütün Mümkün Reseptləri Tapın

class Solution {
    public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
        Map<String, ArrayList<String>> adj = new HashMap();
        Map<String, Integer> indegree = new HashMap();
        Map<String, Integer> recipesAvl = new HashMap();
        ArrayList<String> res = new ArrayList();
        
        int n = recipes.length;
        for(int i=0; i<n; i++) {
            for(int j=0; j<ingredients.get(i).size(); j++) {
                String elem = ingredients.get(i).get(j);
                if(!adj.containsKey(elem)) {
                    adj.put(elem, new ArrayList<String>());
                }
                
                adj.get(elem).add(recipes[i]);
                indegree.put(recipes[i],  indegree.getOrDefault(recipes[i], 0) + 1);
                recipesAvl.put(recipes[i], 1);
            }
        }
        Queue<String> q = new LinkedList();
        for(String s: supplies) q.add(s);
        
        while(!q.isEmpty()) {
            String u = q.peek();
            q.remove();
            if(recipesAvl.containsKey(u)) {
                res.add(u);
            }
            for(String v: adj.getOrDefault(u, new ArrayList<String>())) {
                indegree.put(v, indegree.get(v)-1);
                if(indegree.get(v)==0) {
                    q.add(v);
                }
            }
        }
        
        return res;
        
    }
}

 

Verilmiş Təchizatlardan Bütün Mümkün Reseptləri Tapmaq üçün Mürəkkəblik Təhlili LeetCode Həll

Qrafikdə V = təpələrin sayı və E = kənarların sayı adj olsun

  • Zamanın mürəkkəbliyi: O(V+E). Xarici for döngəsi V dəfə, daxili for döngəsi isə E dəfə yerinə yetiriləcək.
  • Köməkçi məkan: O(V). Növbə və xəritələr qrafikin bütün təpələrini saxlamalıdır. Beləliklə, tələb olunan boşluq O(V)-dir.
Translate »