【算法刷题日记之本手篇】微信红包与计算字符串的编辑距离

⭐️前面的话⭐️

本篇文章介绍来自牛客试题广场的两道题题解，分别为【微信红包】和【计算字符串的编辑距离】，展示语言java。

小贴士：本专栏所有题目来自牛客->面试刷题必用工具

📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创，CSDN首发！
📆首发时间：🌴2022年9月9日🌴
✉️坚持和努力一定能换来诗与远方！
💭推荐书籍：📚《算法》，📚《算法导论》
💬推荐在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

---

---

注意事项：本专栏所有题目都来自牛客网，如果有小伙伴还没有注册牛客，可以点击下方链接进行注册，注册完就能立即刷题了。不仅是刷题，上面还有很多有关就业的面经，面试题库，以及名企的模拟面试，我非常推荐它，博主自己用的也很多，也刷了不少题了！下图可以作证：

注册地址：牛客网

有关任何问题都可以与博主交流，你可以在评论区留言，也可以私信我，更可以加上博主的vx与博主一对一交流（文章最下方有）。

---

⭐️微信红包⭐️

🔐题目详情

春节期间小明使用微信收到很多个红包，非常开心。在查看领取红包记录时发现，某个红包金额出现的次数超过了红包总数的一半。请帮小明找到该红包金额。写出具体算法思路和代码实现，要求算法尽可能高效。

给定一个红包的金额数组 gifts 及它的大小 n ，请返回所求红包的金额。

若没有金额超过总数的一半，返回0。

数据范围：1≤n≤1000 ,红包金额满足1≤gifts[i]≤100000

示例1

输入：

[1,2,3,2,2],5
1

返回值：

2
1

示例2

输入：

[1,1,2,2,3,3],6
1

返回值：

0
1

题目链接： 微信红包

💡解题思路

基本思路： 哈希计数
解题思路：
本题让我们求出现的次数超过了红包总数的一半的红包金额，题目给了我们一个红包金额数组，那么本题本质上求的是数组中出现次数超过一半的数字。

读懂题那就好办了，最简单的思路就是使用哈希表对数组元素进行计数，然后遍历哈希表得到出现次数超过数组长度一半的数字，该数字其实就是我们所需要的微信红包金额。

由于本题红包金额范围为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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

🌱总结

本题的关键是将题目转换为“求数组中出现次数超过一半的元素”，最常规最简单的思路就是使用哈希表进行计数。

⭐️计算字符串的编辑距离⭐️

🔐题目详情

Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。编辑距离的算法是首先由俄国科学家 Levenshtein 提出的，故又叫 Levenshtein Distance 。

例如：

字符串A: abcdefg

字符串B: abcdef

通过增加或是删掉字符 ”g” 的方式达到目的。这两种方案都需要一次操作。把这个操作所需要的次数定义为两个字符串的距离。

要求：

给定任意两个字符串，写出一个算法计算它们的编辑距离。
数据范围：给定的字符串长度满足 1≤len(str)≤1000

输入描述：

每组用例一共2行，为输入的两个字符串

输出描述：

每组用例输出一行，代表字符串的距离

示例1

输入：

abcdefg
abcdef
1
2

输出：

1
1

题目链接：计算字符串的编辑距离

💡解题思路

基本思路： 动态规划
解题思路：
我们不妨设第一个字符串为a，长度为n， 第二个字符串为b， 长度为m。

状态定义： 不妨定义$f[i][j]$为字符串a前$i$个字符与字符串b前$j$个字符之间的最短编辑距离。

确定初始状态： $f[0][0]=0$，因为两个空字符串之间的编辑距离为$0$；如果一个字符串为空字符串另一个不为空字符串，编辑距离就是非空字符串的长度，所以当$i=0,j>0$时，$f[0][j]=f[0][j-1]+1$，同理$i>0,j=0$时，$f[i][0]=f[i-1][0]+1$。

状态转移方程：
情况1：当$a[i-1]==b[j-1]$时，编辑距离为字符串a前i-1个字符与字符串b前j-1个字符的编辑距离，即$f[i][j]=f[i-1][j-1]$。

情况2：当$a[i-1]!=b[j-1]$时，有以下三种小情况：

• 在a中插入字符与b相同，此时$f[i][j]=f[i-1][j]+1$。
• 在a中删除一个字符与b相同等价与在b中插入一个字符与a相同，即$f[i][j]=f[i][j-1]+1$。
• 在a中替换一个字符与b相同，即$f[i][j]=f[i-1][j-1]+1$。

那么最短的编辑距离就是这三种情况中最小的一个，即：
$$f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1,f[i-1][j-1]+1)$$

🔑源代码

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]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

🌱总结

本题为常规动态规划推理题，重点是能够将问题进行抽象，将大问题转化为小问题，最后在通过小问题一步步得到大问题的结果。

---

到文章最后，再来安利一下吧，博主也是经常使用，并且也经常在牛客上刷题，题库也非常丰富：牛客网，刷题，面试，内推都有。也欢迎与博主交流有关刷题，技术方面，以及与博主聊聊天，交个朋友也好啊，毕竟有朋自远方来！

觉得文章写得不错的老铁们，点赞评论关注走一波！谢谢啦！