通过对数组元素应用“+”和“*”操作可以得到的最小数字

阿枫大大_5610

阿枫大大_5610

2023-08-31

876人浏览

转载

通过对数组元素应用“+”和“*”操作可以得到的最小数字

问题陈述

我们给出了一个长度为“N”的数组,其中包含一些正整数。另外,我们给出了长度为“N-1”的字符串,仅包含“*”和“+”字符,其中“*”是乘法运算符,“+”是加法运算符。我们要求对数组元素进行算术运算,以获得最小的正整数值。

示例

输入

array = [1,2,3], str = “*+”

输出

5

说明

它是 ((1*2) + 3) 的结果值。

输入

array = [3, 3, 3, 3], str = ‘*++’

输出

15

说明

它执行 array[0]*array[1],等于 9,并表示结果 1。之后,它将 result1 与 array[2] 相加,等于 12,并表示为 result2。接下来,它将 result2 添加到数组 [3],等于 15。

输入

array =  [1, 3, 5, 6], str = “**+”

输出

21

说明

它是 ((1*3*5) + 6) 的结果值。

方法一

我们将使用位掩码来解决此方法中的问题。

每当我们有两个选择时,我们就可以使用位掩码。在这里,我们要求以任意顺序应用算术运算,但我们需要在给定字符串的乘法和算术运算之间进行选择

因此,位掩码使我们能够获得所有可能的方式来排列两个算术运算符。之后,我们可以对每路进行算术运算,并检查结果是否为最小值。

让我们通过示例输入来清楚上述逻辑。在下面的示例中,数组 = [1. 3, 5, 6],字符串 = “*++”。

这里,字符串长度为3。因此,我们总共可以有8(2^3)个位掩码,分别是000, 001, 010, 100, 110, 101, 011, 111。

现在,如果我们假设“1”为“*”,“0”为“+”运算符,我们就可以得到字符串中给出的算术运算符的所有排列。

然而,只有当“1”的总数等于“*”运算符的数量,并且“0”的数量等于“+”运算符的数量时,我们才应该使用任何排列。

算法

用户应按照以下算法来实现上述方法。

  • 步骤 1 - 定义“totalMul”变量并将其初始化为零,以存储字符串中乘法算术运算符的总数。

    圣诞节日快乐星星元素动画特效
    圣诞节日快乐星星元素动画特效

    css3动画,元素,元素动画,css3绘图,圣诞节,圣诞,纯css3

    下载
  • 步骤 2 - 使用 for 循环迭代给定的字符串。如果当前字符等于“*”,则将“totalMul”变量的值增加 1。

  • 步骤 3 - 使用for循环获取X等于字符串长度时的所有可能位掩码。这里,'len'是数组长度,'len - 1'是字符串长度。

  • 步骤 4 - 定义“setBitCount”变量来存储当前掩码中设置的位数。另外,定义“order”列表来存储算术运算的当前顺序。

  • 步骤 5 - 在 for 循环中,使用另一个 for 循环来获取当前掩码中设置位的总数 (‘1’)。左移1位j,与I进行&运算,判断第j位是否置位。

  • 步骤 6 - 如果当前位是设置位,则增加“setBitCount”变量的值并将“*”推入顺序向量中;否则,将“+”推入顺序向量中。

  • 第7步 - 如果setBitCount的值等于totalMul的值相同,则意味着我们可以使用当前掩码来安排算术运算;否则,我们将进入下一次迭代。

  • 第 8 步 - 在 if 语句中,使用“deque”数据结构定义“currentQueue”来存储数组元素。

  • 步骤 9 - 遍历 'order' 列表。如果当前字符是 '*',则弹出队列中的最后一个元素,并将其与当前数组索引处的元素相乘。

  • 第 10 步 - 如果“orders”列表中的当前字符为“+”,则将当前数组元素推送到“currentQueue”中。

  • 第 11 步 - 使用 while 循环从“currentQueue”中弹出所有元素并对所有元素求和。

  • 第 12 步 - 使用 min() 函数从“minimum”和“sum”变量中获取最小值。

示例

#include <bits>
using namespace std;

