leetcode-13. 罗马数字转整数
罗马数字转整形罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。
12345678字符 数值I 1V 5X 10L 50C 100D 500M 1000
例如, 罗马数字 2 写做 II ,即为两个并列的 1 。12 写做 XII ,即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:
I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边,来 ...
leetcode-42. 接雨水
接雨水给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。
按列来计算,第i列接到的雨水等于min(i左边最大高度,i右边最大高度)-height[i].
所以问题的关键就变成了求i左右两边的最大高度。这是一个非常简单的动态规划问题。
定义left数组,left[i]表示i左边最大高度(包括i,如果i左边最大高度就是height[i],则第i列接不到雨水,右边同理)。初始化left[0]=height[0]
left[i]=max(left[i-1],height[i])
定义right数组,right[i]表示i右边最大高度。 初始化right[n-1]=height[n-1]
right[i]=max(right[i+1],height[i])
注意: right数组必须从后往前遍历。第一 ...
acwing-数的三次方根
数的三次方根给定一个浮点数n,求它的三次方根
输入格式共一行,包含一个浮点数 n。
输出格式共一行,包含一个浮点数,表示问题的解。
注意,结果保留 6 位小数。
数据范围-10000<=n<=10000
注意符号类型为double型,所以边界问题很简单。
123456789101112131415161718192021#include<iostream>using namespace std;double square3(double n){ double l=-10000; double r=10000; while(r-l>1e-8){ double mid=(l+r)/2; if(mid*mid*mid<n) l=mid; else r=mid; } return l;}int main(){ double n; cin>>n; printf("%.6f\n",squar ...
leetcode-135. 分发糖果
分发糖果n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求,给这些孩子分发糖果:
每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果,计算并返回需要准备的 最少糖果数目 。
初始化数组vector<int>t(n,1)存储每个孩子的糖果数量。
分两次遍历数组
从左到右遍历数组,使得右边孩子的评分数大于左边孩子评分数,则右边孩子糖果数比左边孩子多1。
从右到左遍历数组,如果左边孩子的评分数大于右边孩子评分数,则左边孩子糖果数等于max(t[i],t[i+1]+1)。
123456789101112131415161718class Solution {public: int candy(vector<int>& ratings) { int n=ratings.size(); vector<int>t(n,1); for(int i=1;i<n;i++){ ...
leetcode-134. 加油站
加油站在一条环路上有 n 个加油站,其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。
给定两个整数数组 gas 和 cost ,如果你可以按顺序绕环路行驶一周,则返回出发时加油站的编号,否则返回 -1 。如果存在解,则 保证 它是 唯一 的。
这个题上学期的算法课老师出过一个简易版的,只有一个数组既是gas又是cost。而且测试数据很简单所以直接ac了。这个题就直接写不出来了
123456789101112131415161718192021222324class Solution {public: int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { int n = gas.size(); int cur_gas = 0; int start_index = 0 ...
acwing-数的范围
数的范围给定一个按照升序排列的长度为 n的整数数组,以及 q 个查询。
对于每个查询,返回一个元素 k 的起始位置和终止位置(位置从 0 开始计数)。
如果数组中不存在该元素,则返回 -1 -1。
输入格式第一行包含整数 n 和 q,表示数组长度和询问个数。
第二行包含 n 个整数(均在 1∼100001∼10000 范围内),表示完整数组。
接下来 q 行,每行包含一个整数 k,表示一个询问元素。
输出格式共 q 行,每行包含两个整数,表示所求元素的起始位置和终止位置。
如果数组中不存在该元素,则返回 -1 -1。
数据范围1≤n≤1000001≤q≤100001≤k≤10000
经典的二分模板题。
题目要找k的左边界和右边界。
12345678910111213141516171819202122232425262728293031323334353637383940414243#include<iostream>using namespace std;const int N = 1e5+10;int a[N];int left_bound(int k,int n) ...
leetcode-380. O(1) 时间插入、删除和获取随机元素
O(1) 时间插入、删除和获取随机元素实现RandomizedSet 类:
RandomizedSet() 初始化 RandomizedSet 对象
bool insert(int val) 当元素 val 不存在时,向集合中插入该项,并返回 true ;否则,返回 false 。
bool remove(int val) 当元素 val 存在时,从集合中移除该项,并返回 true ;否则,返回 false 。
int getRandom() 随机返回现有集合中的一项(测试用例保证调用此方法时集合中至少存在一个元素)。每个元素应该有 相同的概率 被返回。
你必须实现类的所有函数,并满足每个函数的 平均 时间复杂度为 O(1) 。
要求常数时间下插入和删除元素所以考虑哈希表。随机返回集合中的一项也就是可以对集合随机访问,但是哈希表不能做到这点,所以还要引入顺序表来支持随机访问。
这个题的处理方式很像静态链表,就是用数组构建的链表,链表在空间上是连续的。
设置哈希表hash<元素值,下标>,动态数组a。a的下标对应hash的下标,a的元素值对应hash的元素值。
对应关系 ...
leetcode-238. 除自身以外数组的乘积
除自身以外数组的乘机给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法,且在 O(n) 时间复杂度内完成此题。
这个题最显然的解法就是把所有元素全乘起来,然后除以nums[i],但是除法会出现除数为0的情况,而且题目要求不能用除法。
类似前缀和,这个题用的是前缀积。
设置前缀积数组l[]和后缀积r[]数组,分别存放nums[i]和nums[i]之后所有数的乘积(不包括nums[i])。
注意,后缀积需要逆序求。
12345678910111213141516class Solution {public: vector<int> productExceptSelf(vector<int>& nums) { int n=nums.size(); vector<int> l(n,1),r ...
acwing-逆序对的数量
逆序对的数量给定一个长度为 n的整数数列,请你计算数列中的逆序对的数量。
逆序对的定义如下:对于数列的第 i 个和第 j个元素,如果满足 i<j且 a[i]>a[j],则其为一个逆序对;否则不是。
输入格式第一行包含整数 n,表示数列的长度。
第二行包含 n 个整数,表示整个数列。
输出格式输出一个整数,表示逆序对的个数。
数据范围1≤n≤100000,数列中的元素的取值范围 [1,109]
归并排序合并时可以判断i<j且 a[i]>a[j]。
写递归先确定函数的返回值是什么,显然递归函数的返回值应该是逆序对的个数。
然后确定返回条件:数组只有一个元素时,逆序对个数为0,返回0.
逆序对的总个数等于两部分的逆序对之和,而每个部分的逆序对个数为mid-i+1。最后将ans返回
123456789101112131415161718192021222324252627282930313233#include<iostream>using namespace std;const int N = 1e5+10;int a[N];int t[N];long ...
acwing-归并排序
归并排序给定你一个长度为 n 的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
归并排序的思想是分治,先将数组一分为二,分为[l,mid]和[mid+1,r]重复这个操作直到分为只有一个元素,即l==r时return。
数组两两合并,由于是从只有一个元素开始返回,所以保证每次都是两个有序数组合并。
1234567891011121314151617181920212223242526#include<iostream>using namespace std;const int N = 1e5+10;int a[N];int t[N];void merge(int l,int r){ if(l==r) return; int mid=l+r>>1,i=l,j=mid+1,k=0; merge(l,mid); merge(mid+1,r); while(i<=mid&&j<=r){ if(a[i]<a[j]) t[k++]= ...