6 problems solved.

lintcoder · lintcoder · commit cd1d8e42daa9 · 2020-03-14T09:23:08.000+08:00
diff --git a/src/1161.cpp b/src/1161.cpp
@@ -0,0 +1,37 @@
+int maxLevelSum(TreeNode* root) {
+        if (root == nullptr)
+            return 1;
+        if (root->left == nullptr && root->right == nullptr)
+            return 1;
+        
+        deque<TreeNode*> dq;
+        dq.push_back(root);
+        int len = 1;
+        int maxval = root->val;
+        int level = 1;
+        int ct = 0;
+        while (len != 0)
+        {
+            ++ct;
+            int sum = 0;
+            for (int i = 0; i < len; ++i)
+            {
+                TreeNode* node = dq[i];
+                sum += node->val;
+                if (node->left != nullptr)
+                    dq.push_back(node->left);
+                if (node->right != nullptr)
+                    dq.push_back(node->right);
+            }
+            
+            if (sum > maxval)
+            {
+                maxval = sum;
+                level = ct;
+            }
+            dq.erase(dq.begin(), dq.begin()+len);
+            len = dq.size();
+        }
+        
+        return level;
+    }
diff --git a/src/1370.cpp b/src/1370.cpp
@@ -0,0 +1,35 @@
+string sortString(string s) {
+        int len = s.size();
+        if (len == 1)
+            return s;
+        
+        vector<int> num(26, 0);
+        for (int i = 0; i < len; ++i)
+            num[s[i]-'a']++;
+        int k = 0;
+        string res(len, ' ');
+        while (k < len)
+        {
+            for (int i = 0; i < 26; ++i)
+            {
+                if (num[i] > 0)
+                {
+                    res[k++] = 'a'+i;
+                    --num[i];
+                }
+            }
+            
+            if (k == len)
+                break;
+            for (int i = 25; i >= 0; --i)
+            {
+                if (num[i] > 0)
+                {
+                    res[k++]  = 'a'+i;
+                    --num[i];
+                }
+            }
+        }
+        
+        return res;
+    }
diff --git a/src/1374.cpp b/src/1374.cpp
@@ -0,0 +1,8 @@
+string generateTheString(int n) {
+        if (n == 1)
+            return "a";
+        else if (n%2 == 0)
+            return string(1, 'a') + string(n-1, 'b');
+        else
+            return string(n, 'a');
+    }
diff --git a/src/701.cpp b/src/701.cpp
@@ -0,0 +1,13 @@
+TreeNode* insertIntoBST(TreeNode* root, int val) {
+        if (root == nullptr)
+        {
+            TreeNode* node = new TreeNode(val);
+            return node;
+        }
+        else if (val < root->val)
+            root->left = insertIntoBST(root->left, val);
+        else
+            root->right = insertIntoBST(root->right, val);
+        
+        return root;
+    }
diff --git a/src/914.cpp b/src/914.cpp
@@ -0,0 +1,56 @@
+bool hasGroupsSizeX(vector<int>& deck) {
+        int len = deck.size();
+        if (len <= 1)
+            return false;
+        if (len == 2)
+            return deck[0] == deck[1];
+        
+        map<int,int> mp;
+        for (int i = 0; i < len; ++i)
+            mp[deck[i]]++;
+        
+        int sz = mp.size();
+        if (sz == 1)
+            return true;
+        auto iter = mp.begin();
+        int a = iter->second;
+        ++iter;
+        int b = iter->second;
+        ++iter;
+        int div = gcd(a, b);
+        if (div == 1)
+            return false;
+        for (; iter != mp.end(); ++iter)
+        {
+            div = gcd(iter->second, div);
+            if (div == 1)
+                return false;
+        }
+        
+        return true;
+    }
+    
+    int gcd(int a, int b)
+    {
+        if (a > b)
+        {
+            int t = a;
+            a = b;
+            b = t;
+        }
+        
+        while (a != 1)
+        {
+            b %= a;
+            if (b == 0)
+                break;
+            if (a > b)
+            {
+                int t = a;
+                a = b;
+                b = t;
+            }
+        }
+        
+        return a;
+    }
diff --git a/src/941.cpp b/src/941.cpp
@@ -0,0 +1,25 @@
+bool validMountainArray(vector<int>& A) {
+        int len = A.size();
+        if (len < 3)
+            return false;
+        
+        int i = 1;
+        for (i = 1; i < len; ++i)
+        {
+            if (A[i] == A[i-1])
+                return false;
+            if (A[i] < A[i-1])
+                break;
+        }
+        if (i == 1 || i == len)
+            return false;
+        if (i == len-1)
+            return true;
+        for (; i < len-1; ++i)
+        {
+            if (A[i] <= A[i+1])
+                return false;
+        }
+        
+        return true;
+    }
