date_diff 题目：设计一个算法，把一个含有N个元素的数组循环右移K位，要求时间复杂度为O（N），且空间复杂度为O（1）。

date_diff.cc

//给定两个日期, 求他们相差的天数
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);
}

problems.md

sqrt

见 Leetcode sqrt题目, 主要就是注意边界, sqrt(8) 返回的结果必须是2, 而不是3

中序 + 先序遍历 求 后续遍历

给定二叉树的中序和先序遍历, 在不建树的情况下, 输出后续遍历

TinyUrl 设计

有10亿个长Url, 需要转换成短网址, 短网址越短越好. 每天有几百亿的访问, 架构设计需要尽可能高效, 稳定, 可扩展...

right_shift_array.cc

//题目：设计一个算法，把一个含有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;
}

right_shift_array_2.cc

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;
}