【力扣每日一题】——向表达式添加括号后的最小结果

1年前 (2022) 程序员胖胖胖虎阿

234 0 0

💻个人简介

⌨️作者简介：大家好，我是〖雪月清〗 ❄️

🎉个人主页：〖雪月清〗🌸

📣力扣每日一题：带你感受算法百态⭐

力扣每日一题系列简介：

有些题看起来不难却很复杂，但是如果巧妙的应用Java中的内置函数解决起来就变得简单很多，这些题没见过是真的难想到用什么内置函数，而且就算见过也很容易遗忘，【力扣每日一题】系列将总结归纳诸如使用巧妙方法解决的题、经典算法模板题、高频面试题等力扣算法题

⭐⭐⭐向表达式添加括号后的最小结果⭐⭐⭐

- 🍋1.题目描述：
- 🍊2.题目分析
- 🌰3.代码实现

🍋1.题目描述：

给你一个下标从 0 开始的字符串 expression ，格式为 “<num1>+<num2>” ，其中 <num1> 和 <num2> 表示正整数。请你向 expression 中添加一对括号，使得在添加之后， expression 仍然是一个有效的数学表达式，并且计算后可以得到最小可能值。左括号必须添加在 ‘+’ 的左侧，而右括号必须添加在 ‘+’ 的右侧。

返回添加一对括号后形成的表达式 expression ，且满足 expression 计算得到最小可能值。如果存在多个答案都能产生相同结果，返回任意一个答案。

生成的输入满足：expression 的原始值和添加满足要求的任一对括号之后 expression 的值，都符合 32-bit 带符号整数范围。

输入：expression = “247+38”
输出：“2(47+38)”
解释：表达式计算得到 2 * (47 + 38) = 2 * 85 = 170 。
注意 “2(4)7+38” 不是有效的结果，因为右括号必须添加在 ‘+’ 的右侧。
可以证明 170 是最小可能值。

这是第288场力扣周赛第二题 原题链接

简单来说就是给定一个字符串，这个字符串是两数之和的数学表达式，然后在"+"号左右分别添加左右括号，组成一个新的数学表达式，求可能组成的所有数学表达式的最小值所对应的数学表达式

🍊2.题目分析

这道题刚开始看的时候感觉文字描述很多，看完理解意思其实思路并不难，而且给定字符串的长度范围为[3,10]并且是合法的数学表达式，直接暴力循环模拟每一种情况就好了（但是需要注意的细节很多😭😭😭）

周赛时我的思路是：

1. 先将字符串以“+”为分隔符分成两个字符串s1、s2

2. 然后使用StringBuffer进行拼接，循环每一个左括号和右括号的位置

3. 使用一个函数来计算每次模拟的数学表达式的值，最后记录最小值的表达式

思路很清晰，但是具体实现的时候写了一百多行的代码，问题一堆，跑都跑不起来😣😣😣

遇到的问题：

1. split()如果使用"+“需要转义字符 “\”，而转义字符”\“也需要转义字符”\“，在网上查阅了一下split()函数是支持正则表达式的因此对于 | , + , * , ^ , $ , / , | , [ , ] , ( , ) , . , \ 等字符使用split()函数需要写成”\\+字符"，例如本题应是**“\\+”**

2. StringBuffer进行拼接时两层for循环，需要两个StringBuffer对象不然就会出现一堆奇怪的数学表达式😭😭😭

3. 忘记了Integer.parseInt()可以将字符串类型的数字转化为整数类型的数字

4. 由于大早上被抓去做核酸，写周赛时又困又饿，导致循环遍历搞混淆了一直运行超时，果然对于我这种菜汪状态再不好简直就是要命😵😵😵

🌰3.代码实现

class Solution {
    public String minimizeResult(String expression) {
        int len = expression.length();
        //确定'+'在字符串expression中的位置
        int pos = expression.indexOf('+');
        int min = Integer.MAX_VALUE;
        String result = "";
        //'+'前面的数字
        for (int left = 0; left < pos; left++) {
            //'+'后面的数字
            for (int right = pos + 1; right < len; right++) {
                //以'+'为分割 s1为左括号前面的字符串  
                
                String s1 = expression.substring(0, left);
                
                //s2为括号里面的字符串 主题右括号必须在右边至少一个数字字符右边 即不能")21"
            
                String s2 = expression.substring(left, right + 1);
                
                //s3为右括号右边的字符串
                String s3 = expression.substring(right + 1);
                 //计算表达式的值
                int num = f(s1, s2, s3);
                if (num < min) {
                    min = num;
                    //使用format字符串格式化函数 加括号
                    result = String.format("%s(%s)%s", s1, s2, s3);
                }
            }
        }

        return result;
    }

    public int f(String s1, String s2, String s3) {
        //将s2字符串以'+'为分割 并求括号里面表达式的值
        String[] split = s2.split("\\+");
        int ans = Integer.parseInt(split[0]) + Integer.parseInt(split[1]);
       
        //将括号里面的值乘于括号外面的数 得到最终结果
       
        if (!s1.isEmpty()) {
            ans *= Integer.parseInt(s1);
        }
        if (!s3.isEmpty()) {
            ans *= Integer.parseInt(s3);
        }
        return ans;
    }
}