复试 || 就业day07(2024.01.02)算法篇

前言

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

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

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

数组的度

题目链接：数组的度

C++版AC代码：

class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        unordered_map<int, int> m;
        unordered_map<int, int> st, ed;   // 记录该元素第一次出现的坐标以及最后一次出现的坐标
        for (int i = 0; i < nums.size(); i ++ ) {
            m[nums[i]] ++;
            if (!st.count(nums[i])) st[nums[i]] = i;  // 记录第一次出现的坐标
            ed[nums[i]] = i;                          // 记录最后一次出现的坐标
        }
        int md = 0;
        for (auto i = m.begin(); i != m.end(); i ++ ) {
            int cnt = i -> second;
            md = max(md, cnt);        // 找出数组的度
        }
        int res = nums.size();
        for (auto i = m.begin(); i != m.end(); i ++ ) {
            int num = i -> first, cnt = i -> second;
            if (cnt == md)
                res = min(res, ed[num] - st[num] + 1);
        }
        return res;
    }
};

---

最短补全词

题目链接：最短补全词

C++版AC代码：

class Solution {
public:
    string shortestCompletingWord(string licensePlate, vector<string>& words) {
        unordered_map<char, int> m;            // 统计 licensePlate 中的字符
        for (int i = 0; i < licensePlate.size(); i ++ ) {
            char c = licensePlate[i];
            if (c >= 'A' && c <= 'Z') m[c + 32] ++;   // 根据ASCII大写变小写
            if (c >= 'a' && c <= 'z') m[c] ++;
        }
        string word;                         
        vector<string> v;                             // 存储补全词
        for (int i = 0; i < words.size(); i ++ ) {
            word = words[i];
            unordered_map<char, int> tmp;             // 统计 word 中的字符
            for (int j = 0; j < word.size(); j ++ ) {
                char c = word[j];
                if (c >= 'A' && c <= 'Z') tmp[c + 32] ++; // 根据ASCII大写变小写
                if (c >= 'a' && c <= 'z') tmp[c] ++;
            }
            bool flag = true;
            for (auto k = m.begin(); k != m.end(); k ++ ) {
                char c = k -> first;
                int cnt = k -> second;
                if (tmp[c] < cnt) {             // 注意这里是 < 
                    flag = false;
                    break;
                }
            }
            if (flag) v.push_back(word);         // 符合补全词的定义
        }
        string res = v[0];
        int minlen = v[0].size();
        for (int i = 1; i < v.size(); i ++ ) {   // 找最短补全词 
            if (v[i].size() < minlen) {
                res = v[i];
                minlen = v[i].size();
            }
        }
        return res;
    }
};

---

宝石与石头

题目链接：宝石与石头

C++版AC代码：

class Solution {
public:
    int numJewelsInStones(string jewels, string stones) {
        unordered_map<char, int> m;
        for (int i = 0; i < jewels.size(); i ++ ) m[jewels[i]] = 1;
        int res = 0;
        for (int i = 0; i <stones.size(); i ++ ) 
            if (m.count(stones[i]))
                res ++;
        return res;
    }
};

---

唯一摩尔斯密码词

题目链接：唯一摩尔斯密码词

C++版AC代码：

class Solution {
public:
    int uniqueMorseRepresentations(vector<string>& words) {
        unordered_map<string, int> m;
        unordered_map<char, string> mos;
        string v[] = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
        for (int i = 0; i < 26; i ++ ) mos['a' + i] = v[i];      // 构建mos表
        for (int i = 0; i < words.size(); i ++ ) {
            string word = words[i];
            string mosi;
            for (int j = 0; j < word.size(); j ++ ) mosi += mos[word[j]];
            m[mosi] ++;
        }
        return m.size();
    }
};

---

最常见的单词

题目链接：最常见的单词

注意细节处理就好了，关于字符串的操作还需再熟悉

C++版AC代码：

class Solution {
public:
    unordered_map<string, int> m;
    string getres() {
        string res;
        int maxtimes = 0;
        for (auto i = m.begin(); i != m.end(); i ++ ) {
            int times = i -> second;
            string c = i -> first;
            if (times > maxtimes) {
                maxtimes = times;
                res = c;
            }
        }
        return res;
    }
    string mostCommonWord(string paragraph, vector<string>& banned) {
        for (int i = 0; i < paragraph.size(); i ++ ) {
            char c = paragraph[i];
            if ((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z')) {
                int j = i;
                while (j < paragraph.size()) {
                    c = paragraph[j];
                    if (c >= 'a' && c <= 'z') j ++;
                    else if (c >= 'A' && c <= 'Z') {
                        paragraph[j] += 32;      
                        j ++;
                    }
                    else break;
                }
                string word = paragraph.substr(i, j - i);  // 提取单词
                m[word] ++;
                i = j;
            }
            else continue;
        }
        if (banned.empty()) return getres();
        for (int i = 0; i <banned.size(); i ++ ) m[banned[i]] = 0;  
        return getres();
    }
};

---