【LeetCode刷题】最近一月刷题总结（罗马数字转整数+质数相关+ for的5种用法+错误的集合+符号优先级）

罗马数字转整数+质数相关+ for的5种用法+错误的集合+符号优先级

2019年9月20日

11:15

铁憨憨
class Solution {
public:
int romanToInt(string s) {
string a={'I','V','X','L','C','D','M'};
int sum=0,len=s.length(); `your inline code...`
switch(s[len-1]){
case 'I':sum++;break;
case 'V':sum+=5;break;
case 'X':sum+=10;break;
case 'L':sum+=50;break;
case 'C':sum+=100;break;
case 'D':sum+=500;break;
case 'M':sum+=1000;break;
}
for(int i=len-2;i>=0;i--){
if(a.find(s[i])>=a.find(s[i+1])){
switch(s[i]){
case 'I':sum++;break;
case 'V':sum+=5;break;
case 'X':sum+=10;break;
case 'L':sum+=50;break;
case 'C':sum+=100;break;
case 'D':sum+=500;break;
case 'M':sum+=1000;break;
}
}else{
switch(s[i]){
case 'I':sum--;break;
case 'V':sum-=5;break;
case 'X':sum-=10;break;
case 'L':sum-=50;break;
case 'C':sum-=100;break;
case 'D':sum-=500;break;
case 'M':sum-=1000;break;
}
}
}
return sum;
}
};
来自 <https://leetcode-cn.com/problems/roman-to-integer/comments/>
大神（正则）
class Solution {
public:
int romanToInt(string s) {
string roman[13] = {
"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"
};
int nums[13] = {
1000,900,500,400,100,90,50,40,10,9,5,4,1
};
int res = 0;
int i = 0;
int j = 0;
while (j < 13 && i < s.size()){
while ( s.substr(i, 1)== roman[j] || s.substr(i, 2) == roman[j]){
if (s.substr(i, 1) == roman[j])
i++;
else if (s.substr(i, 2) == roman[j])
i += 2;
res += nums[j];
}
j++;
}
return res;
}
};
来自 <https://leetcode-cn.com/problems/roman-to-integer/comments/>
正常人hashmap解法：
class Solution {
public:
int romanToInt(string s) {
map<char,int> val;
val['I'] = 1;val['V'] = 5;val['X'] = 10;val['L'] = 50;
val['C'] = 100;val['D'] = 500;val['M'] = 1000;
int sum = 0;
for(int i = 0; i < s.size()-1; ++i){
if(val[s[i]] >= val[s[i+1]]) sum += val[s[i]];
else sum -= val[s[i]];
}
sum+=val[s.back()];
return sum;
}
};
来自 <https://leetcode-cn.com/problems/roman-to-integer/comments/>

质数相关

2019年9月23日

20:03

都列出来查表
const int mod = 1e9 + 7;
const vector<int> primes{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
vector<long> factorial_cache(101);
int cache_size = 1;
class Solution {
public:
int numPrimeArrangements(int n) {
factorial_cache[0] = 1;
int numPrimes = distance(primes.begin(), upper_bound(primes.begin(), primes.end(), n));
return factorial(numPrimes) * factorial(n - numPrimes) % mod;
}
long factorial(int n) {
if(factorial_cache[n])
return factorial_cache[n];
for(;cache_size<=n;++cache_size)
factorial_cache[cache_size] = factorial_cache[cache_size - 1] * cache_size % mod;
return factorial_cache[n];
}
};
来自 <https://leetcode-cn.com/problems/prime-arrangements/comments/>
正常解法，在每次乘的时候都取余
public int numPrimeArrangements(int n) {
if (n <= 1)
return 1;
int prime_count = 1;
for (int i = 3; i <= n; i+=2) {
boolean flag = false;
for (int j = 2; j * j <= i; j++)
if (i % j == 0) {
flag = true;
break;
}
prime_count += flag ? 0 : 1;
}
return (int)((getFactorial(prime_count) * getFactorial(n - prime_count))% 1000000007);
}
public long getFactorial(int n) {
long res = 1;
for (int i = 1; i <= n; i++)
res = (res * i) % 1000000007;
return res;
}
来自 <https://leetcode-cn.com/problems/prime-arrangements/comments/>

for的5种用法

2019年10月14日

15:09

#include <algorithm>
#include <vector>
//////////////////////////////////////////////
int nArray[] = {0, 1, 2, 3, 4, 5};
std::vector<int> vecNum(nArray, nArray + 6);
CString strText;
// 第一种用法：最原始的语法(用下标)
for (size_t i = 0; i < vecNum.size(); ++i)
{
strText.Format("%d", nArray[i]);
AfxMessageBox(strText);
}
// 第二种用法：最原始的语法(用迭代器)
for (auto it = vecNum.begin(); it != vecNum.end(); ++it)
{
strText.Format("%d", *it);
AfxMessageBox(strText);
}
// 第三种用法：简化数组遍历语法(从vs2008开始支持)
for each(auto item in vecNum)
{
strText.Format("%d", item);
AfxMessageBox(strText);
}
// 第四种用法：STL函数
std::for_each(vecNum.begin(), vecNum.end(), [](int item){
CString strText;
strText.Format("%d", item);
AfxMessageBox(strText);
});
// 第五种用法：C++11新增加的(VS2012支持)
for(auto item : vecNum)
{
strText.Format("%d", item);
AfxMessageBox(strText);

来自 <https://blog.csdn.net/erinapple/article/details/84193841>

错误的集合

2019年10月22日

17:37

用总数减去总数来求被覆盖的数！！妙

class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
int res[10001]{0};
int sum=0;
int emt=0,rep=0,n=nums.size();
for(int i=0;i<nums.size();i++)
{
if((++res[nums[i]])>1) rep=nums[i];
sum+=nums[i];
}
emt =(1+n)*n/2-sum+rep;
return{rep,emt};
}
};
static const auto io_speed_up=[]{
ios::sync_with_stdio(false);
cin.tie(0);
return 0;
}();

