面试题目：(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，如果有第三个数字的话第二个数字也要等第三个数字变化完，一层一层递归，直到递归到最后一个数字后，才开始进行计算