360笔试：修复方程

题目描述

输入数据只包含合法数字和+或者=，判断是否插入一个数字使得左右两边数值相等，如16=1+23，在1后面插入0，得到16=10+23

解题思路

通过枚举的方法，往结果小的一边的所有可能位置插入0-9的数字「注意处理前导0」，然后找到左右两边相等的情况

代码实现

package main

import (
    "fmt"
    "strconv"
    "strings"
)

func Solution(op []string) {
    // 1. 在最小值的那边插入
    insert := func(fu []byte, target int) bool {
        var l, r int // 记录一个数的左右边界
        for i := 0; i < len(fu); i++ {
            if fu[i] >= '0' && i <= '9' {
                r++
            } else {
                // 一共有n+1种插法
                tfu := fu[l:r]
                n := r - l
                for k := n; k >= 0; k-- {
                    for j := 0; j < 10; j++ {
                        tmp := ""
                        if k == 0 && j == 0 {
                            continue
                        }
                        // 拼接前部分
                        tmp += string(fu[:l])
                        // 拼接当前数字前部分
                        tmp += string(tfu[:k])
                        // 插入数字并拼接剩余部分
                        tmp = tmp + string(byte('0'+j)) + string(tfu[k:]) + string(fu[r:])
                        if getValue(string(tmp)) > target {
                            break
                        }
                        if getValue(string(tmp)) == target {
                            return true
                        }
                    }
                }
                r++
                l = r
            }
        }
        return false
    }

    for _, ps := range op {
        fun := strings.Split(ps, "=")
        l, r := getValue(fun[0]), getValue(fun[1])
        if l < r {
            if insert([]byte(fun[0]), r) {
                fmt.Println("Yes")
            } else {
                fmt.Println("No")
            }
        } else if l > r {
            if insert([]byte(fun[1]), l) {
                fmt.Println("Yes")
            } else {
                fmt.Println("No")
            }
        } else {
            fmt.Println("Yes")
        }
    }
}
func getValue(x string) int {
    var sum int
    addSub := strings.Split(x, "+")
    for _, astr := range addSub {
        muSub := strings.Split(astr, "*")
        a, _ := strconv.Atoi(muSub[0])
        if len(muSub) > 1 {
            b, _ := strconv.Atoi(muSub[1])
            a = a * b
        }
        sum += a
    }
    return sum
}