扬州专业做网站,wordpress主题怎么写,东莞网页设计教程,做招聘网站怎么赚钱文章目录 前言两数之和存在重复元素 II好数对的数目总持续时间可被 60 整除的歌曲 前言 #x1f4ab;你好#xff0c;我是辰chen#xff0c;本文旨在准备考研复试或就业 #x1f4ab;文章题目大多来自于 leetcode#xff0c;当然也可能来自洛谷或其他刷题平台 #x1f4a… 文章目录 前言两数之和存在重复元素 II好数对的数目总持续时间可被 60 整除的歌曲 前言 你好我是辰chen本文旨在准备考研复试或就业 文章题目大多来自于 leetcode当然也可能来自洛谷或其他刷题平台 欢迎大家的关注我的博客主要关注于考研408以及AIoT的内容 仅给出C版代码 以下的几个专栏是本人比较满意的专栏(大部分专栏仍在持续更新)欢迎大家的关注 ACM-ICPC算法汇总【基础篇】 ACM-ICPC算法汇总【提高篇】 AIoT(人工智能物联网) 考研 CSP认证考试历年题解 两数之和 题目链接两数之和
C版AC代码
暴力时间复杂度 O ( n 2 ) O(n^2) O(n2)空间复杂度 O ( 1 ) O(1) O(1)
class Solution {
public:vectorint twoSum(vectorint 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 ) O(n) O(n)【 find 的时间复杂度为 O ( 1 ) O(1) O(1)】空间复杂度 O ( n ) O(n) O(n)【建立了一个空哈希表】
注意因为 find 查的是 first 所以我们在插入的时候first nums[i]second i
class Solution {
public:vectorint twoSum(vectorint nums, int target) {int n nums.size();unordered_mapint, 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(vectorint nums, int k) {unordered_mapint, 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(vectorint 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(vectorint nums) {int cnt 0;unordered_mapint, 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(vectorint time) {unordered_mapint, 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(vectorint 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;}
};
