问题描述

小C在学习二进制运算，他了解到每个非负整数都有其二进制表示。例如，整数 5 可以被表示为二进制 "101"，整数 11 可以被表示为二进制 "1011"，并且除了 N = 0 外，任何二进制表示中都不含前导零。

二进制的反码表示是将每个 1 变为 0，每个 0 变为 1。例如，二进制数 "101" 的二进制反码为 "010"。现在小C想知道，给定一个十进制数 N，它的二进制反码对应的十进制数是多少。

测试样例

样例1：

输入：N = 5
输出：2

样例2：

输入：N = 10
输出：5

样例3：

输入：N = 0
输出：1

代码：

int solution(int N) {
    if (N == 0) {
        return 1;
    }
    int bits = std::log2(N) + 1;
    std::bitset<32> binary(N);
    std::bitset<32> inverted = ~binary;
    int result = (inverted.to_ulong() & ((1 << bits) - 1));
    return result;
}

解释

• std::log2(N) + 1:

  • 计算 N 的二进制位数。

• std::bitset<32> binary(N);:

  • 这行代码将整数 N 转换为一个 32 位的二进制表示。

• std::bitset<32> inverted = ~binary;:

  • 这行代码对 binary 进行按位取反操作，得到 inverted。

• int result = inverted.to_ulong();:

  • 这行代码将 inverted 转换回无符号长整型。

• (1 << bits) - 1:

  • 生成一个掩码，只保留低 bits 位。

• inverted.to_ulong() & ((1 << bits) - 1):

  • 只取 inverted 的低 bits 位，忽略高位部分。

问题描述

小R有nn部电脑，每部电脑的电池容量分别为aiai​。她可以使用两种不同的充电方式来给电脑充电：

1. 普通充电：每单位时间为电脑充电xx单位的电量。
2. 闪充：每单位时间为电脑充电4x4x单位的电量。

现在，所有电脑的电量都为零。小R希望使用闪充给所有电脑充满电，计算她需要的总充电时间。请保留结果的小数点后两位。

测试样例

样例1：

输入：n = 4 ,x = 1 ,a = [2, 3, 4, 5]
输出：'3.50'

样例2：

输入：n = 3 ,x = 2 ,a = [4, 6, 8]
输出：'2.25'

样例3：

输入：n = 2 ,x = 1 ,a = [10, 5]
输出：'3.75'

代码：

string solution(int n, int x, vector<int> a) {
    int res = 0;
    for (int i = 0; i < n; i ++) res += a[i];
    double ans = 1.0 * res / (x * 4); 
    ostringstream oss;
    oss << fixed << setprecision(2) << ans;
    return oss.str();
}

解释：

1. 返回值问题：使用 ostringstream 将浮点数格式化为保留两位小数的字符串，并返回该字符串。
2. 浮点数格式化：使用 iomanip 库中的 fixed 和 setprecision 来格式化浮点数。

问题描述

小U计划进行一场从地点A到地点B的徒步旅行，旅行总共需要 M 天。为了在旅途中确保安全，小U每天都需要消耗一份食物。在路程中，小U会经过一些补给站，这些补给站分布在不同的天数上，且每个补给站的食物价格各不相同。

小U需要在这些补给站中购买食物，以确保每天都有足够的食物。现在她想知道，如何规划在不同补给站的购买策略，以使她能够花费最少的钱顺利完成这次旅行。

• M：总路程所需的天数。
• N：路上补给站的数量。
• p：每个补给站的描述，包含两个数字 A 和 B，表示第 A 天有一个补给站，并且该站每份食物的价格为 B 元。

保证第0天一定有一个补给站，并且补给站是按顺序出现的。

测试样例

样例1：

输入：m = 5 ,n = 4 ,p = [[0, 2], [1, 3], [2, 1], [3, 2]]
输出：7

样例2：

输入：m = 6 ,n = 5 ,p = [[0, 1], [1, 5], [2, 2], [3, 4], [5, 1]]
输出：6

样例3：

输入：m = 4 ,n = 3 ,p = [[0, 3], [2, 2], [3, 1]]
输出：9

代码：

