力扣75——哈希表/哈希集合

这篇具有很好参考价值的文章主要介绍了力扣75——哈希表/哈希集合。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

总结leetcode75中哈希表/哈希集合的算法题解题思路。
上一篇:力扣75——滑动窗口
以下代码大部分为本人所写,少部分为官方示例代码。

1 找出两数组的不同

题目:

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ,请你返回一个长度为 2 的列表 answer ,其中:

answer[0] 是 nums1 中所有 不 存在于 nums2 中的 不同 整数组成的列表。
answer[1] 是 nums2 中所有 不 存在于 nums1 中的 不同 整数组成的列表。
注意:列表中的整数可以按 任意 顺序返回。

题解:先用哈希表分别记录各自的元素,然后各自检测是否有不存在于对方的元素。

class Solution {
public:
    vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> set1, set2;   // nums1 与 nums2 所有元素的哈希集合
        for (int num: nums1) {
            set1.insert(num);
        }
        for (int num: nums2) {
            set2.insert(num);
        }
        vector<vector<int>> res(2);
        for (int num: set1) {
            if (!set2.count(num)) {
                res[0].push_back(num);
            }
        }
        for (int num: set2) {
            if (!set1.count(num)) {
                res[1].push_back(num);
            }
        }
        return res;
    }
};

2 独一无二的出现次数

题目:

给你一个整数数组 arr,请你帮忙统计数组中每个数的出现次数。

如果每个数的出现次数都是独一无二的,就返回 true;否则返回 false

题解:先用unordered_map记录每个字母出现的次数,然后把次数存日哈希表,如果哈希表的长度与map的长度一致,则证明次数都是独一无二的。

 class Solution {
 public:
	 bool uniqueOccurrences(vector<int>& arr) {
		 unordered_map<int,int> umap;
		 for (auto a : arr) {
			 if (umap.count(a)) {
				 umap[a] += 1;
			 }
			 else {
				 umap[a] = 1;
			 }
		 }
		 unordered_set<int> uset;
		 for (auto iter = umap.begin(); iter != umap.end(); iter++) {
			 uset.insert(iter->second);
		}
		 return umap.size() == uset.size();
	 }
 };

3 确定两个字符串是否接近

题目:

如果可以使用以下操作从一个字符串得到另一个字符串,则认为两个字符串 接近 :

操作 1:交换任意两个 现有 字符。
例如,abcde -> aecdb
操作 2:将一个 现有 字符的每次出现转换为另一个 现有 字符,并对另一个字符执行相同的操作。
例如,aacabb -> bbcbaa(所有 a 转化为 b ,而所有的 b 转换为 a )
你可以根据需要对任意一个字符串多次使用这两种操作。

给你两个字符串,word1 和 word2 。如果 word1 和 word2 接近 ,就返回 true ;否则,返回 false

题解:根据题目意思,字符串接近有2个条件:第一个:2个字符串的字符种类一致;第二个:2个字符串中各类字符出现次数的集合相等。

class Solution {
public:
    bool closeStrings(string word1, string word2) {
        // 验证word1和word2长度相同
        if(word1.length() != word2.length()) return false;
        // 验证word1和word2包含的字母相同
        vector<int> v1(26, 0), v2(26, 0);
        for(char c : word1) v1[c - 'a']++;
        for(char c : word2) v2[c - 'a']++;
        for(int i = 0; i < 26; ++i){
            if((v1[i] == 0 && v2[i] != 0)
                ||(v1[i] != 0 && v2[i] == 0)) return false;
        }
        // 验证word1和word2“结构”相同
        sort(v1. begin(), v1.end());
        sort(v2. begin(), v2.end());
        if(v1 != v2) return false;
        return true;
    }
};

4 相等行列对

题目:

给你一个下标从 0 开始、大小为 n x n 的整数矩阵 grid ,返回满足 Ri 行和 Cj 列相等的行列对 (Ri, Cj) 的数目。

如果行和列以相同的顺序包含相同的元素(即相等的数组),则认为二者是相等的。

题解:将行存入哈希表,然后遍历每一列。

