5 problems solved.

lintcoder · lintcoder · commit 3fffff6f4bf6 · 2020-02-16T17:00:03.000+08:00
diff --git a/src/1103.cpp b/src/1103.cpp
@@ -0,0 +1,33 @@
+vector<int> distributeCandies(int candies, int num_people) {
+        int turn = 1;
+        while (true)
+        {
+            int t = (1+num_people*turn)*num_people*turn/2;
+            if (t >= candies)
+                break;
+            ++turn;
+        }
+        
+        vector<int> res(num_people, 0);
+        for (int i = 1; i <= num_people; ++i)
+            res[i-1] = i*(turn-1) + (turn-1)*(turn-2)*num_people/2;
+        int i = 0;
+        candies -= (1+(turn-1)*num_people)*(turn-1)*num_people/2;
+        while (candies > 0 && i < num_people)
+        {
+            int n = i+1+(turn-1)*num_people;
+            if (n <= candies)
+            {
+                res[i] += n;
+                candies -= n;
+            }
+            else
+            {
+                res[i] += candies;
+                break;
+            }
+            ++i;
+        }
+        
+        return res;
+    }
diff --git a/src/1137.cpp b/src/1137.cpp
@@ -0,0 +1,15 @@
+int tribonacci(int n) {
+        int arr[3] = {0,1,1};
+        if (n <= 2)
+            return arr[n];
+        
+        for (int i = 3; i <= n; ++i)
+        {
+            int t = arr[0] + arr[1] + arr[2];
+            arr[0] = arr[1];
+            arr[1] = arr[2];
+            arr[2] = t;
+        }
+        
+        return arr[2];
+    }
diff --git a/src/1170.cpp b/src/1170.cpp
@@ -0,0 +1,40 @@
+vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
+        int len = queries.size();
+        int sz = words.size();
+        
+        vector<int> res(len, 0);
+        vector<int> freq(sz, 0);
+        for (int i = 0; i < sz; ++i)
+            freq[i] = calFreq(words[i]);
+        sort(freq.begin(), freq.end());
+        
+        for (int i = 0; i < len; ++i)
+        {
+            int t = calFreq(queries[i]);
+            auto iter = upper_bound(freq.begin(), freq.end(), t);
+            res[i] = freq.end() - iter;
+        }
+        
+        return res;
+    }
+    
+    int calFreq(const string& str)
+    {
+        int len = str.size();
+        int ct = 1;
+        char minval = str[0];
+        for (int i = 1; i < len; ++i)
+        {
+            if (str[i] < minval)
+            {
+                minval = str[i];
+                ct = 1;
+            }
+            else if (str[i] == minval)
+            {
+                ++ct;
+            }
+        }
+        
+        return ct;
+    }
diff --git a/src/1189.cpp b/src/1189.cpp
@@ -0,0 +1,36 @@
+int maxNumberOfBalloons(string text) {
+        int len = text.size();
+        if (len <= 5)
+            return 0;
+        
+        int arr[5] = {0};
+        for (int i = 0; i < len; ++i)
+        {
+            switch(text[i])
+            {
+                case 'a':
+                    arr[0]++;
+                    break;
+                case 'b':
+                    arr[1]++;
+                    break;
+                case 'l':
+                    arr[4]++;
+                    break;
+                case 'n':
+                    arr[2]++;
+                    break;
+                case 'o':
+                    arr[3]++;
+                    break;
+            }
+        }
+        
+        arr[3] /= 2;
+        arr[4] /= 2;
+        int minnum = arr[0];
+        for (int i = 1; i < 5; ++i)
+            if (arr[i] < minnum)
+                minnum = arr[i];
+        return minnum;
+    }
diff --git a/src/559.cpp b/src/559.cpp
@@ -0,0 +1,26 @@
+int maxDepth(Node* root) {
+        if (root == nullptr)
+            return 0;
+        int maxdepth = 0;
+        maxdepth = search(root);
+        
+        return maxdepth+1;
+    }
+    
+    int search(Node* node)
+    {
+        auto& vec = node->children;
+        int len = vec.size();
+        if (len == 0)
+            return 0;
+        
+        int maxd = 0;
+        for (int i = 0; i < len; ++i)
+        {
+            int t = search(vec[i]);
+            if (t > maxd)
+                maxd = t;
+        }
+        
+        return maxd+1;
+    }
