【算法刷题】Day29

2024-03-06 16:12

文章标签 算法刷题 day29

本文主要是介绍【算法刷题】Day29，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 数青蛙

在这里插入图片描述

原题链接

算法原理：

运用模拟

r，o，a，k 去查找前驱字符，是否在哈希表中
如果存在，前驱数–，当前字符++
如果不存在，返回 -1

当到 c 时，去找最后一个字符是否在哎，哈希表中惨在
如果存在，最后一个字符–，当前字符++
如果不存在，当前字符++
在这里插入图片描述

代码：

class Solution {public int minNumberOfFrogs(String croakOfFrogs) {int c = 0;int r = 0;int o = 0;int a = 0;int k = 0;char[] ch = croakOfFrogs.toCharArray();int ret = 0;for(int i = 0;i < ch.length;i++){if(ch[i] == 'c'){if(k > 0){k--;}else{ret++;}c++;}else if(ch[i] == 'r'){c--;r++;}else if(ch[i] == 'o'){r--;o++;}else if(ch[i] == 'a'){o--;a++;}else if(ch[i] == 'k'){a--;k++;}if(c < 0 || r < 0 || o < 0 || a < 0){break;}}if(c != 0 || r != 0 || o != 0 || a != 0){return -1;}return ret;}
}

class Solution {public int minNumberOfFrogs(String c) {char[] croakOfFrogs = c.toCharArray();String t = "croak";int n = t.length();int[] hash = new int[n];//数组模拟哈希表Map<Character, Integer> index = new HashMap<>();//<x这个字符，x这个字符对行的下标>for(int i = 0; i < n; i++) {index.put(t.charAt(i), i);}for(char ch : croakOfFrogs) {if(ch == t.charAt(0)) {if(hash[n - 1] != 0) {hash[n - 1]--;}hash[0]++;}else {int i = index.get(ch);if(hash[i - 1] == 0) return -1;hash[i - 1]--;hash[i]++;}}for(int i = 0; i < n-1; i++) {if(hash[i] != 0) {return -1;}}return hash[n - 1];}
}

2. 外观数列

在这里插入图片描述
原题链接

算法原理：

运用模拟
利用双指针，找到相同的数字段，解释一下即可
在这里插入图片描述

代码：

class Solution {public String countAndSay(int n) {String ret = "1";for(int i = 1; i < n; i++) {StringBuilder tmp = new StringBuilder();int len = ret.length();for(int left = 0, right = 0; right < len; ) {while(right < len && ret.charAt(left) == ret.charAt(right)) {right++;}tmp.append(Integer.toString(right - left));tmp.append(ret.charAt(left));left = right;}ret = tmp.toString();} return ret;}
}

3. 买卖股票的最佳时机 IV

在这里插入图片描述
原题链接

题干：

整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格
最多可以完成 k 笔交易
在这里插入图片描述

算法原理：

1. 状态表示：

f[i][j] 表示：第 i 天结束后，完成了 j 笔交易，此时处于「有股票」状态的最大收益；
g[i][j] 表示：第 i 天结束后，完成了 j 笔交易，此时处于「无股票」状态的最大收益。
在这里插入图片描述

2. 状态转移方程

f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i])
g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i])
在这里插入图片描述

3. 初始化

当处于第 0 天的时候，只能处于「买⼊过⼀次」的状态，此时的收益为 -prices[0] ，因此 f[0][0] = - prices[0]

为了取 max 的时候，⼀些不存在的状态「起不到⼲扰」的作⽤，我们统统将它们初始化为 -INF
（用 INT_MIN 在计算过程中会有「溢出」的⻛险，这⾥ INF 折半取0x3f3f3f3f ，足够小即可
在这里插入图片描述

4. 填表顺序

从上往下填写每一行
每一行从左往右，两个表一起填

5. 返回值

g 表的最后一行里面的最大值

代码：

class Solution {public int maxProfit(int k, int[] prices) {//1. 预处理int n = prices.length;int INF = 0x3f3f3f3f;k = Math.min(k, n / 2);int[][] f = new int[n][k + 1];int[][] g = new int[n][k + 1];for(int i = 0; i <= k; i++) {f[0][i] = g[0][i] = -INF;}f[0][0] = -prices[0];g[0][0] = 0;for(int i = 1; i < n; i++) {for(int j = 0; j <= k; j++) {f[i][j] = Math.max(f[i - 1][j],g[i - 1][j] - prices[i]);g[i][j] = g[i - 1][j];if(j >= 1) {g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + prices[i]);}}}int ret = 0;for(int i = 0; i <= k; i++) {ret = Math.max(ret, g[n-1][i]);}return ret;}
}