309.Best Time to Buy and Sell Stock with Cooldown
题目：
给出n天股票的价格，求买卖的最大利润。
规则：
- 可以买卖多次。但买入新股票前必须卖出旧股票
- 如果在第i天卖出股票，那第i+1天不能买入股票
分析：
使用动态规划。
len = prices.length。
定义own[]，notOwn[]。
own[i]: 在第i天持有一张股票时，前i天能获取的最大利润；
notOwn[i]: 在第i天不持有股票时，前i天能获得的最大利润；
own递推式：
如果第i天拥有股票，有两种情况。
情况1：第i-2天没有股票，第i天买入了股票
情况2：第i-1天就有股票，第i天也没有卖出
own[i]就是这两种情况的最大值：
own[i] = Max(notOwn[i - 2] - prices[i],own[i - 1]);
notOwn递推式
第i天不持有股票，也有两种情况。
情况1：第i天将前一天持有的股票卖出了，这时要求前一天没有股票
情况2：第i-1天就没有股票，第i天也没买入
notOwn[i] = Max(own[i - 1]+prices[i],notOwn[i - 1])
代码
class Solution {
public int maxProfit(int[] prices) {
if(prices == null || prices.length == 0)
return 0;
int len = prices.length;
int[] own = new int[len];
int[] notOwn = new int[len];
if(len > 0) {
own[0] = -prices[0];
notOwn[0] = 0;
}
if(len > 1) {
own[1] = -Math.min(prices[0],prices[1]);
notOwn[1] = Math.max(0,prices[1] - prices[0]);
}
for(int i = 2; i < len; i++) {
own[i] = Math.max(notOwn[i - 2] - prices[i],own[i - 1]);
notOwn[i] = Math.max(own[i - 1] + prices[i],notOwn[i-1]);
}
return Math.max(own[len-1],notOwn[len-1]);
}
}
322. Coin Change
题目
给出一个数组。数组中的数字代表硬币的面值。再给出一个目标值target。问最少用多上个硬币可以组成target的面值。每种面值的硬币使用次数不限。如果不能组成target则返回-1.
分析一
递归暴力求解。
分析二
记录中间结果再搜索。
设最少用f(i)个硬币组成钱数i。求出f(i - coins[j]) + 1的最小值
分析三
从下往上地搜索，迭代处理，不用递归，效率较高。
class Solution {
public int coinChange(int[] coins, int amount) {
if(coins == null || coins.length == 0 || amount < 0)
return -1;
// Arrays.sort(coins);
// return core(coins,amount,0,coins.length - 1,Integer.MAX_VALUE);
//记录结果再搜索
// int[] count = new int[amount];
// return coinChange(coins,amount,count);
//最优动态
int[] count = new int[amount + 1];
Arrays.fill(count,amount + 1);
count[0] = 0;
for(int i = 1; i < amount + 1; i++) {
for(int j : coins) {
if(i - j >= 0) {
count[i] = Math.min(count[i],count[i - j] + 1);
}
}
}
if(count[amount] > amount)
return -1;
return count[amount];
}
//记录结果再搜索——可以AC
// public int coinChange(int[] coins,int amount,int[] count) {
// if(amount == 0)
// return 0;
// if(count[amount - 1] != 0)
// return count[amount - 1];
// int min = Integer.MAX_VALUE;
// for(int i = 0; i < coins.length; i++) {
// int res = -1;
// if(amount - coins[i] >= 0)
// res = coinChange(coins,amount - coins[i],count);
// if(res != -1 && res < min)
// min = res;
// }
// if(min == Integer.MAX_VALUE) {
// count[amount - 1] = -1;
// } else {
// count[amount - 1] = min + 1;
// }
// return count[amount - 1];
// }
//递归暴力破解————超时
// private int core(int[] coins,int amount,int count,int index) {
// if(amount == 0)
// return count;
// if(index == -1 || minimal <= count)
// return -1;
// int t = amount / coins[index];
// int min = Integer.MAX_VALUE;
// for(int i = 0; i <= t; i++) {
// int a = core(coins,amount - coins[index] * i,count + i,index - 1);
// if(a != -1)
// min = Math.min(a,min);
// }
// if(min == Integer.MAX_VALUE)
// return -1;
// return min;
// }
}
347 Top K Frequent Elements
问题：
求出数组中出现次数最多的K个数。假设数组中有n个不重复的数，保证1<=k<=n;
要求时间复杂度不超过O(NlogN)
分析
top k问题可以使用小顶堆来实现。将所有数字加入到大顶堆中，排序规则是根据其出现次数。最后堆中保留k个元素即为所求。
使用HashMap记录每个数字的出现次数。使用getOrDefault方法，一行代码就判断了i是否在map中存在，不存在时次数初始化为1；
使用PriorityQueue作为堆，使用Lambda表达式定义Compartor的compare方法，使用在map中获取到的次数作为比较规则。
代码
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i : nums)
map.put(i,map.getOrDefault(i,0) + 1);
PriorityQueue<Integer> heap = new PriorityQueue<Integer>((a,b) -> map.get(a) - map.get(b));
for(int i : map.keySet()) {
heap.add(i);
if(heap.size() > k)
heap.poll();
}
List<Integer> list = new ArrayList<Integer>(k);
for(int i = 0; i < k; i++)
list.add(heap.poll());
Collections.reverse(list);
return list;
}
}
338. Conting Bits
题目
给定一个数字n。求0-n这n+1数字中每一个数字的二进制表示中1的个数。
分析
如果求一个数的二级制表示中1的个数。可以使用与1、2、4、8、16、……2^31依次执行相与操作，记录结果不为0的次数即为所求。这个题也可以对每个数这样求一遍。时间复杂度为O(32N)
更好的方法是：F(n) = F(n >> 1) + (n & 1)
F(n >> 1)是n除了最低位之外的1的个数。再加上(n&1)表示的最低位是否是1,就是结果了。时间复杂度为O(N)；
代码
class Solution {
public int[] countBits(int num) {
int[] ans = new int[num + 1];
for(int i = 1; i <= num; i++)
ans[i] = ans[i >> 1] + (i & 1);
return ans;
}
网友评论