11 problems solved.

lintcoder · lintcoder · commit ad2603744acb · 2020-04-19T01:31:31.000+08:00
diff --git a/src/1261.cpp b/src/1261.cpp
@@ -0,0 +1,46 @@
+class FindElements {
+public:
+    FindElements(TreeNode* root) {
+        head = root;
+        if (root != nullptr)
+        {
+            root->val = 0;
+            deque<TreeNode*> dq;
+            dq.push_back(root);
+            elem.push_back(0);
+            int len = 1;
+            
+            while(len != 0)
+            {
+                for (int i = 0; i < len; ++i)
+                {
+                    TreeNode* node = dq[i];
+                    if (node->left != nullptr)
+                    {
+                        node->left->val = 2*node->val + 1;
+                        elem.push_back(node->left->val);
+                        dq.push_back(node->left);
+                    }
+                    if (node->right != nullptr)
+                    {
+                        node->right->val = 2*node->val + 2;
+                        elem.push_back(node->right->val);
+                        dq.push_back(node->right);
+                    }
+                }
+                
+                dq.erase(dq.begin(), dq.begin()+len);
+                len = dq.size();
+            }
+            
+            sort(elem.begin(), elem.end());
+        }
+    }
+    
+    bool find(int target) {
+        return binary_search(elem.begin(), elem.end(), target);
+    }
+private:
+    TreeNode* head;
+    vector<int> elem;
+};
diff --git a/src/1314.cpp b/src/1314.cpp
@@ -0,0 +1,22 @@
+vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int K) {
+        int row = mat.size();
+        int col = mat[0].size();
+        vector<vector<int>> res(row, vector<int>(col, 0));
+        
+        for (int i = 0; i < row; ++i)
+        {
+            for (int j = 0; j < col; ++j)
+            {
+                for (int m = i-K; m <= i+K; ++m)
+                {
+                    for (int n = j-K; n <= j+K; ++n)
+                    {
+                        if (m >= 0 && m < row && n >= 0 && n < col)
+                            res[i][j] += mat[m][n];
+                    }
+                }
+            }
+        }
+        
+        return res;
+    }
diff --git a/src/1379.cpp b/src/1379.cpp
@@ -0,0 +1,50 @@
+TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
+        vector<int> paths;
+        search(original, target, paths);
+
+        int len = paths.size();
+        TreeNode* node = cloned;
+        for (int i = 0; i < len; ++i)
+        {
+            if (paths[i] == 0)
+                node = node->left;
+            else
+                node = node->right;
+        }
+        
+        return node;
+    }
+    
+    bool search(TreeNode* ori, TreeNode* target, vector<int>& paths)
+    {
+        if (ori != target)
+        {
+            if (ori->left == nullptr && ori->right == nullptr)
+                return false;
+            bool flag = false;
+            vector<int> tmp(paths);
+            if (ori->left != nullptr)
+            {
+                tmp.push_back(0);
+                flag = search(ori->left, target, tmp);
+            }
+            
+            if (!flag && ori->right != nullptr)
+            {
+                tmp.swap(paths);
+                tmp.push_back(1);
+                flag = search(ori->right, target, tmp);
+                if (flag)
+                    paths.swap(tmp);
+                return flag;
+            }
+            else
+            {
+                if (flag)
+                    paths.swap(tmp);
+                return flag;
+            }
+        }
+        else
+            return true;
+    }
diff --git a/src/1381.cpp b/src/1381.cpp
@@ -0,0 +1,36 @@
+class CustomStack {
+public:
+    CustomStack(int maxSize) {
+        maxCap = maxSize;
+        curSz = 0;
+        dq.assign(maxCap, -1);
+    }
+    
+    void push(int x) {
+        if (curSz < maxCap)
+        {
+            dq[curSz++] = x;
+        }
+    }
+    
+    int pop() {
+        if (curSz > 0)
+        {
+            --curSz;
+            return dq[curSz];
+        }
+        else
+            return -1;
+    }
+    
+    void increment(int k, int val) {
+        if (curSz < k)
+            k = curSz;
+        for (int i = 0; i < k; ++i)
+            dq[i] += val;
+    }
+private:
+    deque<int> dq;
+    int maxCap;
+    int curSz;
+};
diff --git a/src/1385.cpp b/src/1385.cpp
@@ -0,0 +1,15 @@
+int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
+        int len1 = arr1.size(), len2 = arr2.size();
+        int ct = 0;
+        for (int i = 0; i < len1; ++i)
+        {
+            int j = 0;
+            for (j = 0; j < len2; ++j)
+                if (abs(arr1[i]-arr2[j]) <= d)
+                    break;
+            if (j == len2)
+                ++ct;
+        }
+        
+        return ct;
+    }
diff --git a/src/1387.cpp b/src/1387.cpp
@@ -0,0 +1,34 @@
+int getKth(int lo, int hi, int k) {
+        struct Elem
+        {
+            int val;
+            int ct;
+            Elem(int v = 0, int n = 0):val(v),ct(n){}
+        };
+        
+        vector<Elem> res(hi-lo+1);
+        for (int i = lo; i <= hi; ++i)
+        {
+            int t = i;
+            int ct = 0;
+            while (t != 1)
+            {
+                if (t%2 == 0)
+                    t /= 2;
+                else
+                    t = t*3+1;
+                ++ct;
+            }
+            
+            res[i-lo].val = i;
+            res[i-lo].ct = ct;
+        }
+        
+        auto cmp = [](const Elem& a, const Elem& b) {
+            return a.ct < b.ct || (a.ct == b.ct && a.val < b.val);
+        };
+        
+        sort(res.begin(), res.end(), cmp);
+        
+        return res[k-1].val;
+    }
diff --git a/src/1389.cpp b/src/1389.cpp
@@ -0,0 +1,14 @@
+vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {
+        int len = nums.size();
+        vector<int> res(len, -1);
+        for (int i = 0; i < len; ++i)
+        {
+            if (res[index[i]] == -1)
+                res[index[i]] = nums[i];
+            else
+                res.insert(res.begin()+index[i], 1, nums[i]);
+        }
+        
+        res.resize(len);
+        return res;
+    }
diff --git a/src/1394.cpp b/src/1394.cpp
@@ -0,0 +1,24 @@
+int findLucky(vector<int>& arr) {
+        int len = arr.size();
+        if (len == 1)
+            return arr[0] == 1 ? 1 : -1;
+        sort(arr.begin(), arr.end());
+        int i = len-1;
+        while (i >= 0)
+        {
+            int tmp = arr[i];
+            if (i-tmp+1 >= 0 && arr[i-tmp+1] == tmp)
+            {
+                if (i-tmp < 0 || arr[i-tmp] != tmp)
+                    return tmp;
+                else
+                    i = i-tmp;
+            }
+            
+            for (; i >= 0; --i)
+                if (arr[i] != tmp)
+                    break;
+        }
+        
+        return -1;
+    }
diff --git a/src/1395.cpp b/src/1395.cpp
@@ -0,0 +1,23 @@
+int numTeams(vector<int>& rating) {
+        int len = rating.size();
+        if (len < 3)
+            return 0;
+        
+        int ct = 0;
+        for (int i = 0; i < len-2; ++i)
+        {
+            for (int j = i+1; j < len-1; ++j)
+            {
+                bool flag = rating[i] < rating[j] ? true : false;
+                for (int k = j+1; k < len; ++k)
+                {
+                    if (flag && rating[j] < rating[k])
+                        ++ct;
+                    else if (!flag && rating[j] > rating[k])
+                        ++ct;
+                }
+            }
+        }
+        
+        return ct;
+    }
diff --git a/src/1403.cpp b/src/1403.cpp
@@ -0,0 +1,24 @@
+vector<int> minSubsequence(vector<int>& nums) {
+        int len = nums.size();
+        if (len == 1)
+            return move(nums);
+        
+        int sum = 0;
+        for (int i = 0; i < len; ++i)
+            sum += nums[i];
+        
+        sort(nums.begin(), nums.end());
+        vector<int> res;
+        int subsum = 0;
+        int i = len-1;
+        for (i = len-1; i >= 0; --i)
+        {
+            subsum += nums[i];
+            if (subsum > sum-subsum)
+                break;
+        }
+        
+        res.assign(nums.rbegin(), nums.rbegin()+len-i);
+        
+        return res;
+    }
diff --git a/src/1408.cpp b/src/1408.cpp
@@ -0,0 +1,22 @@
+vector<string> stringMatching(vector<string>& words) {
+        int len = words.size();
+        auto cmp = [](const string& a, const string& b) {
+            return a.size() < b.size();
+        };
+        
+        sort(words.begin(), words.end(), cmp);
+        vector<string> res;
+        for (int i = 0; i < len-1; ++i)
+        {
+            for (int j = i+1; j < len; ++j)
+            {
+                if (words[j].find(words[i]) != string::npos)
+                {
+                    res.push_back(words[i]);
+                    break;
+                }
+            }
+        }
+        
+        return res;
+    }
