已掉线,重新登录

首页 > 绿虎论坛 > 历史版块 > 编程 > PHP > 讨论/求助

标题: 一个算法题

作者: @Ta

时间: 2021-11-03发布,2021-11-03修改

点击: 14592

描述: 手里有一组数字卡片,每个人说出自己想要的一组数字(只能领到一张想要的卡片)。要判断手里的卡片是否能按大家需要分配每一个人。

输入: 一个二维数组(行数组指某人想要的数字,所有行组成的数组指每个人的意愿)和a个元素的一维数组(我手里存在的数字卡片)

输出: true/false(是否可以按需要分配数字给大家)

编程语言: PHP, 只能使用标准库


输入/输出示例:

输入参数1
array(
  array(1,2),
  array(1,3),
  array(3)
)
输入参数2
array(1,3,3)

输出: true


-----
已经按要求重新描述了问题

[隐藏样式|查看源码]


『回复列表(24|隐藏机器人聊天)』

1.

@老虎会游咏q,输入定义的不清楚,无法编写交互代码。
1,2是什么?
1,3是什么?
3是什么?
为什么有一个空行
1,3,3是什么?

(/@Ta/2021-11-03 20:26//)

2.

还有,需要指定编程语言和允许使用的库函数。否则某些题目在某些编程语言+库的组合下会变得十分简单,算法不需要自己编写。
比如,PHP似乎可以直接使用in_array给出答案。如果编程语言自带map结构,算法也会变简单。

(/@Ta/2021-11-03 20:31//)

3.

@老虎会游咏q,你的示例输出是错的吧,1,3,3连2都没有,不可能是true啊。

(/@Ta/2021-11-03 21:41//)

4.

@老虎会游咏q,给你一个关于数据结构的思路:

$map = array(
   '卡片1' => 数量,
   ‘卡片2’ => 数量,
);

比如

$map = array(
   '1' => 1,
   ‘3’ => 2,
);

至于代码逻辑,你应该自己思考。

可能用到的操作:

  • 初始化map:$map = array();
  • map中是否存在某值:if (isset($map[$key])) {...}
  • 把数据放入map:$map[$key] = 1;
  • 增加数量:$map[$key]++;
  • 减少数量:$map[$key]--;
  • 是否还有剩余:if ($map[$key] > 0) {...}
  • foreach循环:foreach ($array as $value) {...}
(/@Ta/2021-11-03 21:54//)

5.

如果零基础,可能需要 https://www.runoob.com/php/php-syntax.html

(/@Ta/2021-11-03 21:52//)

6.

@老虎会游泳,我感觉是动态规划的题唉,还要回溯的。 给的示例好像没错,甲想要1,2;乙想要1,3;丙想要3。我有1,3,3,给甲1,给乙3,给丙3;返回true
红米K30 Pro(变焦版)

(/@Ta/2021-11-03 22:01//)

7. @老虎会游泳,帖子内容确实是准确的描述了该问题。@Curtion,动态规划听说过,不懂。希望能在这里学习下^_^
(/@Ta/2021-11-03 22:23//)

8.

@Curtion@老虎会游咏q,哦确实是,我没看到“只能领到一张想要的卡片”。

(/@Ta/2021-11-03 22:24//)

9.

@老虎会游咏q@Curtion,离散动态规划可以转换成排列组合。
比如:
array(1,2),
array(1,3),
array(3)
全排列为:
1,1,3
2,1,3
1,3,3
2,3,3
然后逐一和1,3,3进行对比就行了。对比成功返回true,全部对比失败返回false。

比较前记得排序,否则可能会出现'3,1,3'不等于'1,3,3'的情况。

(/@Ta/2021-11-03 22:39//)

10.

排序后的数组可以直接比较(使用PHP5.4数组语法):

$a = [3, 1, 3];
$b = [1, 3, 3];
sort($a);
sort($b);
var_dump($a == $b);
var_dump($a === $b);

Screenshot_20211103_223726.jpg

(/@Ta/2021-11-03 22:37//)

11. @老虎会游泳,👍是一种不错的算法。如果是动态规划应该怎么处理,复杂度上有优势吗
(/@Ta/2021-11-03 22:38//)

12. @老虎会游泳,有推荐的关于动态规划的资料(离散动态规划?)吗。我想学一手🙃
(/@Ta/2021-11-03 22:44//)

13.

@老虎会游咏q,这句话是我突然间自己想到的。

离散动态规划可以转换成排列组合

所以资料肯定是没有的啊

(/@Ta/2021-11-03 23:26//)

14.

@老虎会游咏q,上面的方法是对输入参数1进行排列组合,然后在输入参数2上面进行验证。

也可以对输入参数2进行排列组合,然后在输入参数1上面进行验证。

比如array(1,3,3)的排列组合:
1,3,3
3,1,3
3,3,1
按排列顺序把数字分配给每个人,看看符不符合要求。
一但排好,验证只需要一个简单的二层循环就能搞定。
排列也可以优化,每排出一个数字就马上验证,如果验证成功就立即返回。这样平均就能减少一半的时间。

(/@Ta/2021-11-03 23:34//)

15.

两种排列方法的复杂度应该是一样的。方法1排列时操作多,方法2验证时操作多。

(/@Ta/2021-11-03 23:37//)

16. @老虎会游泳,👌学到了。如果参数2数组长度比参数1外层数组长度长时就只能用第一种方法了(sub array?)
(/@Ta/2021-11-03 23:48//)

17.

@老虎会游咏q,还是可以用方法2,只需要一个M选N排列生成器(复杂度转移到这个生成器里)。

此外方法2好像更容易做优化,比如:如果前缀不匹配,那么整个分支都可以抛弃,不必再验证。因为后面无论如何组合,只要前面不符合,都无法通过验证。

这样就可以再少一些验证。

还有边界条件,如果M小于N,直接返回false。

(/@Ta/2021-11-03 23:55//)

18.

M选N排列生成器:

  1. 扔掉M-N个元素。
  2. 执行全排列。
  3. (可选)为了实现优化,要有跳过整个分支的能力。跳过分支是指:所有特定前缀的排列均不再生成。
  4. 回到步骤1,扔不同的元素,直到所有元素组合都被扔过。
(/@Ta/2021-11-03 23:59//)

19.

@老虎会游咏q,方法1也能做前缀优化,而且好像实现起来比方法2更简单。

具体思路就是,从输入参数1的某行取出一个数之后,就把它从输入参数2中拿走。如果某行取到的数在输入参数2里没有,那么整个分支就失败了,后面的行就都不用尝试了。

使用map结构存储输入参数2,然后采用递归保留输入参数2的每种中间状态,就很容易做到这一点。

(/@Ta/2021-11-04 00:11//)

下一页 1/2页,共24楼

回复需要登录

9月21日 04:01 星期天

本站由hu60wap6驱动

备案号: 京ICP备18041936号-1