复试 || 就业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;          // 更新 p2s
            s2p[word] = c;          // 更新 s2p
            wordStart = wordEnd + 1, wordEnd = wordStart;    // 更新单词的标记
        }
        if (wordStart == m + 1) return true;       // 正常遍历结束符合题意即为 wordStart == m + 1
        else return false;
    }
};

---