alg-greedy

发表于 | 更新于: | 分类于

122 买卖任意次数的股票

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

熟练
只要后一天涨就买。

1
2
3
4
5
6
7
8
9
10
public int maxProfit(int[] prices) {
    int n = prices.length;
    int rst = 0;
    for(int i = 1;i<n;i++){
        if(prices[i]-prices[i-1]>0){
            rst += prices[i]-prices[i-1];
        }
    }
    return rst;
}

45. Jump Game II

Input: [2,3,1,1,4]
Output: 2

1
2
3
4
5
6
7
8
9
10
11
12
13
public int jump(int[] nums) {
    int cur = 0;
    int cnt = 0;
    int max = nums[0];
    for(int i = 0;i<nums.length;i++){
        if(cur<i){
            cur=max;
            cnt++;
        }
        max = Math.max(max,i+nums[i]);
    }
    return cnt;
}

41克以下的宝石

（可能是41克以下不包括41克的任意重量），
他只能携带一个天平和【四个砝码】去称重，请问他会携带哪些重量的砝码？
A1 3 9 27
B1 10 20 30 40
C1 4 16 32
D1 3 10 21

3、9、27可以组成3的倍数，多一克可以加1，少一克可以减1 选A
带了四个砝码，即可以用四个进制位表示。设进制数为n，那么n^0+n^1+n^2+n^3>=40。用等比数列的公式可以求得n=3。所以四个砝码分别是1(3^0)、3(3^1)、9(3^2)、27(3^3)。选A

德·梅齐里亚克的砝码问题
https://baike.baidu.com/item/%E5%BE%B7%C2%B7%E6%A2%85%E9%BD%90%E9%87%8C%E4%BA%9A%E5%85%8B%E7%9A%84%E7%A0%9D%E7%A0%81%E9%97%AE%E9%A2%98
40磅的砝码，由于跌落在地而碎成4块.后来，称得每块碎片的重量都是整磅数，而且可以用这4块来称从1至40磅之间的任意整数磅的重物.
问这4块砝码碎片各重多少？

lg1658

现在你手上有N种不同面值的硬币，每种硬币有无限多个。为了方便购物，你希望带尽量少的硬币，但要能组合出1到X之间的任意值。

20 4
1 2 5 10

5


如果已经凑出x以内的数(1)，枚举a[i]找到<=x+1的最大数则1-x+a[i]都可以凑出

从1开始凑，然后凑2，用面值最大的(1,2)凑。
然后可以凑到的最大值为3，下面凑4，用面值最大的(1,2,2)凑。
当前可以凑到最大值是5，下次凑6，用面值最大的(1,2,2,5)凑。
当前可以凑到的最大为10,下次凑11，用面值最大的(1,2,2,5,10)凑。
可以凑的的总数>20 ok

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Arrays.sort(coins);
if(coins[0]!=1) System.out.println(-1);
else{
    int cnt = 0;
    //凑最大面值
    int sum = 0;
    while (sum < x){
        int i;
        // 关键
        for (i =n-1; i>=0  ; i--) {
            if (coins[i] <= sum + 1) break;
        }
            cnt++;
            sum+=coins[i];
    }
    System.out.println(cnt);
}