面试题目：(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