【Java版oj】day22微信红包、编辑距离

约定不等于承诺〃 2024-03-24 13:22 37阅读 0赞

**目录**

一、微信红包

（1）原题再现

（2）问题分析

（3）完整代码

二、编辑距离

（1）原题再现

（2）问题分析

（3）完整代码

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

> ## 一、微信红包 ##
> 
> ### （1）原题再现 ###
> 
> [微信红包\_\_牛客网][Link 1]  
> 春节期间小明使用微信收到很多个红包，非常开心。在查看领取红包记录时发现，某个红包金额出现的次数超过了红包总数的一半。请帮小明找到该红包金额。写出具体算法思路和代码实现，要求算法尽可能高效。
> 
> 给定一个红包的金额数组 **gifts** 及它的大小 **n** ，请返回所求红包的金额。
> 
> 若没有金额超过总数的一半，返回0。
> 
> **示例1**
> 
> 输入
> 
> \[1,2,3,2,2\],5
> 
> 输出
> 
> 2
> 
> **示例2**
> 
> 输入
> 
> \[1,1,2,2,3,3\],6
> 
> 输出
> 
> 0
> 
> ### （2）问题分析 ###
> 
> 本题难度不大，首先利用**Arrays.sort()**对数组排序，overHalf=gifts\[n/2\];直接找到中间数，利用for循环记录中间数的个数。判断中间数的个数是否超过半数。
> 
> ### （3）完整代码 ###
> 
>     import java.util.Arrays;
>     
>     /*
>      * 微信红包
>      */
>     public class Gift {
>       	 public int getValue(int[] gifts, int n) {
>     	        // write code here
>     		 Arrays.sort(gifts);
>     		 int overHalf=gifts[n/2];
>     		 int count=0;
>     		
>     		 for(int i=0;i<n;i++) {
>     			 if(gifts[i]==overHalf) {
>     				count++;
>     			 }
>     		 }
>     		 if(count>n/2) {
>     			 return gifts[n/2];
>     		 }else {
>     			 return 0;
>     		 }
>     	}
>     }
> 
> ![7f4c688482f640339fed1a68b0989a24.png][]

