网站建设清单表格,天元建设集团坑人,哈尔滨寸金网站建设公司口碑,望野原文及翻译赏析目录
题目
代码
思路解析
例子 题目
题目 给定一个仅包含数字 0-9 的字符串 num 和一个目标值整数 target #xff0c;在 num 的数字之间添加 二元 运算符#xff08;不是一元#xff09;、- 或 * #xff0c;返回 所有能够得到 target 的表达式。1 num.length 在 num 的数字之间添加 二元 运算符不是一元、- 或 * 返回 所有能够得到 target 的表达式。1 num.length 10num 仅含数字-231 target 231 - 1注意 返回表达式中的操作数 不应该 包含前导零。示例 1: 输入: num 123, target 6输出: [123, 1*2*3]解释: “1*2*3” 和 “123” 的值都是6。示例 2: 输入: num 232, target 8输出: [2*32, 23*2]解释: “2*32” 和 “23*2” 的值都是8。示例 3: 输入: num 3456237490, target 9191输出: []解释: 表达式 “3456237490” 无法得到 9191 。
代码
#include stdlib.h
#include string.h
#include stdio.hvoid 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
