12/13、Integer to Roman/Roman to Integer
题目
罗马数字规则：
| 符号 | I | V | X | L | C | D | M |
| 数字 | 1 | 5 | 10 | 50 | 100 | 500 | 1000 |
代码如下：
class Solution {
public:
string intToRoman(int num) {
string str;
string symbol[]={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
int value[]= {,,,, , , , , , , , , };
for(int i=;num!=;++i)
{
while(num>=value[i])
{
num-=value[i];
str+=symbol[i];
}
}
return str;
}
};
举一反三，如果是将罗马数字转换为整数呢。思路是一样。参考代码如下：
class Solution {
public:
int romanToInt(string s) {
int ret = toNumber(s[]);
for (int i = ; i < s.length(); i++) {
if (toNumber(s[i - ]) < toNumber(s[i])) {
ret += toNumber(s[i]) - * toNumber(s[i - ]);
} else {
ret += toNumber(s[i]);
}
}
return ret;
}
int toNumber(char ch) {
switch (ch) {
case 'I': return ;
case 'V': return ;
case 'X': return ;
case 'L': return ;
case 'C': return ;
case 'D': return ;
case 'M': return ;
}
return ;
}
};
-------------------------------------------------------------------------------------------------分割线----------------------------------------------------------------------------
14、Longest Common Prefix
题目
这道题目比较简单，参考代码如下：
class Solution {
public:
string longestCommonPrefix(vector<string> &strs) {
int length = strs.size();
string result="";
int index=,i;
char temp;
bool flag=true;
if( == length)
return "";
while(flag)
{
temp=strs[][index];
for (i=;i<length;i++)
{
if (index>=strs[i].length() ||strs[i][index] != temp)
{
flag=false;
break;
}
}
if(i==length)
result += temp;
index++;
}
return result;
}
};
----------------------------------------------------------------------------------------------分割线-------------------------------------------------------------------------------
15、3Sum
题目
这道题目和Leetcode第1题很相似，第1题中是对排序数组进行收尾夹逼求解。因此在这一题中，我们任然也可以采用收尾夹逼的准则去求解。在每次求解的过程中，先固定好一个数c，然后采用夹逼方法判断a+b ?= -c,如果不等且a+b<-c,a右移，相反的，b左移；
题目要求不能有重复的解。为了避免重复解，在每次固定c值时，如果该值之前已经做过判断，直接跳过。
代码如下:
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<vector<int> > ret;
ret.clear();
sort(num.begin(),num.end());
for(int i=; i!=num.size();i++){
if(i > && num[i]==num[i-])
continue;
int j,k;
j=i+;
k=num.size()-;
while(j<k){
if(j>i+&&num[j]==num[j-]){
j++;
continue;
}
if(k<num.size()-&& num[k]==num[k+]){
k--;
continue;
}
int sum = num[i] + num[j] + num[k];
if(sum>){
k--;
}else if(sum<){
j++;
}else{
vector<int> tmp;
tmp.push_back(num[i]);
tmp.push_back(num[j]);
tmp.push_back(num[k]);
ret.push_back(tmp);
j++;
}
}
}
return ret;
}
};
算法的时间复杂度是：排序O(nlogn)和遍历O（n*n）.
--------------------------------------------------------------------------------------------分割线---------------------------------------------------------------------------------
16、3Sum Closest
题目
这题和15题是一个意思，都是采用先排序，再首尾夹逼。代码如下：
class Solution {
public:
int threeSumClosest(vector<int> &num, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
sort(num.begin(), num.end());
int ret;
bool first = true;
for(int i = ; i < num.size(); i++)
{
int j = i + ;
int k = num.size() - ;
while(j < k)
{
int sum = num[i] + num[j] + num[k];
if (first)
{
ret = sum;
first = false;
}
else
{
if (abs(sum - target) < abs(ret - target))
ret = sum;
}
if (ret == target)
return ret;
if (sum > target)
k--;
else
j++;
}
}
return ret;
}
};