1128. 等价多米诺骨牌对的数量给你一个由一些多米诺骨牌组成的列表 如果其中某一张多米诺骨牌可以通过旋转 形式上, 在 示例: 输入:dominoes = [[1,2],[2,1],[3,4],[5,6]]输出:1 提示:
class Solution { public int numEquivDominoPairs(int[][] dominoes) { int len = dominoes.length; boolean[] visited = new boolean[len]; int sum = 0; for(int i = 0;i < len;i ) { if(visited[i]) { continue; } int num = 1; visited[i] = true; for(int j = i 1;j < len;j ) { if(visited[j]) { continue; } if(dominoes[i][0] == dominoes[j][0] && dominoes[i][1] == dominoes[j][1] || dominoes[i][0] == dominoes[j][1] && dominoes[i][1] == dominoes[j][0]) { num ; visited[j] = true; } } sum = num*(num-1)/2; } return sum; } } 学习别人的代码: 作者:LeetCode-Solution 思路: 本题中我们需要统计所有等价的多米诺骨牌,其中多米诺骨牌使用二元对代表,「等价」的定义是,在允许翻转两个二元对的的情况下,使它们的元素一一对应相等。于是我们不妨直接让每一个二元对都变为指定的格式,即第一维必须不大于第二维。这样两个二元对「等价」当且仅当两个二元对完全相同。 注意到二元对中的元素均不大于 99,因此我们可以将每一个二元对拼接成一个两位的正整数,即 (x, y) \to 10x y(x,y)→10x y。这样就无需使用哈希表统计元素数量,而直接使用长度为 100100 的数组即可。 class Solution { public int numEquivDominoPairs(int[][] dominoes) { int[] num = new int[100]; int ret = 0; for (int[] domino : dominoes) { int val = domino[0] < domino[1] ? domino[0] * 10 domino[1] : domino[1] * 10 domino[0]; ret = num[val]; num[val] ; } return ret; } } 作者:LeetCode-Solution 链接:https:///problems/number-of-equivalent-domino-pairs/solution/deng-jie-duo-mi-nuo-gu-pai-dui-de-shu-li-yjlz/ 来源:力扣(LeetCode) 著作权归作者所有。非商业转载请注明出处。来源:https://www./content-4-834851.html |
|