刷题_23：微信红包 and 计算字符串的编辑距离

灰太狼 2023-09-30 21:31 19阅读 0赞

### 一.微信红包 ###

**题目链接：**

> [微信红包][Link 1]

**题目描述：**

> **春节期间小明使用微信收到很多个红包，非常开心。在查看领取红包记录时发现，某个红包金额出现的次数超过了红包总数的一半。请帮小明找到该红包金额。写出具体算法思路和代码实现，要求算法尽可能高效。  
> 给定一个红包的金额数组 gifts 及它的大小 n ，请返回所求红包的金额。  
> 若没有金额超过总数的一半，返回0。  
> 数据范围： 1≤n≤1000 ,红包金额满足 1≤gifti ≤100000**

**输入描述：**

> **无**

**输出描述：**

> **无**

**示例1：**

> **输入：  
> \[1,2,3,2,2\],5  
> 输出：  
> 2**

**示例2：**

> **输入：  
> \[1,1,2,2,3,3\],6  
> 输出：  
> 0**

**个人总结：**

> **时间复杂度O(n)，空间复杂度O(1)。注意他题干说的是红包金额出现的次数超过了红包总数的一半，而不是金额总数，此题哈希表也能写，这个方法也行，用这个方法的话参数n压根没用到，和我之前见的一个题目比较类似，详细请走 [多数元素][Link 2]**

**代码实现：**

import java.util.*;
    
    public class Gift {
        
        public int getValue(int[] gifts, int n) {
        
            // write code here
            //记录金额
            int res = 0;
            //记录出现次数
            int cnt = 0;
            for (int i = 0; i < gifts.length; i++) {
        
                if (res == gifts[i]) {
        
                    cnt++;
                } else {
        
                    cnt--;
                    if (cnt < 0) {
        
                        res = gifts[i];
                        cnt = 0;
                    }
                }
            }
            return cnt == 0 ? 0 : res;
        }
    }

--------------------

### 二.计算字符串的编辑距离 ###

**题目链接：**

> [计算字符串的编辑距离][Link 3]

**题目描述：**

> **Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。编辑距离的算法是首先由俄国科学家 Levenshtein 提出的，故又叫 Levenshtein Distance 。  
> 例如：  
> 字符串A: abcdefg  
> 字符串B: abcdef  
> 通过增加或是删掉字符 ”g” 的方式达到目的。这两种方案都需要一次操作。把这个操作所需要的次数定义为两个字符串的距离。  
> 要求：  
> 给定任意两个字符串，写出一个算法计算它们的编辑距离。  
> 数据范围：给定的字符串长度满足 1≤len(str)≤1000**

**输入描述：**

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

**输出描述：**

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

**示例1：**

> **输入：  
> abcdefg  
> abcdef  
> 输出：  
> 1**

**个人总结：**

> **动态规划题，我们对字符串的编辑操作可以分为：替换、增加、删除三个操作，虽然增加和删除是一个互逆的操作，可以简化转移方程，但是！我忘了怎么搞了，所以我们还是全部考虑吧。我们来分析一下两层for循环内部的代码：  
> 定义一下，方便叙述：s\[i - 1\]意思是 0 ~ i - 1的s子串。  
> `if (s.charAt(i - 1) == p.charAt(j - 1))` ：则`dp[i][j] = dp[i - 1][j - 1];`，意思是如果字符相等可以匹配，则最少的编辑次数等于s\[i - 1\]和p\[j - 1\]的最少编辑次数，即本次不需要编辑，次数和上次一样。  
> `if (s.charAt(i - 1) != p.charAt(j - 1))` ：则取`dp[i - 1][j - 1]`和`dp[i - 1][j]`和`dp[i][j - 1]`的最小值然后加1（进行了一次编辑）。  
> `dp[i - 1][j - 1] + 1`：执行一次替换操作，则最少的编辑次数等于s\[i - 1\]和p\[j - 1\]的最少编辑次数 + 一次替换。  
> `dp[i - 1][j] + 1`：对p执行一次增加操作，则s.charAt(i - 1)和 p.charAt(j - 2)匹配，所以最少的编辑次数等于s\[i - 1\]和p\[j - 2\]的最少编辑次数 + 一次增加。  
> `dp[i][j - 1] + 1`：对p执行一次删除操作，则s.charAt(i - 2)和 p.charAt(j - 1)匹配，所以最少的编辑次数等于s\[i - 2\]和p\[j - 1\]的最少编辑次数 + 一次删除。**

**代码实现：**

import java.util.*;
    
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            String s = sc.nextLine();
            String p = sc.nextLine();
            System.out.println(getMinLevenshtein(s, p));
        }
        
        public static int getMinLevenshtein(String s, String p) {
        
            int lenS = s.length();
            int lenP = p.length();
            //dp[i][j]：长度为i的s编辑成长度为j的p的最少操作次数
            int[][] dp = new int[lenS + 1][lenP + 1];
            for (int i = 1; i <= lenS; i++) {
        
                dp[i][0] = i;
            }
            for (int j = 1; j <= lenP; j++) {
        
                dp[0][j] = j;
            }
            for (int i = 1; i <= lenS; i++) {
        
                for (int j = 1; j <= lenP; j++) {
        
                    if (s.charAt(i - 1) == p.charAt(j - 1)) {
        
                        dp[i][j] = dp[i - 1][j - 1];
                    } else {
        
                        dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                    }
                }
            }
            return dp[lenS][lenP];
        }
    }

[Link 1]: https://www.nowcoder.com/questionTerminal/fbcf95ed620f42a88be24eb2cd57ec54
[Link 2]: https://blog.csdn.net/qq_53130059/article/details/125820973?spm=1001.2014.3001.5502
[Link 3]: https://www.nowcoder.com/questionTerminal/3959837097c7413a961a135d7104c314?answerType=1&f=discussion