8 problems solved.

lintcoder · lintcoder · commit c02953bdd962 · 2021-04-17T19:02:56.000+08:00
diff --git a/src/1233.cpp b/src/1233.cpp
@@ -0,0 +1,24 @@
+vector<string> removeSubfolders(vector<string>& folder) {
+        int len = folder.size();
+        sort(folder.begin(), folder.end());
+        list<string> lst(folder.begin(), folder.end());
+        
+        auto iter = lst.begin();
+        auto iter_next = ++iter;
+        --iter;
+        while (true)
+        {
+            auto iter_end = lst.end();
+            if (iter == iter_end || iter_next == iter_end)
+                break;
+            if ((*iter_next).find(*iter) == 0 && (*iter_next)[(*iter).size()] == '/')
+                iter_next = lst.erase(iter_next);
+            else
+            {
+                ++iter;
+                ++iter_next;
+            }
+        }
+        
+        return vector<string>(lst.begin(), lst.end());
+    }
diff --git a/src/1343.cpp b/src/1343.cpp
@@ -0,0 +1,21 @@
+int numOfSubarrays(vector<int>& arr, int k, int threshold) {
+        int len = arr.size();
+        int sum = 0;
+        int ct = 0;
+        const int thres = k*threshold;
+        
+        for (int i = 0; i < k; ++i)
+            sum += arr[i];
+        if (sum >= thres)
+            ++ct;
+        int j = k;
+        while (j < len)
+        {
+            sum += arr[j]-arr[j-k];
+            if (sum >= thres)
+                ++ct;
+            ++j;
+        }
+        
+        return ct;
+    }
diff --git a/src/1508.cpp b/src/1508.cpp
@@ -0,0 +1,20 @@
+int rangeSum(vector<int>& nums, int n, int left, int right) {
+        vector<int> res(n*(n+1)/2, 0);
+        int k = -1;
+        for (int i = 0; i < n; ++i)
+        {
+            res[++k] = nums[i];
+            for (int j = i+1; j < n; ++j)
+            {
+                int tmp = res[k] + nums[j];
+                res[++k] = tmp;
+            }
+        }
+        
+        sort(res.begin(), res.end());
+        long long sum = 0;
+        for (int i = left-1; i < right; ++i)
+            sum += res[i];
+        
+        return sum%(1000000000+7);
+    }
diff --git a/src/1701.cpp b/src/1701.cpp
@@ -0,0 +1,15 @@
+double averageWaitingTime(vector<vector<int>>& customers) {
+        int len = customers.size();
+        double avgWaitTime = 0;
+        int prefinishtime = 0;
+        int i = 0;
+        
+        while (i < len)
+        {
+            avgWaitTime += customers[i][0] >= prefinishtime ? customers[i][1] : prefinishtime-customers[i][0]+customers[i][1];
+            prefinishtime = customers[i][0] >= prefinishtime ? customers[i][0]+customers[i][1] : prefinishtime+customers[i][1];
+            ++i;
+        }
+        
+        return avgWaitTime / len;
+    }
diff --git a/src/1726.cpp b/src/1726.cpp
@@ -0,0 +1,19 @@
+int tupleSameProduct(vector<int>& nums) {
+        int len = nums.size();
+        map<int, int> mp;
+        for (int i = 0; i < len; ++i)
+        {
+            for (int j = i+1; j < len; ++j)
+                mp[nums[i]*nums[j]]++;
+        }
+        
+        int sum = 0;
+        auto iterend = mp.end();
+        for (auto iter = mp.begin(); iter != iterend; ++iter)
+        {
+            if (iter->second > 1)
+                sum += iter->second*(iter->second-1)*4;
+        }
+        
+        return sum;
+    }
diff --git a/src/1806.cpp b/src/1806.cpp
@@ -0,0 +1,27 @@
+int reinitializePermutation(int n) {
+        vector<int> arr(n, 0);
+        for (int i = 0; i < n; ++i)
+            arr[i] = i;
+        
+        int ct = 0;
+        vector<int> tmp(n, 0);
+        while (true)
+        {
+            ++ct;
+            int k = 0;
+            for (int i = 0; i < n; ++i)
+            {
+                if (i%2 == 0)
+                    tmp[i] = arr[i/2];
+                else
+                    tmp[i] = arr[n/2+(i-1)/2];
+                if (tmp[i] == i)
+                    ++k;
+            }
+            if (k == n)
+                break;
+            swap(arr, tmp);
+        }
+        
+        return ct;
+    }
diff --git a/src/287.cpp b/src/287.cpp
@@ -0,0 +1,13 @@
+int findDuplicate(vector<int>& nums) {
+        int len = nums.size();
+        sort(nums.begin(), nums.end());
+        int i = 1;
+        while (i < len)
+        {
+            if (nums[i] == nums[i-1])
+                break;
+            ++i;
+        }
+        
+        return nums[i];
+    }
diff --git a/src/950.cpp b/src/950.cpp
@@ -0,0 +1,44 @@
+vector<int> deckRevealedIncreasing(vector<int>& deck) {
+        int len = deck.size();
+        sort(deck.begin(), deck.end());
+        vector<int> res(len, 0);
+        vector<int> flag(len, 0);
+        
+        int ct = 0;
+        int v = 0;
+        int i = 0;
+        while (ct < len)
+        {
+            int j;
+            for (j = i; j < len; ++j)
+            {
+                if (flag[j] == 0)
+                {
+                    flag[j] = 1-v;
+                    if (flag[j] == 1)
+                        res[j] = deck[ct++];
+                    v = 1-v;
+                    i = (j+1)%len;
+                    break;
+                }
+            }
+            
+            if (j == len)
+            {
+                for (j = 0; j < i; ++j)
+                {
+                    if (flag[j] == 0)
+                    {
+                        flag[j] = 1-v;
+                        if (flag[j] == 1)
+                            res[j] = deck[ct++];
+                        v = 1-v;
+                        i = (j+1)%len;
+                        break;
+                    }
+                }
+            } 
+        }
+        
+        return res;
+    }
