Skip to content

Instantly share code, notes, and snippets.

View soulmachine's full-sized avatar

Frank Dai soulmachine

3.9k followers · 120 following
View GitHub Profile
@soulmachine
soulmachine / energe_necklace.c
Created August 16, 2013 09:19
wikioi 1154, 能量项链, http://www.wikioi.com/problem/1154
/* wikioi 1154, 能量项链, http://www.wikioi.com/problem/1154 */
#include <stdio.h>
#include <memory.h>
#include <limits.h>
#define MAXN 101
int N; /** 矩阵的个数. */
int a[MAXN];
int p[MAXN]; /** 矩阵Ai的维度是p[i-1]xp[i]. */
@soulmachine
soulmachine / string_serialization.c
Last active December 22, 2015 17:09
FB interview
/**
* @file string_serialization.c
* compile, gcc -std=c99 string_serialization.c ...
*
* @author Frank Dai
* @email soulmachine@gmail
*/
#include <stdio.h>
#include <stdlib.h> /* for strtoll, ato */
#include <string.h>
@soulmachine
soulmachine / poj3630.c
Created September 18, 2013 13:43
POJ 3630 Phone List, http://poj.org/problem?id=3630
/* POJ 3630 Phone List, http://poj.org/problem?id=3630 */
#define MAXN 10000 /** 输入的编码的最大个数. */
#define CHAR_COUNT 10 /** 字符的种类，也即单个节点的子树的最大个数 */
#define MAX_CODE_LEN 10 /** 编码的最大长度. */
#define MAX_NODE_COUNT (CHAR_COUNT * MAXN + 1) /** 字典树的最大节点个数. */
/* 等价于复制粘贴，这里为了节约篇幅，使用include，在OJ上提交时请用复制粘贴 */
#include "trie_tree.c" /* 见“树->Trie树”这节 */
@soulmachine
soulmachine / wikioi1079.cpp
Last active December 24, 2015 05:29
wikioi 1079 回家, http://www.wikioi.com/problem/1079/
// wikioi 1079 回家, http://www.wikioi.com/problem/1079/
#include <iostream>
#include <queue>
#include <map>
#include <utility>
#include <climits>
using namespace std;
/** 边的权值类型，可以为int, float, double. */
@soulmachine
soulmachine / POJ3620.c
Created September 30, 2013 09:44
POJ 3620 Avoid The Lakes, http://poj.org/problem?id=3620
/* POJ 3620 Avoid The Lakes, http://poj.org/problem?id=3620 */
#include <stdio.h>
#include <string.h>
/* N, M最大值是100，加一圈0可以防止越界 */
#define MAX 102
int N, M, K;
int map[MAX][MAX];
@soulmachine
soulmachine / 4sum.cpp
Created October 4, 2013 16:04
LeetCode 4Sum, TLE，怎么破？
// LeetCode, 4Sum
// 先排序，然后二分查找
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& num, int target) {
vector<vector<int>> result;
if (num.size() < 4) return result;
sort(num.begin(), num.end());
auto last = num.end();
@soulmachine
soulmachine / caculator.cpp
Created November 16, 2013 09:34
计算器，支持四则运算，小括号，整数，浮点数，暂时不支持16进制，正号，负号
#include <iostream>
#include <string>
#include <stack>
#include <vector>
using namespace std;
bool is_operator(const char op) {
return string("+-*/").find(op) != string::npos;
@soulmachine
soulmachine / SquareDetector.cpp
Last active December 29, 2015 01:59
Square Detector
#include <iostream>
#include <string>
#include <utility>
#include <vector>
#include <climits>
#include <cstdio>
using namespace std;
bool detect(vector<string> square) {
@soulmachine
soulmachine / 3Sum.cpp
Last active December 31, 2015 07:39
会超时, why? 4sum用同样的手法，却可以AC，见 https://gist.github.com/soulmachine/7957173
#include <iostream>
#include <cstdio>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
@soulmachine
soulmachine / 4sum.cpp
Last active December 31, 2015 07:58
// LeetCode, 4Sum
// 用一个 hashmap 先缓存两个数的和
// 时间复杂度O(n^2)，空间复杂度O(n^2)
// @author 龚陆安(http://weibo.com/luangong)
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& num, int target) {
vector<vector<int>> result;
if (num.size() < 4) return result;
sort(num.begin(), num.end());