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

举报
未见花闻 发表于 2022/11/30 21:03:56 2022/11/30
【摘要】 ⭐️微信红包⭐️ 🔐题目详情春节期间小明使用微信收到很多个红包,非常开心。在查看领取红包记录时发现,某个红包金额出现的次数超过了红包总数的一半。请帮小明找到该红包金额。写出具体算法思路和代码实现,要求算法尽可能高效。给定一个红包的金额数组 gifts 及它的大小 n ,请返回所求红包的金额。若没有金额超过总数的一半,返回0。数据范围:1≤n≤1000 ,红包金额满足1≤gifts[i]≤...

⭐️微信红包⭐️

🔐题目详情

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

给定一个红包的金额数组 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

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

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

状态转移方程:
情况1:当 a [ i 1 ] = = b [ j 1 ] a[i-1]==b[j-1] 时,编辑距离为字符串ai-1个字符与字符串bj-1个字符的编辑距离,即 f [ i ] [ j ] = f [ i 1 ] [ j 1 ] f[i][j]=f[i-1][j-1]

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

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

那么最短的编辑距离就是这三种情况中最小的一个,即:

f [ i ] [ j ] = m i n ( f [ i 1 ] [ j ] + 1 , f [ i ] [ j 1 ] + 1 , 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]);
    }
}

🌱总结

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

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。