6 problems solved.

lintcoder · lintcoder · commit 313ffafc02d1 · 2020-02-23T12:48:18.000+08:00
diff --git a/src/1175.cpp b/src/1175.cpp
@@ -0,0 +1,30 @@
+int numPrimeArrangements(int n) {
+        if (n == 1)
+            return 1;
+        
+        int prime[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,
+                      67,71,73,79,83,89,97};
+        int len = sizeof(prime)/sizeof(prime[0]);    
+        int ct = 0;
+        for (int i = 0; i < len; ++i)
+        {
+            if (prime[i] <= n)
+                ++ct;
+            else
+                break;
+        }
+ 
+        int mod = 1e9+7;
+        long long res = 1;
+        for (int i = 1; i <= ct; ++i)
+        {
+            res = (res*i)%mod;
+        }
+        ct = n-ct;
+        for (int i = 1; i <= ct; ++i)
+        {
+            res = (res*i)%mod;
+        }
+        
+        return res;
+    }
diff --git a/src/1356.cpp b/src/1356.cpp
@@ -0,0 +1,19 @@
+vector<int> sortByBits(vector<int>& arr) {
+        int len = arr.size();
+        if (len == 1)
+            return arr;
+        vector<bitset<32>> vec;
+        for (int i = 0; i < len; ++i)
+            vec.push_back(arr[i]);
+        auto cmp = [](const bitset<32>& a, const bitset<32>& b) {
+            int m = a.count(), n = b.count();
+            return m < n || (m == n && a.to_ulong() < b.to_ulong());
+        };
+        
+        sort(vec.begin(), vec.end(), cmp);
+        vector<int> res(len);
+        for (int i = 0; i < len; ++i)
+            res[i] = vec[i].to_ulong();
+        
+        return res;
+    }
diff --git a/src/733.cpp b/src/733.cpp
@@ -0,0 +1,33 @@
+vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
+        int row = image.size();
+        int col = image[0].size();
+        vector<vector<int>> flag(row, vector<int>(col, 0));
+        vector<vector<int>> res(image);
+        
+        deque<pair<int, int>> dq;
+        dq.push_back(make_pair(sr, sc));
+        int color = image[sr][sc];
+        
+        int len = 1;
+        while (len != 0)
+        {
+            for (int i = 0; i < len; ++i)
+            {
+                int m = dq[i].first, n = dq[i].second;
+                res[m][n] = newColor;
+                flag[m][n] = 1;
+                if (m > 0 && flag[m-1][n] == 0 && image[m-1][n] == color)
+                    dq.push_back(make_pair(m-1, n));
+                if (m < row-1 && flag[m+1][n] == 0 && image[m+1][n] == color)
+                    dq.push_back(make_pair(m+1, n));
+                if (n > 0 && flag[m][n-1] == 0 && image[m][n-1] == color)
+                    dq.push_back(make_pair(m, n-1));
+                if (n < col-1 && flag[m][n+1] == 0 && image[m][n+1] == color)
+                    dq.push_back(make_pair(m, n+1));
+            }
+            dq.erase(dq.begin(), dq.begin()+len);
+            len = dq.size();
+        }
+        
+        return res;
+    }
diff --git a/src/762.cpp b/src/762.cpp
@@ -0,0 +1,32 @@
+int countPrimeSetBits(int L, int R) {
+        bitset<32> num(L);
+        string s = num.to_string();
+        set<int> prime{2,3,5,7,11,13,17,19,23,29,31};
+        int ct = num.count();
+        
+        int res = 0;
+        while (L <= R)
+        {
+            if (prime.find(ct) != prime.end())
+                ++res;
+            int t = 1;
+            for (int i = 31; i >= 0; --i)
+            {
+                char c = s[i] + t;
+                if (c == '1')
+                {
+                    ++ct;
+                    s[i] = '1';
+                    break;
+                }
+                else
+                {
+                    --ct;
+                    s[i] = '0';
+                }
+            }
+            ++L;
+        }
+        
+        return res;
+    }
diff --git a/src/993.cpp b/src/993.cpp
@@ -0,0 +1,39 @@
+bool isCousins(TreeNode* root, int x, int y) {
+        deque<TreeNode*> dq;
+        dq.push_back(root);
+        int ct = 1;
+        int n = 0;
+        int p[2] = {-1,-1};
+        while (ct != 0)
+        {
+            ct = 0;
+            int len = dq.size();
+            for (int i = 0; i < len; ++i)
+            {
+                if (dq[i] == nullptr)
+                {
+                    dq.push_back(nullptr);
+                    dq.push_back(nullptr);
+                }
+                else if (dq[i]->val == x || dq[i]->val == y)
+                {
+                    p[n++] = i;
+                }
+                else
+                {
+                    dq.push_back(dq[i]->left);
+                    dq.push_back(dq[i]->right);
+                    ++ct;
+                }
+            }
+            if (n == 1 || n == 2 || ct == 0)
+                break;
+            dq.erase(dq.begin(), dq.begin()+len);
+        }
+        
+        if (n == 1)
+            return false;
+        if (n == 2)
+            return p[0]/2 != p[1]/2;
+        return false;
+    }
diff --git a/src/997.cpp b/src/997.cpp
@@ -0,0 +1,32 @@
+int findJudge(int N, vector<vector<int>>& trust) {
+        vector<list<int>> vec(N);
+        int len = trust.size();
+        for (int i = 0; i < len; ++i)
+        {
+            vec[trust[i][1]-1].push_back(trust[i][0]);
+        }
+        
+        int judge = -1;
+        int ct = 0;
+        for (int i = 0; i < N; ++i)
+            if (vec[i].size() == N-1)
+            {
+                judge = i+1;
+                ++ct;
+            }
+        if (ct != 1)
+            return -1;
+        for (int i = 0; i < N; ++i)
+        {
+            if (i != judge-1 && vec[i].size() != 0)
+            {
+                for (auto iter = vec[i].begin(); iter != vec[i].end(); ++iter)
+                {
+                    if (*iter == judge)
+                        return -1;
+                }
+            }
+        }
+        
+        return judge;
+    }
