今天分享几个算法题以及题解

一、求2个字符串的编辑距离

描述

编辑距离指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数，包括以下三种操作：
① 将一个字符替换成另一个字符
② 插入一个字符
③ 删除一个字符

输入

两个字符串

输出

字符串的距离

题解

 1public static int minEditDistance(String str1, String str2) {
 2    int[][] dp = new int[str1.length() + 1][str2.length() + 2];
 3
 4    // 从i个字符变成0个字符，需要i步（删除）
 5    for (int i = 0; i < str1.length() + 1; i++) {
 6        dp[i][0] = i;
 7    }
 8
 9    // 当从0个字符变成j个字符，需要j步(增加)
10    for (int j = 0; j < str2.length() + 1; j++) {
11        dp[0][j] = j;
12    }
13
14    for (int i = 1; i < str1.length() + 1; i++) {
15        for (int j = 1; j < str2.length() + 1; j++) {
16            // 当相同时，dp[i][j] = dp[i - 1][j - 1]
17            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
18                dp[i][j] = dp[i - 1][j - 1];
19            } else {
20                // 当不同时，求三种操作的最小值
21                // dp[i - 1][j - 1]表示的是替换，dp[i - 1][j]表示删除字符，do[i][j - 1]表示的是增加字符
22                dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
23            }
24        }
25    }
26    return dp[str1.length()][str2.length()];
27}

二、质数因子

描述

输入一个正整数，按照从小到大的顺序输出它的所有质因子

输入

一个正整数

输出

按照从小到大的顺序输出它的所有质数的因子，以空格隔开

题解

 1public static void primeFactors(Long num) {
 2    double sqrt = Math.sqrt(num);
 3    for (int i = 2; i <= sqrt; i++) {
 4        while (num % i == 0) {
 5            System.out.print(i + " ");
 6            num /= i;
 7        }
 8    }
 9    if (num > 1) {
10        System.out.println(num + " ");
11    }
12}

三、斐波那契数列

描述

由0和1开始，之后的斐波那契数由之前的两数相加而得出

输入

一个整数N

输出

N以内的斐波那契数列

题解

1public static int fibonacci(int n) {
2    if (n == 1 || n == 2) {
3        return 1;
4    } else {
5        return fibonacci(n - 1) + fibonacci(n - 2);
6    }
7}

四、放苹果

描述

把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？

输入

输入两个整数，appleNum表示苹果数量，plateNum表示盘子数量

输出

一个整数，表示苹果有多少种分法

题解

 1public static Integer putApple(int appleNum, int plateNum) {
 2    // 盘子只有一个或者苹果只有一个
 3    if (appleNum == 1 || plateNum == 1) {
 4        return 1;
 5    }
 6    // 没有苹果
 7    if (appleNum == 0) {
 8        return 1;
 9    }
10    // 没有盘子
11    if (plateNum == 0) {
12        return 0;
13    }
14    // 盘子大于苹果
15    if (plateNum > appleNum) {
16        return putApple(appleNum, plateNum);
17    }
18    // 苹果大于盘子
19    return putApple(appleNum, plateNum - 1) + putApple(appleNum - plateNum, plateNum);
20}

五、最长回文子串

描述

回文串，指左右对称的字符串，给定一个字符串，求最长的回文子串

输入

输入一个仅包含小写字母的字符串

输出

返回最长回文子串的长度

题解

 1public static void maxHuiWen(String str) {
 2    int max = 0;
 3    // 从左往右遍历
 4    for (int i = 0; i < str.length(); i++) {
 5        // 从右往左遍历
 6        for (int j = str.length(); j > i; j--) {
 7            // 截取
 8            String substring = str.substring(i, j);
 9            // 如果截取的字符串和反转之后的一样，则是回文子串
10            if (substring.contentEquals(new StringBuilder(substring).reverse())) {
11                // j-i表示回文子串的长度，求最大值
12                max = Math.max(max, j - i);
13            }
14        }
15    }
16    System.out.println(max);
17}

六、最小公倍数

描述

正整数A和正整数B 的最小公倍数是指 能被A和B整除的最小的正整数值

输入

两个正整数A和B

输出

输出A和B的最小公倍数

题解

1public static void minCommonMultiple(int a, int b) {
2    for (int i = 1; i <= a * b; i++) {
3        if (i%a == 0 && i%b == 0) {
4            System.out.println(i);
5            break;
6        }
7    }
8}

七、打家劫舍

描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

输入

[1,2,3,1]

输出

4

题解

 1public static int rob(int[] nums) {
 2    int n = nums.length;
 3    if (n == 1) return nums[0];
 4    if (n == 2) return Math.max(nums[0], nums[1]);
 5    int[] dp = new int[n];
 6    dp[0] = nums[0];
 7    dp[1] = Math.max(nums[0], nums[1]);
 8
 9    for (int i = 2; i < n; i++) {
10        dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
11    }
12    return dp[n-1];
13}