面试题目:(4)给表达式添加运算符
目录
题目
代码
思路解析
例子
题目
- 题目
- 给定一个仅包含数字 0-9 的字符串 num 和一个目标值整数 target ,在 num 的数字之间添加 二元 运算符(不是一元)+、- 或 * ,
- 返回
- 所有能够得到 target 的表达式。
- 1 <= num.length <= 10
- num 仅含数字
- -231 <= target <= 231 - 1
- 注意
- 返回表达式中的操作数 不应该 包含前导零。
- 示例 1:
- 输入: num = "123", target = 6
- 输出: ["1+2+3", "1*2*3"]
- 解释: “1*2*3” 和 “1+2+3” 的值都是6。
- 示例 2:
- 输入: num = "232", target = 8
- 输出: ["2*3+2", "2+3*2"]
- 解释: “2*3+2” 和 “2+3*2” 的值都是8。
- 示例 3:
- 输入: num = "3456237490", target = 9191
- 输出: []
- 解释: 表达式 “3456237490” 无法得到 9191 。
代码
#include <stdlib.h>
#include <string.h>
#include <stdio.h>void evaluate(int* num_list, int* num_flag, int n, int target) {int end = num_list[0]; for (int i = 1; i < n; i++) {if (num_flag[i] == 1) {end *= num_list[i];} else if (num_flag[i] == 2) {end += num_list[i];} else if (num_flag[i] == 3) {end -= num_list[i];}}if (end == target) {printf("找到表达式: ");for (int i = 0; i < n; i++) {if (i > 0) {if (num_flag[i] == 1) printf("*");if (num_flag[i] == 2) printf("+");if (num_flag[i] == 3) printf("-");}printf("%d", num_list[i]);}printf(" = %d\n", target);}
}void backtrack(int* num_list, int* num_flag, int n, int target, int pos) {if (pos == n) {evaluate(num_list, num_flag, n, target);return;}for (int i = 1; i <= 3; i++) { // 遍历三种运算符num_flag[pos] = i;backtrack(num_list, num_flag, n, target, pos + 1);// 递归下一个运算符}
}int main() {char num[256] = "";int target;printf("num = ");fgets(num, sizeof(num), stdin);if (strlen(num) > 10) return 0;int n = strlen(num) - 1;int num_list[n];for (int i = 0; i < n; i++) {if (num[i] >= '0' && num[i] <= '9') {num_list[i] = num[i] - '0';} else {return 0;}}printf("target = ");scanf("%d", &target);if (target > 230 || target < -231) return 0;int num_flag[n]; // 保存操作符的数组backtrack(num_list, num_flag, n, target, 1);return 0;
}
思路解析
- 接收输入的字符串和目标数字
- 判断其是否输入正确
- 将字符串数字转为整数数组
- 调用递归backtrack函数,从第一位开始递归
- 判断递归索引是否是到最后一位
- 是的话调用验算函数
- 递归标志位数组进行判断加减算出答案
- 判断答案于目标数字是否一样,一样就打印
- 是的话调用验算函数
- 不是的话就继续就进行对标志位数组进行初始化
- 一个数字一个标志位,如果是1就表示乘法,2为加法,3为减法
- 递归索引+1进行递归
- 判断递归索引是否是到最后一位
简单来说就是先从第一个字符开始变化标志位,从1到2到3,也就从乘法加法减法,但在第一个执行乘法前,后面的要先完成从1到2到3的变化,所以就是在第一个执行1的时候要等第二个数字从1到2到3变化完才进行变2,然后又要等第二个数字从1到2到3才变3,如果有第三个数字的话第二个数字也要等第三个数字变化完,一层一层递归,直到递归到最后一个数字后,才开始进行计算
例子
输入 1234 目标 10

相关文章:
面试题目:(4)给表达式添加运算符
目录 题目 代码 思路解析 例子 题目 题目 给定一个仅包含数字 0-9 的字符串 num 和一个目标值整数 target ,在 num 的数字之间添加 二元 运算符(不是一元)、- 或 * ,返回 所有能够得到 target 的表达式。1 < num.length &…...
[C#]将opencvsharp的Mat对象转成onnxruntime的inputtensor的3种方法
第一种方法:在创建tensor时候直接赋值改变每个tensor的值,以下是伪代码: var image new Mat(image_path);inpWidth image.Width;inpHeight image.Height;//将图片转为RGB通道Mat image_rgb new Mat();Cv2.CvtColor(image, image_rgb, Col…...
CTF入门教程(非常详细)从零基础入门到竞赛,看这一篇就够了!
一、CTF简介 CTF(Capture The Flag)中文一般译作夺旗赛,在网络安全领域中指的是网络安全技术人员之间进行技术竞技的一种比赛形式。CTF起源于1996年DEFCON全球黑客大会,以代替之前黑客们通过互相发起真实攻击进行技术比拼的方式。…...
数据链路层 I(组帧、差错控制)【★★★★★】
(★★)代表非常重要的知识点,(★)代表重要的知识点。 为了把主要精力放在点对点信道的数据链路层协议上,可以采用下图(a)所示的三层模型。在这种三层模型中,不管在哪一段…...
悟空降世 撼动全球
文|琥珀食酒社 作者 | 积溪 一只猴子能值多少钱? 答案是:13个小目标 这两天 只要你家没有断网 一定会被这只猴子刷屏 它就是咱国产的3A游戏 《黑神话:悟空》 这只猴子到底有多火? 这么跟你说吧 茅台见了它都…...
Swoole 和 Java 哪个更有优势呢
Swoole 和 Java 各有优势,在性能上不能简单地说哪一个更好,需要根据具体的应用场景来分析。 Swoole 优势:高并发:Swoole 是一个基于 PHP 的异步、协程框架,专为高并发场景设计,适用于 I/O 密集型应用&…...
Salesforce 发布开源大模型 xGen-MM
xGen-MM 论文 在当今 AI 技术飞速发展的时代,一个新的多模态 AI 模型悄然崛起,引起了业界的广泛关注。这个由 Salesforce 推出的开源模型—— xGen-MM,正以其惊人的全能特性和独特优势,在 AI 领域掀起一阵旋风。那么,x…...
冒 泡 排 序
今天咱们单独拎出一小节来聊一聊冒泡排序昂 冒泡排序的核心思想就是:两两相邻的元素进行比较(理解思路诸君可看下图) 接下来我们上代码演示: 以上就是我们初步完成的冒泡排序,大家不难发现,不管数组中的元…...
采用先进的人工智能视觉分析技术,能够精确识别和分析,提供科学、精准的数据支持的智慧物流开源了。
智慧物流视频监控平台是一款功能强大且简单易用的实时算法视频监控系统。它的愿景是最底层打通各大芯片厂商相互间的壁垒,省去繁琐重复的适配流程,实现芯片、算法、应用的全流程组合,从而大大减少企业级应用约95%的开发成本可通过边缘计算技术…...
IAA游戏APP如何让合理地让用户观看更多广告,提高广告渗透率
广告变现已经成为休闲游戏开发者重要的收益方式之一,超50%国内休闲游戏已经采用广告变现的方式,游戏广告预算是游戏行业开发者广告变现的主要预算来源。 #深度好文计划#如何合理地提高广告渗透率? 广告渗透率能直接反映游戏中有广告行为用户…...
环网交换机的特殊作用是什么?
环网交换机作为现代网络建设的重要组成部分,具有独特而特殊的作用。在信息技术迅猛发展的今天,各类数据传输和网络连接需求日益增加,环网交换机的出现为解决这些问题提供了理想的方案。环网交换机通常将多个网络节点通过环形结构连接起来&…...
mac电脑安装Zsh并启用
安装 Zsh 1. 安装 Zsh 新版mac系统会默认安装并使用zsh,如没用,需在终端中安装: brew install zsh2. 安装 Oh My Zsh 克隆Oh My Zsh到你的目录: git clone https://github.com/robbyrussell/oh-my-zsh.git ~/.oh-my-zsh3. 复…...
【后续更新】python搜集上海二手房数据
源码如下: import asyncio import aiohttp from lxml import etree import logging import datetime import openpyxlwb = openpyxl.Workbook() sheet = wb.active sheet.append([房源, 房子信息, 所在区域, 单价, 关注人数和发布时间, 标签]) logging.basicConfig(level=log…...
创建GPTs,打造你的专属AI聊天机器人
在2023年11月的「OpenAI Devday」大会上,OpenAI再度带来了一系列令人瞩目的新功能,其中ChatGPT方面的突破尤为引人关注。而GPTs的亮相,不仅标志着个性化AI时代的到来,更为开发者和普通用户提供了前所未有的便利。接下来࿰…...
深度学习 vector 之模拟实现 vector (C++)
1. 基础框架 这里我们有三个私有变量,使用 _finish - _start 代表 _size,_end_of_storage - _start 代表 _capacity,并且使用到了模版,可以灵活定义存储不同类型的 vector,这里将代码量较小的函数直接定义在类的内部使…...
关于LLC知识10
在LLC谐振腔中能够变化的量 1、输入电压 2、Rac(负载) 所以增益曲线为红色(Rac无穷大)已经是工作的最大极限了,LLC不可能工作在红色曲线之外 负载越重时,增益曲线越往里面 假设: 输入电压…...
最长的严格递增或递减子数组
给你一个整数数组 nums 。 返回数组 nums 中 严格递增 或 严格递减 的最长非空子数组的长度。 示例 1: 输入:nums [1,4,3,3,2] 输出:2 解释: nums 中严格递增的子数组有[1]、[2]、[3]、[3]、[4] 以及 [1,4] 。 nums 中…...
【JavaEE】SpringBoot 统一功能处理:拦截器、统一数据返回与异常处理的综合应用与源码解析
目录 SpringBoot 统⼀功能处理拦截器拦截器快速⼊⻔拦截器详解拦截路径拦截器执⾏流程 登录校验定义拦截器注册配置拦截器 DispatcherServlet 源码分析(了解)初始化(了解) DispatcherServlet的初始化1. HttpServletBean.init()2. FrameworkServlet.initServletBean() WebApplic…...
I2C学习:上拉电阻选取
一.I2C简介 I2C总线是由Philips公司开发的一种简单、双向二线制同步串行总线。I2C总线在使用时,需要接上拉电阻,这是因为I2C接口是开漏输出,如图1所示。 图1 I2C开漏输出 I2C有5种速度模式:标准(100KHz&am…...
AC自动机-1
AC自动机(Aho-Corasick Automaton)是一种高效的多模式字符串匹配算法。它是由Alfred Aho和Margaret Corasick在1975年提出的。这种算法可以在一次扫描输入文本的情况下,同时查找多个模式串。 基本概念 Trie树 AC自动机是基于字典树数据结构构建的字典树…...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...
成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战
在现代战争中,电磁频谱已成为继陆、海、空、天之后的 “第五维战场”,雷达作为电磁频谱领域的关键装备,其干扰与抗干扰能力的较量,直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器,凭借数字射…...
selenium学习实战【Python爬虫】
selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...
AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机
这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机,因为在使用过程中发现 Airsim 对外部监控相机的描述模糊,而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置,最后在源码示例中找到了,所以感…...
系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文通过代码驱动的方式,系统讲解PyTorch核心概念和实战技巧,涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...
数据结构:递归的种类(Types of Recursion)
目录 尾递归(Tail Recursion) 什么是 Loop(循环)? 复杂度分析 头递归(Head Recursion) 树形递归(Tree Recursion) 线性递归(Linear Recursion)…...
