【算法刷题日记之本手篇】微信红包与计算字符串的编辑距离
⭐️微信红包⭐️
🔐题目详情
春节期间小明使用微信收到很多个红包,非常开心。在查看领取红包记录时发现,某个红包金额出现的次数超过了红包总数的一半。请帮小明找到该红包金额。写出具体算法思路和代码实现,要求算法尽可能高效。
给定一个红包的金额数组 gifts 及它的大小 n ,请返回所求红包的金额。
若没有金额超过总数的一半,返回0。
数据范围:1≤n≤1000 ,红包金额满足1≤gifts[i]≤100000
示例1
输入:
[1,2,3,2,2],5
返回值:
2
示例2
输入:
[1,1,2,2,3,3],6
返回值:
0
题目链接: 微信红包
💡解题思路
基本思路: 哈希计数
解题思路:
本题让我们求出现的次数超过了红包总数的一半的红包金额,题目给了我们一个红包金额数组,那么本题本质上求的是数组中出现次数超过一半的数字。
读懂题那就好办了,最简单的思路就是使用哈希表对数组元素进行计数,然后遍历哈希表得到出现次数超过数组长度一半的数字,该数字其实就是我们所需要的微信红包金额。
由于本题红包金额范围为1-1000000,所以我们可以申请一个1000001
大小的数组来代替哈希表进行计数,遍历数组,将对应哈希数组下标处的元素值加1
即可,直到遍历完整个数组为止。
最终我们返回出现次数超过数组长度一半的数字,如果不存在就返回0
。
🔑源代码
import java.util.*;
public class Gift {
public int getValue(int[] gifts, int n) {
// write code here
//本质上求数组中出现次数超过一半的数字
//思路:哈希表 数据范围1-100000 所以可以使用数组来表示哈希表
int[] hash = new int[100001];
for (int x : gifts) {
hash[x]++;
if (hash[x] > n / 2) {
return x;
}
}
return 0;
}
}
🌱总结
本题的关键是将题目转换为“求数组中出现次数超过一半的元素”,最常规最简单的思路就是使用哈希表进行计数。
⭐️计算字符串的编辑距离⭐️
🔐题目详情
Levenshtein 距离,又称编辑距离,指的是两个字符串之间,由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。编辑距离的算法是首先由俄国科学家 Levenshtein 提出的,故又叫 Levenshtein Distance 。
例如:
字符串A: abcdefg
字符串B: abcdef
通过增加或是删掉字符 ”g” 的方式达到目的。这两种方案都需要一次操作。把这个操作所需要的次数定义为两个字符串的距离。
要求:
给定任意两个字符串,写出一个算法计算它们的编辑距离。
数据范围:给定的字符串长度满足 1≤len(str)≤1000
输入描述:
每组用例一共2行,为输入的两个字符串
输出描述:
每组用例输出一行,代表字符串的距离
示例1
输入:
abcdefg
abcdef
输出:
1
题目链接:计算字符串的编辑距离
💡解题思路
基本思路: 动态规划
解题思路:
我们不妨设第一个字符串为a
,长度为n
, 第二个字符串为b
, 长度为m
。
状态定义: 不妨定义
为字符串a
前
个字符与字符串b
前
个字符之间的最短编辑距离。
确定初始状态: ,因为两个空字符串之间的编辑距离为 ;如果一个字符串为空字符串另一个不为空字符串,编辑距离就是非空字符串的长度,所以当 时, ,同理 时, 。
状态转移方程:
情况1:当
时,编辑距离为字符串a
前i-1
个字符与字符串b
前j-1
个字符的编辑距离,即
。
情况2:当 时,有以下三种小情况:
- 在
a
中插入字符与b
相同,此时 。 - 在
a
中删除一个字符与b
相同等价与在b
中插入一个字符与a
相同,即 。 - 在
a
中替换一个字符与b
相同,即 。
那么最短的编辑距离就是这三种情况中最小的一个,即:
🔑源代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//动态规划
//定义f[i][j]为字符串a前i个字符到字符串b前j个字符的最短编辑距离
//初始状态f[0][0] = 0 f[0][j] = f[0][j - 1] + 1 f[i][0] = f[i - 1][0] + 1
//从a中删除相当于在b中插入一个字符,这是等价的
//状态转移方程
//情况1:a[i] == b[j] f[i][j] = f[i-1][j-1]
//情况2:a[i] != b[j] f[i][j] = min(f[i-1][j] + 1, f[i][j-1] + 1, f[i-1][j-1] + 1)
String a = sc.nextLine();
String b = sc.nextLine();
char[] as = a.toCharArray();
char[] bs = b.toCharArray();
int n = as.length;
int m = bs.length;
int[][] f = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
f[i][0] = f[i - 1][0] + 1;
}
for (int j = 1; j <= m; j++) {
f[0][j] = f[0][j - 1] + 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (as[i - 1] == bs[j - 1]) {
f[i][j] = f[i - 1][j - 1];
}
else {
int tmp = f[i - 1][j] < f[i][j - 1] ? f[i - 1][j] + 1 : f[i][j - 1] + 1;
f[i][j] = f[i - 1][j - 1] + 1 < tmp ? f[i - 1][j - 1] + 1 : tmp;
}
}
}
System.out.println(f[n][m]);
}
}
🌱总结
本题为常规动态规划推理题,重点是能够将问题进行抽象,将大问题转化为小问题,最后在通过小问题一步步得到大问题的结果。
- 点赞
- 收藏
- 关注作者
评论(0)