java打卡day 23 ①计算字符串的编辑距离(动态规划)较难 ②微信红包

目录

①计算字符串的编辑距离

②微信红包(遍历计数)

①计算字符串的编辑距离

刷题链接:

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String str1;
        while ((str1 = reader.readLine()) != null) {
            String str2 = reader.readLine();
            System.out.println(getDistance(str1, str2));
        }
    } 
    //采用动态规划来完成这一题目
     public static int getDistance(String str1, String str2) {
         //分别将两个字符串转化为数组
        char[] wd1 = str1.toCharArray();
         //要转化的字符串数组
        char[] wd2 = str2.toCharArray();
         //两字符串的长度
        int len1 = wd1.length;
        int len2 = wd2.length;
         //定义一个矩阵来规划插入删除替换 *** 作的动态变化
         //多定义了长度为了使得i和j与前i个转化为前
         //j个的动态规划相匹配
        int[][] dist = new int[len1 + 1][len2 + 1];
         //初始状态 为F(i, 0) = i; F(0, j) = j
         //表示将i个字符串变为0个字符串需要经过i次插入 *** 作，将
         //0个字符串转变为j个字符串需要j次插入 *** 作
        for (int i = 0; i <= len1; ++i)
            //初始化删除操作
            dist[i][0] = i;
        for (int j = 0; j <= len2; ++j)
            //初始化插入操作
            dist[0][j] = j;
        for (int i = 1; i <= len1; ++i) {
            for (int j = 1; j <= len2; ++j) {
          //F(i,j) = min(F(i-1, j) + 1,
          //F(i, j-1) + 1, F(i-1, j-1) + (wd1[i] == wd2[j] ? 0 : 1))
                //**关键步骤*//
          //首先求出插入和删除的最小值，如果最小值是dis[i-1][j]，
                //+1表示插入第i个字符操作转化为dis[i，j]
                //并且操作数+1
                dist[i][j] = Math.min(dist[i - 1][j], dist[i][j - 1]) + 1;
          //再和替换进行比较，如果第i个字符和第j个字符相等
                if (wd1[i - 1] == wd2[j - 1]) {
           //不需要进行替换，只需要去比较上一个状态和删除插入操作两者最小值
                    dist[i][j] = Math.min(dist[i][j], dist[i - 1][j - 1]);
                } else {
                    //如果需要进行替换，那么将替换之前的状态步数+1(替换操作)，然后与
                    //插入删除操作最小值比较
                    dist[i][j] = Math.min(dist[i][j], dist[i - 1][j - 1] + 1);
                }
            }
            //返回长度为len1的字符串转化为长度为len2字符串的最小步数
        } return dist[len1][len2];
    }
}

②微信红包(遍历计数)

刷题链接:微信红包_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/fbcf95ed620f42a88be24eb2cd57ec54?tpId=49&&tqId=29311&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking

import java.util.*;

public class Gift {
    public int getValue(int[] gifts, int n) {
        // write code here
        //定义一个数组存放每个数字出现的次数
        int[]arr=new int[100000];
        for(int i=0;in/2){
                return gifts[i];
            }
        }
        return 0;
    }
}