int solution(int m, int n, std::vector<std::vector<int>> p) {
    // 在末尾添加一个虚拟站点表示终点，价格设为0（方便处理，但不会实际购买）
    p.push_back({m, 0});
    int totalCost = 0;
    int currentIndex = 0; // 当前站点索引
    while (currentIndex < p.size() - 1) { // 最后一个虚拟站点不作为实际购买点
        int currentDay = p[currentIndex][0];
        int currentPrice = p[currentIndex][1];
        int nextIndex = currentIndex + 1;
        // 找到下一个比当前站价格低的站点或者终点
        while (nextIndex < p.size() && p[nextIndex][1] >= currentPrice) {
          nextIndex++;
        }
        // 如果未找到更便宜的，nextIndex 会指向虚拟终点站
        if (nextIndex == p.size()) {
          nextIndex = p.size() - 1;
        }
        int nextDay = p[nextIndex][0];
        // 计算从当前站到目标站之间需要的天数差
        int daysNeeded = nextDay - currentDay;
        // 在当前站购买足够的食物以覆盖到下一个更便宜的站或终点
        totalCost += daysNeeded * currentPrice;
        // 将当前站点移动到找到的更便宜的站点
        currentIndex = nextIndex;
    }
    return totalCost;
}

tag：
贪心

思路：
用贪心的策略，每次都找一个花费比当前补给站少的点，然后买刚好到那个补给站的食物。然后将当前的位置更新到那个补给站，直到到达终点。

问题描述

小S正在帮助她的朋友们建立一个搜索引擎。为了让用户能够更快地找到他们感兴趣的帖子，小S决定使用倒排索引。倒排索引的工作原理是：每个单词都会关联一个帖子ID的列表，这些帖子包含该单词，且ID按从小到大的顺序排列。
例如，单词“夏天”可能出现在帖子1、帖子3和帖子7中，那么这个单词的倒排链就是 [1, 3, 7]。如果用户想同时找到包含“夏天”和“海滩”的帖子，小S需要找出两个倒排链的交集，且将结果按照从大到小的顺序输出。现在，给定两个单词的倒排链数组 a 和 b，请你帮助小S找出同时包含这两个单词的帖子ID，并按从大到小的顺序返回结果。

测试样例

样例1：

输入：a = [1, 2, 3, 7], b = [2, 5, 7]
输出：[7, 2]

样例2：

输入：a = [1, 4, 8, 10], b = [2, 4, 8, 10]
输出：[10, 8, 4]

样例3：

输入：a = [3, 5, 9], b = [1, 4, 6]
输出：[]

样例4：

输入：a = [1, 2, 3], b = [1, 2, 3]
输出：[3, 2, 1]

思路：
通过迭代器逐个比较a和b两个vector中的值，当发现一样就放到答案C中，如果a的值大于b的值就让b的迭代器++，反之如果a的值小于b的值就让a的迭代器++，当有一个vector被遍历完时while循环结束，使用reverse函数反转vector然后返回。

代码：

vector<int> solution(vector<int>& a, vector<int>& b) {
    vector<int> C;
    auto A = a.begin(), B = b.begin();
    while(A != a.end() && B != b.end())
    {
        if(*A == *B) C.push_back(*A), ++A, ++B;
        else if (*A > *B) ++B;
        else ++ A;
    }
    reverse(C.begin(), C.end());
    return C;
}

ps：我发现稀土掘金的简单题都好有意思，可以学到挺多stl容器的用法。

问题描述
小M想要通过查看往届游戏比赛的排名来确定自己比赛的目标分数。他希望找到往届比赛中排名第三的分数，作为自己的目标。具体规则如下：

如果分数中有三个或以上不同的分数，返回其中第三大的分数。
如果不同的分数只有两个或更少，那么小M将选择最大的分数作为他的目标。
请你帮小M根据给定的分数数组计算目标分数。

测试样例
样例1：

输入：n = 3,nums = [3, 2, 1]
输出：1

样例2：

输入：n = 2,nums = [1, 2]
输出：2

样例3：

输入：n = 4,nums = [2, 2, 3, 1]
输出：1

题解：

int solution(int n, std::vector<int> nums) {
    set<int> uniqueNums(nums.begin(), nums.end());
    if (uniqueNums.size() < 3) return *uniqueNums.rbegin();
    auto it = uniqueNums.rbegin();
    it ++;
    it ++;
    return *it;
}

这里主要用到了set的去重和排序。set是从小到大排，所以为了拿到最大值用来 rbegin() 这个反向迭代器。因为std::set 的迭代器是双向迭代器所以没有 += -= 这种操作。

双向迭代器：只支持单步的前进和后退操作，即使用 ++it 或 --it。它们不支持像 += 或 -= 这样的算术操作。

还有一个用法很有意思就是 set<int> uniqueNums(nums.begin(), nums.end()); 可以通过给set传一个范围（vector）来创建set。同样的用法在vector也有，例如：

std::vector<int> vec(uniqueNums.begin(), uniqueNums.end());
// 现在可以使用随机访问操作
return vec[vec.size() - 3];