贪心算法相关题目
1.1 动态规划
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];
Arrays.fill(dp, -1);
dp[0] = 0;
for (int i=1; i<=amount; i++) {
int m = Integer.MAX_VALUE;
for (int coin: coins) {
if (i-coin>=0 && dp[i-coin]>-1) {
m = Math.min(dp[i-coin]+1, m);
}
}
dp[i] = m==Integer.MAX_VALUE?-1:m;
}
return dp[amount];
}
解法一：贪心
每个都用匹配刚好满足胃口的饼干匹配。
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int res = 0;
for (int i=0, j=0; i<g.length; i++) {
for (;j<s.length; j++) {
if (g[i]<=s[j]) {
res++;
j++;
break;
}
}
}
return res;
}
解法一：动态规划
dp[i][0] 不持有股票；dp[i][1] 持有股票
public int maxProfit(int[] prices) {
int m = prices.length;
int[][] dp = new int[m][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i=1; i<m; i++) {
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]+prices[i]);
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0]-prices[i]);
}
return dp[m-1][0];
}
解法二：贪心算法
public int maxProfit(int[] prices) {
int maxPrice = 0;
for (int i=1; i<prices.length; i++) {
if (prices[i]>prices[i-1]) {
maxPrice += prices[i]-prices[i-1];
}
}
return maxPrice;
}
解法一：将所有可达路径标为true
public boolean canJump(int[] nums) {
int n = nums.length;
boolean[] dp = new boolean[n];
dp[0] = true;
for (int i=0; i<n; i++) {
for (int j=i+1; j<=i+nums[i] && j<n; j++) {
if (dp[i]) {
dp[j] = true;
}
}
}
return dp[n-1];
}
解法二：贪心算法(从后往前贪心求解)
public boolean canJump(int[] nums) {
if (nums==null) return false;
int endReachable = nums.length-1;
for (int i=endReachable; i>=0; i--) {
if (nums[i]+i>=endReachable) {
endReachable = i;
}
}
return endReachable==0;
}
解法一：贪心
每次用最优解决当前问题。
public boolean lemonadeChange(int[] bills) {
int b5=0, b10=0, b20=0;
for (int i=0; i<bills.length; i++) {
if (bills[i]==5) b5++;
if (bills[i]==10) {
b10++;
if (b5==0) return false;
else b5--;
}else if (bills[i]==20) {
b20++;
if (b10>0 && b5>0) {
b10--;
b5--;
}else if (b5>3) {
b5 -= 3;
}else {
return false;
}
}
}
return true;
}
解法一：方向的确定
public int robotSim(int[] commands, int[][] obstacles) {
Set<Pair> set = new HashSet<>();
for (int k=0; k<obstacles.length; k++) {
int[] a = obstacles[k];
set.add(new Pair(a[0], a[1]));
}
int[] dx = {0, 1, 0, -1};
int[] dy = {1, 0, -1, 0};
int dir = 0, x = 0, y = 0;
int res = 0;
for (int i=0; i<commands.length; i++) {
int v = commands[i];
if (v==-1) {
dir = (dir+1) % 4;
}else if (v==-2) {
dir = (dir+3) % 4;
}else {
for (int k=0; k<v; k++) {
int x2 = x + dx[dir];
int y2 = y + dy[dir];
if (!set.contains(new Pair(x2, y2))) {
x = x2;
y = y2;
res = Math.max(res, x2*x2 + y2*y2);
}else {
break;
}
}
}
}
return res;
}
private class Pair {
private int x;
private int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
public boolean equals(Object o) {
Pair other = (Pair)o;
return this.x==other.x && this.y==other.y;
}
public int hashCode() {
return Objects.hash(x, y);
}
}
解法一：BFS+记忆化搜索
public int jump(int[] nums) {
Deque<Integer> deque = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
deque.offer(0);
visited.add(0);
int result = 0;
while (!deque.isEmpty()) {
int n = deque.size();
for (int i=0; i<n; i++) {
int k = deque.pop();
if (k==nums.length-1) return result;
for (int j=nums[k];j>=1; j--) {
if (k+j<nums.length && !visited.contains(k+j)) {
visited.add(k+j);
deque.offer(k+j);
}
}
}
result++;
}
return result;
}
解法二：贪心：从后往前推
public int jump(int[] nums) {
int positation = nums.length - 1;
int steps = 0;
while (positation>0) {
for (int i=0; i<positation; i++) {
if (nums[i]+i>=positation) {
positation = i;
steps++;
}
}
}
return steps;
}
解法三：贪心：正向推
public int jump(int[] nums) {
int positation = 0;
int steps = 0;
int end = 0;
for (int i=0; i<nums.length-1; i++) {
positation = Math.max(positation, nums[i]+i);
if (i==end) {
steps++;
end = positation;
}
}
return steps;
}
|