// Function to get the minimum number by applying mathematical operations in any order.
int getMinimumSum(int array[], int len, string str){
   // to store a total number of multiplication operators in the string.
   int totalMul = 0;
   for (int i = 0; i  order;
      // finding a total number of mask bits in the current mask 'i'. If the current bit is set to bit, push '*' in the order vector; else, push '+'.
      for (int j = 0; j  currentQueue;
         // push the first element in the queue.
         currentQueue.push_back(array[0]);
         for (int j = 0; j  0){
            int temp = currentQueue.front();
            sum += temp;
            currentQueue.pop_front();
         }
         // get the minimum value.
         minimum = min(minimum, sum);
      }
   }
   return minimum;
}

int main(){
   int array[] = {1, 3, 5, 6};
   string str = "*++";
   int len = sizeof(array) / sizeof(array[0]);
   cout <h3>输出</h3>
<pre class="brush:php;toolbar:false;">Minimum number value can be achieved is : 14
  • 时间复杂度 - O(2N-1*N),其中 N 是数组的长度。当我们迭代所有位掩码时,在其中,我们使用 for 循环来计算当前掩码中设置位的总数,它是 O(2N-1*N)。

  • 空间复杂度 − O(N),因为我们使用列表来存储算术运算符的顺序。

相关文章

PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

2026.11.12

120

15

Go-Zero安装与goctl环境配置教程
Go-Zero安装与goctl环境配置教程

本专题围绕Go-Zero的安装与工具链配置展开,讲清Go版本要求、goctl安装方式、代理镜像、protoc依赖与环境变量设置,说明多版本共存、升级回退与CI流水线安装的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.12

100

15

Go-Zero零基础入门教程
Go-Zero零基础入门教程

本专题整理Go-Zero的入门知识,从框架定位、环境准备到跑通第一个API服务,讲清目录分层、配置加载、日志与中间件的基本用法,并对比Gin、Kratos的差异,帮助Go开发者建立整体认知,判断它是否适合当前项目。

2026.11.12

60

15

Postman身份认证怎么配置
Postman身份认证怎么配置

本专题从实际API接口调试场景出发,讲解Postman身份认证的完整配置流程,包括常见认证协议介绍、授权参数设置、访问令牌填写、OAuth 2.0授权及认证失败排查,帮助用户正确完成接口授权与访问验证。

2026.11.06

160

12

Postman请求头Headers怎么设置
Postman请求头Headers怎么设置

围绕Postman HTTP请求头配置展开,讲解Headers选项的具体使用方式,包括Key和Value参数填写、请求头信息添加、常见Header字段设置及请求头修改方法,帮助用户解决接口调试过程中遇到的请求头配置问题。

2026.11.06

140

13

Postman接口请求发送教程
Postman接口请求发送教程

详细介绍Postman接口请求的创建与发送方法,涵盖GET和POST请求、URL配置、请求参数、Headers请求头、Body请求体设置以及响应结果查看,帮助用户掌握Postman接口请求的完整操作流程。

2026.11.06

120

10

DBeaver怎么导入数据
DBeaver怎么导入数据

DBeaver数据导入专题,整理Excel、CSV、SQL、TXT等常见文件的数据导入方法,涵盖目标数据库选择、数据表创建、字段映射、数据类型设置及导入参数配置等操作,帮助用户将本地文件中的数据写入数据库,并了解批量导入、重复数据处理和导入失败等常见问题的解决方法。

2026.11.05

100

12

DBeaver安全防护教程大全
DBeaver安全防护教程大全

DBeaver安全防护专题,围绕数据库连接安全、账号密码保护和访问权限管理展开,整理SSL/TLS加密连接、SSH隧道、数据库凭据保存及证书验证等配置方法,同时介绍敏感信息保护、远程连接风险和高权限账号使用等注意事项,帮助用户提高数据库日常管理的安全性。

2026.11.05

100

12

DBeaver连接创建与配置教程
DBeaver连接创建与配置教程

本专题聚焦DBeaver数据库连接配置与管理,覆盖从新建连接、选择数据库类型到填写连接参数和验证连接的完整流程。针对MySQL、PostgreSQL、SQL Server等常见数据库,整理相应的连接设置方法,并提供驱动缺失、认证失败和连接异常等问题的排查方向。

2026.11.04

100

16

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
可灵 VIDEO 3.0官方使用手册
可灵 VIDEO 3.0官方使用手册

共0课时 | 0人学习

CSS教程
CSS教程

共754课时 | 102.3万人学习