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

一、解码嵌套编码字符串

在编程中，我们经常遇到需要对特定格式的字符串进行解析和解码的任务。今天，我们来探讨一个具体的例子：如何解码一个按照特定规则编码的字符串。这个规则允许字符串中的一部分被重复多次，且这种重复可以嵌套。

问题描述

给定一个经过编码的字符串，我们需要返回它解码后的字符串。编码规则如下：

• k[encoded_string]：表示其中方括号内部的 encoded_string 正好重复 k 次。
• k 保证为正整数，且不会出现像 3a 或 2[4] 这样的无效输入。
• 输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

示例

• 输入：s = "3[a]2[bc]"

• 输出："aaabcbc"

• 输入：s = "3[a2[c]]"

• 输出："accaccacc"

• 输入：s = "2[abc]3[cd]ef"

• 输出："abcabccdcdcdef"

解决方案：使用栈

为了解决这个问题，我们可以利用栈这种数据结构。栈非常适合处理嵌套结构，因为它遵循后进先出的原则，这与我们解析嵌套编码字符串时需要的操作顺序相吻合。

Java实现步骤

1. 初始化栈：我们需要两个栈，一个用于存储数字（表示重复次数），另一个用于存储字符串片段。

2. 遍历输入字符串：逐个字符检查，根据不同字符类型执行相应操作。

   • 如果是数字字符，则构建完整的数字（因为数字可能不止一位）。
   • 如果是左括号 '['，则将当前数字和字符串片段压入栈，并重置当前数字和字符串片段。
   • 如果是字母字符，则将其添加到当前字符串片段中。
   • 如果是右括号 ']'，则从栈中弹出之前的数字和字符串片段，根据弹出的数字重复弹出字符串片段，然后将结果字符串片段重新压入栈中（或者直接用于构建最终结果，如果栈已经为空）。

3. 构建最终结果：遍历结束后，栈中应该只剩下一个字符串片段，即为解码后的字符串。如果栈为空（实际上在这个特定问题中不会发生，因为输入总是有效的），则结果为空字符串。

Java代码实现

以下是完整的Java代码实现：

