LeetCode 05/29/2014

daiwb · daiwb · commit 0270d5474b72 · 2014-05-29T17:35:16.000-07:00
diff --git a/LeetCode/anagrams.cpp b/LeetCode/anagrams.cpp
@@ -0,0 +1,53 @@
+#include <algorithm>
+#include <iostream>
+#include <sstream>
+#include <string>
+#include <vector>
+#include <queue>
+#include <set>
+#include <map>
+#include <cstdio>
+#include <cstdlib>
+#include <cctype>
+#include <cmath>
+#include <string>
+#include <cstring>
+using namespace std;
+
+#define REP(i,n) for(int i=0;i<(n);++i)
+#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
+#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
+#define FOREACH(it,c) for(typeof((c).begin())it=(c).begin();it!=(c).end();++it)
+#define CLR(x) memset((x),0,sizeof((x)))
+#define MP make_pair
+#define MPI make_pair<int, int>
+#define PB push_back
+typedef long long LL;
+typedef vector<int> VI;
+typedef vector<string> VS;
+typedef pair<int, int> PI;
+
+class Solution {
+public:
+    vector<string> anagrams(vector<string> &strs) {
+        vector<string> res;
+        int n = strs.size();
+        map<string, int> mp;
+        REP(i,n) {
+            string s = strs[i];
+            sort(s.begin(), s.end());
+            if (mp.find(s) == mp.end()) mp[s] = i;
+            else {
+                if (mp[s] >= 0) res.PB(strs[mp[s]]);
+                res.PB(strs[i]);
+                mp[s] = -1;
+            }
+        }
+        return res;
+    }
+};
+
+int main() {
+    Solution s = Solution();
+    return 0;
+}
diff --git a/LeetCode/combine.cpp b/LeetCode/combine.cpp
@@ -0,0 +1,63 @@
+#include <algorithm>
+#include <iostream>
+#include <sstream>
+#include <string>
+#include <vector>
+#include <queue>
+#include <set>
+#include <map>
+#include <cstdio>
+#include <cstdlib>
+#include <cctype>
+#include <cmath>
+#include <string>
+#include <cstring>
+using namespace std;
+
+#define REP(i,n) for(int i=0;i<(n);++i)
+#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
+#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
+#define FOREACH(it,c) for(typeof((c).begin())it=(c).begin();it!=(c).end();++it)
+#define CLR(x) memset((x),0,sizeof((x)))
+#define MP make_pair
+#define MPI make_pair<int, int>
+#define PB push_back
+typedef long long LL;
+typedef vector<int> VI;
+typedef vector<string> VS;
+typedef pair<int, int> PI;
+
+class Solution {
+public:
+    vector<VI> res;
+    VI mm;
+    void doit(int idx, int n, int k) {
+        if (idx == k) {
+            res.PB(mm);
+        } else {
+            int st;
+            if (idx == 0) st = 1;
+            else st = mm[idx - 1] + 1;
+            FOR(i,st,n) {
+                mm[idx] = i;
+                doit(idx + 1, n, k);
+            }
+        }
+    }
+    vector<vector<int> > combine(int n, int k) {
+        res.clear();
+        mm.resize(k);
+        doit(0, n, k);
+        return res;
+    }
+};
+
+int main() {
+    Solution s = Solution();
+    vector<VI> mm = s.combine(4, 2);
+    REP(i,mm.size()) {
+        REP(j,mm[i].size()) cout << mm[i][j] << " ";
+        cout << endl;
+    }
+    return 0;
+}
diff --git a/LeetCode/pow.cpp b/LeetCode/pow.cpp
@@ -0,0 +1,13 @@
+class Solution {
+public:
+    double doit(double x, int n) {
+        if (n == 0) return 1;
+        double t = pow(x, n / 2);
+        if (n & 1) return t * t * x;
+        else return t * t;
+    }
+    double pow(double x, int n) {
+        if (n < 0) return 1.0 / doit(x, -n);
+        else return doit(x, n);
+    }
+};
diff --git a/LeetCode/solveNQueens.cpp b/LeetCode/solveNQueens.cpp
@@ -0,0 +1,66 @@
+#include <algorithm>
+#include <iostream>
+#include <sstream>
+#include <string>
+#include <vector>
+#include <queue>
+#include <set>
+#include <map>
+#include <cstdio>
+#include <cstdlib>
+#include <cctype>
+#include <cmath>
+#include <string>
+#include <cstring>
+using namespace std;
+
+#define REP(i,n) for(int i=0;i<(n);++i)
+#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
+#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
+#define FOREACH(it,c) for(typeof((c).begin())it=(c).begin();it!=(c).end();++it)
+#define CLR(x) memset((x),0,sizeof((x)))
+#define MP make_pair
+#define MPI make_pair<int, int>
+#define PB push_back
+typedef long long LL;
+typedef vector<int> VI;
+typedef vector<string> VS;
+typedef pair<int, int> PI;
+
+class Solution {
+public:
+    vector<VS> res;
+    bool isok(VI& mm, int row) {
+        REP(i,row) {
+            if (mm[i] == mm[row] || (abs(mm[i] - mm[row]) == (row - i))) return false;
+        }
+        return true;
+    }
+    void doit(VI& mm, int row, int n) {
+        if (row == n) {
+            VS t;
+            REP(i,n) {
+                string s(n, '.');
+                s[mm[i]] = 'Q';
+                t.PB(s);
+            }
+            res.PB(t);
+        } else {
+            REP(i,n) {
+                mm[row] = i;
+                if (isok(mm, row)) doit(mm, row + 1, n);
+            }
+        }
+    }
+    vector<vector<string> > solveNQueens(int n) {
+        res.clear();
+        VI mm(n, -1);
+        doit(mm, 0, n);
+        return res;
+    }
+};
+
+int main() {
+    Solution s = Solution();
+    return 0;
+}
diff --git a/LeetCode/totalNQueens.cpp b/LeetCode/totalNQueens.cpp
@@ -0,0 +1,61 @@
+#include <algorithm>
+#include <iostream>
+#include <sstream>
+#include <string>
+#include <vector>
+#include <queue>
+#include <set>
+#include <map>
+#include <cstdio>
+#include <cstdlib>
+#include <cctype>
+#include <cmath>
+#include <string>
+#include <cstring>
+using namespace std;
+
+#define REP(i,n) for(int i=0;i<(n);++i)
+#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
+#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
+#define FOREACH(it,c) for(typeof((c).begin())it=(c).begin();it!=(c).end();++it)
+#define CLR(x) memset((x),0,sizeof((x)))
+#define MP make_pair
+#define MPI make_pair<int, int>
+#define PB push_back
+typedef long long LL;
+typedef vector<int> VI;
+typedef vector<string> VS;
+typedef pair<int, int> PI;
+
+class Solution {
+public:
+    int res;
+    bool isok(int mm[], int row) {
+        REP(i,row) {
+            if (mm[i] == mm[row] || (abs(mm[i] - mm[row]) == (row - i))) return false;
+        }
+        return true;
+    }
+    void doit(int mm[], int row, int n) {
+        if (row == n) {
+            ++res;
+        } else {
+            REP(i,n) {
+                mm[row] = i;
+                if (isok(mm, row)) doit(mm, row + 1, n);
+            }
+        }
+    }
+
+    int totalNQueens(int n) {
+        res = 0;
+        int *mm = new int[n];
+        doit(mm, 0, n);
+        return res;
+    }
+};
+
+int main() {
+    Solution s = Solution();
+    return 0;
+}
