如何不用百度推广做网站,教育行业网站模板,人人秀h5制作软件,上海百度移动关键词排名优化说在前面 #x1f388;不知道大家对于算法的学习是一个怎样的心态呢#xff1f;为了面试还是因为兴趣#xff1f;不管是出于什么原因#xff0c;算法学习需要持续保持。 题目描述
给你一个下标从 0 开始的字符串 expression #xff0c;格式为 “num1num2” #xff0c;…说在前面 不知道大家对于算法的学习是一个怎样的心态呢为了面试还是因为兴趣不管是出于什么原因算法学习需要持续保持。 题目描述
给你一个下标从 0 开始的字符串 expression 格式为 “num1num2” 其中 num1 和 num2 表示正整数。 请你向 expression 中添加一对括号使得在添加之后 expression 仍然是一个有效的数学表达式并且计算后可以得到 最小 可能值。左括号 必须 添加在 ‘’ 的左侧而右括号必须添加在 ‘’ 的右侧。 返回添加一对括号后形成的表达式 expression 且满足 expression 计算得到 最小 可能值。如果存在多个答案都能产生相同结果返回任意一个答案。 生成的输入满足expression 的原始值和添加满足要求的任一对括号之后 expression 的值都符合 32-bit 带符号整数范围。 示例 1
输入expression 24738
输出2(4738)
解释表达式计算得到 2 * (47 38) 2 * 85 170 。
注意 2(4)738 不是有效的结果因为右括号必须添加在 的右侧。
可以证明 170 是最小可能值。示例 2
输入expression 1234
输出1(23)4
解释表达式计算得到 1 * (2 3) * 4 1 * 5 * 4 20 。示例 3
输入expression 999999
输出(999999)
解释表达式计算得到 999 999 1998 。提示
3 expression.length 10
expression 仅由数字 1 到 9 和 组成
expression 由数字开始和结束
expression 恰好仅含有一个 .
expression 的原始值和添加满足要求的任一对括号之后 expression 的值都符合 32-bit 带符号整数范围思路分析
题目要求其实很简单就是我们可以在式子中加一个加一对括号要求是括号必须在加号的两边然后要我们求加括号后算出的结果为最小的式子。 总结一下就是式子可以写成n1(n2n3)n4、(n2n3)n4 或 n1(n2n3) 这三种形式我们只需要枚举每一种分割情况然后记录最小值结果维护最小值式子即可。 如示例1的24738,总共有这么几种情况
(24738)-285(2473)8-20002(4738)-1702(473)8-80024(738)-108024(73)8-1920 枚举完所有情况之后我们就能很清楚的知道答案就是2(4738)
AC代码
/*** param {string} expression* return {string}*/
var minimizeResult function (expression) {const num expression.split();const num1 num[0].toString();const num2 num[1].toString();let res parseInt(num[0]) parseInt(num[1]);let ans ( expression );for (let i 1; i num1.length; i) {let n1 parseInt(num1.slice(0, i)),n2 parseInt(num1.slice(i)) || ;for (let j 0; j num2.length; j) {let n3 parseInt(num2.slice(0, j) || Infinity),n4 parseInt(num2.slice(j));let sum n1 * (n2 n3) * (n4 || 1);if (n2 ) sum (n1 n3) * (n4 || 1);if (res sum) {if (n2 ! ) ans n1 ( n2 n3 );else ans ( n1 n3 );if (n4) ans n4;res sum;}}}return ans;
};公众号
关注公众号『前端也能这么有趣』获取更多有趣内容。
说在后面 这里是 JYeontu现在是一名前端工程师有空会刷刷算法题平时喜欢打羽毛球 平时也喜欢写些东西既为自己记录 也希望可以对大家有那么一丢丢的帮助写的不好望多多谅解 写错的地方望指出定会认真改进 偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章有兴趣的也可以关注下。在此谢谢大家的支持我们下文再见 。
