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

发布时间: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;
    }
};

文章来源:https://blog.csdn.net/qq_52156445/article/details/135289123
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。