4 problems solved.

lintcoder · lintcoder · commit e6f47f74c838 · 2020-02-03T18:43:32.000+08:00
diff --git a/src/1047.cpp b/src/1047.cpp
@@ -0,0 +1,28 @@
+string removeDuplicates(string S) {
+        int len = S.size();
+        if (len == 1)
+            return S;
+        string res;
+        stack<char> stk;
+        for (int i = 0; i < len; ++i)
+        {
+            if (stk.empty())
+                stk.push(S[i]);
+            else
+            {
+                if (stk.top() == S[i])
+                    stk.pop();
+                else
+                    stk.push(S[i]);
+            }
+        }
+        
+        while (!stk.empty())
+        {
+            res.push_back(stk.top());
+            stk.pop();
+        }
+        
+        reverse(res.begin(), res.end());
+        return res;
+    }
diff --git a/src/1341.cpp b/src/1341.cpp
@@ -0,0 +1,30 @@
+vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
+        int row = mat.size();
+        if (row == 1)
+            return {0};
+        int col = mat[0].size();
+        
+        struct Elem
+        {
+            int num;
+            int index;
+            Elem(int n = 0, int id = -1):num(n),index(id){}
+        };
+        auto cmp = [](const Elem& a, const Elem& b){
+            return a.num < b.num || (a.num == b.num && a.index < b.index);
+        };
+        
+        vector<Elem> vec(row, Elem());
+        for (int i = 0; i < row; ++i)
+        {
+            vec[i].num = mat[i].rend() - upper_bound(mat[i].rbegin(), mat[i].rend(), 0);
+            vec[i].index = i;
+        }
+        
+        sort(vec.begin(), vec.end(), cmp);
+        vector<int> res(k, -1);
+        for (int i = 0; i < k; ++i)
+            res[i] = vec[i].index;
+        
+        return res;
+    }
diff --git a/src/145.cpp b/src/145.cpp
@@ -0,0 +1,61 @@
+vector<int> postorderTraversal(TreeNode* root) {
+        vector<int> res;
+        if (root == nullptr)
+        	 return res;
+
+        deque<TreeNode*> dq;
+        deque<int> flag;
+
+        dq.push_back(root);
+        flag.push_back(0);
+
+        while (!dq.empty())
+        {
+            TreeNode* node = dq.back();
+            int status = flag.back();
+            if (status == 0)
+            {
+                if (node->left != nullptr)
+                {
+                    flag.back() = 1;
+                    dq.push_back(node->left);
+                    flag.push_back(0);
+                }
+                else if (node->right != nullptr)
+                {
+                    flag.back() = 2;
+                    dq.push_back(node->right);
+                    flag.push_back(0);
+                }
+                else
+                {
+                    res.push_back(node->val);
+                    dq.pop_back();
+                    flag.pop_back();
+                }
+            }
+            else if (status == 1)
+            {
+                if (node->right != nullptr)
+                {
+                    flag.back() = 2;
+                    dq.push_back(node->right);
+                    flag.push_back(0);
+                }
+                else
+                {
+                    res.push_back(node->val);
+                    dq.pop_back();
+                    flag.pop_back();
+                }
+            }
+            else
+            {
+                res.push_back(node->val);
+                dq.pop_back();
+                flag.pop_back();
+            }
+        }
+        
+        return res;
+    }
diff --git a/src/199.cpp b/src/199.cpp
@@ -1,3 +1,25 @@
 vector<int> rightSideView(TreeNode* root) {
+        if (root == nullptr)
+            return {};
+        deque<TreeNode*> dq;
+        dq.push_back(root);
+        int len = 1;
         
+        vector<int> res;
+        while (len > 0)
+        {
+            for (int i = 0; i < len; ++i)
+            {
+                TreeNode* node = dq[i];
+                if (node->left != nullptr)
+                    dq.push_back(node->left);
+                if (node->right != nullptr)
+                    dq.push_back(node->right);
+            }
+            res.push_back(dq[len-1]->val);
+            dq.erase(dq.begin(), dq.begin()+len);
+            len = dq.size();
+        }
+        
+        return res;
     }
