0996 added.

liuyubobobo · liuyubobobo · commit deca28fb2244 · 2019-02-19T18:17:24.000-08:00
diff --git a/0996-Number-of-Squareful-Arrays/cpp-0996/CMakeLists.txt b/0996-Number-of-Squareful-Arrays/cpp-0996/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.13)
+project(D)
+
+set(CMAKE_CXX_STANDARD 11)
+
+add_executable(D main3.cpp)
diff --git a/0996-Number-of-Squareful-Arrays/cpp-0996/main.cpp b/0996-Number-of-Squareful-Arrays/cpp-0996/main.cpp
@@ -0,0 +1,96 @@
+/// Source : https://leetcode.com/problems/number-of-squareful-arrays/
+/// Author : liuyubobobo
+/// Time   : 2019-02-16
+
+#include <iostream>
+#include <vector>
+#include <cmath>
+#include <unordered_set>
+
+using namespace std;
+
+
+/// Backtrack
+/// Using string hash to record the same value
+/// Time Complexity: O(n^n)
+/// Space Complexity: O(n)
+class Solution {
+
+private:
+    int n;
+
+public:
+    int numSquarefulPerms(vector<int>& A) {
+
+        n = A.size();
+        vector<vector<int>> ok(n);
+        for(int i = 0; i < n; i ++)
+            for(int j = 0; j < n; j ++)
+                if(j != i && perfectSquare(A[i] + A[j]))
+                    ok[i].push_back(j);
+
+        int res = 0;
+        unordered_set<string> hashset;
+        for(int i = 0; i < n; i ++){
+            vector<bool> visited(n, false);
+            visited[i] = true;
+
+            vector<int> seqindex = {i};
+
+            string hash = to_string(A[i]);
+            hashset.insert(hash);
+
+            res += dfs(A, ok, 1, seqindex, hash, visited, hashset);
+        }
+        return res;
+    }
+
+private:
+    int dfs(const vector<int>& A, const vector<vector<int>>& ok,
+            int index, vector<int>& seqindex, const string& hash, vector<bool>& visited,
+            unordered_set<string>& hashset){
+
+        if(index == n)
+            return 1;
+
+        int res = 0;
+        for(int next: ok[seqindex[index - 1]])
+            if(!visited[next]){
+
+                string newhash = hash + "#" + to_string(A[next]);
+                if(!hashset.count(newhash)){
+                    hashset.insert(newhash);
+
+                    seqindex.push_back(next);
+                    visited[next] = true;
+                    res += dfs(A, ok, index + 1, seqindex, newhash, visited, hashset);
+                    visited[next] = false;
+                    seqindex.pop_back();
+                }
+            }
+        return res;
+    }
+
+    bool perfectSquare(int x){
+        int t = sqrt(x);
+        return t * t == x;
+    }
+};
+
+
+int main() {
+
+    vector<int> A1 = {1, 17, 8};
+    cout << Solution().numSquarefulPerms(A1) << endl;
+    // 2
+
+    vector<int> A2 = {2, 2, 2};
+    cout << Solution().numSquarefulPerms(A2) << endl;
+    // 1
+
+    vector<int> A3(12, 0);
+    cout << Solution().numSquarefulPerms(A3) << endl;
+    // 1
+
+    return 0;
+}
diff --git a/0996-Number-of-Squareful-Arrays/cpp-0996/main2.cpp b/0996-Number-of-Squareful-Arrays/cpp-0996/main2.cpp
@@ -0,0 +1,90 @@
+/// Source : https://leetcode.com/problems/number-of-squareful-arrays/
+/// Author : liuyubobobo
+/// Time   : 2019-02-19
+
+#include <iostream>
+#include <vector>
+#include <cmath>
+#include <unordered_map>
+#include <unordered_set>
+
+using namespace std;
+
+
+/// Backtrack
+/// Using HashMap to record the same value
+/// Time Complexity: O(n^n)
+/// Space Complexity: O(n)
+class Solution {
+
+private:
+    int n;
+
+public:
+    int numSquarefulPerms(vector<int>& A) {
+
+        n = A.size();
+        unordered_map<int, int> freq;
+        unordered_set<int> elements;
+        for(int e: A){
+            freq[e] ++;
+            elements.insert(e);
+        }
+
+        unordered_map<int, unordered_set<int>> g;
+        for(int i = 0; i < n; i ++)
+            for(int j = i + 1; j < n; j ++)
+                if(perfectSquare(A[i] + A[j])){
+                    g[A[i]].insert(A[j]);
+                    g[A[j]].insert(A[i]);
+                }
+
+        int res = 0;
+        for(int e: elements){
+            freq[e] --;
+            res += dfs(g, e, 1, freq);
+            freq[e] ++;
+        }
+        return res;
+    }
+
+private:
+    int dfs(unordered_map<int, unordered_set<int>>& g,
+            int e, int index, unordered_map<int, int>& freq){
+
+        if(index == n)
+            return 1;
+
+        int res = 0;
+        for(int next: g[e])
+            if(freq[next]){
+                freq[next] --;
+                res += dfs(g, next, index + 1, freq);
+                freq[next] ++;
+            }
+        return res;
+    }
+
+    bool perfectSquare(int x){
+        int t = sqrt(x);
+        return t * t == x;
+    }
+};
+
+
+int main() {
+
+    vector<int> A1 = {1, 17, 8};
+    cout << Solution().numSquarefulPerms(A1) << endl;
+    // 2
+
+    vector<int> A2 = {2, 2, 2};
+    cout << Solution().numSquarefulPerms(A2) << endl;
+    // 1
+
+    vector<int> A3(12, 0);
+    cout << Solution().numSquarefulPerms(A3) << endl;
+    // 1
+
+    return 0;
+}
diff --git a/0996-Number-of-Squareful-Arrays/cpp-0996/main3.cpp b/0996-Number-of-Squareful-Arrays/cpp-0996/main3.cpp
@@ -0,0 +1,92 @@
+/// Source : https://leetcode.com/problems/number-of-squareful-arrays/
+/// Author : liuyubobobo
+/// Time   : 2019-02-19
+
+#include <iostream>
+#include <vector>
+#include <cmath>
+#include <unordered_map>
+
+using namespace std;
+
+
+/// Memory Search
+/// Divide corresponding factorial number to avoid repeating counting :-)
+/// Time Complexity: O(n*2^n)
+/// Space Complexity: O(n*2^n)
+class Solution {
+
+private:
+    int n;
+
+public:
+    int numSquarefulPerms(vector<int>& A) {
+
+        n = A.size();
+
+        vector<vector<int>> g(n);
+        for(int i = 0; i < n; i ++)
+            for(int j = i + 1; j < n; j ++)
+                if(perfectSquare(A[i] + A[j])){
+                    g[i].push_back(j);
+                    g[j].push_back(i);
+                }
+
+        int res = 0;
+        vector<vector<int>> dp(n, vector<int>(1 << n, -1));
+        for(int i = 0; i < n; i ++)
+            res += dfs(g, i, 1 << i, dp);
+
+        unordered_map<int, int> freq;
+        for(int e: A) freq[e] ++;
+        for(const pair<int, int>& p: freq) res /= fac(p.second);
+        return res;
+    }
+
+private:
+    int dfs(const vector<vector<int>>& g,
+            int index, int visited, vector<vector<int>>& dp){
+
+        if(visited == (1 << n) - 1)
+            return 1;
+
+        if(dp[index][visited] != -1) return dp[index][visited];
+
+        int res = 0;
+        for(int next: g[index])
+            if(!(visited & (1 << next))){
+                visited += (1 << next);
+                res += dfs(g, next, visited, dp);
+                visited -= (1 << next);
+            }
+        return dp[index][visited] = res;
+    }
+
+    int fac(int x){
+        if(x == 0 || x == 1) return 1;
+        return x * fac(x - 1);
+    }
+
+    bool perfectSquare(int x){
+        int t = sqrt(x);
+        return t * t == x;
+    }
+};
+
+
+int main() {
+
+    vector<int> A1 = {1, 17, 8};
+    cout << Solution().numSquarefulPerms(A1) << endl;
+    // 2
+
+    vector<int> A2 = {2, 2, 2};
+    cout << Solution().numSquarefulPerms(A2) << endl;
+    // 1
+
+    vector<int> A3(12, 0);
+    cout << Solution().numSquarefulPerms(A3) << endl;
+    // 1
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -660,4 +660,5 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | 993 | [Cousins in Binary Tree](https://leetcode.com/problems/cousins-in-binary-tree/) | [solution](https://leetcode.com/problems/cousins-in-binary-tree/solution/) | [C++](0993-Cousins-in-Binary-Tree/cpp-0993/) | | |
 | 994 | [Rotting Oranges](https://leetcode.com/problems/rotting-oranges/) | [solution](https://leetcode.com/problems/rotting-oranges/solution/) | [C++](0994-Rotting-Oranges/cpp-0994/) | | |
 | 995 | [Minimum Number of K Consecutive Bit Flips](https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/) | [solution](https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/solution/) | [C++](0995-Minimum-Number-of-K-Consecutive-Bit-Flips/cpp-0995/) | | |
+| 996 | [Number of Squareful Arrays](https://leetcode.com/problems/number-of-squareful-arrays/) | [solution](https://leetcode.com/problems/number-of-squareful-arrays/solution/) | [C++](0996-Number-of-Squareful-Arrays/cpp-0996/) | | |
 | | | | | | |
