青田网站做服装找工作,如何做网站在网上销售,网站正能量入口,温岭网站设计2024.1.11 题目来源我的题解方法一 暴力模拟方法二 动态规划方法三 直接拼接方法四 计算组数 题目来源
力扣每日一题#xff1b;题序#xff1a;2645
我的题解
方法一 暴力模拟 直接模拟#xff0c;根据题意可知 若是abc则不用插入#xff0c;若是ab,ac,bc这需要 插入一… 2024.1.11 题目来源我的题解方法一 暴力模拟方法二 动态规划方法三 直接拼接方法四 计算组数 题目来源
力扣每日一题题序2645
我的题解
方法一 暴力模拟 直接模拟根据题意可知 若是abc则不用插入若是ab,ac,bc这需要 插入一个字符其他的则需要插入两个字符。因此使用String的替换功能先将word中的所有abc替换成 _ 然后再分别将ab,ac,bc从左到右替换成 _ 最后统计剩下的字符中 a b c的数量 时间复杂度O( n 2 n^2 n2) n是字符串的长度。除了遍历的O(n)还有替换方法内部的O(n) 空间复杂度O(1) public int addMinimum(String word) {wordword.replaceAll(abc,_);int nword.length();if(n0)return 0;int res0;while(word.contains(ab)){res;wordword.replaceFirst(ab,_);}while(word.contains(bc)){res;wordword.replaceFirst(bc,_);}while(word.contains(ac)){res;wordword.replaceFirst(ac,_);}for(int i0;iword.length();i){char chword.charAt(i);if(chachc){res2;}}return res;
}方法二 动态规划 定义dp[i]状态表示前i个字符凑成若干个abc所需插入的字符数则转移过程 若第i个字符单独在一组abc中则dp[i]dp[i-1]2若word[i]word[i-1]则表示word[i]和word[i-1]在一组abc中则dp[i]dp[i-1]-1 时间复杂度O(n) 空间复杂度O(n) public int addMinimum(String word) {int nword.length();int[] dpnew int[n1];for(int i0;in;i){dp[i1]dp[i]2;if(in-1word.charAt(i1)word.charAt(i)){dp[i1]dp[i]-1;}}return dp[n];
}当然可以发现转移至于i-1状态有关所以可以使用滚动数组优化空间
public int addMinimum(String word) {int nword.length();int dp_00;int dp_10;for(int i0;in;i){dp_1dp_02;if(in-1word.charAt(i1)word.charAt(i)){dp_1dp_0-1;}dp_0dp_1;}return dp_1;
}方法三 直接拼接
参考官方题解 当前字符小于等于前面字符说明它们一定不在同一组 abc 中只需要添置若干字符过渡这两者即可。例如 b前面是 c则需要在中间添置 a又例如 b 前面是 b则需要在中间添置 ca。 以上两种情况可以用一个模型来表示设当前字符是 x前面字符是 y那么需要添置的字符个数为 (x−y−13)mod 3。其中 3 再对 3取模可以应对 x 小于等于 y 的情况。 最后还需要处理头尾两个字符word[0] 前面添置 word[0]−‘a′ 个字符word[n−1]后面添置 ‘c′−word[n−1]个字符。两个可以合并为 word[0]−word[n−1]2 时间复杂度O(n) 空间复杂度O(1) public int addMinimum(String word) {int nword.length();int res0;if(n1)return 2;resword.charAt(0)-word.charAt(n-1)2;for(int i0;in-1;i){int countword.charAt(i1)-word.charAt(i)-13;rescount%3;}return res;}方法四 计算组数 计算递增序列的组——也就是每一个递增序列都是一个组然后使用一个变量count记录当前递增序列的长度需要插入的字符数3-count。在不满足递增的时候才会计算需要插入的字符数并且重置count。 时间复杂度O(n)。n是word的长度 空间复杂度O(1) public int addMinimum(String word) {int nword.length();if(n1){return 2;}int res0;int count1;for(int i0;in-1;i){if(word.charAt(i1)word.charAt(i)){res3-count;count1;}else{count;}}return res(3-count);}有任何问题欢迎评论区交流欢迎评论区提供其它解题思路代码也可以点个赞支持一下作者哈~
