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 | public int maxProfit(int[] prices) { |
45. Jump Game II
Input: [2,3,1,1,4]
Output: 2
1 | public int jump(int[] nums) { |
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 | Arrays.sort(coins); |