Fraction to Recurring Decimal(STRING-TYPE CONVERTION)
QUESTION
Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.
If the fractional part is repeating, enclose the repeating part in parentheses.
For example,
Given numerator = 1, denominator = 2, return "0.5".
Given numerator = 2, denominator = 1, return "2".
Given numerator = 2, denominator = 3, return "0.(6)".
1ST TRY
class Solution {
public:
string fractionToDecimal(int numerator, int denominator) {
char* ch = new char();
string ret;
string fractionStr = "";
int remain;
vector<bool> flag(, false); //integer part
*ch = numerator/denominator +'';
ret = ch; //fraction part
while()
{
remain = numerator%denominator;
if(remain == ) return ret;
else if(flag[remain]) return ret + ".(" + fractionStr + ")";
else
{
flag[remain] = true;
*ch = numerator/denominator +'';
fractionStr += ch;
}
}
}
};
Result: Runtime Error
Last executed input: -50, 8
2ND TRY
考虑了负数情况
class Solution {
public:
string fractionToDecimal(int numerator, int denominator) {
string intStr = "";
string fractionStr = "";
string tmpStr = "";
int remain;
vector<bool> flag(, false); // int 转 string
stringstream ss; //negative or not
if(numerator > && denominator < )
{
intStr = "-";
denominator = ~(denominator-);
}
else if(numerator < && denominator > )
{
intStr = "-";
numerator = ~(numerator-);
}
else if(numerator < && denominator < )
{
numerator = ~(numerator-);
denominator = ~(denominator-);
} //integer part
ss << numerator/denominator;
ss >> tmpStr;
intStr += tmpStr;
remain = numerator%denominator;
if(remain == ) return intStr; //fraction part
while()
{
if(remain == ) return intStr + "." + fractionStr;
else if(flag[remain]) return intStr + ".(" + fractionStr + ")";
else
{
flag[remain] = true;
numerator = remain * ;
remain = numerator%denominator;
ss.clear();
ss << numerator/denominator;
ss >> tmpStr;
fractionStr += tmpStr;
}
}
}
};
Result: Runtime Error
Last executed input: -2147483648, -10
3RD TRY
考虑溢出的情况
class Solution {
public:
string fractionToDecimal(int numerator, int denominator) {
long long int num = (long long int) numerator;
long long int den = (long long int) denominator; string intStr = "";
string fractionStr = "";
string tmpStr = "";
int remain;
set<int> flag; // int 转 string
stringstream ss; //negative or not
if(num > && denominator < )
{
intStr = "-";
den = ~(den-);
}
else if(num < && den > )
{
intStr = "-";
num = ~(num-);
}
else if(num < && den < )
{
num = ~(num-);
den = ~(den-);
} //integer part
ss << num/den;
ss >> tmpStr;
intStr += tmpStr;
remain = num%den;
if(remain == ) return intStr; //fraction part
while()
{
if(remain == ) return intStr + "." + fractionStr;
else if(flag.find(remain)!=flag.end()) return intStr + ".(" + fractionStr + ")";
else
{
flag.insert(remain);
num = remain * ;
remain = num%den;
ss.clear();
ss << num/den;
ss >> tmpStr;
fractionStr += tmpStr;
}
}
}
};
Result: Wrong
Input: 1, 6
Output: "0.(16)"
Expected: "0.1(6)"
4TH TRY
循环的位置得准确,所以用map代替set
class Solution {
public:
string fractionToDecimal(int numerator, int denominator) {
long long int num = (long long int) numerator;
long long int den = (long long int) denominator; string ret = "";
string tmpStr = "";
int remain;
map<int,int> flag; // int 转 string
stringstream ss; //negative or not
if(num > && denominator < )
{
ret = "-";
den = ~(den-);
}
else if(num < && den > )
{
ret = "-";
num = ~(num-);
}
else if(num < && den < )
{
num = ~(num-);
den = ~(den-);
} //integer part
ss << num/den;
ss >> tmpStr;
ret += tmpStr;
remain = num%den;
if(remain == ) return ret; //fraction part
ret += ".";
while()
{
if(remain == ) return ret;
else if(flag.find(remain)!=flag.end())
{
ret.insert(flag[remain], , '(');
return ret + ")";
}
else
{
flag[remain] = ret.length();
num = remain * ;
remain = num%den;
ss.clear();
ss << num/den;
ss >> tmpStr;
ret += tmpStr;
}
}
}
};
Result: Wrong
Input: -1, -2147483648
Output: "0.000000000000000000000000000000-1"
Expected: "0.0000000004656612873077392578125"
5TH TRY
remain也要申请为long long int, 否则在num = remain * 10;会溢出
class Solution {
public:
string fractionToDecimal(int numerator, int denominator) {
long long int num = (long long int) numerator;
long long int den = (long long int) denominator; string ret = "";
string tmpStr = "";
long long int remain;
map<int,int> flag; // int 转 string
stringstream ss; //negative or not
if(num > && denominator < )
{
ret = "-";
den = ~(den-);
}
else if(num < && den > )
{
ret = "-";
num = ~(num-);
}
else if(num < && den < )
{
num = ~(num-);
den = ~(den-);
} //integer part
ss << num/den;
ss >> tmpStr;
ret += tmpStr;
remain = num%den;
if(remain == ) return ret; //fraction part
ret += ".";
while()
{
if(remain == ) return ret;
else if(flag.find(remain)!=flag.end())
{
ret.insert(flag[remain], , '(');
return ret + ")";
}
else
{
flag[remain] = ret.length();
num = remain * ;
remain = num%den;
ss.clear();
ss << num/den;
ss >> tmpStr;
ret += tmpStr;
}
}
}
};
Result: Accepted
最新文章
- Double Dispatch讲解与实例-面试题
- ListView只更新某个item
- Java面向对象练习
- linux下的服务器搭建集成环境
- SICP— 第一章 构造过程抽象
- opengl典型例程立方体投影与地图绘制
- 优之星S900平板电脑root方法
- stuff about set multiset map multimap
- full-background.js
- 问题:Excel在“xxx.xlsx”中发现不可读取的内容。是否恢复此工作薄的内容?【原创】
- Delphi访问活动目录
- UpdataData
- SQL:多表关联采取这一纪录迄今为止最大
- 关于Java中数组的常用操作方法
- npm install
- 关于 html input标签的几个常用操作
- 快速理解VirtualBox的四种网络连接方式
- Linux之清理linux内存cache
- Expm 1_1 实现基于分治法的归并排序算法.
- efcore从数据库快速生成实体及context
热门文章
- 【ASP.NET 问题】IIS发布网站后出现“检测到在集成的托管管道模式下不适用的ASP.NET设置”的解决办法
- Mysql 获取表属性
- hadoop报错:hdfs.DFSClient: Exception in createBlockOutputStream
- react-native android 和ios 集成 jpush-react-native 激光推送
- springboot 多环境选择
- Spring Cloud (6)A config 服务端配置 与github通信
- day08-MySQl创建用户和授权
- 分布式ID生成学习
- docker之container
- 剑指offer例题——二维数组中的查找