终于知道为什么hr和猎头说招不到人了，这样能招到人真是奇怪。。。

码农学习联盟 · 公众号 · · 2024-05-25 21:38

正文

一网友说最近投了一个3-5年的岗位，薪酬标的是25~40k，结果面试成功之后才开出16k的薪资，让他感觉到了侮辱，最低的都给不到就不要标那么高。还有网友说： 16k不过分，但是标25-40k，面完给16k就过分了。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第77题：组合，我们来看下。

问题描述

来源：LeetCode第77题

难度：中等

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按任何顺序返回答案。

示例1：

输入：n = 4, k = 2

输出：

[

[2,4],

[3,4],

[2,3],

[1,2],

[1,3],

[1,4],

]

示例2：

输入：n = 1, k = 1

输出：[[1]]

1 <= n <= 20
1 <= k <= n

问题分析

这题返回从 1 到 n 中所有 k 个数的组合，所谓的组合也就是从数组中选择 k 个数，这种选择只是其中的一个组合。我们知道排列是有顺序的，但组合是没有顺序的，比如[1,2]和[2,1]只能算一个组合。组合选择的过程我们可以把它看作是一棵树，如下图所示：

因为每个数字在每个组合中只能选择一次，所以选择当前数字的时候，下一步只能选择他后面的数字，否则就会出现类似于[1,2]和[2,1]这种重复的组合。当选择个数达到 k 个的时候就不要再往下选了，然后把这个组合添加到最终的集合中，这是一道回溯算法问题，代码非常简单。

JAVA：

public List> combine(int n, int k) {
    List> ans = new ArrayList<>();
    dfs(ans, new ArrayList<>(k), n, k, 1);
    return ans;
}

private void dfs(List> ans, List path, int n, int k, int start) {
    if (path.size() == k) {
        ans.add(new ArrayList<>(path));
        return;
    }
    for (int i = start; i <= n; i++) {
        path.add(i);// 选择
        dfs(ans, path, n, k, i + 1);// 递归到下一层
        path.remove(path.size() - 1);// 撤销选择
    }
}

C++：

public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ans;
        vector<int> path;
        dfs(ans, path, n, k, 1);
        return ans;
    }

    void dfs(vector<vector<int>> &ans, vector<int> &path, int n, int k, int start) {
        if (path.size() == k) {
            ans.emplace_back(path);
            return;
        }
        for (int i = start; i <= n; i++) {
            path.emplace_back(i);// 选择
            dfs(ans, path, n, k, i + 1);// 递归到下一层
            path.pop_back();// 撤销选择
        }
    }

C：

终于知道为什么hr和猎头说招不到人了，这样能招到人真是奇怪。。。

正文

请到「今天看啥」查看全文