Java每日精进·45天挑战·Day19

第一部分：移除数字以形成最小数的贪心算法实现

在编程的世界里，我们经常遇到需要对字符串表示的数字进行操作的问题。今天，我们要深入探讨一个具体的挑战：给定一个以字符串形式表示的非负整数 num 和一个整数 k，我们的任务是移除 k 位数字，以使得剩下的数字尽可能小。最终，我们需要返回这个最小的数字（仍然以字符串形式）。

问题背景

这个问题看似简单，实则充满了挑战。我们需要仔细思考如何高效地移除数字，以确保剩下的数字最小。为了更好地理解这个问题，让我们先来看几个示例：

• 输入：num = "1432219"，k = 3
  输出："1219"
  解释：移除数字 4、3 和 2 后，我们得到新的最小数字 "1219"。

• 输入：num = "10200"，k = 1
  输出："200"
  解释：移除首位的 1 后，剩下的数字为 "200"。注意，输出不能有任何前导零，除非整个数字就是零。

• 输入：num = "10"，k = 2
  输出："0"
  解释：移除所有数字后，结果为空，因此返回 "0"。

贪心算法思路

为了解决这个问题，我们可以采用贪心算法。贪心算法在每一步选择中都采取最好或最优（即最有利）的选择，从而希望能够导致结果是全局最好或最优的算法。

在这个问题中，我们的每一步选择是：尽可能让高位数字小。具体思路如下：

1. 使用一个栈来维护当前构建的最小数字。栈的特点是后进先出（LIFO），非常适合用于这种需要“回溯”的场景。

2. 遍历输入字符串的每一个字符：

   • 如果栈不为空，当前字符比栈顶字符小，且还有移除次数 k 大于 0，那么我们可以弹出栈顶字符，并将 k 减 1。这样做的目的是确保高位数字尽可能小。
   • 将当前字符压入栈中。

3. 遍历结束后，如果移除次数 k 仍然大于 0，说明还需要从栈顶继续移除字符，直到 k 为 0。

4. 构建结果字符串并去除前导零。将栈中的字符依次弹出并拼接成字符串。注意要去除前导零，除非整个数字就是零。

5. 处理边界情况。如果最终结果为空字符串，则返回 "0"。

Java 实现

下面，我们将上述思路转化为 Java 代码：