import java.util.Stack;public class Solution {public String decodeString(String s) {Stack<Integer> counts = new Stack<>();Stack<StringBuilder> strings = new Stack<>();StringBuilder currentString = new StringBuilder();int currentCount = 0;for (char c : s.toCharArray()) {if (Character.isDigit(c)) {currentCount = currentCount * 10 + (c - '0');} else if (c == '[') {counts.push(currentCount);strings.push(currentString);currentCount = 0;currentString = new StringBuilder();} else if (Character.isLetter(c)) {currentString.append(c);} else if (c == ']') {StringBuilder temp = currentString;int repeatTimes = counts.pop();currentString = strings.pop();for (int i = 0; i < repeatTimes; i++) {currentString.append(temp);}}}return currentString.toString();}public static void main(String[] args) {Solution solution = new Solution();System.out.println(solution.decodeString("3[a]2[bc]")); // 输出: aaabcbcSystem.out.println(solution.decodeString("3[a2[c]]"));  // 输出: accaccaccSystem.out.println(solution.decodeString("2[abc]3[cd]ef")); // 输出: abcabccdcdcdefSystem.out.println(solution.decodeString("abc3[cd]xyz")); // 输出: abccdcdcdxyz}
}

 

代码解释与测试

• 变量初始化：我们初始化了两个栈 counts 和 strings 分别用于存储数字和字符串片段，以及两个变量 currentString 和 currentCount 用于构建当前的字符串片段和数字。
• 遍历字符串：我们逐个字符检查输入字符串，并根据字符类型执行相应的操作。特别地，当遇到右括号 ']' 时，我们从栈中弹出之前的数字和字符串片段，并根据弹出的数字重复弹出字符串片段。
• 返回结果：遍历结束后，currentString 中存储的就是解码后的字符串。

为了验证代码的正确性，我们在 main 方法中添加了一些测试用例，并打印了输出结果。这些测试用例涵盖了不同的嵌套情况和重复次数，确保了代码的健壮性和正确性。

总结

  通过使用栈这种数据结构，我们能够高效地解析和解码嵌套编码字符串。这种方法不仅简单易懂，而且具有很好的扩展性和鲁棒性。希望这篇博客能够帮助你更好地理解这个问题及其解决方案！

二、大整数乘法：手动实现字符串形式的数字相乘

在编程中，我们有时会遇到需要处理非常大的数字的情况，这些数字超出了Java原生数据类型（如int、long）的表示范围。虽然Java提供了BigInteger类来处理大整数运算，但在某些情况下，我们可能希望手动实现这些功能，以便更好地理解其背后的原理或满足特定的性能要求。

今天，我们将讨论如何手动实现两个以字符串形式表示的非负整数的乘法，并将结果也以字符串形式返回。这个问题看似简单，但实际上涉及到一些有趣的算法和技巧。

问题描述

给定两个以字符串形式表示的非负整数num1和num2，我们需要返回它们的乘积，乘积也以字符串形式表示。这里有几个关键点需要注意：

• num1和num2的长度可能非常大（最多200位）。
• 不能使用任何内置的BigInteger库或直接将输入转换为整数。
• 输入的数字只包含数字字符，并且不包含任何前导零（除了数字0本身）。

解决方案：模拟手工乘法

为了解决这个问题，我们可以模拟手工乘法的过程。具体步骤如下：

1. 初始化结果数组：创建一个足够大的整数数组来存储乘积的每一位。由于乘积的位数最多为两个乘数位数的和，因此我们可以创建一个长度为len1 + len2的数组。

2. 双重循环计算乘积：从后往前遍历两个字符串的每一位数字，计算它们的乘积，并加上之前的结果（如果有进位）。然后，更新当前位的值和进位到下一位的值。

3. 构建结果字符串：遍历结果数组，将每一位数字添加到字符串中，注意跳过前导零。

4. 处理特殊情况：如果结果为空（即所有位都是0），则返回字符串"0"。

Java代码实现

以下是Java代码的实现：

public class Solution {public String multiply(String num1, String num2) {if (num1.equals("0") || num2.equals("0")) {return "0";}int len1 = num1.length();int len2 = num2.length();int[] result = new int[len1 + len2]; // 用于存储乘积的每一位，可能最长为len1+len2位// 从后往前遍历num1和num2的每一位数字for (int i = len1 - 1; i >= 0; i--) {for (int j = len2 - 1; j >= 0; j--) {int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0'); // 计算当前两位数字的乘积int sum = mul + result[i + j + 1]; // 加上之前的结果（如果有进位）// 更新当前位的值result[i + j + 1] = sum % 10;// 更新进位到下一位result[i + j] += sum / 10;}}// 构建结果字符串StringBuilder sb = new StringBuilder();for (int num : result) {if (!(sb.length() == 0 && num == 0)) { // 跳过前导零sb.append(num);}}return sb.length() == 0 ? "0" : sb.toString(); // 如果结果为空，则返回"0"}public static void main(String[] args) {Solution solution = new Solution();System.out.println(solution.multiply("2", "3")); // 输出: "6"System.out.println(solution.multiply("123", "456")); // 输出: "56088"// 可以添加更多测试用例来验证代码的正确性}
}

 

代码解释

• 边界情况处理：如果num1或num2为"0"，则直接返回"0"。
• 双重循环：使用两个嵌套的循环来遍历两个字符串的每一位数字，并计算乘积。
• 更新结果数组：计算当前两位数字的乘积，并加上之前的结果（如果有进位），然后更新当前位的值和进位到下一位的值。
• 构建结果字符串：遍历结果数组，将每一位数字添加到StringBuilder对象中，并跳过前导零。
• 返回结果：如果结果为空，则返回"0"；否则，返回构建好的字符串。

测试用例

在main方法中，我们添加了一些测试用例来验证代码的正确性。这些测试用例包括简单的数字、较大的数字和边界情况（如0）。你可以根据需要添加更多的测试用例来确保代码的健壮性。

总结

通过手动实现大整数乘法，我们不仅能够更好地理解其背后的原理，还能在特定情况下获得更好的性能。虽然Java提供了BigInteger类来简化大整数运算，但手动实现这些功能仍然是一个有价值的练习。

希望这篇博客能够帮助你更好地理解大整数乘法的问题及其解决方案！如果你有任何问题或建议，请随时在评论区留言。