class Solution {
public:
    int equalPairs(vector<vector<int>>& grid) {
        int n = grid.size();
        map<vector<int>, int> cnt;
        for (auto row : grid) {
            cnt[row]++;
        }

        int res = 0;
        for (int j = 0; j < n; j++) {
            vector<int> arr;
            for (int i = 0; i < n; i++) {
                arr.emplace_back(grid[i][j]);
            }
            if (cnt.find(arr) != cnt.end()) {
                res += cnt[arr];
            }
        }
        return res;
    }
};

1-4 解题总结

这几道题都比较简单。
特点:当需要对一串数据做统计时,可以考虑用哈希表。文章来源地址https://www.toymoban.com/news/detail-604171.html

到了这里,关于力扣75——哈希表/哈希集合的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【leetcode 力扣刷题】数学题之除法:哈希表解决商的循环节➕快速乘求解商

    题目链接:166. 分数到小数 题目内容: 题目是要我们把一个分数变成一个小数,并以字符串的形式返回。按道理,直接将分子numerator除以分母denominator就得到了小数,转换成string返回就好。题目要求里指出了特殊情况—— 小数部分如果有循环,就把循环节括在括号里 。 那么

    2024年02月10日
    浏览(39)
  • LeetCode 2441. Largest Positive Integer That Exists With Its Negative【哈希集合】简单

    本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,

    2024年02月05日
    浏览(40)
  • 力扣75——二分查找

    总结leetcode75中的 二分查找 算法题解题思路。 上一篇:力扣75——堆/优先队列 题目: 题解: 二分查找。用 left 、 right 分别记录左端点和右端点。然后计算出它们的平均值 mid ,接着用 guess(mid) 判断是大了还是小了。 题目: 题解: 先 快速排序 ,然后用 upper_bound() 找到第一

    2024年02月12日
    浏览(40)
  • 力扣75——堆/优先队列

    总结leetcode75中的 堆/优先队列 算法题解题思路。 上一篇:力扣75——图广度优先搜索 题目: 题解: 最大堆 。 建立最大堆。然后依次取出k-1个,每取一个就重新修复最大堆。最后堆顶元素即为所求值。 题目: 题解: 用set类型的s记录被删除的变量。用minV记录最小值。 如果

    2024年02月12日
    浏览(35)
  • 力扣75——链表

    总结leetcode75中 链表 的算法题解题思路。 上一篇:力扣75——队列 以下代码大部分为本人所写,少部分为官方示例代码。 题目: 题解:前后指针。前指针指向最后一个个节点时,后指针指向了中间节点。 题目: 题解:双指针,分别指向奇数节点和偶数节点,然后再串起来

    2024年02月15日
    浏览(32)
  • 力扣75——前缀树

    总结leetcode75中的 前缀树 算法题解题思路。 上一篇:力扣75——位运算 题目: 题解: 前缀树。对于每个类对象trie,它有一个长度为26的vectorTrie*,记录着当前节点之后是否还存在哪些字母,如果不存在则是空指针。此外还有一个bool类型的isEnd,它记录当前节点是否为某个字符

    2024年02月12日
    浏览(35)
  • 力扣75——图广度优先搜索

    总结leetcode75中的 图广度优先搜索 算法题解题思路。 上一篇:力扣75——图深度优先搜索 题目: 题解: 广度优先搜索 。 将与入口相邻的空格子压入队列。 然后用 while循环 遍历队列中的格子,每个访问过的格子都要做标记(记录它到入口的距离,并将状态设置为已访问)。

    2024年02月12日
    浏览(31)
  • 力扣(LeetCode)算法_C++—— 快乐数

    编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」 定义为: 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。 如果这个过程 结果为 1,那么这个数就是快乐数。 如果 n 是

    2024年02月09日
    浏览(39)
  • 算法学习——LeetCode力扣回溯篇2

    40. 组合总和 II - 力扣(LeetCode) 描述 给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意:解集不能包含重复的组合。 示例 示例 1: 输入: candidates = [10,1,2,7

    2024年02月20日
    浏览(36)
  • 【LeetCode 算法】Walking Robot Simulation 模拟行走机器人 - 哈希

    机器人在一个无限大小的 XY 网格平面上行走,从点 (0, 0) 处开始出发,面向北方。该机器人可以接收以下三种类型的命令 commands : -2 :向左转 90 度 -1 :向右转 90 度 1 = x = 9 1 = x = 9 1 = x = 9 :向前移动 x 个单位长度 在网格上有一些格子被视为障碍物 obstacles 。第 i 个障碍物位

    2024年02月15日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包