科大讯飞笔试题

1贪心

/*
* 爆炸
1234
[10,16,6,66,99,963]
[4,6,-1,18,27,243]
*/

    vector<int> minimumNumber(vector<int>& target) {
        // write code here
        vector<int> result;
        //贪心算法
        for (int i = 0; i < target.size(); i++) {
            int num = target[i];
            if (num < 10) {
                result.push_back(-1);
                continue;
            }
            int count = 4;
            num = num - 10;
            int yushu = num % 4;
            num = num - yushu;
            count += num / 4;
            if (yushu > 0) {
                count += 1;
            }
            result.push_back(count);
        }
        return result;
    }

2三角形，判断

1）剪枝一次可以过95~80的样子~

bool is_tri(vector<int> &length,int x, int y, int z, vector<int> &length2) {

    if (length[x]  == length[z]) {
        return false;
    }
    if (length2[x] == (length2[y] + length2[z])) {
        return false;
    }
    if (length[x] + length[y] <= length[z] || length[x] + length[z] <= length[y] || length[z] + length[y] <= length[x]) {
        return false;
    }

    return true;
}
int happyTriangle(vector<int>& length) {
    // write code here
    int result = 0;
    vector<int> length2;
    int size = length.size();
    sort(length.begin(), length.end());
    reverse(length.begin(), length.end());
    for (int x = 0; x < size; x++) {
        length2.push_back(length[x] * length[x]);
    }
    vector<vector<int>> res;
    for (int x = 0; x < size-2; x++) {
        for (int y = x + 1; y < size-1; y++) {
            for (int z = y + 1; z < size; z++) {
                if (length[z] + length[y] <= length[x]) {
                    break;
                }
                    if (is_tri(length,x,y,z, length2) == true) {
                        result += 1;
                    }
            }
        }
    }
    return result;
}

2）精简了判断条件，省去函数调用，过了

 int happyTriangle(vector<int>& length) {
        // write code here
        int result = 0;
        vector<int> length2;
        int size = length.size();
        sort(length.begin(), length.end(),greater());
                //这里算平方会重复计算，提前算出来一遍
        for (int x = 0; x < size; x++) {
            length2.push_back(length[x] * length[x]);
        }    
        for (int x = 0; x < size - 2; x++) {
            for (int y = x + 1; y < size - 1; y++) {
                //if (2 * length[y] <= length[x]) {
                //    break;
                //}
                for (int z = y + 1; z < size; z++) {
                    //剪枝
                    if (length[z] + length[y] <= length[x]) {
                        break;
                    }
                                        //等边
                    if (length[x] == length[z]) {
                        continue;
                    }
                                        //直角三角形
                    if (length2[x] == (length2[y] + length2[z])) {
                        continue;
                    }

                    result += 1;
                }
            }
        }        
        return result;
    }

#科大讯飞##笔经#