guoliqiang2006
BAN USERint Atoi(const char * ptr) {
long long rs = 0;
bool minus = false;
while (*ptr == ' ') ptr++;
if (*ptr == '-') {
minus = true;
ptr++;
} else if (*ptr == '+') ptr++;
while (*ptr >= '0' && *ptr <= '9') {
rs = rs * 10 + *ptr - '0';
ptr++;
if (rs > INT_MAX) break;
}
if (minus) rs *= -1;
if (rs > INT_MAX) return INT_MAX;
if (rs < INT_MIN) return INT_MIN;
return rs;
}
void Split(std::vector<int> & vec) {
int k = -1;
for (int i = 0; i < vec.size(); i++) {
if (vec[i] != 0) std::swap(vec[++k], vec[i]);
}
}
using dynamic programming.
int Dp(std::string & str) {
int n = str.size();
std::vector<std::vector<int> > dp(n, std::vector<int>(n, 0));
int rs = 0;
for (int k = 0; k < n; k++) {
for (int i = 0; i < n - k; i++) {
if (k == 0) dp[i][i + k] = 1;
else if (k == 1) dp[i][i + k] = str[i] == str[i + k] ? 1 : 0;
else {
if (dp[i + 1][i + k - 1] && str[i] == str[i + k]) dp[i][i + k] = 1;
}
if (dp[i][i + k] == 1) rs++;
}
}
return rs;
}
morris inorder traversal.
TreeNode * InOrder(TreeNode * root, int n) {
int cnt = 0;
TreeNode * rs = NULL;
while (root != NULL) {
if (root->left != NULL) {
cnt++;
if (cnt == n) rs = root;
root = root->left;
} else {
TreeNode * tmp = root->left;
while (tmp->right != NULL && tmp->right != root) tmp = tmp->right;
if (tmp->right == NULL) {
tmp->right = root;
root = root->left;
} else {
cnt++;
if (cnt == n) rs = root;
tmp->right = NULL;
root = root->right;
}
}
}
return rs;
}
}
- guoliqiang2006 January 03, 2014using dynamic programming language.
int Dp(std::vector<int> & v, int k) {
v.insert(v.begin(), 0);
k += 1;
int n = v.size();
std::vector<int> dp(n, 0);
std::vector<int> pre(n, 0);
int rs = 0;
for (int i = 1; i < k; i++) {
int max = INT_MIN;
for (int j = k; j < n; j++) {
dp[j] = std::max(dp[j - 1], pre[j - 1]) + v[j];
pre[j - 1] = max;
max = std::max(max, dp[j]);
rs = std::max(rs, dp[j]);
}
pre[n - 1] = max;
}
return rs;
}
int MaxProfit(std::vector<int> & price, int n) {
std::vector<int> v;
for (int i = 1; i < price.size(); i++) {
v.push_back(price[i] - price[i - 1]);
}
return Dp(v, n);
}
This code will be ok.
int Roman2Int(std::string & str) {
int rs = 0;
int pre = 1001;
int cur = 0;
for (int i = 0; i < str.size(); i++) {
if (str[i] == 'I') cur = 1;
else if (str[i] == 'V') cur = 5;
else if (str[i] == 'X') cur = 10;
else if (str[i] == 'L') cur = 50;
else if (str[i] == 'C') cur = 100;
else if (str[i] == 'D') cur = 500;
else cur = 1000;
if (cur <= pre) rs += cur;
else rs = rs - pre + (cur - pre);
pre = cur;
}
return rs;
}
This code will be ok.
void Trace(std::string & path, std::vector<std::string> & rs, std::map<char, std::string> & dict, int k) {
if (k == path.size()) {
rs.push_back(path);
} else {
Trace(path, rs, dict, k + 1);
char ch = path[k];
if (dict.count(ch)) {
for (int i = 0; i < dict[ch].size(); i++) {
path[k] = dict[ch][i];
Trace(path, rs, dict, k + 1);
}
path[k] = ch;
}
}
}
std::vector<std::string> Trace(std::string & str, std::map<char, std::string> & dict) {
std::vector<std::string> rs;
Trace(str, rs, dict, 0);
return rs;
}
This code will be ok.
void Trace(std::vector<std::vector<int> > & rs, std::vector<int> & path, std::vector<int> & v, int k) {
if (k == v.size()) {
rs.push_back(path);
} else {
Trace(rs, path, v, k + 1);
path.push_back(v[k]);
Trace(rs, path, v, k + 1);
path.pop_back();
}
}
std::vector<std::vector<int> > PSet(std::vector<int> & v) {
std::vector<std::vector<int> > rs;
std::vector<int> path;
Trace(rs, path, v, 0);
return rs;
}
KMP
void Next(char * p, std::vector<int> & next) {
int n = strlen(p);
if (p == 0) return;
next.resize(n, 0);
int i = 0;
next[i] = -1;
int k = next[i];
while (i < n) {
while (k >= 0 && p[i] != p[k]) k = next[k];
i++;
k++;
if (i == n) break;
if (p[i] == p[k]) next[i] = next[k];
else next[i] = k;
}
}
char * KMP(char *s, char * p) {
int s_len = strlen(s);
int p_len = strlen(p);
if (p_len == 0) return s;
std::vector<int> next;
Next(p, next);
int i = 0;
int j = 0;
while (i < s_len) {
if (s[i] == p[j]) {
i++;
j++;
} else j = next[j];
if (j == p_len) return s + i - p_len;
if (j == -1) {
i++;
j++;
}
}
return NULL;
}
This code will be ok.
bool Skip(char ch) {
if (ch >= 'A' && ch <= 'Z' ||
ch >= 'a' && ch <= 'z' ||
ch >= '0' && ch <= '9') return false;
return true;
}
char Lower(char ch) {
if (ch >= 'A' && ch <= 'Z') return 'a' + ch - 'A';
return ch;
}
bool IsPalindrome(std::string s) {
int b = 0;
int e = s.size() - 1;
while (b < e) {
if (Skip(s[b])) b++;
else if (Skip(s[e])) e--;
else if (Lower(s[b]) != Lower(s[e])) return false;
else {
b++;
e--;
}
}
return true;
}
This code will be ok.
void Trace(std::vector<std::vector<int> > & rs, std::vector<int> & v, std::vector<int> & cnt,
std::vector<int> & path, int k, int t) {
if (path.size() == t) {
rs.push_back(path);
} else {
for (int i = k; i < v.size(); i++) {
if (cnt[i] > 0) {
cnt[i]--;
path.push_back(v[i]);
Trace(rs, v, cnt, path, i, t);
path.pop_back();
cnt[i]++;
}
}
}
}
std::vector<std::vector<int> > KSubset(std::vector<int> & num, int k) {
std::map<int, int> tmap;
for (int i = 0; i < num.size(); i++) {
if (!tmap.count(num[i])) tmap[num[i]] = 0;
tmap[num[i]]++;
}
std::vector<int> v;
std::vector<int> cnt;
for (std::map<int, int>::iterator i = tmap.begin(); i != tmap.end(); i++) {
v.push_back(i->first);
cnt.push_back(i->second);
}
std::vector<std::vector<int> > rs;
std::vector<int> path;
Trace(rs, v, cnt, path, 0, k);
return rs;
}
This code will be ok.
bool IsMatch(const char * s, const char * p) {
if (*s == '\0' && *p == '\0') return true;
if (*p == '\0') return false;
if (*(p + 1) == '*' && IsMatch(s, p + 2)) return true;
if (*p == '+' || *p == '*') {
if (IsMatch(s, p + 1)) return true;
if (*s == *(s - 1) && IsMatch(s + 1, p)) return true;
return false;
} else if (*p == *s) {
return IsMatch(s + 1, p + 1);
} else {
return false;
}
}
This code will be ok.
int Dp(std::vector<int> & v) {
int n = v.size();
std::vector<int> dp(n, 0);
if (n == 0) return 0;
else if (n == 1) return v[0];
else if (n == 2) return std::max(v[0], v[1]);
else {
dp[0] = v[0];
dp[1] = std::max(v[0], v[1]);
int rs = std::max(dp[0], dp[1]);
int max = dp[0];
for (int i = 2; i < n; i++) {
dp[i] = std::max(v[i], v[i] + max);
max = std::max(max, dp[i - 1]);
rs = std::max(rs, dp[i]);
}
return rs;
}
}
This code will be ok.
int Search(std::vector<int> & v, int k) {
int b = 0;
int e = v.size() - 1;
while (b <= e) {
int mid = b + (e - b) / 2;
if (v[mid] == k) return mid;
else if (v[mid] > v[e]) {
if (k > v[e] && k < v[mid]) e = mid - 1;
else b = mid + 1;
} else if (v[mid] < v[e]) {
if (t > v[mid] && t <= v[e]) b = mid + 1;
else e = mid - 1;
} else {
e--;
}
}
return -1;
}
This code will be ok.
{
void Trace(std::vector<std::vector<int> > &rs, std::vector<int> & v, std::vector<int> & cnt, std::vector<int> & path, int k) {
rs.push_back(path);
for (int i = k; i < v.size(); i++) {
if (cnt[i] > 0) {
cnt[i]--;
path.push_back(v[i]);
Trace(rs, v, cnt, path, i);
path.pop_back();
cnt[i]++;
}
}
}
std::vector<std::vector<int> > PSet(std::vector<int> & num) {
std::map<int, int> tmap;
for (int i = 0; i < num.size(); i++) {
if (!tmap.count(num[i])) tmap[num[i]] = 0;
tmap[num[i]]++;
}
std::vector<int> v;
std::vector<int> cnt;
for (std::map<int, int>::iterator i = tmap.begin(); i != tmap.end(); i++) {
v.push_back(i->first);
cnt.push_back(i->second);
}
std::vector<std::vector<int> > rs;
std::vector<int> path;
Trace(rs, v, cnt, path, 0);
return rs;
}
bool IsValidBST(TreeNode * root, TreeNode * & pre) {
if (root == NULL) return true;
if (!IsValidBST(root->left, pre)) return false;
if (pre != NULL && pre->val >= root->val) return false;
pre = root;
if (!IsValidBST(root->right, pre)) return false;
return true;
}
bool IsValidBST(TreeNode * root) {
TreeNode * pre = NULL;
return IsValidBST(root, pre);
}
I do not think it is a good idea to use static variable, if we have many cases to test,
- guoliqiang2006 December 29, 2013// log(n)
int Missing(std::vector<int> & v) {
int b = 0;
int e = v.size() - 1;
while (b <= e) {
int mid = b + (e - b) / 2;
if (v[mid] == 2 * mid + 1) b = mid + 1;
else e = mid - 1;
}
return 2 * b + 1;
}
int Remove(std::vector<int> & v) {
int k = -1;
std::set<int> seen;
for (int i = 0; i < v.size(); i++) {
if (seen.count(v[i])) continue;
seen.insert(v[i]);
v[++k] = v[i];
}
return k + 1;
}
This problem can be solved by total least squares method.
If in 2 plane, its equation can be computed exactly.
// y = a0x + a1
std::pair<double, double> Line(std::vector<std::pair<double, double> > & v) {
double s_x_y = 0;
double s_x = 0;
double s_y = 0;
double s_x2 = 0;
for (int i = 0; i < v.size(); i++) {
s_x_y += v[i].first * v[i].second;
s_x += v[i].first;
s_y += v[i].second;
s_x2 += v[i].first * v[i].first;
}
double t1 = s_y * s_x - v.size() * s_x_y;
double t2 = s_x * s_x - v.size() * s_x2;
double a0 = t2 == 0 ? 0 : t1 / t2;
t1 = s_x_y - a0 * s_x2;
t2 = s_x;
double a1 = t2 == 0 ? 0 : t1 / t2;
return std::make_pair(a0, a1);
}
This problem can be resolved using dynamic programming.
int Dp(std::string & str) {
int n = str.size();
int rs = 0;
std::vector<std::vector<int> > dp(n, std::vector<int>(n, 0));
for (int k = 0; k < n; k++) {
for (int i = 0; i < n - k; i++) {
if (k == 0) dp[i][i + k] = 1;
else if (k == 1) dp[i][i + k] = str[i] == str[i + k] ? 1 : 0;
else {
if (dp[i + 1][i + k - 1] == 1 && str[i] == str[i + k]) dp[i][i + k] = 1;
}
if (dp[i][i + k] == 1) rs++;
}
}
return rs;
}
void Trace(std::vector<std::vector<int> > & rs, std::vector<int> & path, int c, int t) {
if (c == t) rs.push_back(path);
if (c >= t) return;
for (int i = 1; i < t; i++) {
path.push_back(i);
Trace(rs, path, c + i; t);
path.pop_back();
}
}
void Trace(std::vector<std::string> & rs, std::string cur, int left, int right, int n) {
if (left == n) {
cur.append(n - right, ')');
rs.push_back(cur);
} else {
Trace(rs, cur + "(", left + 1, right, n);
if (left > right) {
Trace(rs, cur + ")", left, right + 1, n);
}
}
}
std::string Add(std::string & str1, std::string & str2) {
int m = str1.size();
int n = str2.size();
int i = m - 1;
int j = n - 1;
int c = 0;
std::string rs(std::max(m, n), '0');
int k = rs.size() - 1;
while (i >= 0 || j >= 0 || c >0) {
int t = c;
if (i >= 0) t += str1[i--] - '0';
if (j >= 0) t += str2[j--] - '0';
c = t / 2;
t = t % 2;
if (k >= 0) rs[k--] = t + '0';
else rs.insert(rs.begin(), t + '0');
}
return rs;
}
- guoliqiang2006 January 05, 2014