见 Leetcode sqrt题目, 主要就是注意边界, sqrt(8) 返回的结果必须是2, 而不是3
给定二叉树的中序和先序遍历, 在不建树的情况下, 输出后续遍历
有10亿个长Url, 需要转换成短网址, 短网址越短越好. 每天有几百亿的访问, 架构设计需要尽可能高效, 稳定, 可扩展...
//给定两个日期, 求他们相差的天数 | |
bool leapyear(int y) { | |
return (y%4 == 0) && (0 != y%100 || y%400 == 0); | |
} | |
int days(int y, int m, int d) { | |
//static int mt[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; | |
static int mt[] = {0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334}; | |
int x = y-1; | |
int ans = x*365 + x/4 - x/100 + x/400; | |
ans += mt[m-1]; | |
ans += d; | |
if(leapyear(y) && m>2) { | |
ans ++; | |
} | |
return ans; | |
} | |
int days_diff(int y1, int m1, int d1, int y2, int m2, int d2) { | |
return days(y1, m1, d1) - days(y2, m2, d2); | |
} |
//题目:设计一个算法,把一个含有N个元素的数组循环右移K位,要求时间复杂度为O(N),且空间复杂度为O(1)。 | |
int gcd(int m, int n) { | |
if(m<n) { | |
swap(m,n); | |
} | |
while(n) { | |
int tmp = m%n; | |
m = n; | |
n = tmp; | |
} | |
return m; | |
} | |
void rightmove(vector<int> &vec, int k) { | |
if(vec.size() && k >= vec.size()) { | |
k %= vec.size(); | |
} | |
if(vec.size() <= 1 || k < 1) { | |
return; | |
} | |
int M = gcd(vec.size(), k); | |
for(int i=0;i<M;i++) { | |
int tmp = vec[i]; | |
for(int j=(i-k)%vec.size(); j!=i; j=(j-k)%vec.size()) { | |
swap(tmp, vec[j]); | |
} | |
vec[i] = tmp; | |
} | |
return; | |
} |
void rightmove2(vector<int> &vec, int k) { | |
if(vec.size() && k >= vec.size()) { | |
k %= vec.size(); | |
} | |
if(vec.size() <= 1 || k < 1) { | |
return; | |
} | |
int m, n; //the only two variable | |
//calc m=gcd(vec.size(), k); | |
m=vec.size(); | |
n=k; | |
if(m<n) { | |
//swap(m,n); | |
m ^= n; | |
n ^= m; | |
m ^= n; | |
} | |
while(n) { | |
m = m%n; | |
if(m==0) { | |
m=n; | |
break; | |
} | |
n = n%m; | |
} | |
//eqaul to: for(int i=0;i<m;i++) | |
for(m--;m>=0;m--) { | |
n = m; | |
do { // vec[n] swap with it left var, so that it's left var shift to right | |
//swap(vec[(n+k)%vec.size()], vec[n]); | |
vec[(n+k)%vec.size()] ^= vec[n]; | |
vec[n] ^= vec[(n+k)%vec.size()]; | |
vec[(n+k)%vec.size()] ^= vec[n]; | |
n=(n+k)%vec.size(); | |
}while( (n+k)%vec.size() > m ); | |
//do swap only when next shift is larget than the start point | |
} | |
return; | |
} |