Derolol Blog

leetcode274 H 指数

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。 根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且 至少 有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值，h 指数 是其中最大的那个。

题解

int hIndex(vector<int>& citations) {
        sort(citations.begin(), citations.end());
        int h = 0, i = citations.size() - 1;
        while (i >= 0 && citations[i] > h) {
            h++;
            i--;
        }
        return h;
    }

给定数组求组合

leetcode39 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 对于给定的输入，保证和为 target 的不同组合数少于 150 个。

思路

题目要求得到所有组合，而不是值。所以考虑通过递归和回溯的方式得到不用的组合 组成元素和数量相同的两个组合为同一种组合，所以在递归的时候需要传递当前的候选值范围 由于有目标值的要求，可以通过排序剪枝不可能的组合

class Solution {
private:
    vector<vector<int>> ret;
public:

    void getSum(vector<int>& candidates, int target, int start, int sum, vector<int>& host) {
        // 若满足条件则记录
        if (sum == target) {
            ret.push_back(host);
            return;
        }
        // 从取值起始点遍历候选值
        for (int i = start, num = candidates.size(); i < num; i ++) {
            // 如果加上最小值都超过目标条件，那么可以直接结束遍历
            if (sum + candidates[i] > target) break;
            // 加入当前值到组合中
            host.push_back(candidates[i]);
            // 通过罗列自身及之后的候选值构建满足条件的组合
            getSum(candidates, target, i, sum + candidates[i], host);
            // 回溯组合
            host.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<int> v;
        getSum(candidates, target, 0, 0, v);
        return ret;
    }
};