[C++] Clean Code - 7 lines with Explanation


  • 0
    class Solution {
    public:
        vector<string> findRestaurant(vector<string>& l1, vector<string>& l2) {
            int noshow = l1.size() + l2.size();  // use sum of size as a punishment for missing in either list;
            map<string, int> punish;
            for (int i = 0; i < l1.size(); i++) punish[l1[i]] = i - noshow; // unpunish 1 * noshow for showing up at least in l1
            for (int j = 0; j < l2.size(); j++) punish[l2[j]] += j - noshow;// unpunish 1 * noshow for showing up at least in l2
            map<int, vector<string>> rank;
            for (auto p : punish) rank[p.second].push_back(p.first);
            return rank.begin()->second;
        }
    };
    

    The idea is to use sum of index in both list as score for every restaurant ever appeared, but need to manage punishment for not show up in either list.

    1. Use sum of size as a punishment for missing in either list : l1.size() + l2.size(), the punish need to be big enough to bigger than showing up at the end of both list;
    2. Create a map, for every restaurant appear in either list, initialize the score as 2 times punish;
    3. For every restaurant in every list, remove 1*punish for showing up in 1 list.
    4. On top of the punishment, don't forget to add indexs as score, the smaller the better.

    Intuitively

    class Solution {
    public:
        vector<string> findRestaurant(vector<string>& l1, vector<string>& l2) {
            int punish = l1.size() + l2.size(); // use sum of size as a punishment for missing in either list;
            map<string, int> m;
            for (int i = 0; i < l1.size(); i++) {
                m.emplace(l1[i], punish * 2);   // add 2 times punish by default
                m[l1[i]] += i - punish;         // reduce 1 punish for appearing in l1
            }
            for (int j = 0; j < l2.size(); j++) {
                m.emplace(l2[j], punish * 2);   // add 2 times punish by default
                m[l2[j]] += j - punish;         // reduce 1 punish for appearing in l2
            }
            
            map<int, vector<string>> rank; // use a sorted map rank the restaurants
            for (auto p : m) {
                rank[p.second].push_back(p.first);
            }
            return rank.begin()->second;
        }
    };
    

    Simplified
    In the above solution, we really wish we have a type with default value as 2*punishment in the map.

    • Unfortunately map[] operator will create an value default to 0;
    • Fortunately we don't really need to initialize the score as 2 times punishment;
    • The score can be negative, but still, the smaller the better:
    class Solution {
    public:
        vector<string> findRestaurant(vector<string>& l1, vector<string>& l2) {
            int punish = l1.size() + l2.size();  // use n as a punishment for missing in either list;
            map<string, int> m;
            for (int i = 0; i < l1.size(); i++) m[l1[i]] += i - punish;
            for (int j = 0; j < l2.size(); j++) m[l2[j]] += j - punish;
            map<int, vector<string>> rank;
            for (auto p : m) rank[p.second].push_back(p.first);
            return rank.begin()->second;
        }
    };
    

    Yet Another Solution

    class Solution {
    public:
        vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
            int n = list1.size() + list2.size();
            map<string, vector<int>> m;
            for (int i = 0; i < list1.size(); i++) {
                m[list1[i]] = {i, n};
            }
            for (int j = 0; j < list2.size(); j++) {
                if (m.count(list2[j])) {
                    m[list2[j]][1] = j;
                }
                else {
                    m[list2[j]] = {n, j};
                }
            }
    
            int minsum = INT_MAX;
            map<int, vector<string>> sumMap;
            for (auto p : m) {
                int sum = p.second[0] + p.second[1];
                sumMap[sum].push_back(p.first);
                minsum = min(minsum, sum);
            }
            
            return sumMap[minsum];
        }
    };
    

  • 0
    M

    @alexander Hey I'm new to STL,can you please explain me how does this work?
    rank[p.second].push_back(p.first);
    Sorry for the naïve question.Hope you'll help! :)


  • 1

    @mansipradhan rank is defined as: map<int, vector<string>> rank

            map<int, vector<string>> rank; // use a sorted map rank the restaurants
            for (auto p : m) {
                rank[p.second].push_back(p.first);
            }
    

    std::map::[key] is an overloaded operator act just the same as java.util.Map.get(key), retrieve the value for the given key.
    The [] will create an default value if the key is not found, in this case rank[p.second] will create an empty vector if p.second is not found as a key in the map rank.

    equals:

            map<int, vector<string>> rank; // use a sorted map rank the restaurants
            for (pair<string, int> p : m) {
                string restaurant = p.first;
                int punish = p.second;
                vector<string> restarauts = rank[punish];
                restarauts.push_back(restaurant);
            }
    

    Please refer to this for more information:
    http://www.cplusplus.com/reference/map/map/operator[]/


  • 0
    M

    @alexander Got it.
    Thanks :)


  • 0
    J
    This post is deleted!

  • 0
    C

    My C++ code, straightforward using find(), and I get 122ms. Not very fast, but easy to understand. :)

    class Solution {
    public:
    	vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
    		vector<string> result;
    		unordered_multimap<int, string> mp;
    		int min_sum = INT_MAX;
    		for (int i = 0; i < list1.size(); i++) {
    			if (find(list2.begin(), list2.end(), list1[i]) != list2.end()) {
    				int temp = find(list2.begin(), list2.end(), list1[i]) - list2.begin() + i;
    				if (temp <= min_sum) {
    					mp.insert(pair<int, string>(temp, list1[i]));
    					min_sum = temp;
    				}
    			}
    		}
    		unordered_multimap<int, string>::iterator it;
    		for (it = mp.begin(); it != mp.end(); it++) {
    			if (it->first == min_sum)
    				result.push_back((*it).second);
    		}
    		return result;
    	}
    };
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.