复试 || 就业day16(2024.01.16)算法篇

前言

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

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

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

环和杆

题目链接：环和杆

C++版AC代码：

class Solution {
public:
    int countPoints(string rings) {
        unordered_set<char> s[10];
        for (int i = 0; i < rings.size(); i += 2) {
            int ad = rings[i + 1] - '0';
            s[ad].insert(rings[i]);
        }
        int res = 0;
        for (int i = 0; i < 10; i ++ ) 
            if (s[i].size() == 3) 
                res ++;
        return res;
    }
};

---

检查是否每一行每一列都包含全部整数

题目链接：检查是否每一行每一列都包含全部整数

C++版AC代码：

class Solution {
public:
    bool checkValid(vector<vector<int>>& matrix) {
        int n = matrix.size();
        unordered_set<int> row[n], col[n];
        for (int i = 0; i < n; i ++ ) 
            for (int j = 0; j < n; j ++ ) {
                if (row[i].find(matrix[i][j]) != row[i].end()) 
                    return false;
                if (col[j].find(matrix[i][j]) != col[j].end())
                    return false;
                row[i].insert(matrix[i][j]), col[j].insert(matrix[i][j]);
            }
        return true;
    }
};

---

将找到的值乘以 2

题目链接：将找到的值乘以 2

C++版AC代码：

class Solution {
public:
    int findFinalValue(vector<int>& nums, int original) {
        unordered_set<int> s;
        for (auto x : nums) s.insert(x);
        while (1) {
            if (s.count(original)) original *= 2;
            else break;
        }
        return original;
    }
};

---

数组中紧跟 key 之后出现最频繁的数字

题目链接：数组中紧跟 key 之后出现最频繁的数字

C++版AC代码：

class Solution {
public:
    int mostFrequent(vector<int>& nums, int key) {
        unordered_map<int, int> m;
        for (int i = 0; i < nums.size() - 1; i ++ ) 
            if (nums[i] == key) 
                m[nums[i + 1]] ++;
        int times = 0, res = 0;
        for (auto it : m)
            if (it.second > times) {
                res = it.first;
                times = it.second;
            }
        return res;
    } 
};

---

将数组划分成相等数对

题目链接：将数组划分成相等数对

C++版AC代码：

class Solution {
public:
    bool divideArray(vector<int>& nums) {
        unordered_map<int, int> m;
        for (auto x : nums) m[x] ++;
        for (auto it : m) 
            if (it.second % 2) 
                return false;
        return true;
    }
};

---

找出两数组的不同

题目链接：找出两数组的不同

C++版AC代码：

class Solution {
public:
    vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> res(2);
        unordered_set<int> s1(nums1.begin(), nums1.end());
        unordered_set<int> s2(nums2.begin(), nums2.end());
        for (auto it : s1) 
            if (!s2.count(it))
                res[0].push_back(it);
        for (auto it : s2)
            if (!s1.count(it))
                res[1].push_back(it);
        return res;
    }
};

---

多个数组求交集

题目链接：多个数组求交集

C++版AC代码：

class Solution {
public:
    vector<int> intersection(vector<vector<int>>& nums) {
        vector<int> res;
        unordered_map<int, int> m;
        int n = nums.size();
        for (int i = 0; i < n; ++ i ) 
            for (auto x : nums[i])
                m[x] ++;
        for (auto it : m) 
            if (it.second == n)
                res.push_back(it.first);
        sort(res.begin(), res.end());
        return res;
    }
};

---

移除字母异位词后的结果数组*

题目链接：移除字母异位词后的结果数组

C++版AC代码：

首先把 word[0] 放入 res 中，依次依照题意比较后续 word[i]，即 word[i] 与 res[res.size() - 1] 进行比较即可

class Solution {
public:
    bool isAnagrams(string word1, string word2) {
        unordered_map<char, int> m;
        for (auto c : word1) m[c] ++;
        for (auto c : word2) m[c] --;
        for (auto it : m) 
            if (it.second) 
                return false;
        return true;
    }
    vector<string> removeAnagrams(vector<string>& words) {
        vector<string> res = {words[0]};
        for (int i = 1; i < words.size(); ++ i ) 
            if (isAnagrams(words[i], res[res.size() - 1])) continue;
            else res.push_back(words[i]);
        return res;
    }
};

---