如何用C++实现比特位计数和买卖股票的最佳时机

在编程中，我们经常会遇到一些经典的算法问题，比如比特位计数和买卖股票的最佳时机。本文将介绍如何用C++实现这两个问题的解决方案。

1. 比特位计数

问题描述

给定一个非负整数 n，要求计算从 0 到 n 的每个整数的二进制表示中 1 的个数，并返回一个数组。

示例

输入: 5
输出: [0, 1, 1, 2, 1, 2]
解释:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

解决方案

我们可以使用动态规划来解决这个问题。对于一个整数 i，它的二进制表示中 1 的个数可以通过以下方式计算：

• 如果 i 是偶数，那么 i 的二进制表示中 1 的个数与 i/2 的二进制表示中 1 的个数相同。
• 如果 i 是奇数，那么 i 的二进制表示中 1 的个数等于 i-1 的二进制表示中 1 的个数加 1。

基于这个规律，我们可以写出以下代码：

#include <vector>

std::vector<int> countBits(int n) {
    std::vector<int> result(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        result[i] = result[i >> 1] + (i & 1);
    }
    return result;
}

代码解释

• result[i] = result[i >> 1] + (i & 1);：i >> 1 相当于 i / 2，i & 1 相当于 i % 2。如果 i 是偶数，i & 1 为 0；如果 i 是奇数，i & 1 为 1。

2. 买卖股票的最佳时机

问题描述

给定一个数组 prices，其中 prices[i] 表示某只股票在第 i 天的价格。你只能进行一次买卖操作（即买入和卖出一只股票），设计一个算法来计算你所能获取的最大利润。

示例

输入: [7, 1, 5, 3, 6, 4]
输出: 5
解释: 在第 2 天买入（价格 = 1），在第 5 天卖出（价格 = 6），最大利润 = 6 - 1 = 5。

解决方案

我们可以使用贪心算法来解决这个问题。我们只需要找到最低的买入价格和最高的卖出价格，并且卖出时间在买入时间之后。

具体步骤如下：

1. 初始化最低价格 minPrice 为第一天的价格。
2. 初始化最大利润 maxProfit 为 0。
3. 遍历数组，更新最低价格和最大利润：
   • 如果当前价格小于 minPrice，则更新 minPrice。
   • 否则，计算当前价格与 minPrice 的差值，并更新 maxProfit。

基于这个思路，我们可以写出以下代码：

#include <vector>
#include <algorithm>

int maxProfit(std::vector<int>& prices) {
    if (prices.empty()) return 0;
    
    int minPrice = prices[0];
    int maxProfit = 0;
    
    for (int i = 1; i < prices.size(); ++i) {
        if (prices[i] < minPrice) {
            minPrice = prices[i];
        } else {
            maxProfit = std::max(maxProfit, prices[i] - minPrice);
        }
    }
    
    return maxProfit;
}

代码解释

• minPrice = prices[0];：初始化最低价格为第一天的价格。
• maxProfit = 0;：初始化最大利润为 0。
• if (prices[i] < minPrice)：如果当前价格小于最低价格，则更新最低价格。
• maxProfit = std::max(maxProfit, prices[i] - minPrice);：否则，计算当前价格与最低价格的差值，并更新最大利润。

3. 总结

本文介绍了如何用C++实现比特位计数和买卖股票的最佳时机这两个经典算法问题。通过动态规划和贪心算法，我们可以高效地解决这些问题。希望本文对你理解这些算法有所帮助。

参考代码

#include <iostream>
#include <vector>
#include <algorithm>

// 比特位计数
std::vector<int> countBits(int n) {
    std::vector<int> result(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        result[i] = result[i >> 1] + (i & 1);
    }
    return result;
}

// 买卖股票的最佳时机
int maxProfit(std::vector<int>& prices) {
    if (prices.empty()) return 0;
    
    int minPrice = prices[0];
    int maxProfit = 0;
    
    for (int i = 1; i < prices.size(); ++i) {
        if (prices[i] < minPrice) {
            minPrice = prices[i];
        } else {
            maxProfit = std::max(maxProfit, prices[i] - minPrice);
        }
    }
    
    return maxProfit;
}

int main() {
    // 测试比特位计数
    int n = 5;
    std::vector<int> bits = countBits(n);
    for (int bit : bits) {
        std::cout << bit << " ";
    }
    std::cout << std::endl;

    // 测试买卖股票的最佳时机
    std::vector<int> prices = {7, 1, 5, 3, 6, 4};
    int profit = maxProfit(prices);
    std::cout << "最大利润: " << profit << std::endl;

    return 0;
}

输出结果

0 1 1 2 1 2 
最大利润: 5

希望这篇文章对你有所帮助！