7 problems solved.

lintcoder · lintcoder · commit 3028f46982df · 2020-02-09T19:02:15.000+08:00
diff --git a/src/1022.cpp b/src/1022.cpp
@@ -0,0 +1,26 @@
+int sumRootToLeaf(TreeNode* root) {
+        if (root == nullptr)
+            return 0;
+        
+        int res = 0;
+        int sum = 0;
+        search(root, res, sum);
+        
+        return sum;
+    }
+    
+    void search(TreeNode* node, int res, int& sum)
+    {
+        res = res*2 + node->val;
+        if (node->left != nullptr || node->right != nullptr)
+        {
+            if (node->left != nullptr)
+                search(node->left, res, sum);
+            if (node->right != nullptr)
+                search(node->right, res, sum);
+        }
+        else
+        {
+            sum += res;
+        }
+    }
diff --git a/src/1291.cpp b/src/1291.cpp
@@ -0,0 +1,16 @@
+vector<int> sequentialDigits(int low, int high) {
+        vector<vector<int>> nums{{12,23,34,45,56,67,78,89},{123,234,345,456,567,678,789},{1234,2345,3456,4567,5678,6789},
+                                 {12345,23456,34567,45678,56789},{123456,234567,345678,456789},{1234567,2345678,3456789},{12345678,23456789},
+                                 {123456789}};
+        
+        vector<int> res;
+        for (int i = 0; i < 8; ++i)
+        {
+            int sz = nums[i].size();
+            for (int j = 0; j < sz; ++j)
+                if (nums[i][j] >= low && nums[i][j] <= high)
+                    res.push_back(nums[i][j]);
+        }
+        
+        return res;
+    }
diff --git a/src/1296.cpp b/src/1296.cpp
@@ -0,0 +1,25 @@
+bool isPossibleDivide(vector<int>& nums, int k) {
+        int len = nums.size();
+        if (len%k != 0)
+            return false;
+        
+        map<int, int> mp;
+        for (int i = 0; i < len; ++i)
+            mp[nums[i]]++;
+        
+        for (auto iter = mp.begin(); iter != mp.end(); ++iter)
+        {
+            if (iter->second == 0)
+                continue;
+            int t = iter->first;
+            for (int i = t+1; i < t+k; ++i)
+            {
+                if (mp[i] < iter->second)
+                    return false;
+                else
+                    mp[i] -= iter->second;
+            }
+        }
+        
+        return true;
+    }
diff --git a/src/1346.cpp b/src/1346.cpp
@@ -0,0 +1,13 @@
+bool checkIfExist(vector<int>& arr) {
+        int len = arr.size();
+        for (int i = 0; i < len-1; ++i)
+        {
+            for (int j = i+1; j < len; ++j)
+            {
+                if (arr[i]*2 == arr[j] || arr[i] == arr[j]*2)
+                    return true;
+            }
+        }
+        
+        return false;
+    }
diff --git a/src/1347.cpp b/src/1347.cpp
@@ -0,0 +1,18 @@
+int minSteps(string s, string t) {
+        vector<int> ct1(26, 0);
+        vector<int> ct2(26, 0);
+        int len = s.size();
+        for (int i = 0; i < len; ++i)
+        {
+            ct1[s[i]-'a']++;
+            ct2[t[i]-'a']++;
+        }
+        
+        for (int i = 0; i < 26; ++i)
+        {
+            if (ct1[i] > 0 && ct2[i] > 0)
+                len -= min(ct1[i], ct2[i]);
+        }
+        
+        return len;
+    }
diff --git a/src/1348.cpp b/src/1348.cpp
@@ -0,0 +1,46 @@
+class TweetCounts {
+public:
+    TweetCounts() {
+    }
+    
+    void recordTweet(string tweetName, int time) {
+        mp[tweetName].push_back(time);
+    }
+    
+    vector<int> getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime) {
+        if (mp.find(tweetName) != mp.end())
+        {
+            int ct = 0;
+            int interval = 0;
+            if (freq == "minute")
+            {
+                ct = (endTime-startTime+60)/60;
+                interval = 60;
+            }
+            else if (freq == "hour")
+            {
+                ct = (endTime-startTime+3600)/3600;
+                interval = 3600;
+            }
+            else
+            {
+                ct = (endTime-startTime+86400)/86400;
+                interval = 86400;
+            }
+            vector<int> res(ct, 0);
+            int len = mp[tweetName].size();
+            for (int i = 0; i < len; ++i)
+            {
+                if (mp[tweetName][i] < startTime || mp[tweetName][i] >= endTime+1)
+                    continue;
+                res[(mp[tweetName][i]-startTime)/interval]++;
+            }
+            
+            return res;
+        }
+        else
+            return {};
+    }
+    private:
+            map<string, vector<int>> mp;
+};
diff --git a/src/15.cpp b/src/15.cpp
@@ -0,0 +1,37 @@
+vector<vector<int>> threeSum(vector<int>& nums) {
+        vector<vector<int>> res;
+        int len = nums.size();
+        if (len < 3)
+            return res;
+        
+        sort(nums.begin(), nums.end());
+        int i = 0, j = 0;
+        while (i < len-2)
+        {
+            if (nums[i] > 0)
+                break;
+            j = i+1;
+            while (j < len-1)
+            {
+                if (nums[i]+nums[j] > 0)
+                {
+                    break;
+                }
+                bool ans = binary_search(nums.begin()+j+1, nums.end(), -nums[i]-nums[j]);
+                if (ans)
+                    res.push_back({nums[i], nums[j], -nums[i]-nums[j]});
+                auto iter = upper_bound(nums.begin()+j+1, nums.end(), nums[j]);
+                if (iter == nums.end())
+                    break;
+                j = iter-nums.begin();
+            }
+            
+            auto iter2 = upper_bound(nums.begin()+i+1, nums.end(), nums[i]);
+            if (iter2 == nums.end())
+                break;
+            else
+                i = iter2-nums.begin();
+        }
+        
+        return res;
+    }
