复试 || 就业day12(2024.01.08)算法篇

2024-01-08 18:33:46

前言

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

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

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

旅行终点站


题目链接:旅行终点站

C++版AC代码:

class Solution {
public:
    string destCity(vector<vector<string>>& paths) {
        // 理解成找出度为0的结点(由题结果必然存在)
        unordered_map<string, int> m;
        for (int i = 0; i < paths.size(); i ++ ) {
            string add = paths[i][0];    // 统计有出度的点
            m[add] = 1;
        }
        string res;
        for (int i = 0; i < paths.size(); i ++ ) {
            string ed = paths[i][1];     // 找所有出度可能为0的点
            if (!m.count(ed)) {
                res = ed;
                break;
            }
        }
        return res;
    }
};

通过翻转子数组使两个数组相等


题目链接:通过翻转子数组使两个数组相等

C++版AC代码:

class Solution {
public:
    bool canBeEqual(vector<int>& target, vector<int>& arr) {
        unordered_map<int, int> m;
        for (int i = 0; i < target.size(); i ++ ) m[target[i]] ++;
        bool flag = true;
        for (int i = 0; i < arr.size(); i ++ ) {
            if (m.count(arr[i]) && m[arr[i]] >= 1) m[arr[i]] --;
            else {
                flag = false;
                break;
            }
        }
        return flag;
    }
};

判断路径是否相交


题目链接:判断路径是否相交

C++版AC代码:

原本想用坐标哈希的,但是不能套 pair,根据题目范围:1 <= path.length <= 1e4,故可以把横坐标映射为 1e5,纵坐标映射为 1,映射成 double 类型的 10.00001 的话会有精度问题

class Solution {
public:
    bool isPathCrossing(string path) {
        unordered_map<int, int> m;
        m[0] = 1;
        double nowad = 0;
        bool flag = false;
        for (int i = 0; i < path.size(); i ++ ) {
            char ad = path[i];
            if (ad == 'N') nowad += 1e5;
            else if (ad == 'S') nowad -= 1e5;
            else if (ad == 'E') nowad += 1;
            else nowad -= 1;
            if (m.count(nowad)) {
                flag = true;
                break;
            }
            m[nowad] = 1;
        }
        return flag;
    }
};

两个相同字符之间的最长子字符串


题目链接:两个相同字符之间的最长子字符串

C++版AC代码:

class Solution {
public:
    int maxLengthBetweenEqualCharacters(string s) {
        unordered_map<char, int> m;
        for (int i = 0; i < s.size(); i ++ ) m[s[i]] = i;   // 记录最后一次出现的位置
        int res = -1;
        for (int i = 0; i < s.size(); i ++ ) 
            res = max(res, m[s[i]] - i - 1);
        return res;
    }
};

按照频率将数组升序排序


题目链接:按照频率将数组升序排序

C++版AC代码:

注意对 sort 的定义与调用

class Solution {
public:
    vector<int> frequencySort(vector<int>& nums) {
        unordered_map<int, int> m;
        for (int i = 0; i < nums.size(); i ++ ) m[nums[i]] ++;
        sort(nums.begin(), nums.end(), [&](const int a, const int b) {
            if (m[a] == m[b]) return a > b;
            return m[a] < m[b];
        });
        return nums;
    }
    
};

能否连接形成数组 *


题目链接:能否连接形成数组

C++版AC代码:

class Solution {
public:
    bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
        unordered_map<int, int> m;
        for (int i = 0; i < pieces.size(); i ++ ) 
            m[pieces[i][0]] = i;      // 仅标记第一个
        for (int i = 0; i < arr.size();) {      // 注意这里没有 i ++
            int k = arr[i];
            if (!m.count(k)) return false;
            int ad = m.find(k) -> second;
            for (int j = 0; j < pieces[ad].size(); j ++, i ++ ) // i 在此更新
                if (arr[i] != pieces[ad][j]) 
                    return false;
        }
        return true;
    }
};

关于sort

sort(nums.begin(), nums.end(), [&](const int a, const int b) {
	if (m[a] == m[b]) return a > b;
	return m[a] < m[b];
});

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