算法题解—戳气球、Pow(x, n)、编辑距离

戳气球(数组、动态规划)

有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
求所能获得硬币的最大数量。

示例 1：
输入：nums = [3,1,5,8] 输出：167 解释： nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> [] coins = 315 + 358 + 138 + 181 = 167
示例 2：
输入：nums = [1,5] 输出：10

提示：

• n == nums.length
• 1 <= n <= 500
• 0 <= nums[i] <= 100

解答：

public class Solution {
    public int maxCoins(int[] iNums) {
        int n = iNums.length;
        int[] nums = new int[n + 2];
        for (int i = 0; i < n; i++)
            nums[i + 1] = iNums[i];
        nums[0] = nums[n + 1] = 1;
        int[][] dp = new int[n + 2][n + 2];
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n - k + 1; i++) {
                int j = i + k - 1;
                for (int x = i; x <= j; x++) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][x - 1] + nums[i - 1] * nums[x] * nums[j + 1] + dp[x + 1][j]);
                }
            }
        }
        return dp[1][n];
    }
}

Pow(x, n) （递归、数学）

实现 pow(x, n)(https://www.cplusplus.com/reference/valarray/pow/) ，即计算 x 的 n 次幂函数（即，xn）。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

提示：

• -100.0 < x < 100.0
• -231 <= n <= 231-1
• -104 <= xn <= 104

public class Solution {
    public double myPow(double x, int n) {
        if (n < 0) {
            return 1 / pow(x, -n);
        } else {
            return pow(x, n);
        }
    }
    private double pow(double x, int n) {
        if (n == 0) {
            return 1.0;
        }
        if (n == 1) {
            return x;
        }
        double val = pow(x, n / 2);
        if (n % 2 == 0) {
            return val * val;
        } else {
            return val * val * x;
        }
    }
}

编辑距离(字符串、动态规划)

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2_ _所使用的最少操作数 。
你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：horse -> rorse (将 'h' 替换为 'r')rorse -> rose (删除 'r')rose -> ros (删除 'e')

示例 2：

输入：word1 = "intention", word2 = "execution"
输出：5
解释：intention -> inention (删除 't')inention -> enention (将 'i' 替换为 'e')enention -> exention (将 'n' 替换为 'x')exention -> exection (将 'n' 替换为 'c')exection -> execution (插入 'u')

提示：

• 0 <= word1.length, word2.length <= 500
• word1 和 word2 由小写英文字母组成

以下程序实现了这一功能，请你填补空白处内容：

class Solution {
	public int minDistance(String word1, String word2) {
		int len1 = word1.length();
		int len2 = word2.length();

		if (len1 * len2 == 0)
			return len1 + len2;
		String longerStr = len1 > len2 ? word1 : word2;
		String shorterStr = len1 > len2 ? word2 : word1;
		int shorterOne = Math.min(len1, len2);

		int[] dp = new int[shorterOne + 1];

		for (int i = 0; i < shorterOne + 1; i++) {
			dp[i] = i;
		}

		for (int j = 1; j <= longerStr.length(); j++) {

			int left = j;

			for (int i = 1; i <= shorterStr.length(); i++) {
				int updateDown = dp[i] + 1;
				int updateLeft = left + 1;
				int updateLeftDown = dp[i - 1];

				if (longerStr.charAt(j - 1) != shorterStr.charAt(i - 1)) {
					updateLeftDown++;
				}

				int min = Math.min(updateLeft, Math.min(updateDown, updateLeftDown));

				dp[i - 1] = left;

				_____________________;
			}
		}
		return dp[shorterOne];
	}
}

解答：

if (i == dp.length - 1) {
	dp[i] = min;
} else {
	left = min;
}

本文内容到此结束了，
如有收获欢迎点赞👍收藏💖关注✔️，您的鼓励是我最大的动力。
如有错误❌疑问💬欢迎各位大佬指出。
保持热爱，奔赴下一场山海。🏃🏃🏃