文章目录
-
-
- [2645. 构造有效字符串的最少插入数](https://leetcode.cn/problems/minimum-additions-to-make-valid-string/)
-
-
-
- 方法一：计算组数
- 方法二：动态规划
- 方法三: 考虑相邻字母
-
-
- [2085. 统计出现过一次的公共字符串](https://leetcode.cn/problems/count-common-words-with-one-occurrence/)
-
-
-
- 思路：哈希表计算
-
-
- [2807. 在链表中插入最大公约数](https://leetcode.cn/problems/insert-greatest-common-divisors-in-linked-list/)
-
-
-
- 求最大公约数的几种方法：
-
-
- 1.暴力枚举法
- 2.辗转相除法
- 3.辗转相除法 —递归调用
- 4.辗转相除法 —递归调用—简化写法
- 5.调用函数递归 更相减损法
- 6.调用函数递归 更相减损法–简化
-
2645. 构造有效字符串的最少插入数
方法一：计算组数
1.用count统计，能构成几组abc
2.如果当前字符大于之前字符，说明还在组内，不更新
3.如果当前字符小于等于之前字符,说明不是同一组的abc,组数更新
4.最终返回值：组数*3，再减去原本的字符数，就是要插入的次数
//2645. 构造有效字符串的最少插入数---计算组数
public int addMinimum2(String word) {
int n = word.length();
int count = 1;
//最终构成abc的组数
for (int i = 1; i < n; i++) {
if (word.charAt(i - 1) >= word.charAt(i)) {
//当前字符小于等于之前字符
count++;
//组数加一
}
}
return count*3-n;
//返回最终构成abc的总数-原本字符，即为要插入的次数
}
方法二：动态规划
1.从1开始，d[i]为前i个字符拼成abc需要的最小插入数
2.情况一：word[i]单独存在于一组abc中，需要插两次，才能组成abc.插入次数为之前的次数+2
3.情况二：当前字符比前一个字符大，需要插一次，就可以组成abc.修改当前插入次数为：之前的次数-1，因为之前插入的两次中已经包含了当前字符。
public int addMinimum(String word) {
int n = word.length();
int[] d = new int[n + 1];
//d[]数组用来统计，1到n的插入次数
//从1开始，d[i]为前i个字符拼成abc需要的最小插入数。
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],前一个位置的插入数-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’ ，结尾的一个字符：‘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. 统计出现过一次的公共字符串
思路：哈希表计算
1.用两个哈希表分别统计word1和word2中字符出现的次数
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<>();
//存储每个单词在对应数组中出现的次数
for (String x:
words1 ) {
// 遍历第一个字符串数组words1，将单词及其出现次数存储到count1中
count1.put(x,count1.getOrDefault(x,0)+1);
}
for (String x:
words2 ) {
// 遍历第二个字符串数组words2，将单词及其出现次数存储到count2中
count2.put(x,count2.getOrDefault(x,0)+1);
}
int res = 0;
//记录相同单词的数量
for (String x:
count1.keySet()) {
// 遍历count1的键集合，判断在count1中出现次数为1且在count2中也出现次数为1的单词
if (count1.get(x)==1&&count2.getOrDefault(x,0)==1){
res++;
}
}
return res;
}
2807. 在链表中插入最大公约数
思路：模拟
1.调用函数求出要插入的最大公约数
2.插入到cur的后面
3.因为插了一位，所以移动两个位置
public ListNode insertGreatestCommonDivisors(ListNode head) {
ListNode cur = head;
while (cur.next!=null){
int gcdVal = gcd(cur.val,cur.next.val);
//调用函数求出要插入的最大公约数
cur.next = new ListNode(gcdVal,cur.next);
//插入到cur的后面
cur = cur.next.next;
//因为插了一位，所以移动两个位置
}
return head;
}
/**
* 求两个结点值的最大公约数
* @param a
* @param b
* @return
*/
private int gcd(int a,int b){
//求最大公约数有多种写法
while (a!=0){
int temp = a;
a = b % a;
b = temp;
}
return b;
}
求最大公约数的几种方法：
1.暴力枚举法
public static int gcd(int a, int b) {
int min = a < b ? a : b;//判断并取出两个数中小的数
for (int i = min; i >= 1; i--) { //循环,从最小值开始,依次递减,直到i=1
if (a%i==0&&b%i==0){ //当i能同时被A和B余尽时,返回i
return i;
}
}
return 0;
}
}
2.辗转相除法
public static int gcd(int a, int b) {// 辗转相除法
int c = a % b; //先将a对b取余
while (c != 0) { //当余数不等于0时,一直进行循环,直到余数等于0,公约数就为b
a = b; //将a对b的余数再对b取余,直到循环结束
b = c;
c = a % b;
}
return b;
}
3.辗转相除法 —递归调用
public static int gcd(int a, int b) {// 辗转相除法 改进,调用函数递归
int max = a > b ? a : b; //求出大的数
int min = a < b ? a : b; //求出小的数
if(max%min==0){
return min; //当大数模小数能余尽时,最大公约数就是小的数
}
return gcd(max%min,min);//递归函数,参数去前两个数的余数,和小的数
4.辗转相除法 —递归调用—简化写法
public static int gcd(int a, int b) {// 辗转相除法 改进,调用函数递归
return (a % b == 0) ? b : gcd(b, a%b );// 相同思路,三元运算/简化写法
}
1.如果a余b等于0，说明b就是最大公约数
2.否则，进行递归，b代替曾经的a，让a%b产生的余数代替曾经的b。
3.始终确保大数%小数
4.即使b位置上是值大于a, b代替a后，a（小数）%b(大数) = a ，相当于替换位置
- （b,a%b）的位置不能交换，否则无法跳出递归
5.调用函数递归 更相减损法
public static int gcd(int a, int b) {//调用函数递归 更相减损法
int max = a>b?a:b;
int min = a<b?a:b;
if(max%min==0){
return min;
}
return gcd(max-min,min);//相同思路,将%改为-,优化速度
}
6.调用函数递归 更相减损法–简化
public static int gcd(int a, int b) {//调用函数递归 更相减损法 简易写法
if (a < b) {
int tmp = a;
a = b;
b = tmp;
}
return (a % b == 0) ? b : gcd(a - b, b);
简化不用找大小数，把大数放到前面
因为小数减大数为负数，所以要把大数替换到前面，
public static int gcd5(int a, int b) {//调用函数递归 更相减损法 简易写法
return (a % b == 0) ? b : a > b ? gcd5(a - b, b) : gcd5(b-a,a);
}
压行写法，就是三目嵌套，就是可读性不高
点击移步博客主页，欢迎光临~
版权声明：本文为博主作者：翁佳明原创文章，版权归属原作者，如果侵权，请联系我们删除！
原文链接：https://blog.csdn.net/m0_64003319/article/details/136420582
