目录
7. 整数反转
9. 回文数
12. 整数转罗马数字
13. 罗马数字转整数
29. 两数相除
7. 整数反转
给你一个 32 位的有符号整数 x
,返回将 x
中的数字部分反转后的结果。
-如果反转后整数超过 32 位的有符号整数的范围 [2^31, 2^31 -1]
,就返回 0。
假设环境不允许存储 64 位整数(有符号或无符号)。
示例 1:
输入:x = 123 输出:321
示例 2:
输入:x = -123 输出:-321
示例 3:
输入:x = 120 输出:21
示例 4:
输入:x = 0 输出:0
提示:
-2^31 <= x <= 2^31 - 1
解法1:
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
int reverse(int x)
{
int MAX = 0x7fffffff;
int MIN = 1 << 31;
ostringstream stream, smax, smin;
string ss;
stream << x;
ss += stream.str();
smax << MAX;
string max_num = smax.str();
smin << MIN;
string min_num = smin.str();
std::reverse(ss.begin(), ss.end());
if (x < 0)
{
ss.insert(0, "-");
ss.pop_back();
}
if (x > 0 && ss.size() >= max_num.size() && (ss > max_num))
return 0;
else if (x < 0 && ss.size() >= min_num.size() && ss > min_num)
return 0;
else
return atoi(ss.c_str());
}
};
int main()
{
Solution s;
vector<int> nums = {123,-123,120,0};
for(auto num:nums)
cout << s.reverse(num) << endl;
return 0;
}
解法2:
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
#define INT_MAX 2147483647
#define INT_MIN (-INT_MAX - 1)
int reverse(int x)
{
int flag = x < 0 ? -1 : 1;
int num = 0;
while (x)
{
if ((flag == -1 && (INT_MIN / 10 > num)) || (flag == 1 && INT_MAX / 10 < num))
return 0;
num = num * 10 + x % 10;
x /= 10;
}
return num;
}
};
int main()
{
Solution s;
vector<int> nums = {123,-123,120,0};
for(auto num:nums)
cout << s.reverse(num) << endl;
return 0;
}
解法3:
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
int reverse(int x)
{
int rev = 0;
while (x != 0)
{
int pop = x % 10;
x = x / 10;
if (rev > INT_MAX / 10 || (rev == INT_MAX / 10 && pop > 7))
return 0;
if (rev < INT_MIN / 10 || (rev == INT_MIN / 10 && pop < -8))
return 0;
rev = rev * 10 + pop;
}
return rev;
}
};
int main()
{
Solution s;
vector<int> nums = {123,-123,120,0};
for(auto num:nums)
cout << s.reverse(num) << endl;
return 0;
}
9. 回文数
给你一个整数 x
,如果 x
是一个回文整数,返回 true
;否则,返回 false
。
回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。例如,121
是回文,而 123
不是。
示例 1:
输入:x = 121 输出:true
示例 2:
输入:x = -121 输出:false 解释:从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入:x = 10 输出:false 解释:从右向左读, 为 01 。因此它不是一个回文数。
示例 4:
输入:x = -101 输出:false
提示:
-2^31 <= x <= 2^31 - 1
进阶:你能不将整数转为字符串来解决这个问题吗?
解法1:
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
bool isPalindrome(long int x)
{
long int rev;
if (x < 0)
return false;
string str_x = to_string(x);
std::reverse(str_x.begin(), str_x.end());
stringstream out(str_x);
out >> rev;
return x == rev;
}
};
int main()
{
Solution s;
vector<int> nums = {121,-121,10,-101};
for(auto num:nums)
cout << s.isPalindrome(num) << endl;
return 0;
}
解法2:
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
bool isPalindrome(long int x)
{
long int midrev = 0;
if (x < 0 || (x % 10 == 0 && x != 0))
return false;
while (x > midrev)
{
midrev = midrev * 10 + x % 10;
x /= 10;
}
return midrev == x || midrev / 10 == x;
}
};
int main()
{
Solution s;
vector<int> nums = {121,-121,10,-101};
for(auto num:nums)
cout << s.isPalindrome(num) << endl;
return 0;
}
解法3:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isPalindrome(long int x) {
if (x < 0) return false;
long int sum = 0, t = x;
while(x)
{
sum = sum * 10 + x % 10;
x /= 10;
}
return t == sum;
}
};
int main()
{
Solution s;
vector<int> nums = {121,-121,10,-101};
for(auto num:nums)
cout << s.isPalindrome(num) << endl;
return 0;
}
12. 整数转罗马数字
罗马数字包含以下七种字符: I
, V
, X
, L
,C
,D
和 M
。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如, 罗马数字 2 写做 II
,即为两个并列的 1。12 写做 XII
,即为 X
+ II
。 27 写做 XXVII
, 即为 XX
+ V
+ II
。
通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII
,而是 IV
。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX
。这个特殊的规则只适用于以下六种情况:
-
I
可以放在V
(5) 和X
(10) 的左边,来表示 4 和 9。 -
X
可以放在L
(50) 和C
(100) 的左边,来表示 40 和 90。 -
C
可以放在D
(500) 和M
(1000) 的左边,来表示 400 和 900。
给你一个整数,将其转为罗马数字。
示例 1:
输入: num = 3 输出: "III"
示例 2:
输入: num = 4 输出: "IV"
示例 3:
输入: num = 9 输出: "IX"
示例 4:
输入: num = 58 输出: "LVIII" 解释: L = 50, V = 5, III = 3.
示例 5:
输入: num = 1994 输出: "MCMXCIV" 解释: M = 1000, CM = 900, XC = 90, IV = 4.
提示:
1 <= num <= 3999
解法1:
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
string getNum1000(int num1000)
{
if (num1000 == 3)
{
return "MMM";
}
else if (num1000 == 2)
{
return "MM";
}
else if (num1000 == 1)
{
return "M";
}
else
{
return "";
}
}
string getNum100(int num100)
{
switch (num100)
{
case 1:
return "C";
case 2:
return "CC";
case 3:
return "CCC";
case 4:
return "CD";
case 5:
return "D";
case 6:
return "DC";
case 7:
return "DCC";
case 8:
return "DCCC";
case 9:
return "CM";
default:
return "";
}
}
string getNum10(int num10)
{
switch (num10)
{
case 1:
return "X";
case 2:
return "XX";
case 3:
return "XXX";
case 4:
return "XL";
case 5:
return "L";
case 6:
return "LX";
case 7:
return "LXX";
case 8:
return "LXXX";
case 9:
return "XC";
default:
return "";
}
}
string getNum1(int num1)
{
switch (num1)
{
case 1:
return "I";
case 2:
return "II";
case 3:
return "III";
case 4:
return "IV";
case 5:
return "V";
case 6:
return "VI";
case 7:
return "VII";
case 8:
return "VIII";
case 9:
return "IX";
default:
return "";
}
}
string intToRoman(int num)
{
int num1000 = num / 1000;
int num100 = (num % 1000) / 100;
int num10 = (num % 100) / 10;
int num1 = (num % 10);
string res;
res = getNum1000(num1000) + getNum100(num100) + getNum10(num10) + getNum1(num1);
return res;
}
};
int main()
{
Solution s;
vector<int> nums = {3,4,9,58,1994};
for(auto num:nums)
cout << s.intToRoman(num) << endl;
return 0;
}
解法2:
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
string intToRoman(int num)
{
int values[13] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
string reps[13] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
string res;
for (int i = 0; i < 13; i++)
{
while (num >= values[i])
{
num -= values[i];
res += reps[i];
}
}
return res;
}
};
int main()
{
Solution s;
vector<int> nums = {3,4,9,58,1994};
for(auto num:nums)
cout << s.intToRoman(num) << endl;
return 0;
}
解法3:
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
string intToRoman(int num)
{
string bit1[10] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
string bit10[10] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
string bit100[10] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
string bit1000[4] = {"", "M", "MM", "MMM"};
return bit1000[num / 1000] + bit100[num % 1000 / 100] + bit10[num % 100 / 10] + bit1[num % 10];
}
};
int main()
{
Solution s;
vector<int> nums = {3,4,9,58,1994};
for(auto num:nums)
cout << s.intToRoman(num) << endl;
return 0;
}
13. 罗马数字转整数
罗马数字包含以下七种字符: I
, V
, X
, L
,C
,D
和 M
。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如, 罗马数字 2 写做 II
,即为两个并列的 1。12 写做 XII
,即为 X
+ II
。 27 写做 XXVII
, 即为 XX
+ V
+ II
。
通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII
,而是 IV
。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX
。这个特殊的规则只适用于以下六种情况:
-
I
可以放在V
(5) 和X
(10) 的左边,来表示 4 和 9。 -
X
可以放在L
(50) 和C
(100) 的左边,来表示 40 和 90。 -
C
可以放在D
(500) 和M
(1000) 的左边,来表示 400 和 900。
给你一个整数,将其转为罗马数字。
示例 1:
输入: num = 3 输出: "III"
示例 2:
输入: num = 4 输出: "IV"
示例 3:
输入: num = 9 输出: "IX"
示例 4:
输入: num = 58 输出: "LVIII" 解释: L = 50, V = 5, III = 3.
示例 5:
输入: num = 1994 输出: "MCMXCIV" 解释: M = 1000, CM = 900, XC = 90, IV = 4.
提示:
1 <= num <= 3999
解法1:
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
int romanToInt(string s)
{
int sum = 0;
for (int i = 1; i <= s.size(); i++)
{
if (s[i - 1] == 'I' && s[i] == 'V')
{
sum += 4;
i++;
}
else if (s[i - 1] == 'I' && s[i] == 'X')
{
sum += 9;
i++;
}
else if (s[i - 1] == 'X' && s[i] == 'L')
{
sum += 40;
i++;
}
else if (s[i - 1] == 'X' && s[i] == 'C')
{
sum += 90;
i++;
}
else if (s[i - 1] == 'C' && s[i] == 'D')
{
sum += 400;
i++;
}
else if (s[i - 1] == 'C' && s[i] == 'M')
{
sum += 900;
i++;
}
else if (s[i - 1] == 'I')
{
sum += 1;
}
else if (s[i - 1] == 'V')
{
sum += 5;
}
else if (s[i - 1] == 'X')
{
sum += 10;
}
else if (s[i - 1] == 'L')
{
sum += 50;
}
else if (s[i - 1] == 'C')
{
sum += 100;
}
else if (s[i - 1] == 'D')
{
sum += 500;
}
else if (s[i - 1] == 'M')
{
sum += 1000;
}
}
return sum;
}
};
int main()
{
Solution s;
vector<string> roma = {"III","IV","IX","LVIII","MCMXCIV"};
for (auto r:roma)
cout << s.romanToInt(r) << endl;
return 0;
}
解法2:
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
int romanToInt(string s)
{
int result = 0;
int n = s.length();
for (int i = 0; i < n; i++)
{
switch (s[i])
{
case 'I':
if (i < n - 1 && s[i + 1] == 'V')
{
result += 4;
i++;
}
else if (i < n - 1 && s[i + 1] == 'X')
{
result += 9;
i++;
}
else
result++;
break;
case 'V':
result += 5;
break;
case 'X':
if (i < n - 1 && s[i + 1] == 'L')
{
result += 40;
i++;
}
else if (i < n - 1 && s[i + 1] == 'C')
{
result += 90;
i++;
}
else
result += 10;
break;
case 'L':
result += 50;
break;
case 'C':
if (i < n - 1 && s[i + 1] == 'D')
{
result += 400;
i++;
}
else if (i < n - 1 && s[i + 1] == 'M')
{
result += 900;
i++;
}
else
result += 100;
break;
case 'D':
result += 500;
break;
case 'M':
result += 1000;
}
}
return result;
}
};
int main()
{
Solution s;
vector<string> roma = {"III","IV","IX","LVIII","MCMXCIV"};
for (auto r:roma)
cout << s.romanToInt(r) << endl;
return 0;
}
解法3:
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
int romanToInt(string s)
{
int result = 0;
map<char, int> luomab;
luomab.insert(map<char, int>::value_type('I', 1));
luomab.insert(map<char, int>::value_type('V', 5));
luomab.insert(map<char, int>::value_type('X', 10));
luomab.insert(map<char, int>::value_type('L', 50));
luomab.insert(map<char, int>::value_type('C', 100));
luomab.insert(map<char, int>::value_type('D', 500));
luomab.insert(map<char, int>::value_type('M', 1000));
for (int i = 0; i < s.length(); i++)
{
if (luomab[s[i]] >= luomab[s[i + 1]])
result += luomab[s[i]];
else
{
result += (luomab[s[i + 1]] - luomab[s[i]]);
i++;
}
}
return result;
}
};
int main()
{
Solution s;
vector<string> roma = {"III","IV","IX","LVIII","MCMXCIV"};
for (auto r:roma)
cout << s.romanToInt(r) << endl;
return 0;
}
29. 两数相除
给定两个整数,被除数 dividend
和除数 divisor
。将两数相除,要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend
除以除数 divisor
得到的商。
整数除法的结果应当截去(truncate
)其小数部分,例如:truncate(8.345) = 8
以及 truncate(-2.7335) = -2
示例 1:
输入: dividend = 10, divisor = 3 输出: 3 解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
示例 2:
输入: dividend = 7, divisor = -3 输出: -2 解释: 7/-3 = truncate(-2.33333..) = -2
提示:
- 被除数和除数均为 32 位有符号整数。
- 除数不为 0。
- 假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−2^31, 2^31 − 1]。本题中,如果除法结果溢出,则返回 2^31 − 1。
解法1:
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
int divide(int dividend, int divisor)
{
int INI_MIN = -2147483648, INI_MAX = 2147483647;
if (dividend == divisor)
return 1;
if (divisor == 1)
return dividend;
if (dividend == INI_MIN && divisor == -1)
return INI_MAX;
if (divisor == INI_MIN)
{
if (dividend == INI_MIN)
return 1;
else
return 0;
}
bool sign = false;
if (dividend > 0 && divisor > 0 || dividend < 0 && divisor < 0)
{
sign = true;
}
int result_1 = 0;
if (dividend == INI_MIN)
{
if (divisor > 0)
dividend = dividend + divisor;
else
dividend = dividend - divisor;
result_1++;
}
dividend = abs(dividend);
divisor = abs(divisor);
while (dividend >= divisor)
{
unsigned int temp = divisor, res = 1;
while (dividend >= (temp << 1))
{
res <<= 1;
temp <<= 1;
}
result_1 += res;
dividend -= temp;
}
if (sign == true)
{
return result_1;
}
else
{
return -result_1;
}
}
};
int main()
{
Solution s;
cout << s.divide(10, 3) << endl;
cout << s.divide(7, -3) << endl;
return 0;
}
解法2:
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
int divide(int dividend, int divisor)
{
int signal = 1;
unsigned int dvd = dividend;
if (dividend < 0)
{
signal *= -1;
dvd = ~dvd + 1;
}
unsigned int dvs = divisor;
if (divisor < 0)
{
signal *= -1;
dvs = ~dvs + 1;
}
int shift = 0;
while (dvd > dvs << shift)
{
shift++;
}
unsigned int res = 0;
while (dvd >= dvs)
{
while (dvd < dvs << shift)
{
shift--;
}
res |= (unsigned int)1 << shift;
dvd -= dvs << shift;
}
if (signal == 1 && res >= INT_MAX)
{
return INT_MAX;
}
else
{
return res * signal;
}
}
};
int main()
{
Solution s;
cout << s.divide(10, 3) << endl;
cout << s.divide(7, -3) << endl;
return 0;
}
解法3: 文章来源:https://www.toymoban.com/news/detail-561623.html
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
int divide(int dividend, int divisor)
{
if (dividend == INT_MIN && divisor == -1)
return INT_MAX;
if (dividend == 0)
return 0;
int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
long x = (dividend < 0) ? -(long)dividend : (long)dividend;
long y = (divisor < 0) ? -(long)divisor : (long)divisor;
long result = 0;
while (x >= y)
{
long temp = y, mid = 1;
while (x >= (temp << 1))
{
mid <<= 1;
temp <<= 1;
}
result += mid;
x -= temp;
}
return sign > 0 ? result : -result;
}
};
int main()
{
Solution s;
cout << s.divide(10, 3) << endl;
cout << s.divide(7, -3) << endl;
return 0;
}
完文章来源地址https://www.toymoban.com/news/detail-561623.html
到了这里,关于力扣C++|一题多解之数学题专场(1)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!