> ## 二、编辑距离 ##
> 
> ### （1）原题再现 ###
> 
> [编辑距离\_牛客题霸\_牛客网][Link 2]
> 
> **描述**
> 
> 给定两个单词word1和word2，请计算将word1转换为word2至少需要多少步操作。  
> 你可以对一个单词执行以下3种操作：  
> a）在单词中插入一个字符  
> b）删除单词中的一个字符  
> c）替换单词中的一个字符
> 
> **示例1**
> 
> 输入：
> 
> "b",""
> 
> 返回值：
> 
> 1
> 
> **示例2**
> 
> 输入：
> 
> "ab","bc"
> 
> 返回值：
> 
> 2
> 
> ### （2）问题分析 ###
> 
> 本题是经典的一道动态规划题。
> 
> **子状态：word1的前1，2，3，...m个字符转换成word2的前1，2，3，...n个字符需要的编辑距离。  
> F(i,j):word1的前i个字符对于word2的前j个字符的编辑距离**  
> **状态递推：**  
>  **F(i,j) = min \{ F(i-1,j）+1, F(i,j-1) +1, F(i-1,j-1) +(w1\[i\]==w2\[j\]?0:1) \}**  
> 上式表示从删除，增加和替换操作中选择一个最小操作数  
> F(i-1,j): w1\[1,...,i-1\]于w2\[1,...,j\]的编辑距离，删除w1\[i\]的字符--->F(i,j)  
> F(i,j-1): w1\[1,...,i\]于w2\[1,...,j-1\]的编辑距离，增加一个字符--->F(i,j)  
> F(i-1,j-1): w1\[1,...,i-1\]于w2\[1,...,j-1\]的编辑距离，如果w1\[i\]与w2\[j\]相同，  
> 不做任何操作，编辑距离不变，如果w1\[i\]与w2\[j\]不同，替换w1\[i\]的字符为w2\[j\]--->F(i,j)  
> 初始化：  
> 初始化一定要是确定的值，如果这里不加入空串，初始值无法确定  
> F(i,0) = i :word与空串的编辑距离，删除操作  
> F(0,i) = i :空串与word的编辑距离，增加操作  
> 返回结果：F(m,n)  
> 举一个例子：abc 、abd
> 
> <table style="width:500px;"> 
>  <tbody> 
>   <tr> 
>    <td></td> 
>    <td>""</td> 
>    <td>"a"</td> 
>    <td>"ab"</td> 
>    <td>"abc"</td> 
>   </tr> 
>   <tr> 
>    <td>""</td> 
>    <td>0</td> 
>    <td>1</td> 
>    <td>2</td> 
>    <td>3</td> 
>   </tr> 
>   <tr> 
>    <td>"a"</td> 
>    <td>1</td> 
>    <td>0</td> 
>    <td>1</td> 
>    <td>2</td> 
>   </tr> 
>   <tr> 
>    <td>"ab"</td> 
>    <td>2</td> 
>    <td>1</td> 
>    <td>0</td> 
>    <td>1</td> 
>   </tr> 
>   <tr> 
>    <td>"abd"</td> 
>    <td>3</td> 
>    <td>2</td> 
>    <td>1</td> 
>    <td>1</td> 
>   </tr> 
>  </tbody> 
> </table>
> 
> 这一行表示，当字符串2为空时，字符串1到字符串2所需要的步骤，其他同理。
> 
> <table style="width:500px;"> 
>  <tbody> 
>   <tr> 
>    <td>""</td> 
>    <td>"a"</td> 
>    <td>"ab"</td> 
>    <td>"abc"</td> 
>   </tr> 
>   <tr> 
>    <td>0</td> 
>    <td>1</td> 
>    <td>2</td> 
>    <td>3</td> 
>   </tr> 
>  </tbody> 
> </table>
> 
> ### （3）完整代码 ###
> 
>     import java.util.*;
>     public class Solution {
>         /**
>          * @param word1 string字符串 
>          * @param word2 string字符串 
>          * @return int整型
>          */
>         public int minDistance (String word1, String word2) {
>             // write code here
>             if(word1.length()==0||word2.length()==0){
>                 return Math.max(word1.length(),word2.length());
>             }
>             int len1=word1.length();
>             int len2=word2.length();
>             int minStep[][]=new int[len1+1][len2+1];
>             for(int i=0;i<=len1;i++){
>                 minStep[i][0]=i;
>             }
>             for(int i=0;i<=len2;i++){
>                 minStep[0][i]=i;
>             }
>             for(int i=1;i<=len1;i++){
>                 for(int j=1;j<=len2;j++){
>                     if(word1.charAt(i-1)==word2.charAt(j-1)){
>                         minStep[i][j]=minStep[i-1][j-1];
>                     }else{
>                         minStep[i][j]=Math.min(Math.min(minStep[i][j-1],minStep[i-1][j]),minStep[i-1][j-1])+1;
>                     }
>                 }
>             }
>             return minStep[len1][len2];
>         }
>     }
> 
> ![93317840ba1d418db14dc204642a54b3.png][]

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

![d272b8b0422b4cca89c016e25f0d7af5.png][]

[Link 1]: https://www.nowcoder.com/questionTerminal/fbcf95ed620f42a88be24eb2cd57ec54
[7f4c688482f640339fed1a68b0989a24.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/fd260b0a06cb4377885ab562c8a77ce8.png
[Link 2]: https://www.nowcoder.com/practice/81d7738f954242e5ade5e65ec40e5027?tpId=46&tqId=29106&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking
[93317840ba1d418db14dc204642a54b3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/087aae9563db4c0aa4850c3c79a67903.png
[d272b8b0422b4cca89c016e25f0d7af5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/6b9de77b291047cdba1547da41d5a002.png