48天笔试训练错题——day23

目录

选择题

1.

2.

编程题

1. 计算字符串的编辑距离

---

选择题

1.

六层一共有 2^6 - 1 = 63 个节点，而第六层的节点数为 2^(6 - 1) = 32

32 - 9 = 23，假设第六层 剩下节点全是度为 2 的节点，则 总节点：63 + 23 * 2 = 109

2.

平均查找次数 = 查找次数 / 数组最大下标

就将 数组的元素按照哈希函数的方式，依次放入数组中，如果那个位置被占了，那就继续往后走，直到遇到空位，将元素放完后，将它们的查找次数都加起来，然后除以数组元素个数即可。

编程题

1. 计算字符串的编辑距离

代码实现：

import java.util.Scanner;
 
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String s1 = in.nextLine();
            String s2 = in.nextLine();
            print(s1, s2);
        }
    }
 
 
    public static void print(String s1, String s2) {
        char[] arr1 = s1.toCharArray();
        char[] arr2 = s2.toCharArray();
        // 用动态规划来做
        // dp[i][j] 表示 以 i 结尾的 s1 和 以 b 结尾的 s2 串的编辑距离
        int len1 = arr1.length;
        int len2 = arr2.length;
        // 多初始化是为了防止越界
        int[][] dp = new int[len1 + 1][len2 + 1];
        // 初始化 dp
        for (int i = 0; i <= len1; i++) {
            // 从以 i 结尾的 s1 串到 空串所需要进行的操作次数
            dp[i][0] = i;
        }
        for (int j = 0; j <= len2; j++) {
            // 从空串到以 j 结尾的 s2 串所需要进行的操作次数
            dp[0][j] = j;
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                // 插入，删除，替换 中的最小值
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
                if (arr1[i - 1] == arr2[j - 1]) {
                    // 字符相同，不需要替换
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1]);
                } else {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1] + 1);
                }
            }
        }
        System.out.println(dp[len1][len2]);
    }
}