前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2022-04-23:给定一个长度为4的整数数组 cards 。你有 4 张卡片,每张卡片上都包含一个范围在 [1,9] 的数字

2022-04-23:给定一个长度为4的整数数组 cards 。你有 4 张卡片,每张卡片上都包含一个范围在 [1,9] 的数字

作者头像
福大大架构师每日一题
发布2022-06-04 10:36:00
3460
发布2022-06-04 10:36:00
举报

2022-04-23:给定一个长度为4的整数数组 cards 。你有 4 张卡片,每张卡片上都包含一个范围在 [1,9] 的数字。您应该使用运算符 ['+', '-', '*', '/'] 和括号 '(' 和 ')' 将这些卡片上的数字排列成数学表达式,以获得值24。

你须遵守以下规则:

除法运算符 '/' 表示实数除法,而不是整数除法。

例如, 4 /(1 - 2 / 3)= 4 /(1 / 3)= 12 。

每个运算都在两个数字之间。特别是,不能使用 “-” 作为一元运算符。

例如,如果 cards =[1,1,1,1] ,则表达式 “-1 -1 -1 -1” 是 不允许 的。

你不能把数字串在一起

例如,如果 cards =[1,2,1,2] ,则表达式 “12 + 12” 无效。

如果可以得到这样的表达式,其计算结果为 24 ,则返回 true ,否则返回 false 。

输入: cards = [4, 1, 8, 7]。

输出: true。

解释: (8-4) * (7-1) = 24。

力扣679. 24 点游戏。

答案2022-04-23:

自然智慧,暴力尝试。可利用原数组空间。

代码用golang编写。代码如下:

代码语言:javascript
复制
package main

import "fmt"

func main() {
  cards := []int{1, 1, 3, 4}
  ret := judgePoint24(cards)
  fmt.Println(ret)
}

func judgePoint24(cards []int) bool {
  if len(cards) == 0 {
    return false
  }
  n := len(cards)
  arr := make([]*Number, n)
  for i := 0; i < n; i++ {
    arr[i] = NewNumber(cards[i], 1)
  }
  return judge(arr, len(cards))
}

// arr中,有效的范围arr[0...size-1] ... 再往右,都无效了,不用看了!
func judge(arr []*Number, size int) bool {
  if size == 1 {
    return arr[0].numerator == 24 && arr[0].denominator == 1
  }
  for i := 0; i < size; i++ {
    for j := i + 1; j < size; j++ {
      inum := arr[i]
      jnum := arr[j]
      arr[j] = arr[size-1]
      arr[i] = add(inum, jnum)
      if judge(arr, size-1) {
        return true
      }
      arr[i] = minus(inum, jnum)
      if judge(arr, size-1) {
        return true
      }
      arr[i] = minus(jnum, inum)
      if judge(arr, size-1) {
        return true
      }
      arr[i] = multiply(inum, jnum)
      if judge(arr, size-1) {
        return true
      }
      arr[i] = divide(inum, jnum)
      if arr[i] != nil && judge(arr, size-1) {
        return true
      }
      arr[i] = divide(jnum, inum)
      if arr[i] != nil && judge(arr, size-1) {
        return true
      }
      arr[i] = inum
      arr[j] = jnum
    }
  }
  return false
}

type Number struct {
  numerator   int
  denominator int
}

func NewNumber(n, d int) *Number {
  ans := new(Number)
  ans.numerator = n
  ans.denominator = d
  return ans
}

func add(a, b *Number) *Number {
  return simple(a.numerator*b.denominator+b.numerator*a.denominator, a.denominator*b.denominator)
}

func minus(a, b *Number) *Number {
  return simple(a.numerator*b.denominator-b.numerator*a.denominator, a.denominator*b.denominator)
}

func multiply(a, b *Number) *Number {
  return simple(a.numerator*b.numerator, a.denominator*b.denominator)
}

func divide(a, b *Number) *Number {
  if b.numerator == 0 {
    return nil
  } else {
    return simple(a.numerator*b.denominator, a.denominator*b.numerator)
  }
}

func simple(up, down int) *Number {
  if up == 0 {
    return NewNumber(0, 1)
  }
  gcd0 := abs(gcd(up, down))
  return NewNumber(up/gcd0, down/gcd0)
}

func abs(a int) int {
  if a < 0 {
    return -a
  } else {
    return a
  }
}

func gcd(a, b int) int {
  if b == 0 {
    return a
  } else {
    return gcd(b, a%b)
  }
}

执行结果如下:

***

[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_02_2_week/Code01_24Game.java)

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-04-23,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 福大大架构师每日一题 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档