复试 || 就业day01(2023.12.27)算法篇

前言

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

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

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

两数之和

题目链接：两数之和

C++版AC代码：

暴力：时间复杂度 $O(n^2)$，空间复杂度 $O(1)$

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int n = nums.size();for (int i = 0; i < n; i ++ )for (int j = i + 1; j < n; j ++ ){if (nums[i] + nums[j] == target){return {i, j};}}return {};}
};

哈希：时间复杂度 $O(n)$【 find 的时间复杂度为$O(1)$】，空间复杂度 $O(n)$【建立了一个空哈希表】

注意因为 find 查的是 first 所以我们在插入的时候，first = nums[i]，second = i

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int n = nums.size();unordered_map<int, int> m;for (int i = 0; i < n; i ++ ) {auto it = m.find(target - nums[i]);if (it != m. end()){return {it -> second, i};}m[nums[i]] = i;}return {};}
};

---

存在重复元素 II

题目链接：存在重复元素 II

C++版AC代码：

同样是使用哈希表，这里需要注意，哈希的插入是直接使用 m[nums[i]] = i; 不可以使用 m.insert(make_pair(nums[i], i))，因为nums中是会有相同的值重复出现的，我们只需要保存距离最近的一个点就可以了，但是 insert 操作只会保存第一个存入的键值对，后续相同的键值不会更新

class Solution {
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {unordered_map<int, int> m;for (int i = 0; i < nums.size(); i ++ ) {auto it = m.find(nums[i]);if (it != m.end() && abs(m[nums[i]] - i) <= k) return true;m[nums[i]] = i;}return false;}
};                                                                                              

---

好数对的数目

题目链接：好数对的数目

C++版AC代码：

桶的思想

class Solution {
public:int numIdenticalPairs(vector<int>& nums) {int cnt = 0;int t[110] = {0};for (int i = 0; i < nums.size(); i ++ ){cnt += t[nums[i]];t[nums[i]] ++;}return cnt;}
};

C++版AC代码：

哈希也可，本质无区别

class Solution {
public:int numIdenticalPairs(vector<int>& nums) {int cnt = 0;unordered_map<int, int> m;for (int i = 0; i < nums.size(); i ++ ){cnt += m[nums[i]];m[nums[i]] ++;}return cnt;}
};

---

总持续时间可被 60 整除的歌曲

题目链接：总持续时间可被 60 整除的歌曲

C++版AC代码：

哈希维护出现的次数，依次枚举可能的解，因为元素的大小为 [1, 500]，故 j 的上限为 1000，每次 +60

class Solution {
public:int numPairsDivisibleBy60(vector<int>& time) {unordered_map<int, int> m;int cnt = 0;for (int i = 0; i < time.size(); i ++ ){for (int j = 60; j < 1000; j += 60 ){int tmp = j - time[i];auto it = m.find(tmp);if (it != m.end()) cnt += m[tmp];}m[time[i]] ++;}return cnt;}
};

C++版AC代码：

其实是没必要进行枚举的，开一个大小为 60 的数组，找可以被 60 整除的另一个数实际上就是在找 60 - time[i] % 60，特别的对于自身就可以被 60 整除的数，需要将其映射回 0，故对于每一个 time[i]，去找 (60 - time[i] % 60) % 60

class Solution {
public:int numPairsDivisibleBy60(vector<int>& time) {int cnt = 0;int nums[65] = {0};for (int i = 0; i < time.size(); i ++ ){cnt += nums[(60 - time[i] % 60) % 60];nums[time[i] % 60] ++;}return cnt;}
};