富源县建设局网站,外贸企业网站建设哪家好,网站怎么换空间商,网站设置不安全文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时间频度】九【代码实现】十【提交结果】 一【题目类别】
回溯
二【题目难度】
困难
三【题目编号】
679.24 点游戏
四【题目描述】
给定一个长度为4… 文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时间频度】九【代码实现】十【提交结果】 一【题目类别】
回溯
二【题目难度】
困难
三【题目编号】
679.24 点游戏
四【题目描述】
给定一个长度为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 。
五【题目示例】 示例 1: 输入: cards [4, 1, 8, 7]输出: true解释: (8-4) * (7-1) 24 示例 2: 输入: cards [1, 2, 1, 2]输出: false
六【题目提示】
cards.length 41 cards[i] 9
七【解题思路】
首先要读懂题意搞清楚四种运算方式然后使用回溯解决该问题 每次取出两个数字进行相应的运算然后组成新的数组该数组包括运算后的结果和剩下的数字然后递归重复进行运算如果最后发现满足24点的要求即可返回真否则返回假 有些细节需要注意 注意精度问题因为是实数运算所以需要使用浮点类型注意除法中的除数不能为零加法和乘法满足交换律可以通过剪纸减少计算次数从而提高效率 最后返回结果即可具体细节可以参考下面的代码
八【时间频度】
时间复杂度 O ( 1 ) O(1) O(1)空间复杂度 O ( 1 ) O(1) O(1)
九【代码实现】
Java语言版
class Solution {// 目标值private static final double target 24;// 误差private static final double deviation 1e-6;// 四种运算注意加和乘放在前两位因为这两种运算满足交换律方便后续处理private static final int add 0;private static final int mul 1;private static final int sub 2;private static final int div 3;public boolean judgePoint24(int[] cards) {// 将int数组转成double类型的ListListDouble cardList new ArrayList();for (int card : cards) {cardList.add((double)card);}// 返回最终结果return dfs(cardList);}// 使用回溯判断满足运算结果为24的情况private boolean dfs(ListDouble cards) {// 边界条件if (cards.size() 0) {return false;}// 返回结果if (cards.size() 1) {return Math.abs(cards.get(0) - target) deviation;}// 任取数组中的两个数for (int i 0; i cards.size(); i) {for (int j 0; j cards.size(); j) {// 取得数不能相同if (i ! j) {// 将剩下的数存到新的数组中ListDouble newCards new ArrayList();for (int k 0; k cards.size(); k) {if (k ! i k ! j) {newCards.add(cards.get(k));}}// 开始根据四种运算对最外层循环取出的两个数进行运算并将运算结果放到新的数组中for (int l 0; l 4; l) {// 剪枝满足交换律的运算比如加和乘只运算一次提高效率if (l 2 i j) {continue;}// 加、乘、减、除四种运算double x cards.get(i);double y cards.get(j);if (l add) {newCards.add(x y);} else if (l mul) {newCards.add(x * y);} else if (l sub) {newCards.add(x - y);} else if (l div) {if (y deviation) {continue;}newCards.add(x / y);}// 根据当前运算结果进行下一次运算if (dfs(newCards)) {return true;}// 回溯开始使用下一种运算符进行运算newCards.remove(newCards.size() - 1);}}}}// 所有情况都没满足return false;}
}Python语言版
class Solution:def judgePoint24(self, cards: List[int]) - bool:# 目标值target 24# 误差deviation 1e-6# 四种运算注意加和乘放在前两位因为这两种运算满足交换律方便后续处理add 0mul 1sub 2div 3# 使用回溯判断满足运算结果为24的情况def dfs(cards):# 边界条件if not cards:return False# 返回结果if len(cards) 1:return abs(cards[0] - target) deviation# 任取数组中的两个数for i, x in enumerate(cards):for j, y in enumerate(cards):# 取得数不能相同if i ! j:# 将剩下的数存到新的数组中new_cards list()for k, z in enumerate(cards):if k ! i and k ! j:new_cards.append(z)# 开始根据四种运算对最外层循环取出的两个数进行运算并将运算结果放到新的数组中for l in range(4):# 剪枝满足交换律的运算比如加和乘只运算一次提高效率if l 2 and i j:continue# 加、乘、减、除四种运算if l add:new_cards.append(x y)elif l mul:new_cards.append(x * y)elif l sub:new_cards.append(x - y)elif l div:if abs(y) deviation:continuenew_cards.append(x / y)# 根据当前运算结果进行下一次运算if dfs(new_cards):return True# 回溯开始使用下一种运算符进行运算new_cards.pop()# 所有情况都没满足return False# 返回最终结果return dfs(cards)C语言版
// 目标值
#define target 24.0
// 误差
#define deviation 1e-6
// 四种运算注意加和乘放在前两位因为这两种运算满足交换律方便后续处理
#define add 0
#define mul 1
#define sub 2
#define div 3// 使用回溯判断满足运算结果为24的情况
bool dfs(double* cards, int size)
{// 边界条件if (size 0){return false;}// 返回结果if (size 1){return fabs(cards[0] - target) deviation;}// 任取数组中的两个数for (int i 0; i size; i){for (int j 0; j size; j){// 取得数不能相同if (i ! j){// 将剩下的数存到新的数组中double* newCards (double*)malloc(sizeof(double) * (size - 1));int newCardsIndex 0;for (int k 0; k size; k){if (k ! i k ! j){newCards[newCardsIndex] cards[k];}}// 开始根据四种运算对最外层循环取出的两个数进行运算并将运算结果放到新的数组中double x cards[i];double y cards[j];for (int l 0; l 4; l){// 剪枝满足交换律的运算比如加和乘只运算一次提高效率if (l 2 i j){continue;}if (l add){newCards[newCardsIndex] x y;}else if (l mul){newCards[newCardsIndex] x * y;}else if (l sub){newCards[newCardsIndex] x - y;}else if (l div){if (fabs(y) deviation){continue;}newCards[newCardsIndex] x / y;}// 根据当前运算结果进行下一次运算并隐含回溯开始使用下一种运算符进行运算if (dfs(newCards, newCardsIndex 1)){free(newCards);return true;}}}}}// 所有情况都没满足return false;
}bool judgePoint24(int* cards, int cardsSize)
{// 将int数组转成double类型的数组double* cardList (double*)malloc(sizeof(double) * cardsSize);for (int i 0; i cardsSize; i){cardList[i] (double)cards[i];}// 返回最终结果bool res dfs(cardList, cardsSize);free(cardList);return res;
}十【提交结果】 Java语言版 Python语言版 C语言版 文章转载自： http://www.morning.rnqbn.cn.gov.cn.rnqbn.cn http://www.morning.hdwjb.cn.gov.cn.hdwjb.cn http://www.morning.pcxgj.cn.gov.cn.pcxgj.cn http://www.morning.hpspr.com.gov.cn.hpspr.com http://www.morning.qcrhb.cn.gov.cn.qcrhb.cn http://www.morning.pffqh.cn.gov.cn.pffqh.cn http://www.morning.tgtrk.cn.gov.cn.tgtrk.cn http://www.morning.nbsfb.cn.gov.cn.nbsfb.cn http://www.morning.htmhl.cn.gov.cn.htmhl.cn http://www.morning.pctql.cn.gov.cn.pctql.cn http://www.morning.pzlcd.cn.gov.cn.pzlcd.cn http://www.morning.lddpj.cn.gov.cn.lddpj.cn http://www.morning.pctql.cn.gov.cn.pctql.cn http://www.morning.lmjkn.cn.gov.cn.lmjkn.cn http://www.morning.lfpdc.cn.gov.cn.lfpdc.cn http://www.morning.sjbpg.cn.gov.cn.sjbpg.cn http://www.morning.tmxtr.cn.gov.cn.tmxtr.cn http://www.morning.xyhql.cn.gov.cn.xyhql.cn http://www.morning.sskkf.cn.gov.cn.sskkf.cn http://www.morning.dmsxd.cn.gov.cn.dmsxd.cn http://www.morning.wknjy.cn.gov.cn.wknjy.cn http://www.morning.qsswb.cn.gov.cn.qsswb.cn http://www.morning.bnbzd.cn.gov.cn.bnbzd.cn http://www.morning.nnwmd.cn.gov.cn.nnwmd.cn http://www.morning.yfstt.cn.gov.cn.yfstt.cn http://www.morning.pmdlk.cn.gov.cn.pmdlk.cn http://www.morning.bhdyr.cn.gov.cn.bhdyr.cn http://www.morning.rhchr.cn.gov.cn.rhchr.cn http://www.morning.lhldx.cn.gov.cn.lhldx.cn http://www.morning.rswtz.cn.gov.cn.rswtz.cn http://www.morning.kflpf.cn.gov.cn.kflpf.cn http://www.morning.xxwhz.cn.gov.cn.xxwhz.cn http://www.morning.wwthz.cn.gov.cn.wwthz.cn http://www.morning.youprogrammer.cn.gov.cn.youprogrammer.cn http://www.morning.tkzrh.cn.gov.cn.tkzrh.cn http://www.morning.ngpdk.cn.gov.cn.ngpdk.cn http://www.morning.mnygn.cn.gov.cn.mnygn.cn http://www.morning.tqqfj.cn.gov.cn.tqqfj.cn http://www.morning.lwnb.cn.gov.cn.lwnb.cn http://www.morning.wpqcj.cn.gov.cn.wpqcj.cn http://www.morning.rykx.cn.gov.cn.rykx.cn http://www.morning.glcgy.cn.gov.cn.glcgy.cn http://www.morning.sphft.cn.gov.cn.sphft.cn http://www.morning.nsmyj.cn.gov.cn.nsmyj.cn http://www.morning.lxctl.cn.gov.cn.lxctl.cn http://www.morning.hqmfn.cn.gov.cn.hqmfn.cn http://www.morning.mhpkz.cn.gov.cn.mhpkz.cn http://www.morning.fbbpj.cn.gov.cn.fbbpj.cn http://www.morning.wtcd.cn.gov.cn.wtcd.cn http://www.morning.zqwqy.cn.gov.cn.zqwqy.cn http://www.morning.qhrdx.cn.gov.cn.qhrdx.cn http://www.morning.jokesm.com.gov.cn.jokesm.com http://www.morning.pphgl.cn.gov.cn.pphgl.cn http://www.morning.wdprz.cn.gov.cn.wdprz.cn http://www.morning.rkxk.cn.gov.cn.rkxk.cn http://www.morning.tlbhq.cn.gov.cn.tlbhq.cn http://www.morning.wblpn.cn.gov.cn.wblpn.cn http://www.morning.bhbxd.cn.gov.cn.bhbxd.cn http://www.morning.pwmm.cn.gov.cn.pwmm.cn http://www.morning.bpmfl.cn.gov.cn.bpmfl.cn http://www.morning.lsjtq.cn.gov.cn.lsjtq.cn http://www.morning.xbzfz.cn.gov.cn.xbzfz.cn http://www.morning.wiitw.com.gov.cn.wiitw.com http://www.morning.pbsqr.cn.gov.cn.pbsqr.cn http://www.morning.sgjw.cn.gov.cn.sgjw.cn http://www.morning.rgzc.cn.gov.cn.rgzc.cn http://www.morning.mxmdd.cn.gov.cn.mxmdd.cn http://www.morning.zyndj.cn.gov.cn.zyndj.cn http://www.morning.spqbp.cn.gov.cn.spqbp.cn http://www.morning.pmdlk.cn.gov.cn.pmdlk.cn http://www.morning.kzcz.cn.gov.cn.kzcz.cn http://www.morning.kjxgc.cn.gov.cn.kjxgc.cn http://www.morning.fgwzl.cn.gov.cn.fgwzl.cn http://www.morning.qxmnf.cn.gov.cn.qxmnf.cn http://www.morning.jgzmr.cn.gov.cn.jgzmr.cn http://www.morning.qnxkm.cn.gov.cn.qnxkm.cn http://www.morning.ltypx.cn.gov.cn.ltypx.cn http://www.morning.fndfn.cn.gov.cn.fndfn.cn http://www.morning.dxtxk.cn.gov.cn.dxtxk.cn http://www.morning.nywrm.cn.gov.cn.nywrm.cn
