复试 || 就业day06(2024.01.01)算法篇

前言

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

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

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

分糖果

题目链接：分糖果

C++版AC代码：

class Solution {
public:
    int min(int a, int b){
        if (a > b) return b;
        else return a;
    }
    int distributeCandies(vector<int>& candyType) {
        unordered_map<int, int> m;
        for (int i = 0; i < candyType.size(); i ++ ) m[candyType[i]] ++;
        int num = 0;
        for (auto i = m.begin(); i != m.end(); i ++ ) num ++;
        return min(candyType.size() / 2, num);
    }
};

---

最长和谐子序列

题目链接：最长和谐子序列

C++版AC代码：

class Solution {
public:
    int findLHS(vector<int>& nums) {
        unordered_map<int, int> m;
        for (int i = 0; i < nums.size(); i ++ ) m[nums[i]] ++;
        int res = 0;
        for (auto i = m.begin(); i != m.end(); i ++ ) {
            int k = i -> first;
            if (m.count(k + 1)) res = max(res, m[k] + m[k + 1]);
        }
        return res;
    }
};

---

两个列表的最小索引总和

题目链接：两个列表的最小索引总和

C++版AC代码：

class Solution {
public:
    vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
        vector<string> res;
        unordered_map<string, int> m;
        for (int i = 0; i < list1.size(); i ++ ) m[list1[i]] = i;
        int maxindex = 2000;        // 最大索引和
        for (int i = 0; i < list2.size(); i ++ ) {
            string k = list2[i];
            if (m.count(k) && i + m[k] <= maxindex) {
                maxindex = i + m[k];
            }            
        }
        for (int i = 0; i < list2.size(); i ++ ){
            string k = list2[i];
            if (m.count(k) && i + m[k] == maxindex)
                res.push_back(k);
        }
        return res;
    }
};

---

错误的集合

题目链接：错误的集合

C++版AC代码：

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        unordered_map<int, int> m;
        int n = nums.size();
        for (int i = 0; i < n; i ++ ) m[nums[i]] ++;
        int lost, re;
        for (int i = 1; i <= n; i ++ ) {
            if (!m.count(i)) lost = i;
            if (m[i] == 2) re = i;
        }
        return {re, lost};
    }
};

---

两数之和 IV - 输入二叉搜索树

题目链接：两数之和 IV - 输入二叉搜索树

C++版AC代码：

emm，没有用到 BST，使用哈希的话 BST 这个条件貌似没有什么用处。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    unordered_map<int, int> m;
    void LNR(TreeNode* root){
        if (root == NULL) return;
        if (root -> left) LNR(root -> left);
        m[root -> val] ++;
        if (root -> right) LNR(root -> right);
    }
    bool findTarget(TreeNode* root, int k) {
        LNR(root);
        bool flag = false;
        for (auto i = m.begin(); i != m.end(); i ++ ) {
            int a = i -> first;
            if ((2 * a == k) && m[a] > 1) return true;
            if ((2 * a == k) && m[a] <= 1) continue;
            if (m.count(k - a)){
                flag = true;
                break;
            }
        }
        return flag;
    }
};

---