1.
@老虎会游咏q,输入定义的不清楚,无法编写交互代码。
1,2是什么?
1,3是什么?
3是什么?
为什么有一个空行
1,3,3是什么?
2.
还有,需要指定编程语言和允许使用的库函数。否则某些题目在某些编程语言+库的组合下会变得十分简单,算法不需要自己编写。
比如,PHP似乎可以直接使用in_array
给出答案。如果编程语言自带map结构,算法也会变简单。
3.
@老虎会游咏q,你的示例输出是错的吧,1,3,3连2都没有,不可能是true啊。
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) {...}
6.
@老虎会游泳,我感觉是动态规划的题唉,还要回溯的。 给的示例好像没错,甲想要1,2;乙想要1,3;丙想要3。我有1,3,3,给甲1,给乙3,给丙3;返回true
红米K30 Pro(变焦版)
8.
@Curtion,@老虎会游咏q,哦确实是,我没看到“只能领到一张想要的卡片”。
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'的情况。
10.
排序后的数组可以直接比较(使用PHP5.4数组语法):
$a = [3, 1, 3];
$b = [1, 3, 3];
sort($a);
sort($b);
var_dump($a == $b);
var_dump($a === $b);

11.
@老虎会游泳,👍是一种不错的算法。如果是动态规划应该怎么处理,复杂度上有优势吗
12.
@老虎会游泳,有推荐的关于动态规划的资料(离散动态规划?)吗。我想学一手🙃
14.
@老虎会游咏q,上面的方法是对输入参数1进行排列组合,然后在输入参数2上面进行验证。
也可以对输入参数2进行排列组合,然后在输入参数1上面进行验证。
比如array(1,3,3)的排列组合:
1,3,3
3,1,3
3,3,1
按排列顺序把数字分配给每个人,看看符不符合要求。
一但排好,验证只需要一个简单的二层循环就能搞定。
排列也可以优化,每排出一个数字就马上验证,如果验证成功就立即返回。这样平均就能减少一半的时间。
15.
两种排列方法的复杂度应该是一样的。方法1排列时操作多,方法2验证时操作多。
16.
@老虎会游泳,👌学到了。如果参数2数组长度比参数1外层数组长度长时就只能用第一种方法了(sub array?)
17.
@老虎会游咏q,还是可以用方法2,只需要一个M选N排列生成器(复杂度转移到这个生成器里)。
此外方法2好像更容易做优化,比如:如果前缀不匹配,那么整个分支都可以抛弃,不必再验证。因为后面无论如何组合,只要前面不符合,都无法通过验证。
这样就可以再少一些验证。
还有边界条件,如果M小于N,直接返回false。
19.
@老虎会游咏q,方法1也能做前缀优化,而且好像实现起来比方法2更简单。
具体思路就是,从输入参数1的某行取出一个数之后,就把它从输入参数2中拿走。如果某行取到的数在输入参数2里没有,那么整个分支就失败了,后面的行就都不用尝试了。
使用map结构存储输入参数2,然后采用递归保留输入参数2的每种中间状态,就很容易做到这一点。