Google 电面两道算法题

 2014.11. from 1point3

1.找出missing number 范围
number范围[0,99]

input: [0, 1, 2,50 , 52, 75]

output: "3-49,51,53-74,76-99"

2. 找出一个数由最少几个平方的和的组成
例子：
input： 14    output:  9 ,4 , 1  虽然也能由1 +1 +....+1组成 但长度是14 不是最优解

input:   50     ouput :  25, 25

Ans:
1. idea from the solution the leetcode problem: Longest Consecutive Sequence
use the map property that the key is sorted

 int merge(map<int, int> &amap, int left, int right) {
    int upper = right + amap[right] - 1;
    int lower = left - amap[left] + 1;
    int len = upper - lower + 1;
    amap[upper]= len;
    amap[lower]= len;
    return len;
}

//the range is [start, end]
int missingRanges(vector<int> & a,int start,int end) {
    map<int, int> amap;
    for (int i=0;i<a.size();i++) {
        if (amap.count(a[i])) continue;
        amap[a[i]]=1;
        if (amap.count(a[i]-1)) {
            merge(amap, a[i]-1, a[i]);
        }
        if (amap.count(a[i]+ 1) ){
            merge(amap, a[i], a[i]+1);
        }
    }

    for(auto it=amap.begin();it!=amap.end();it++){
        if(start==it->first){
            start=it->first+it->second;
        }
        else if(start<it->first){
            cout<<start<<"-"<<it->first-1<<", ";
            start=it->first+it->second;
        }
    }
    if(start<=end)
        cout<<start<<"-"<<end<<"\n";
    return 0;
}

2. dp, first one
int minNumber1(int num){
    vector<int> dp(num+1);
    dp[0]=0;
    for(int i=1;i<=(int)(sqrt((double)num));i++)
        dp[i*i]=1;
    for(int i=2;i<=num;i++){
        if(dp[i]!=0) continue;
        int amin=INT_MAX;
        for(int k=1;k<=i/2;k++){
            amin=min(amin,dp[k]+dp[i-k]);
            if(amin==2)
                break;
        }
        dp[i]=amin;
    }
    return dp[num];
}

//another flavor, faster.
int minNumber2(int n){
    vector<int> f(n+1);
    f[0] = 0;
    f[1] = 1;
    for (int i = 2; i <= n ; i++){
        int amin = INT_MAX;
        for(int k=1;k*k<=i;k++){
            int cur = 1 + f[i-k*k];
            amin = min(amin, cur);
        }
        f[i] = amin;
    }
    return f[n];
}