中等题
罗马人真不太聪明吧,搞这么复杂的数字转换方式。做好判断,这题没啥东西。
#include
#include
using namespace std;
class Solution {
public:
string intToRoman(int num) {
vector<vector<string>> rule = {{"I","V","X"},{"X","L","C"},{"C","D","M"},{"M"}};
string res = "";
int level = 0;
while(num>0){
res = bitChange(rule,num%10,level) + res;
num /= 10;
level ++;
}
return res;
}
string bitChange(const vector<vector<string>>& rule, int bit, int level){
string res = "";
if(bit == 0) return res;
if(bit <= 3){
res.insert(0,bit,rule[level][0][0]);
return res;
}
if(bit == 4) return rule[level][0]+rule[level][1];
if(bit == 5) return rule[level][1];
if(bit <= 8){
res += rule[level][1];
res.insert(1,bit-5,rule[level][0][0]);
return res;
}
if(bit == 9) return rule[level][0]+rule[level][2];
else return res;
}
};
int main(){
Solution st;
cout<<st.intToRoman(1954)<<endl;
return 0;
}
简单题
和罗马人过去不了是吧!做过上一题后,这一题就更简单了,随手秒掉。
#include
using namespace std;
class Solution {
public:
int romanToInt(string s) {
int res = 0;
int len = s.size();
s += " ";
for(int i=len-1;i>=0;i--){
res += bitValue(s,i,i+1);
}
return res;
}
int bitValue(const string& s, int cur, int pre){
int curbit = bitChange(s[cur]);
int prebit = bitChange(s[pre]);
if(curbit < prebit) return (-1)*curbit;
else return curbit;
}
int bitChange(char s){
switch(s){
case 'I': return 1;
case 'V': return 5;
case 'X': return 10;
case 'L': return 50;
case 'C': return 100;
case 'D': return 500;
case 'M': return 1000;
default: return 0;
}
}
};
int main(){
Solution st;
cout<<st.romanToInt("MCMXCIV")<<endl;
return 0;
}
简单题
这里选择纵向扫描,即一列一列比。当然也可以横向扫描,两两比较找公共等。而选择分治、二分等算法并没有太多提高算法效率,所以不写。
#include
#include
using namespace std;
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
int len = strs.size();
int maxsize = 0;
string res = "";
while(maxsize<strs[0].size()){
//随便找一个,反正公共子串不会比这个长了
char pub = strs[0][maxsize];
int i = 0;
while(i<len){
if(strs[i][maxsize] != pub) break;
i++;
}
if(i == len) maxsize++;
else break;
}
return strs[0].substr(0,maxsize);
}
};
int main(){
Solution st;
vector<string> vt = {"flower","aflow","sflight"};
cout<<st.longestCommonPrefix(vt)<<endl;
return 0;
}
中等题
显然,在不考虑任何别的条件的情况下,在一个数组中找到所有长度为3的组合需要3次循环,达到O(n3)的复杂度。这在本题中肯定是不能接受的,所以a+b+c=0的条件非常关键。这个条件可以被继续理解。结合题目中别的条件可以整理成以下信息:
首先在这里提出一种没有走到最后的设想。设置左右指针分别指向升序排序的数组首尾,然后这两个指针向内侧移动。再设置第三个中间指针,在左右指针之间从左到右运动。这里左指针在小于0的区间增大,右指针在大于0的区间减小。不过问题是,这样无法规避可能出现的重复情况。尽管我们排了序,但是仍然不允许使用相邻的数必须不同这一判断,原因是类似于数组<-2,-2,4>确实包含了相同的数,而我们的两个指针一个降序,一个升序,会在不同的循环中得到相同结果的数组。并且虽然看起来这样循环次数少了,但是其复杂度还是由三个循环组成,即O(n3)。
接下来是官解,同样在排序的基础上进行。首先以指针first进行一重循环作为选择的第一个数,要保证:这个数与上一个选择的数不相同,以防止重复。接着以指针second进行二重循环作为选择的第二个数。其实,当我们确定了一重循环的第一个数nums[first]后,我们的表达式变为:nums[second]+nums[third] = -nums[first],即和为定值。当nums[second]增大,nums[third]只能减小。而数组也已经升序排列好。我们只要再设置一个指针third,从数组的最后向前减小,观察它减少到哪里能使得式子成立就可以了。这样的好处在于二重循环second指针右移1个单位,third指针左移若干个单位,这一重循环平均只要N次就可以了(为什么?没搞明白这个平均是怎么来的)。
#include
#include
#include
using namespace std;
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
if(nums.size()<3) return res; //小于三个直接返回空
sort(nums.begin(),nums.end()); //排序
for(int first=0; first<nums.size(); first++){
if((first == 0 || nums[first] != nums[first-1]) && nums[first]<=0){
//前后重复,取后一个,顺便这里考虑到第一个数必须小于等于0来剪枝
int third = nums.size()-1;
for(int second=first+1; second<nums.size(); second++){
if(second == first+1 || nums[second] != nums[second-1]){
//前后重复,选择后一个
while(second<third && nums[first] + nums[second] + nums[third] >0){
third--;
}
if(second == third) break; //第二第三个指针相遇,第二个指针进行下一轮右移
if(nums[first] + nums[second] + nums[third] == 0) res.push_back(vector<int> {nums[first],nums[second],nums[third]});
}
}
}
}
return res;
}
};
int main(){
Solution st;
vector<int> vt = {-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6};
vector<vector<int>> res;
res = st.threeSum(vt);
return 0;
}
总结:当我们需要枚举数组中的两个元素时,如果我们发现随着第一个元素的递增,第二个元素是递减的,那么就可以使用双指针的方法,将枚举的时间复杂度从 O(n2)减少至O(n)。 这是一个重要结论:和为定值的两个数能在O(n)的复杂度下完成搜索。