复试 || 就业day03(2023.12.29)算法篇

前言

💫你好，我是辰chen，本文旨在准备考研复试或就业
💫文章题目大多来自于 leetcode，当然也可能来自洛谷或其他刷题平台
💫欢迎大家的关注，我的博客主要关注于考研408以及AIoT的内容
🌟 仅给出C++版代码

以下的几个专栏是本人比较满意的专栏(大部分专栏仍在持续更新)，欢迎大家的关注：

💥ACM-ICPC算法汇总【基础篇】
💥ACM-ICPC算法汇总【提高篇】
💥AIoT(人工智能+物联网)
💥考研
💥CSP认证考试历年题解

同构字符串

题目链接：同构字符串

C++版AC代码：

哈希表，注意.count() 是用来查找表里是否有该元素，哈希只需要保存离遍历元素最近的一次出现位置即可。

class Solution {
public:bool isIsomorphic(string s, string t) {unordered_map<char, 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(vector<int>& nums) {unordered_map<int, 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_map<char, 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(vector<int>& 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_map<char, string> p2s;unordered_map<string, 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;}
};

---