来自 <http://www.planetb.ca/projects/syntaxHighlighter/popup.php>

符号优先级

优先级	运算符	名称或含义	使用形式	结合方向	说明
1	[]	数组下标	数组名[整型表达式]	左到右
	()	圆括号	（表达式）/函数名(形参表)
	.	成员选择（对象）	对象.成员名
	->	成员选择（指针）	对象指针->成员名
2	-	负号运算符	-算术类型表达式	右到左	单目运算符
	(type)	强制类型转换	(纯量数据类型)纯量表达式
	++	自增运算符	++纯量类型可修改左值表达式		单目运算符
	--	自减运算符	--纯量类型可修改左值表达式		单目运算符
	*	取值运算符	*指针类型表达式		单目运算符
	&	取地址运算符	&表达式		单目运算符
	!	逻辑非运算符	!纯量类型表达式		单目运算符
	~	按位取反运算符	~整型表达式		单目运算符
	sizeof	长度运算符	sizeof 表达式 sizeof(类型)
3	/	除	表达式/表达式	左到右	双目运算符
	*	乘	表达式*表达式		双目运算符
	%	余数（取模）	整型表达式%整型表达式		双目运算符
4	+	加	表达式+表达式	左到右	双目运算符
	-	减	表达式-表达式		双目运算符
5	<<	左移	整型表达式<<整型表达式	左到右	双目运算符
	>>	右移	整型表达式>>整型表达式		双目运算符
6	>	大于	表达式>表达式	左到右	双目运算符
	>=	大于等于	表达式>=表达式		双目运算符
	<	小于	表达式<表达式		双目运算符
	<=	小于等于	表达式<=表达式		双目运算符
7	==	等于	表达式==表达式	左到右	双目运算符
	!=	不等于	表达式!= 表达式		双目运算符
8	&	按位与	整型表达式&整型表达式	左到右	双目运算符
9	^	按位异或	整型表达式^整型表达式	左到右	双目运算符
10	\|	按位或	整型表达式\|整型表达式	左到右	双目运算符
11	&&	逻辑与	表达式&&表达式	左到右	双目运算符
12	\|\|	逻辑或	表达式\|\|表达式	左到右	双目运算符
13	?:	条件运算符	表达式1? 表达式2: 表达式3	右到左	三目运算符
14	=	赋值运算符	可修改左值表达式=表达式	右到左
	/=	除后赋值	可修改左值表达式/=表达式
	*=	乘后赋值	可修改左值表达式*=表达式
	%=	取模后赋值	可修改左值表达式%=表达式
	+=	加后赋值	可修改左值表达式+=表达式
	-=	减后赋值	可修改左值表达式-=表达式
	<<=	左移后赋值	可修改左值表达式<<=表达式
	>>=	右移后赋值	可修改左值表达式>>=表达式
	&=	按位与后赋值	可修改左值表达式&=表达式
	^=	按位异或后赋值	可修改左值表达式^=表达式
	\|=	按位或后赋值	可修改左值表达式\|=表达式
15	,	逗号运算符	表达式,表达式,…	左到右	从左向右顺序结合

来自 <https://baike.baidu.com/item/%E8%BF%90%E7%AE%97%E7%AC%A6%E4%BC%98%E5%85%88%E7%BA%A7/4752611?fr=aladdin>