复试 || 就业day15(2024.01.13)算法篇

前言

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

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

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

数组中第 K 个独一无二的字符串

题目链接：数组中第 K 个独一无二的字符串

C++版AC代码：

class Solution {
public:
    string kthDistinct(vector<string>& arr, int k) {
        unordered_map<string, int> m;
        for (auto str : arr) m[str] ++;
        int cnt = 0;
        for (auto str : arr) 
            if (m[str] == 1) {
                cnt ++;
                if (cnt == k) return str;
            } 
        return "";
    }
};

---

统计字符串中的元音子字符串

题目链接：统计字符串中的元音子字符串

C++版AC代码：

class Solution {
public:
    int countVowelSubstrings(string word) {
        unordered_set<char> vowel = {'a', 'e', 'i', 'o', 'u'};
        int res = 0;
        for (int i = 0; i < word.size(); i ++ ) {
            unordered_set<char> str;
            for (int j = i; j < word.size(); j ++ ) {
                char c = word[j];
                if (c != 'a' && c != 'e' && c != 'i' && c != 'o' && c != 'u') {
                    if (j - i < 5) i = j;
                    break;
                }
                str.insert(c);
                if (vowel == str) res ++;
            }
        }
        return res;
    }
};

---

检查两个字符串是否几乎相等

题目链接：检查两个字符串是否几乎相等

C++版AC代码：

class Solution {
public:
    bool checkAlmostEquivalent(string word1, string word2) {
        unordered_map<char, int> m;
        for (auto c : word1) m[c] ++;
        for (auto c : word2) m[c] --;
        for (auto i : m) 
            if (abs(i.second) > 3) return false;
        return true;
    }
};

---

统计出现过一次的公共字符串

题目链接：统计出现过一次的公共字符串

C++版AC代码：

class Solution {
public:
    int countWords(vector<string>& words1, vector<string>& words2) {
        unordered_map<string, int> m1, m2;
        for (auto word : words1) m1[word] ++;
        for (auto word : words2) m2[word] ++;
        int res = 0;
        for (auto i : m1) 
            if (i.second == 1 && m2[i.first] == 1) 
                res ++;
        return res;
    }
};

---

找出 3 位偶数

题目链接：找出 3 位偶数

C++版AC代码：

$O(n^3)$ 的时间复杂度，很慢

class Solution {
public:
    vector<int> findEvenNumbers(vector<int>& digits) {
        vector<int> per, dec, unit;   // 百位,十位,个位
        unordered_map<int, int> m;
        for (auto x : digits) {
            if (x != 0) per.push_back(x);
            if (!(x % 2)) unit.push_back(x);
            dec.push_back(x);
            m[x] ++;
        }
        vector<int> res;
        for (auto h : per) {
            m[h] --;
            for (auto t : dec) {
                if (m[t] == 0) continue;
                m[t] --;
                for (auto o : unit) {
                    if (m[o] == 0) continue;
                    res.push_back(h * 100 + t * 10 + o);
                }
                m[t] ++;
            }
            m[h] ++;
        }                  
        sort(res.begin(), res.end());
        // 去重
        auto last = unique(res.begin(), res.end());
        res.erase(last, res.end());
        return res;
    }
};

C++版AC代码：

枚举所有的三位数偶数，看是否可以用题给数组表示，从小到大进行枚举还可以省去排序

class Solution {
public:
    vector<int> findEvenNumbers(vector<int>& digits) {
        unordered_map<int, int> m;
        for (auto x : digits) m[x] ++;
        vector<int> res;
        for (int i = 100; i < 1000; i += 2) {
            unordered_map<int, int> may;
            may[i % 10] ++, may[i / 10 % 10] ++, may[i / 100] ++;
            bool flag = true;
            for (auto k : may) 
                if (!m.count(k.first) || k.second > m[k.first]) {
                    flag = false;
                    break;
                }
            if (flag) res.push_back(i);
        }
        return res;
    }
};

---

找到和最大的长度为 K 的子序列

题目链接：找到和最大的长度为 K 的子序列

C++版AC代码：

class Solution {
public:
    static bool cmp (int a, int b) {
        return a > b;
    }
    vector<int> maxSubsequence(vector<int>& nums, int k) {
        vector<int> tmp = nums;
        sort(tmp.begin(), tmp.end(), cmp);
        unordered_map<int, int> m;
        for (int i = 0; i < k; i ++ ) m[tmp[i]] ++;
        vector<int> res;
        int cnt = 0;
        for (auto x : nums) {
            if (m.count(x) && m[x]) {
                res.push_back(x);
                cnt ++, m[x] --;
            }
            if (cnt == k) break;
        }
        return res;
    }
};

---