2645. 構造有效字符串的最少插入數(shù)
方法一：計算組數(shù)
1.用count統(tǒng)計，能構成幾組abc
2.如果當前字符大于之前字符，說明還在組內(nèi)，不更新
3.如果當前字符小于等于之前字符,說明不是同一組的abc,組數(shù)更新
4.最終返回值：組數(shù)*3，再減去原本的字符數(shù)，就是要插入的次數(shù)
//2645. 構造有效字符串的最少插入數(shù)---計算組數(shù)
public int addMinimum2(String word) {
int n = word.length();
int count = 1;
//最終構成abc的組數(shù)
for (int i = 1; i < n; i++) {
if (word.charAt(i - 1) >= word.charAt(i)) {
//當前字符小于等于之前字符
count++;
//組數(shù)加一
}
}
return count*3-n;
//返回最終構成abc的總數(shù)-原本字符，即為要插入的次數(shù)
}
方法二：動態(tài)規(guī)劃
1.從1開始，d[i]為前i個字符拼成abc需要的最小插入數(shù)
2.情況一：word[i]單獨存在于一組abc中，需要插兩次，才能組成abc.插入次數(shù)為之前的次數(shù)+2
3.情況二：當前字符比前一個字符大，需要插一次，就可以組成abc.修改當前插入次數(shù)為：之前的次數(shù)-1，因為之前插入的兩次中已經(jīng)包含了當前字符。
public int addMinimum(String word) {
int n = word.length();
int[] d = new int[n + 1];
//d[]數(shù)組用來統(tǒng)計，1到n的插入次數(shù)
//從1開始，d[i]為前i個字符拼成abc需要的最小插入數(shù)。
for (int i = 1; i <= n; i++) {
d[i] = d[i - 1] + 2;
//word[i]單獨存在于一組abc中，在之前情況的基礎上+2. eg: a+bc / b+ac / c+ab
if (i > 1 && word.charAt(i - 1) > word.charAt(i - 2)) {
//如果當前字符比前一個字符大，eg:ab/ ac / bc
d[i] = d[i - 1] - 1;
//當前字符和之前的字符在同一個abc中，重新覆蓋d[i],前一個位置的插入數(shù)-1
}
}
return d[n];
}
方法三: 考慮相鄰字母
1.設當前字符為x,前一個字符為y,
2.x大于y的情況：x-y-1
3.x小于等于y的情況：(x-y-1+3)mod 3 ，將計算的結果控制在0-2之間
4.開頭的單獨一個字符：word[0]-‘a(chǎn)’ ，結尾的一個字符：‘c’-word[n-1],合并為word[0]-word[n-1]+2
public int addMinimum3(String word) {
int n = word.length();
int res = word.charAt(0) - word.charAt(n - 1) + 2;
//合并處理開頭和結尾的情況
for (int i = 1; i < n; i++) {
res += (word.charAt(i) - word.charAt(i - 1) + 2) % 3;
}
return res;
}
1-11 生日快樂
2085. 統(tǒng)計出現(xiàn)過一次的公共字符串
思路：哈希表計算
1.用兩個哈希表分別統(tǒng)計word1和word2中字符出現(xiàn)的次數(shù)
2.遍歷words1中的每個單詞x，并使用count1.put(x,count1.getOrDefault(x,0)+1)將單詞x作為鍵，將其在count1中對應的值加1存儲起來,count1.getOrDefault(x,0)表示獲取count1中鍵為x的值，如果不存在則返回默認值0。
3.同理遍歷word2,同樣操作
4.遍歷count1的鍵集合count1.keySet()，對于每個鍵x，判斷count1.get(x)是否等于1且count2.getOrDefault(x,0)是否等于1。如果滿足條件，則將res加1。
public int countWords(String[] words1, String[] words2) {
Map<String,Integer> count1 = new HashMap<>();
Map<String,Integer> count2 = new HashMap<>();
//存儲每個單詞在對應數(shù)組中出現(xiàn)的次數(shù)
for (String x:
words1 ) {
// 遍歷第一個字符串數(shù)組words1，將單詞及其出現(xiàn)次數(shù)存儲到count1中
count1.put(x,count1.getOrDefault(x,0)+1);
}
for (String x:
words2 ) {
// 遍歷第二個字符串數(shù)組words2，將單詞及其出現(xiàn)次數(shù)存儲到count2中
count2.put(x,count2.getOrDefault(x,0)+1);
}
int res = 0;
//記錄相同單詞的數(shù)量
for (String x:
count1.keySet()) {
// 遍歷count1的鍵集合，判斷在count1中出現(xiàn)次數(shù)為1且在count2中也出現(xiàn)次數(shù)為1的單詞
if (count1.get(x)==1&&count2.getOrDefault(x,0)==1){
res++;
}
}
return res;
}
2807. 在鏈表中插入最大公約數(shù)
思路：模擬
1.調(diào)用函數(shù)求出要插入的最大公約數(shù)
2.插入到cur的后面
3.因為插了一位，所以移動兩個位置
public ListNode insertGreatestCommonDivisors(ListNode head) {
ListNode cur = head;
while (cur.next!=null){
int gcdVal = gcd(cur.val,cur.next.val);
//調(diào)用函數(shù)求出要插入的最大公約數(shù)
cur.next = new ListNode(gcdVal,cur.next);
//插入到cur的后面
cur = cur.next.next;
//因為插了一位，所以移動兩個位置
}
return head;
}
/**
* 求兩個結點值的最大公約數(shù)
* @param a
* @param b
* @return
*/
private int gcd(int a,int b){
//求最大公約數(shù)有多種寫法
while (a!=0){
int temp = a;
a = b % a;
b = temp;
}
return b;
}
求最大公約數(shù)的幾種方法：
1.暴力枚舉法
public static int gcd(int a, int b) {
int min = a < b ? a : b;//判斷并取出兩個數(shù)中小的數(shù)
for (int i = min; i >= 1; i--) { //循環(huán),從最小值開始,依次遞減,直到i=1
if (a%i==0&&b%i==0){ //當i能同時被A和B余盡時,返回i
return i;
}
}
return 0;
}
}
2.輾轉(zhuǎn)相除法
public static int gcd(int a, int b) {// 輾轉(zhuǎn)相除法
int c = a % b; //先將a對b取余
while (c != 0) { //當余數(shù)不等于0時,一直進行循環(huán),直到余數(shù)等于0,公約數(shù)就為b
a = b; //將a對b的余數(shù)再對b取余,直到循環(huán)結束
b = c;
c = a % b;
}
return b;
}
3.輾轉(zhuǎn)相除法 —遞歸調(diào)用
public static int gcd(int a, int b) {// 輾轉(zhuǎn)相除法 改進,調(diào)用函數(shù)遞歸
int max = a > b ? a : b; //求出大的數(shù)
int min = a < b ? a : b; //求出小的數(shù)
if(max%min==0){
return min; //當大數(shù)模小數(shù)能余盡時,最大公約數(shù)就是小的數(shù)
}
return gcd(max%min,min);//遞歸函數(shù),參數(shù)去前兩個數(shù)的余數(shù),和小的數(shù)
4.輾轉(zhuǎn)相除法 —遞歸調(diào)用—簡化寫法
public static int gcd(int a, int b) {// 輾轉(zhuǎn)相除法 改進,調(diào)用函數(shù)遞歸
return (a % b == 0) ? b : gcd(b, a%b );// 相同思路,三元運算/簡化寫法
}
1.如果a余b等于0，說明b就是最大公約數(shù)
2.否則，進行遞歸，b代替曾經(jīng)的a，讓a%b產(chǎn)生的余數(shù)代替曾經(jīng)的b。
3.始終確保大數(shù)%小數(shù)
4.即使b位置上是值大于a, b代替a后，a（小數(shù)）%b(大數(shù)) = a ，相當于替換位置
- （b,a%b）的位置不能交換，否則無法跳出遞歸
5.調(diào)用函數(shù)遞歸 更相減損法
public static int gcd(int a, int b) {//調(diào)用函數(shù)遞歸 更相減損法
int max = a>b?a:b;
int min = a<b?a:b;
if(max%min==0){
return min;
}
return gcd(max-min,min);//相同思路,將%改為-,優(yōu)化速度
}
6.調(diào)用函數(shù)遞歸 更相減損法–簡化
public static int gcd(int a, int b) {//調(diào)用函數(shù)遞歸 更相減損法 簡易寫法
if (a < b) {
int tmp = a;
a = b;
b = tmp;
}
return (a % b == 0) ? b : gcd(a - b, b);
簡化不用找大小數(shù)，把大數(shù)放到前面
因為小數(shù)減大數(shù)為負數(shù)，所以要把大數(shù)替換到前面，
public static int gcd5(int a, int b) {//調(diào)用函數(shù)遞歸 更相減損法 簡易寫法
return (a % b == 0) ? b : a > b ? gcd5(a - b, b) : gcd5(b-a,a);
}
壓行寫法，就是三目嵌套，就是可讀性不高
點擊移步博客主頁，歡迎光臨~文章來源：http://www.zghlxwxcb.cn/news/detail-848502.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-848502.html
到了這里，關于【LeetCode題解】2645. 構造有效字符串的最少插入數(shù)（計算組數(shù)+動態(tài)規(guī)劃+考慮相鄰字母）+2085. 統(tǒng)計出現(xiàn)過一次的公共字符串（哈希表）+2807. 在鏈表中插入最大公約數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
