4 problems solved.

lintcoder · lintcoder · commit d455edbb653d · 2020-04-25T17:49:06.000+08:00
diff --git a/src/1110.cpp b/src/1110.cpp
@@ -0,0 +1,79 @@
+vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
+        vector<TreeNode*> vec;
+        struct Elem
+        {
+            TreeNode* node;
+            bool status;
+            Elem(TreeNode* tn = nullptr, bool flag = false):node(tn), status(flag){}
+        };
+        
+        deque<Elem> dq;
+        dq.push_back(Elem(root, true));
+        
+        int index = 0, len = 1;
+        bool flag = true;
+        while (flag)
+        {
+            flag = false;
+            int lim = len;
+            for (int i = index; i < lim; ++i)
+            {
+                TreeNode* tmp = dq[i].node;
+                if (tmp->left != nullptr)
+                {
+                    flag = true;
+                    dq.push_back(Elem(tmp->left, true));
+                    len++;
+                }
+                if (tmp->right != nullptr)
+                {
+                    flag = true;
+                    dq.push_back(Elem(tmp->right, true));
+                    len++;
+                }
+            }
+            index = lim;
+        }
+        
+        int len1 = dq.size();
+        int len2 = to_delete.size();
+        map<TreeNode*, TreeNode*> mp;
+        mp.insert(make_pair(root, nullptr));
+        for (int i = 0; i < len1; ++i)
+        {
+            TreeNode* node = dq[i].node;
+            if (node->left != nullptr)
+                mp[node->left] = node;
+            if (node->right != nullptr)
+                mp[node->right] = node;
+        }
+        
+        for (int i = 0; i < len2; ++i)
+        {
+            for (int j = 0; j < len1; ++j)
+            {
+                if (dq[j].node->val == to_delete[i])
+                {
+                    dq[j].status = false;
+                    if (dq[j].node->left != nullptr)
+                        mp[dq[j].node->left] = nullptr;
+                    if (dq[j].node->right != nullptr)
+                        mp[dq[j].node->right] = nullptr;
+                }
+                else if (dq[j].node->left != nullptr && dq[j].node->left->val == to_delete[i])
+                    dq[j].node->left = nullptr;
+                else if (dq[j].node->right != nullptr && dq[j].node->right->val == to_delete[i])
+                    dq[j].node->right = nullptr;
+            }
+        }
+        
+        for (int i = 0; i < len1; ++i)
+        {
+            if (dq[i].status && mp[dq[i].node] == nullptr)
+            {
+                vec.push_back(dq[i].node);
+            }
+        }
+        
+        return vec;
+    }
diff --git a/src/1325.cpp b/src/1325.cpp
@@ -0,0 +1,51 @@
+TreeNode* removeLeafNodes(TreeNode* root, int target) {
+        if (root == nullptr)
+            return nullptr;
+        
+        vector<stack<TreeNode*>> vec;
+        stack<TreeNode*> stk;
+        
+        search(root, target, stk, vec);
+        int len = vec.size();
+        for (int i = 0; i < len; ++i)
+        {
+            TreeNode* node = vec[i].top();
+            vec[i].pop();
+            while (!vec[i].empty())
+            {
+                TreeNode* par = vec[i].top();
+                if (par->left == node)
+                    par->left = nullptr;
+                else
+                    par->right = nullptr;
+                delete node;
+                if (par->val == target && par->left == nullptr && par->right == nullptr)
+                {
+                    node = par;
+                    vec[i].pop();
+                }
+                else
+                    break;
+            }
+            if (vec[i].empty())
+                return nullptr;
+        }
+        
+        return root;
+    }
+    
+    void search(TreeNode* node, int target, stack<TreeNode*> stk, vector<stack<TreeNode*>>& vec)
+    {
+        stk.push(node);
+        if (node->val == target && node->left == nullptr && node->right == nullptr)
+        {
+            vec.push_back(stk);
+        }
+        else
+        {
+            if (node->left != nullptr)
+                search(node->left, target, stk, vec);
+            if (node->right != nullptr)
+                search(node->right, target, stk, vec);
+        }
+    }
diff --git a/src/1338.cpp b/src/1338.cpp
@@ -0,0 +1,29 @@
+int minSetSize(vector<int>& arr) {
+        int len = arr.size();
+        if (len == 2)
+            return 1;
+        
+        map<int, int> mp;
+        for (int i = 0; i < len; ++i)
+        {
+            mp[arr[i]]++;
+        }
+        
+        int sz = mp.size();
+        vector<int> vec(sz);
+        int i = 0;
+        for (auto iter = mp.begin(); iter != mp.end(); ++iter)
+            vec[i++] = iter->second;
+        sort(vec.begin(), vec.end());
+        int sum = 0;
+        int ct = 0;
+        for (i = sz-1; i >= 0; --i)
+        {
+            sum += vec[i];
+            ++ct;
+            if (sum >= len/2)
+                break;
+        }
+        
+        return ct;
+    }
diff --git a/src/1409.cpp b/src/1409.cpp
@@ -0,0 +1,25 @@
+vector<int> processQueries(vector<int>& queries, int m) {
+        vector<int> arr(m);
+        for (int i = 0; i < m; ++i)
+            arr[i] = i+1;
+        
+        int len = queries.size();
+        vector<int> res(len);
+        for (int i = 0; i < len; ++i)
+        {
+            int j;
+            for (j = m-1; j >= 0; --j)
+            {
+                if (arr[j] == queries[i])
+                {
+                    res[i] = j;
+                    break;
+                }
+            }
+            for (; j >= 1; --j)
+                arr[j] = arr[j-1];
+            arr[0] = queries[i];
+        }
+        
+        return res;
+    }