import java.util.Stack;public class RemoveKDigitsBlog {public String removeKDigits(String num, int k) {Stack<Character> stack = new Stack<>();// 遍历输入字符串的每一个字符for (char digit : num.toCharArray()) {// 如果栈不为空，当前字符比栈顶字符小，且还有移除次数 k 大于 0while (!stack.isEmpty() && stack.peek() > digit && k > 0) {stack.pop(); // 弹出栈顶字符k--; // 移除次数减 1}stack.push(digit); // 将当前字符压入栈中}// 如果还有剩余的 k 需要移除，继续从栈顶移除while (k > 0) {stack.pop();k--;}// 构建结果字符串，并去除前导零StringBuilder result = new StringBuilder();while (!stack.isEmpty()) {char digit = stack.pop();if (!(result.length() == 0 && digit == '0')) {result.insert(0, digit);}}// 如果结果为空，则返回 "0"return result.length() == 0 ? "0" : result.toString();}// 为了方便测试，我们在这里添加了一个 main 方法public static void main(String[] args) {RemoveKDigitsBlog solution = new RemoveKDigitsBlog();System.out.println(solution.removeKDigits("1432219", 3)); // 输出 "1219"System.out.println(solution.removeKDigits("10200", 1));   // 输出 "200"System.out.println(solution.removeKDigits("10", 2));      // 输出 "0"// 可以添加更多测试用例来验证算法的正确性}
}

总结

通过贪心算法，我们能够高效地解决这个问题。该算法的时间复杂度是 O(n)，其中 n 是输入字符串的长度。这个算法不仅简单易懂，而且在实际应用中表现良好。

希望这篇博客能够帮助你更好地理解这个问题及其解决方案！如果你有任何疑问或建议，请随时在评论区留言。编程的世界充满了无限可能，让我们一起探索、学习和成长！

第二部分：最大和的连续子数组--动态规划与分治法的探索

在算法的世界里，寻找最大和的连续子数组是一个经典的问题，它有多种解法，每种解法都有其独特的魅力和应用场景。今天，我们将深入探讨两种解法：动态规划和分治法，并通过Java代码实现它们。

问题背景

给定一个整数数组 nums，我们需要找到一个具有最大和的连续子数组（子数组至少包含一个元素），并返回其最大和。连续子数组是数组中的一个连续部分。

动态规划解法

动态规划是一种通过将问题分解为子问题来求解的方法。在这个问题中，我们可以定义一个数组 dp，其中 dp[i] 表示以 nums[i] 结尾的连续子数组的最大和。状态转移方程为：

dp[i] = max(nums[i], dp[i-1] + nums[i])

这意味着，对于每个元素 nums[i]，我们要么选择它作为一个新的子数组的起点（即 nums[i] 本身），要么将它加到之前的子数组上（即 dp[i-1] + nums[i]）。我们取这两种选择中的较大值作为 dp[i] 的值。

最终，我们遍历 dp 数组，找到其中的最大值，即为所求的最大和的连续子数组的和。

Java 实现（动态规划）

public class MaxSubArraySum {public int maxSubArray(int[] nums) {int n = nums.length;int[] dp = new int[n];dp[0] = nums[0];int maxSum = dp[0];for (int i = 1; i < n; i++) {dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);maxSum = Math.max(maxSum, dp[i]);}return maxSum;}public static void main(String[] args) {MaxSubArraySum solution = new MaxSubArraySum();int[] nums1 = {-2, 1, -3, 4, -1, 2, 1, -5, 4};System.out.println(solution.maxSubArray(nums1)); // 输出 6int[] nums2 = {1};System.out.println(solution.maxSubArray(nums2)); // 输出 1int[] nums3 = {5, 4, -1, 7, 8};System.out.println(solution.maxSubArray(nums3)); // 输出 23}
}

 

分治法解法

分治法是一种将问题递归地分解为更小的问题，然后合并这些更小的问题的解决方案来得到原问题的解决方案的方法。在这个问题中，我们可以将数组 nums 分为左右两部分，然后分别求解左右两部分的最大和的连续子数组。同时，我们还需要考虑跨越左右两部分的子数组，即最大和的连续子数组可能从左边开始，穿过中间点，然后结束在右边。

对于跨越左右两部分的子数组，我们可以通过在左边部分找到从右往左的最大和的子数组，在右边部分找到从左往右的最大和的子数组，然后将它们相加得到跨越部分的最大和。最后，我们将左右两部分的最大和以及跨越部分的最大和进行比较，取其中的最大值作为当前问题的解。

Java 实现（分治法）

public class MaxSubArraySumDivideAndConquer {public int maxSubArray(int[] nums) {return maxSubArrayHelper(nums, 0, nums.length - 1);}private int maxSubArrayHelper(int[] nums, int left, int right) {if (left == right) {return nums[left];}int mid = left + (right - left) / 2;int leftSum = maxSubArrayHelper(nums, left, mid);int rightSum = maxSubArrayHelper(nums, mid + 1, right);int crossSum = findMaxCrossingSubarray(nums, left, mid, right);return Math.max(Math.max(leftSum, rightSum), crossSum);}private int findMaxCrossingSubarray(int[] nums, int left, int mid, int right) {int leftSum = Integer.MIN_VALUE;int sum = 0;for (int i = mid; i >= left; i--) {sum += nums[i];leftSum = Math.max(leftSum, sum);}int rightSum = Integer.MIN_VALUE;sum = 0;for (int i = mid + 1; i <= right; i++) {sum += nums[i];rightSum = Math.max(rightSum, sum);}return leftSum + rightSum;}public static void main(String[] args) {MaxSubArraySumDivideAndConquer solution = new MaxSubArraySumDivideAndConquer();int[] nums1 = {-2, 1, -3, 4, -1, 2, 1, -5, 4};System.out.println(solution.maxSubArray(nums1)); // 输出 6int[] nums2 = {1};System.out.println(solution.maxSubArray(nums2)); // 输出 1int[] nums3 = {5, 4, -1, 7, 8};System.out.println(solution.maxSubArray(nums3)); // 输出 23}
}

 

总结

通过动态规划和分治法，我们能够高效地解决寻找最大和的连续子数组的问题。动态规划通过记录以当前元素结尾的子数组的最大和来逐步构建解决方案，而分治法则通过递归地将问题分解为更小的问题来求解。这两种方法都有其独特的优势和适用场景，我们可以根据具体问题的规模和特点来选择合适的方法。

希望这篇博客能够帮助你更好地理解这个问题及其两种解法！如果你有任何疑问或建议，请随时在评论区留言。