如何用C++實現比特位計數和買賣股票的最佳時機

如何用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

希望這篇文章對你有所幫助！