南京服装网站建设,网站规划设计的一般流程,提升学历的重要性与意义,昆明网站开发文章目录 前言同构字符串存在重复元素有效的字母异位词丢失的数字单词规律 前言 #x1f4ab;你好#xff0c;我是辰chen#xff0c;本文旨在准备考研复试或就业 #x1f4ab;文章题目大多来自于 leetcode#xff0c;当然也可能来自洛谷或其他刷题平台 #x1f4ab;欢迎大… 文章目录 前言同构字符串存在重复元素有效的字母异位词丢失的数字单词规律 前言 你好我是辰chen本文旨在准备考研复试或就业 文章题目大多来自于 leetcode当然也可能来自洛谷或其他刷题平台 欢迎大家的关注我的博客主要关注于考研408以及AIoT的内容 仅给出C版代码 以下的几个专栏是本人比较满意的专栏(大部分专栏仍在持续更新)欢迎大家的关注 ACM-ICPC算法汇总【基础篇】 ACM-ICPC算法汇总【提高篇】 AIoT(人工智能物联网) 考研 CSP认证考试历年题解 同构字符串 题目链接同构字符串
C版AC代码
哈希表注意.count() 是用来查找表里是否有该元素哈希只需要保存离遍历元素最近的一次出现位置即可。
class Solution {
public:bool isIsomorphic(string s, string t) {unordered_mapchar, int m1, m2;for (int i 0; i s.size(); i ){char a s[i], b t[i];if ((m1.count(a) !m2.count(b)) || (!m1.count(a) m2.count(b))) return false;if (m1[a] ! m2[b]) return false;m1[a] i, m2[b] i;}return true;}
};存在重复元素 题目链接存在重复元素
C版AC代码
最基础的哈希表
class Solution {
public:bool containsDuplicate(vectorint nums) {unordered_mapint, int m;for (int i 0; i nums.size(); i ){if (m.find(nums[i]) ! m.end()) return true;m[nums[i]] 1;}return false;}
};有效的字母异位词 题目链接有效的字母异位词
C版AC代码
class Solution {
public:bool isAnagram(string s, string t) {if (s.size() ! t.size()) return false;unordered_mapchar, int m1, m2;for (int i 0; i s.size(); i ){char a s[i], b t[i];m1[a] , m2[b] ;}for (int i 0; i s.size(); i ){char a s[i];if (m1[a] ! m2[a]) return false;}return true;}
};丢失的数字 题目链接丢失的数字
C版AC代码
class Solution {
public:int missingNumber(vectorint nums) {int a[10010] {0};for (int i 0; i nums.size(); i ) a[nums[i]] ;int i 0;for (; i 1e4; i ) if (!a[i]) break;return i;}
};单词规律 题目链接单词规律
C版AC代码
双哈希因为两个符号串都需要一一对应所以需要开两个哈希表分别记录 pattern 到 s 的映射以及 s 到 pattern 的映射str.substr(pos, len); 用来返回从 pos 号位开始长度为 len 的子串
class Solution {
public:bool wordPattern(string pattern, string s) {unordered_mapchar, string p2s;unordered_mapstring, char s2p;int n pattern.size(), m s.size();int wordStart 0, wordEnd 0; // 用于标记单词的位置for (int i 0; i n; i ){if (wordStart m) return false; // s串已经遍历完了但是pattern串还没遍历完int j;for (j wordStart; j m s[j] ! ; j ); // 用来找到单词wordEnd j;string word s.substr(wordStart, wordEnd - wordStart); // 把该单词截出来char c pattern[i];if (p2s.count(c) p2s[c] ! word || s2p.count(word) s2p[word] ! c) return false; // p2s中有该字符但对应的不是这个单词或者s2p中有该单词但是对应的不是这个字符p2s[c] word; // 更新 p2ss2p[word] c; // 更新 s2pwordStart wordEnd 1, wordEnd wordStart; // 更新单词的标记}if (wordStart m 1) return true; // 正常遍历结束符合题意即为 wordStart m 1else return false;}
};
