91algo's People
91algo's Issues
Pair
- 定义构造
pair<int,double> p1; //默认构造函数
pair<int,double> p2(1,2.4) //初始化
pair<int,double> p3(p2) //拷贝构造函数
#include<iostream>
using namespace std;
#include<string>
#include <utility>
int main()
{
pair<int, string> p1; //default constructor
pair<string, double>p2("zhouyu", 100); // overroad constructor
pair<string, double>p3 = (p2);
p2.first = "nobody"; p2.second = 20;
cout << p2.first << " " << p2.second << endl;
cout << p3.first << " " << p3.second << endl;
return 0;
}
- make_pair 由定义给它的两个实参生成一个新的pair对象
pair<string, string> next_auth;
string first,last;
while(cin>>first>>last) {
next_auth=make_pair(first,last);
}
- vector中pair的使用
声明vectorvector <pair<int,int>> vec;
插入数据要make_pair
vec.push_back(make_pair(10,20));
STL中的priority_queue优先队列
题目地址(1046. 最后一块石头的重量)
https://leetcode-cn.com/problems/last-stone-weight/
题目描述
有一堆石头,每块石头的重量都是正整数。
每一回合,从中选出两块 最重的 石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:
如果 x == y,那么两块石头都会被完全粉碎;
如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x。
最后,最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下,就返回 0。
示例:
输入:[2,7,4,1,8,1]
输出:1
解释:
先选出 7 和 8,得到 1,所以数组转换为 [2,4,1,1,1],
再选出 2 和 4,得到 2,所以数组转换为 [2,1,1,1],
接着是 2 和 1,得到 1,所以数组转换为 [1,1,1],
最后选出 1 和 1,得到 0,最终数组转换为 [1],这就是最后剩下那块石头的重量。
提示:
1 <= stones.length <= 30
1 <= stones[i] <= 1000
前置知识
- priority_queue 优先队列
- 1.头文件 #include
- 2.定义 priority_queue q;
- 3.优先输出最大数——即默认大顶堆
priority_queue<Type,container,functional>
type为数据类型,container为保存数据的容器,functional为元素的比较方式
后面两个参数不写时,容器默认是vector,比较方式默认operator<,也就是优先对列是大顶堆,队首是最大数 - 4.如何输出最小元素
- 方法一
priority_queue<int ,vector,greater> q; - 方法二
自己定义优先顺序,重载默认的<符号
例子
struct Node{
int x,y;
Node(int a=0,int b=0):x(a),y(b){}
};
static bool cmp(Node &a,Node &b){
if(a.x==b.x) return a.y>b.y;
return a.x>b.x;
}
priority_queue<Node,vector,decltype(&cmp)> q(cmp);
- 方法一
思路
关键点
- 优先队列输出最大,弹出队首a,在输出弹出现有的队首b,即原队列的最大两个数,如果a==b,则说明最大两个数相等,不用再push进队列,否则push(a-b)
代码
- 语言支持:C++
C++ Code:
class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
priority_queue<int> q;
for(int stone:stones){
q.push(stone);
}
while(q.size()>1){
int a=q.top();
q.pop();
int b=q.top();
q.pop();
if(a!=b) q.push(a-b);
}
if(q.size()==1) return q.top();
return 0;
}
};
复杂度分析
令 n 为数组长度。
- 时间复杂度:$O(nlogn)$
- 空间复杂度:$O(n)$
1590 使数组和能被P整除
class Solution {
public:
int minSubarray(vector<int>& nums, int p) {
int ans=nums.size(),len=nums.size();
long mod=0,sum=0;
for(int i=0;i<len;i++){//数组总和对p取余
sum+=nums[i];
}
mod=sum%p;
//排除两个特殊情况,数组和被整除以及数组和<p
if(mod==0) return 0;
if(sum<p) return -1;
long m=0,s=0;
//哈西表
unordered_map<long,int>map{{0,-1}};//其实位置-1
for(int i=0;i<len;i++){
s+=nums[i];
m=(s-mod+p)%p;//同余定理推倒
if(map.count(m)) {
ans=min(ans,i-map[m]);
}
map[s%p]=i;//记录前缀和对p取余及下标
}
return ans==nums.size()?-1:ans;
}
};
DAY 11 环形链表||
给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意,pos 仅仅是用于标识环的情况,并不会作为参数传递到函数中。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/linked-list-cycle-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.