leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0135.cpp (1492B)

0 // original solution - accepted 1 class Solution { 2 public: 3 int candy(vector<int> &ratings) { 4 // place holder rating for easy neighbor calculation 5 ratings.insert(ratings.begin(), -1), ratings.push_back(-1); 6 int n = ratings.size(); 7 8 // sort by rating remembering the original index 9 vector<pair<int, int>> vec; 10 vec.reserve(n); 11 for (int i = 1; i < n - 1; i++) 12 vec.push_back({ratings[i], i}); 13 sort(vec.begin(), vec.end()); 14 15 vector<int> res(n, 1); // 'Each child must have at least one candy' 16 res.front() = res.back() = 0; // except placeholders 17 for (auto &[rating, index] : vec) { 18 if (rating < ratings[index + 1]) res[index + 1] = max(res[index + 1], res[index] + 1); 19 20 if (rating < ratings[index - 1]) res[index - 1] = max(res[index - 1], res[index] + 1); 21 } 22 23 return accumulate(res.begin(), res.end(), 0); 24 } 25 }; 26 27 // improved solution - same logic no nonsense 28 class Solution { 29 public: 30 int candy(vector<int> &ratings) { 31 int n = ratings.size(); 32 if (n <= 1) return n; 33 34 vector<int> res(n, 1); 35 for (int i = 0; i < n - 1; i++) { 36 if (ratings[i] < ratings[i + 1]) res[i + 1] = res[i] + 1; 37 } 38 39 for (int i = n - 1; i > 0; i--) { 40 if (ratings[i] < ratings[i - 1]) res[i - 1] = max(res[i - 1], res[i] + 1); 41 } 42 43 return accumulate(res.begin(), res.end(), 0); 44 } 45 };