Sunday, April 19, 2020

LeetCode.1419 Minimum Number of Frogs Croaking

1.Problem
https://leetcode.com/problems/minimum-number-of-frogs-croaking/

2.Idea
Counting chars while making sure order and number are correct.

3.Souce
 bool cmp(string a, string b)  
 {  
      return std::stoi(a) < std::stoi(b);  
 }  
 class Solution {  
 public:  
      vector<vector<string>> displayTable(vector<vector<string>>& orders) {  
           int N = orders.size();  
           map< pair<string, string>, int> ords;  
           vector<string> tables, items;  
           for (int i = 0; i < N; i++) {  
                string table = orders[i][1];  
                string item = orders[i][2];  
                ords[make_pair(table, item)]++;  
                tables.push_back(table);  
                items.push_back(item);  
           }  
           sort(tables.begin(), tables.end(), cmp);  
           std::vector<string>::iterator it;  
           it = std::unique(tables.begin(), tables.end());   
           tables.resize(std::distance(tables.begin(), it));  
           sort(items.begin(), items.end());  
           it = std::unique(items.begin(), items.end());  
           items.resize(std::distance(items.begin(), it));  
           int n = tables.size() + 1, m = items.size() + 1;  
           vector<vector<string>> ans(1);  
           ans[0].push_back("Table");  
           for (int i = 0; i < items.size(); i++) {  
                ans[0].push_back(items[i]);  
           }  
           for (int i = 0; i < tables.size(); i++) {  
                vector<string> tmp(m);  
                tmp[0] = tables[i];  
                ans.push_back(tmp);  
           }  
           for (int i = 1; i < n; i++) {  
                for (int j = 1; j < m; j++) {  
                     if (ords.find(make_pair(ans[i][0], ans[0][j])) == ords.end()) {  
                          ans[i][j] = "0";  
                     }  
                     else {  
                          ans[i][j] = std::to_string(ords[make_pair(ans[i][0], ans[0][j])]);  
                     }  
                }  
           }  
           return ans;  
      }  
 };  

No comments:

Post a Comment