本篇文章记录在leetcode中Math主题下面的题目和自己的思考以及优化过程,具体内容层次按照{题目,分析,初解,初解结果,优化解,优化解结果,反思}的格式来记录,供日后复习和反思[注:有些题目的解法比较单一,就没有优化过程]。题目的顺序按照leetcode给出的题目顺序,有些题目在并不是按照题目本身序号顺序排列的,也不是严格按照难易程度来排列的。
因此,这篇文章并不具有很强的归类总结性,归类总结性知识将会在其他文章记录,本篇重点在记录解题过程中的思路,希望能对自己有所启发。
class Solution {
public:
int reverse(int x) {
if(x==0)
return 0;
bool flag = true;
if(x<0)
{
flag = false;
x = -x;
}
int times = 1;
long re_val = re(x, times);
int tmp = re_val;
if(tmp != re_val)
return 0;
if(flag==false)
tmp = -tmp;
return tmp;
}
long re(int val, int& times)
{
if(val == 0)
return 0;
long extract_val = val % 10;
val = val/10;
long res = re(val, times);
if(val != 0)
times = times * 10;
res += extract_val * times;
return res;
}
};
class Solution {
public:
bool isPalindrome(int x) {
if(x < 10 && x >=0 )
return true;
if(x < 0 || x == 10)
return false;
int front = 1, val = x, end = 1;
while(1)
{
val = val / 10;
if(val != 0)
front = front * 10;
else break;
}
return judge_bit(x, front, end);
}
bool judge_bit(int x, int front, int end)
{
if(front > end)
{
if(((x / front) % 10) == ((x / end) % 10))
{
if(judge_bit(x, front / 10, end * 10) == true)
return true;
else return false;
}
else return false;
}
else return true;
}
};
class Solution {
public:
string intToRoman(int num) {
char unit[7] ={'M','D','C','L','X','V','I'};
int val[7] ={1000,500,100,50,10,5,1};
string res = "";
int unit_index = 0;
while(num != 0)
{
int multiple = num / val[unit_index];
if( multiple > 0 )
{
switch(multiple)
{
case 1:res+=unit[unit_index];break;
case 2:res+=string(2,unit[unit_index]);break;
case 3:res+=string(3,unit[unit_index]);break;
case 4:res+=string(1,unit[unit_index])+string(1,unit[unit_index-1]);break;
case 5:res+=unit[unit_index-1];break;
case 6:res+=string(1,unit[unit_index-1])+string(1,unit[unit_index]);break;
case 7:res+=string(1,unit[unit_index-1])+string(2,unit[unit_index]);break;
case 8:res+=string(1,unit[unit_index-1])+string(3,unit[unit_index]);break;
case 9:res+=string(1,unit[unit_index])+string(1,unit[unit_index-2]);break;
}
}
num = num - multiple * val[unit_index];
unit_index += 2;
}
return res;
}
};
class Solution {
public:
int romanToInt(string s) {
int res = 0;
unordered_map<char, int> flag_val;
flag_val['I'] = 1;
flag_val['X'] = 10;
flag_val['C'] = 100;
flag_val['V'] = 5;
flag_val['L'] = 50;
flag_val['D'] = 500;
flag_val['M'] = 1000;
for(int i = 0; i < s.size(); ++i)
{
if(i+1 < s.size())
{
if(flag_val[s[i]] >= flag_val[s[i+1]])
res += flag_val[s[i]];
else res -= flag_val[s[i]];
}
else res += flag_val[s[i]];
}
return res;
}
};
class Solution {
public:
string numberToWords(int num) {
if(num == 0)
return string("Zero");
string unit[] = {"Zero"," One", " Two", " Three", " Four"," Five"," Six"," Seven"," Eight"," Nine"," Ten"," Eleven"," Twelve"," Thirteen"," Fourteen"," Fifteen"," Sixteen"," Seventeen"," Eighteen"," Nineteen"};
string decade[] = {"Zero"," Ten"," Twenty"," Thirty"," Forty"," Fifty"," Sixty"," Seventy"," Eighty"," Ninety"};
string radix[] = {""," Thousand"," Million"," Billion"};
int radix_index = 0;
string res = "";
while(num != 0)
{
int a = num % 100, b = num % 10, c = (num / 10) % 10, d = (num / 100) % 10;
string tmp = "";
if(a < 20 && a != 0)
{
tmp = unit[a];
}
else
{
if(b != 0)
tmp = unit[b];
if(c != 0)
tmp = decade[c] + tmp;
}
if(d != 0)
tmp = unit[d] + string(" Hundred") + tmp;
if(a !=0 || b!=0 || c!=0 || d!=0)
res = tmp + radix[radix_index] + res;
num = num / 1000;
++radix_index;
}
return res.substr(1,res.size());
}
};