发表于 | 分类于 | 阅读次数:
字数统计: 242 | 阅读时长 ≈ 1 
1
2
3
4
5
6
7
8
9
10
11
12
13
#include<stdio.h>

int main() {
    int a[] = {1, 1, 2, 2, 3, 3, 4, 4, 5};
    int sz = sizeof(a) / sizeof(a[0]);
    int i = 0;
    int x = 0;
    for (i = 0; i < sz; i++) {
        x ^= a[i];    //将所有的数异或一下
    }
    printf("%d\n", x);
    return 0;
}

任何一个数字 异或它自己都等于0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<stdio.h>

int main() {
    int a[] = {1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7};
    int i = 0;
    int sz = sizeof(a) / sizeof(a[0]);
    int n = 0;
    int pos = 0;
    int x = 0;
    int y = 0;
    for (i = 0; i < sz; i++) {
        n ^= a[i];       //将所有的数异或 得到 6^7 的结果
    }
    for (i = 0; i < 32; i++) {
        if (((n >> i) & 1) == 1) {
            pos = i;   //找到 6^7 的二进制数中为1的一位
            break;
        }
    }
    for (i = 0; i < sz; i++)    //开始分组
    {
        if (((a[i] >> pos) & 1) == 1) {
            x ^= a[i];    //得到一个数
        } else {
            y ^= a[i];       //得到另一个数
        }
    }
    printf("%d  %d\n", x, y);
    return 0;
}

发表于 | 分类于 | 阅读次数:
字数统计: 212 | 阅读时长 ≈ 1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
n = len(prices)
if n < 2:
    return 0
# k is big enougth to cover all ramps.
if k >= n / 2:
    return sum(i - j
               for i, j in zip(prices[1:], prices[:-1]) if i - j > 0)
globalMax = [[0] * n for _ in xrange(k + 1)]
for i in xrange(1, k + 1):
    # The max profit with i transations and selling stock on day j.
    localMax = [0] * n
    for j in xrange(1, n):
        profit = prices[j] - prices[j - 1]
        localMax[j] = max(
            # We have made max profit with (i - 1) transations in
            # (j - 1) days.
            # For the last transation, we buy stock on day (j - 1)
            # and sell it on day j.
            globalMax[i - 1][j - 1] + profit,
            # We have made max profit with (i - 1) transations in
            # (j - 1) days.
            # For the last transation, we buy stock on day j and
            # sell it on the same day, so we have 0 profit, apparently
            # we do not have to add it.
            globalMax[i - 1][j - 1],  # + 0,
            # We have made profit in (j - 1) days.
            # We want to cancel the day (j - 1) sale and sell it on
            # day j.
            localMax[j - 1] + profit)
        globalMax[i][j] = max(globalMax[i][j - 1], localMax[j])
return globalMax[k][-1]

发表于 | 分类于 | 阅读次数:
字数统计: 315 | 阅读时长 ≈ 1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {

        // Step 1: Find out all profit opportunities            
        vector<int> profits;
        stack<pair<int, int>> vps; // valley-peak pairs
        
        int v;
        int p = -1;
        for (;;) {
            // find next valley-peak pair
            for (v = p+1; (v+1 < prices.size()) && (prices[v] >= prices[v+1]); ++v);
            for (p = v  ; (p+1 < prices.size()) && (prices[p] <= prices[p+1]); ++p);
            
            if (v == p) { // v==p means that both v and p reach the end of the array
                break;
            }
            
            // Consider two transactions (v1, p1) (back of the stack) and (v2, p2) (the new-found).
            // If prices[v1] >= prices[v2], 
            // it is meaningless to combine the two transactions.
            // Save of profit of (v1, p1), and pop it out of the record.
            while ((!vps.empty()) && (prices[v] <= prices[vps.top().first])) {
                profits.push_back(prices[vps.top().second] - prices[vps.top().first]);
                vps.pop();
            }
            
            // If prices[v1]<prices[v2] and prices[p1]<prices[p2], 
            // then it is meaningful to combine the two transactions
            // update (v1, p1) to (v1, p2), and save the profit of (v2, p1)
            while ((!vps.empty()) && (prices[p] >= prices[vps.top().second])) {
                profits.push_back(prices[vps.top().second] - prices[v]);
                v = vps.top().first;
                vps.pop();
            }
            
            // save the new-found valley-peak pair
            vps.emplace(v, p);
        }
        
        // save all remaining profits
        while (!vps.empty()) {
            profits.push_back(prices[vps.top().second] - prices[vps.top().first]);
            vps.pop();
        }
        
        // Step 2: Calculate the k highest profits
        int ret;
        if (profits.size() <= k) {
            ret = accumulate(profits.begin(), profits.end(), 0);
        } else {
            nth_element(profits.begin(), profits.end() - k, profits.end());
            ret = accumulate(profits.end() - k, profits.end(), 0);
        }
        return ret;
    }
};

发表于 | 分类于 | 阅读次数:
字数统计: 51 | 阅读时长 ≈ 1 
1
2
3
4
5
6
7
8
9
int total = 0;

//遍历所有交易日
for (int i = 0; i < prices.length - 1; i++) {
    //只要是后一天比前一天贵,就卖出
    if (prices[i + 1] > prices[i]) total += prices[i + 1] - prices[i];
}

return total;

发表于 | 分类于 | 阅读次数:
字数统计: 125 | 阅读时长 ≈ 1

这题使用双指针法

1
2
3
4
5
6
7
8
9
10
def maxProfit(self, prices):
    """
    :type prices: List[int]
    :rtype: int
    """
    max_profit, min_price = 0, float('inf')
    for price in prices:
        min_price = min(min_price, price)
        max_profit = max(max_profit, price - min_price)
    return max_profit
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxPro = 0;
        int minPrice = INT_MAX;
        for(int i = 0; i < prices.size(); i++){
            minPrice = min(minPrice, prices[i]);
            maxPro = max(maxPro, prices[i] - minPrice);
        }
        return maxPro;
    }
};
1
2
3
4
5
6
7
8
9
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res=0,buyp=INT_MAX;
        for(auto i:prices) 
            (i<buyp)?(buyp=i):(res=max(i-buyp,res));
        return res;
    }
};

更加简洁的cpp