从两个数组中查找不同组合的PHP程序
皮的父亲丹尼经营着哈克维尔动物园。他要搬到Rookieville，想通过船把动物园里的所有动物都带走。他对如何安排它们感到困惑，因为少数物种不能放在同一个小木屋里。
有许多动物被放在一条直线上。每种动物都是按照顺序由1到n的唯一数字来识别的。有m对( ai，bi)，这意味着动物ai和bi是敌人，不应该放在同一个小木屋里。Pi擅长解决问题，他提出了以下挑战:计算不包含任何对子的不同组的数量，因为它们是敌人。群被定义为一个区间(x，y)，使得从x到y范围内的所有动物都形成一个群。根据Pi的挑战确定可以形成的组数。
例如，如果n=3只动物，m=3对敌人，那么a= 1，2，3和b= 3，3，1，动物1是动物3的敌人，动物3是动物1和2的敌人。因为3是1和2的敌人，所以它必须在自己的小屋里。动物1和2可以放在一起或分开。
有四种可能的分组满足这些约束：{1, 2} , {1}, {2}, {3}。
请注意，间隔沿动物的原始线连续编号从1到n，即1，2，3在这种情况下。他们不能被重新排序。函数描述在下面的编辑器中完成函数angryAnimals。函数必须返回根据Pi的挑战可以形成的组数。
angryAnimals具有以下参数：
n:表示唯一动物数量的整数。
a[a，.am-1]：整数数组
b[b，.bm-1]：整数数组
约束条件
1≤n≤10
1≤m≤10
1≤ai，bi≤n
我已经能够得到不同的组合，但我发现很难比较和删除组合的敌人出现在一起。
function __construct($s, $k) {
if(is_array($s)) {
$this->s = array_values($s);
$this->n = count($this->s);
} else {
$this->s = (string) $s;
$this->n = strlen($this->s);
}
$this->k = $k;
$this->rewind();
}
function key() {
return $this->pos;
}
function current() {
$r = array();
for($i = 0; $i < $this->k; $i++)
$r[] = $this->s[$this->c[$i]];
return is_array($this->s) ? $r : implode('', $r);
}
function next() {
if($this->_next())
$this->pos++;
else
$this->pos = -1;
}
function rewind() {
$this->c = range(0, $this->k);
$this->pos = 0;
}
function valid() {
return $this->pos >= 0;
}
//
protected function _next() {
$i = $this->k - 1;
while ($i >= 0 && $this->c[$i] == $this->n - $this->k + $i)
$i--;
if($i < 0)
return false;
$this->c[$i]++;
while($i++ < $this->k - 1)
$this->c[$i] = $this->c[$i - 1] + 1;
return true;
}用于自定义测试的示例输入
4
2
1
2
2
3
4我的输出
1
2
3
4
12
13
14
23
24
34
123
124
134
234
123415.
预期产出
1
2
3
4
12
23
347.
解释(1)，(1,2)，(2,3)，(3)，(3,4)，(4)是根据Pi的挑战形成的7组。
https://drive.google.com/file/d/18kHmOiJ8HQ8uA7BqQZ3GQ6eVZ4afn2Fm/view?usp=sharing
回答 2
Stack Overflow用户
发布于 2019-09-22 05:59:54
我不知道这是否有帮助，但我在这里用回溯编程做了一个C#
驱动功能：
public static long angryAnimals(int n, List<int> a, List<int> b)
{
return count(1, n, new bool[n + 2], a.ToArray(), b.ToArray(), 0, 1, 0);
}递归函数：
public static int count(int start, int n, bool[] used, int[] a, int[] b, int numgroup, int cur, int c)
{
if (start <= n || cur != n)
{
used[start] = true;
numgroup++;
if (numgroup == 1)
{
c++;
return count(start + 1, n, used, a, b, numgroup, start, c);
}
for (var j = 0; j < a.Length; j++)
{
if (used[a[j]] && used[b[j]])
{
return count(cur + 1, n, new bool[n + 1], a, b, 0, cur, c);
}
}
c++;
if (start == n)
{
return count(cur + 1, n, new bool[n + 1], a, b, 0, cur, c);
}
return count(start + 1, n, used, a, b, numgroup, cur, c);
}
return c;
}Stack Overflow用户
发布于 2019-10-16 10:55:45
这是我在C#上的答案
public static long angryAnimals(int n, List<int> a, List<int> b)
{
int possibilities = 0;
var ban = new Dictionary<int, int>();
var min = 0;
for (int i = 0; i < a.Count; i++)
{
if (a[i] == b[i])
continue;
min = Math.Min(a[i], b[i]);
var other = Math.Max(a[i], b[i]);
if(!ban.TryGetValue(min, out var current))
ban.Add(min, other);
if (current > other)
ban[min] = other;
}
var lastEnemy = n + 1;
for (int i = n; i >= 1; i--)
{
var add = lastEnemy;
if (ban.TryGetValue(i, out var enemy))
{
if (lastEnemy > enemy)
{
lastEnemy = enemy;
add = enemy;
}
}
possibilities += (add - i);
}
return possibilities;
}https://stackoverflow.com/questions/57920251
复制相似问题
腾讯云开发者
