前言
经过前期的数据结构和算法学习,开始以OD机考题作为练习题,继续加强下熟练程度。
描述
三元组 是一个由三个整数组成的数组。给你一个二维整数数组
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]
。如果通过以上操作我们可以使得目标 三元组
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 。提示:
1 <= triplets.length <= 105
triplets[i].length == target.length == 3
1 <= ai, bi, ci, x, y, z <= 1000
实现原理与步骤
1.解读题干,原数组对应下标位不断更新最大值,使得与target下标位置一致。
2.过滤triplets[i][j]大于target[i][j]中的值
3.更新temp[j]为Math.max(temp[j],triplets[i][j]);
4.比较temp[j]是否与target[j]一致
实现代码
class Solution {public boolean mergeTriplets(int[][] triplets, int[] target) {int len=triplets.length;int[] temp=new int[3];for(int i=0;i<len;i++){if(triplets[i][0]>target[0]||triplets[i][1]>target[1]||triplets[i][2]>target[2]){continue;}temp[0]=Math.max(temp[0],triplets[i][0]);temp[1]=Math.max(temp[1],triplets[i][1]);temp[2]=Math.max(temp[2],triplets[i][2]);if(temp[0]==target[0]&&temp[1]==target[1]&&temp[2]==target[2]){return true;}}return false;}
}