数学 - acgtyrant/Algorithm-and-Data-Structure GitHub Wiki
一开始分别写了两个用于进制转换的函数 binary2decimal, decimal2binary. 注意后者为了方便，直接构造一个字符串了。
class Solution {
public:
int binary2decimal(int binary_digit) {
int quotient = binary_digit / 10;
int remainder = binary_digit % 10;
int power = 0;
int decimal_digit = remainder * pow(2, power);
while (quotient != 0) {
++power;
remainder = quotient % 10;
decimal_digit += remainder * pow(2, power);
quotient = quotient / 10;
}
return decimal_digit;
}
string decimal2binary(int decimal_digit) {
string binary_digit_string;
int remainder = decimal_digit % 2;
binary_digit_string = to_string(remainder);
int quotient = decimal_digit / 2;
while (quotient != 0) {
remainder = quotient % 2;
binary_digit_string = to_string(remainder) + binary_digit_string;
quotient = quotient / 2;
}
return binary_digit_string;
}
string addBinary(string a, string b) {
int a_binary_digit = stoi(a);
int b_binary_digit = stoi(b);
int a_decimal_digit = binary2decimal(a_binary_digit);
int b_decimal_digit = binary2decimal(b_binary_digit);
int sum = a_decimal_digit + b_decimal_digit;
return decimal2binary(sum);
}
};然后在一次 test case 溢出了。
重写，直接处理字符串，留意好 carry_digit 即可，特别是最后的进位：
class Solution {
public:
string addBinary(string a, string b) {
auto a_iterator = a.rbegin();
auto b_iterator = b.rbegin();
string sum_string;
int a_digit;
int b_digit;
int carry_digit = 0;
int sum;
while (a_iterator != a.rend() || b_iterator != b.rend()) {
if (a_iterator != a.rbegin()) {
a_digit = *a_iterator - '0';
++a_iterator;
} else {
a_digit = 0;
}
if (b_iterator != b.rbegin()) {
b_digit = *b_iterator - '0';
++b_iterator;
} else {
b_digit = 0;
}
sum = a_digit + b_digit + carry_digit;
if (sum > 1) {
carry_digit = 1;
sum %= 2;
} else {
carry_digit = 0;
}
sum_string = to_string(sum) + sum_string;
}
if (carry_digit == 1) {
sum_string = "1" + sum_string;
}
return sum_string;
}
};播个小插曲，我曾一度脑子秀逗，把迭代器初始化成 rend() 并企图遍历到 rbegin(). 此外，这算法耗时 8ms, 落后于基于索引值的 4ms 代码，毕竟有太多的复制构造销毁析构开销。
曾试图用代数学分析，不过还是行不通，放弃解说了……
只好一路瞥 Hint 过去，看了那篇 wikipedia article, 如果你像我这么干，到时你就知道怎么解了：
int addDigits(int num) {
return 1 + (num - 1) % 9;
}顺便一提，Ｃ是怎么对负数取余的。那个公式挺有用，可以用在 C++ 的 % 运算符重载函数里。
不过耗时高达 8ms, 试了下有多重条件判断的题解，则耗时 4ms:
int addDigits(int num) {
if (num == 0) return 0;
if (num % 9 == 0) return 9;
return num % 9;
}可读性差点是了。
拼的就是可读性！Discuss 里大多题解惨不忍睹。
bool isUgly(int num) {
if (num == 0) return false;
while (num % 2 == 0) num /= 2;
while (num % 3 == 0) num /= 3;
while (num % 5 == 0) num /= 5;
return num == 1;
}我不喜欢这题，需要答题者自己揣摩考官的心意，就像高考那些鬼阅读题一样。而且这也违背了双方平起平坐签订契约的原则，比如我该不该为对方传的 "--1", "0xa", " 1 ", "00001", "1.1", 甚至"1e2" 擦屁股？再次，万一对方传了完全不合法的字符串，我又该如何返回值给他？
所以大家尽管看 requirements 并依样画葫芦。至于怎么判断有无溢出，简单，直接用 long 储存值并直接与最大 int 数 2147483647 比较即可；最后别忘了与表示正负的 sign 相乘。
int myAtoi(char* str) {
long integer = 0;
int sign = 1;
while (isspace(*str)) ++str;
if (*str == '-') {
sign = -1;
++str;
} else if (*str == '+') {
++str;
}
while (isdigit(*str)) {
integer = integer * 10 + (*str - '0');
if (integer > 2147483647) {
return sign == 1 ? 2147483647 : -2147483648;
}
++str;
}
return (int)(integer * sign);
}又一个要揣摩考官心思的题，比如 3 的根该四舍五入还是零舍全入？不做也罢。
别看那维基百科讲的，反而更复杂了。一言以蔽之：根据罗马数字与整数数字对应关系进行加法操作，如果前一个数字比后一个大就相减，否则进行相加。
class Solution {
public:
int romanToInt(string s) {
if (s.length() == 0) return 0;
map<char, int> roman_to_arabic;
roman_to_arabic['I'] = 1;
roman_to_arabic['V'] = 5;
roman_to_arabic['X'] = 10;
roman_to_arabic['L'] = 50;
roman_to_arabic['C'] = 100;
roman_to_arabic['D'] = 500;
roman_to_arabic['M'] = 1000;
int result = roman_to_arabic[s.back()];
auto iterator = s.rbegin();
auto next_iterator = iterator + 1;
while (next_iterator != s.rend()) {
if (roman_to_arabic[*next_iterator] >= roman_to_arabic[*iterator])
result += roman_to_arabic[*next_iterator];
if (roman_to_arabic[*next_iterator] < roman_to_arabic[*iterator])
result -= roman_to_arabic[*next_iterator];
++iterator; ++next_iterator;
}
return result;
}
};效率很差，大抵是因为用上了抽象高一层的 std::map 和反向迭代器吧。
直接上 std::string 和 std::reverse, 注意处理好 front() == '-' 的情况。
class Solution {
public:
int reverse(int x) {
int sign = 1;
string x_s = to_string(x);
auto iterator = x_s.begin();
if (*iterator == '-') {
sign = -1;
++iterator;
}
std::reverse(iterator, x_s.end());
x_s = string(iterator, x_s.end());
long x_l = stol(x_s) * sign;
if (x_l > INT_MAX || x_l < INT_MIN) return 0;
return static_cast<int>(x_l);
}
};比最快实现慢了 4ms.
非正数都不是 2 的幂，直接返回 false 即可。此外，2 的幂转换为二进制数字时，皆为一个开头为 1, 其后要么没有数字，要么全是零的数字，于是位运算就易如反掌。
bool isPowerOfTwo(int n) {
if (n <= 0) return false;
while ((n & 1) == 0) n >>= 1;
return n == 1;
}