从零开始刷LeetCode-0

最新推荐文章于 2025-03-14 06:04:48 发布

bea_tree

最新推荐文章于 2025-03-14 06:04:48 发布

阅读量591

点赞数

分类专栏：代码文章标签： LeetCode 零基础

本文链接：https://blog.csdn.net/bea_tree/article/details/96923278

版权

代码专栏收录该内容

2 篇文章

订阅专栏

从leetcode中简单的题开始，上车吧

给定数组vector<vector>& dominoes；
若其中元素为二维数组，若元素i=元素j
或元素i=元素j[::-1]则称其可等价；
求在i<j的前提下，给定dominoes一共有多少个等价的pair？
?：
输入：dominoes =[[1,2],[2,1],[3,4],[5,6]]
输出：1 来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-equivalent-domino-pairs

解题思路1：

使用两个循环嵌套伪代码如下：

for i in range (len_d):
    for j in range (i+1,len_d,1):
          balabala....

这样的思路是简单明了，但是缺点就是复杂度太高，运行慢，能不用嵌套循环就不用

解题思路2：

先使用一次循环，统计每个vector元素出现的个数n；

然后某个vector元素可以组成的pair数量就是n*(n-1)/2；

累加即可；

代码：

class Solution {
public:
int numEquivDominoPairs(vector<vector<int>>& dominoes) {
int len_dominoes=dominoes.size();
int num_e=0;
map<pair<int,int>, int> pair_map;
for (auto &vec_i: dominoes){
    if (vec_i[0]>vec_i[1]){
        swap(vec_i[0],vec_i[1]);
            }
            pair_map[make_pair(vec_i[0],vec_i[1])]++;  
        }
for (auto &pv:pair_map){
    if (pv.second>1){
        num_e+=pv.second*(pv.second-1)/2;
            }
        }
return num_e;
    }
};

c++ 知识点：

swap: 此处swap 交换vector 两个元素的地址；

map 程序中初始值默认为0；

map.second :使用迭代器访问，iter->first指向元素的键，iter->second指向键对应的值。另外，使用下标访问map容器与使用下标访问vector的不同之处：用下标访问map中不存在的元素将导致在map容器中添加一个新的元素；