1899. 合并若干三元组以形成目标三元组-c语言-贪心算法+标记数组

1899. 合并若干三元组以形成目标三元组

三元组 是一个由三个整数组成的数组。给你一个二维整数数组 triplets ，其中 triplets[i] = [ai, bi, ci] 表示第 i 个 三元组 。同时，给你一个整数数组 target = [x, y, z] ，表示你想要得到的 三元组 。

为了得到 target ，你需要对 triplets 执行下面的操作 任意次（可能 零 次）：

选出两个下标（下标 从 0 开始 计数）i 和 j（i != j），并 更新 triplets[j] 为 [max(ai, aj), max(bi, bj), max(ci, cj)] 。
    例如，triplets[i] = [2, 5, 3] 且 triplets[j] = [1, 7, 5]，triplets[j] 将会更新为 [max(2, 1), max(5, 7), max(3, 5)] = [2, 7, 5] 。
1
2

如果通过以上操作我们可以使得目标 三元组 target 成为 triplets 的一个 元素 ，则返回 true ；否则，返回 false 。

示例 1：

输入：triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]
输出：true
解释：执行下述操作：

• 选择第一个和最后一个三元组 [[2,5,3],[1,8,4],[1,7,5]] 。更新最后一个三元组为 [max(2,1), max(5,7), max(3,5)] = [2,7,5] 。triplets = [[2,5,3],[1,8,4],[2,7,5]]
  目标三元组 [2,7,5] 现在是 triplets 的一个元素。

示例 2：

输入：triplets = [[1,3,4],[2,5,8]], target = [2,5,8]
输出：true
解释：目标三元组 [2,5,8] 已经是 triplets 的一个元素。

示例 3：

输入：triplets = [[2,5,3],[2,3,4],[1,2,5],[5,2,3]], target = [5,5,5]
输出：true
解释：执行下述操作：

• 选择第一个和第三个三元组 [[2,5,3],[2,3,4],[1,2,5],[5,2,3]] 。更新第三个三元组为 [max(2,1), max(5,2), max(3,5)] = [2,5,5] 。triplets = [[2,5,3],[2,3,4],[2,5,5],[5,2,3]] 。
• 选择第三个和第四个三元组 [[2,5,3],[2,3,4],[2,5,5],[5,2,3]] 。更新第四个三元组为 [max(2,5), max(5,2), max(5,3)] = [5,5,5] 。triplets = [[2,5,3],[2,3,4],[2,5,5],[5,5,5]] 。
  目标三元组 [5,5,5] 现在是 triplets 的一个元素。

示例 4：

输入：triplets = [[3,4,5],[4,5,6]], target = [3,2,5]
输出：false
解释：无法得到 [3,2,5] ，因为 triplets 不含 2 。

这题还是很有趣的，看起来无从下手，但是我们要了解这个问题的一些运行机制，然后，根据这个下手解决就可以了，这个问题的机制就是，如果两个三元组运算，那么一定会取最大的，所以，我们要选择，不能比我们目标三元组大的三元组进行合并：
解题代码如下：

bool mergeTriplets(int** triplets, int tripletsSize, int* tripletsColSize, int* target, int targetSize){
    int x=target[0],y=target[1],z=target[2];
    int r[3]={0};
    int rcount=0;
    int i;
    for(i=0;i<tripletsSize;i++){
        int xt=triplets[i][0];
        int yt=triplets[i][1];
        int zt=triplets[i][2];
        if(xt==x&&yt<=y&&zt<=z&&r[0]==0){
            r[0]=1;
            rcount++;

        }
        if(xt<=x&&yt==y&&zt<=z&&r[1]==0){
            r[1]=1;
            rcount++;

        }
         if(xt<=x&&yt<=y&&zt==z&&r[2]==0){
            r[2]=1;
            rcount++;

        }
        if(rcount==3){
            return true;
        }
    }
    return false;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31