5 problems solved.

lintcoder · lintcoder · commit f9c7b9de17e8 · 2020-03-22T01:30:14.000+08:00
diff --git a/src/1008.cpp b/src/1008.cpp
@@ -0,0 +1,31 @@
+TreeNode* bstFromPreorder(vector<int>& preorder) {
+        int len = preorder.size();
+        if (len == 0)
+            return nullptr;
+        if (len == 1)
+            return new TreeNode(preorder[0]);
+        
+        return search(preorder, 0, len-1);
+    }
+    
+    TreeNode* search(vector<int>& vec, int p, int q)
+    {
+        if (p > q)
+            return nullptr;
+        if (p == q)
+            return new TreeNode(vec[p]);
+        TreeNode* node = new TreeNode(vec[p]);
+        int i = 0;
+        for (i = p+1; i <= q; ++i)
+        {
+            if (vec[i] > vec[p])
+                break;
+        }
+        
+        if (vec[p+1] < vec[p])
+            node->left = search(vec, p+1, i-1);
+        if (i <= q)
+            node->right = search(vec, i, q);
+        
+        return node;
+    }
diff --git a/src/1380.cpp b/src/1380.cpp
@@ -0,0 +1,35 @@
+vector<int> luckyNumbers (vector<vector<int>>& matrix) {
+        int row = matrix.size();
+        int col = matrix[0].size();
+        
+        vector<int> res;
+        for (int i = 0; i < row; ++i)
+        {
+            int minval = matrix[i][0];
+            int index = 0;
+            int j = 0;
+            for (j = 1; j < col; ++j)
+            {
+                if (matrix[i][j] < minval)
+                {
+                    index = j;
+                    minval = matrix[i][j];
+                }
+            }
+            
+            bool flag = true;
+            for (j = 0; j < row; ++j)
+            {
+                if (matrix[j][index] > minval)
+                {
+                    flag = false;
+                    break;
+                }
+            }
+            
+            if (flag)
+                res.push_back(minval);
+        }
+        
+        return res;
+    }
diff --git a/src/501.cpp b/src/501.cpp
@@ -0,0 +1,37 @@
+vector<int> findMode(TreeNode* root) {
+        if (root == nullptr)
+            return {};
+        if (root->left == nullptr && root->right == nullptr)
+            return {root->val};
+        
+        map<int, int> mp;
+        mp[root->val] = 1;
+        if (root->left != nullptr)
+            search(root->left, mp);
+        if (root->right != nullptr)
+            search(root->right, mp);
+        int m = 0;
+        for (auto iter = mp.begin(); iter != mp.end(); ++iter)
+        {
+            if (iter->second > m)
+                m = iter->second;
+        }
+        
+        vector<int> res;
+        for (auto iter = mp.begin(); iter != mp.end(); ++iter)
+        {
+            if (iter->second == m)
+                res.push_back(iter->first);
+        }
+        
+        return res;
+    }
+    
+    void search(TreeNode* node, map<int, int>& mp)
+    {
+        mp[node->val]++;
+        if (node->left != nullptr)
+            search(node->left, mp);
+        if (node->right != nullptr)
+            search(node->right, mp);        
+    }
diff --git a/src/680.cpp b/src/680.cpp
@@ -0,0 +1,38 @@
+bool validPalindrome(string s) {
+        int len = s.size();
+        if (len <= 2)
+            return true;
+        
+        return search(s, 0, len-1, false);
+    }
+    
+    bool search(const string& s, int p, int q, bool flag)
+    {
+        if (p >= q)
+            return true;
+        if (flag)
+        {
+            while (p < q)
+            {
+                if (s[p] != s[q])
+                    return false;
+                else
+                {
+                    ++p;
+                    --q;
+                }
+            }
+            
+            return true;
+        }
+        else
+        {
+            if (s[p] == s[q])
+            {
+                return search(s, p+1, q-1, false) || search(s, p+1, q, true)
+                    || search(s, p, q-1, true);
+            }
+            else
+                return search(s, p+1, q, true) || search(s, p, q-1, true);
+        }
+    }
diff --git a/src/868.cpp b/src/868.cpp
@@ -0,0 +1,34 @@
+int binaryGap(int N) {
+        int index[2] = {-1,-1};
+        int ct = 0;
+        int i = 0, maxdist = 0;
+        while (N != 0)
+        {
+            if (N%2 == 1)
+            {
+                if (ct < 2)
+                {
+                    index[ct++] = i;
+                }
+                else
+                {
+                    int t = index[1] - index[0];
+                    if (t > maxdist)
+                        maxdist = t;
+                    index[0] = index[1];
+                    index[1] = i;
+                }
+            }
+            N /= 2;
+            ++i;
+        }
+        if (ct < 2)
+            return 0;
+        else
+        {
+            int t = index[1] - index[0];
+            if (t > maxdist)
+                maxdist = t;
+            return maxdist;
+        }
+    }
