Math
12. Integer to Roman
Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.
class Solution {
public:
string intToRoman(int num) {
vector<string> M = { "", "M", "MM", "MMM" };
vector<string> C = { "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" };
vector<string> X = { "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" };
vector<string> I = { "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" };
return M[num / 1000] + C[(num % 1000) / 100] + X[(num % 100) / 10] + I[num % 10];
}
};
13. Roman to Integer
Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.
class Solution {
public:
int romanToInt(string s) {
unordered_map<char, int> num_dict {{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}};
int len = s.size();
int res = 0;
int pre = 0;
while (len > 0) {
int num = num_dict[s[len-1]];
if (num < pre) res -= num;
else res += num;
pre = num;
--len;
}
return res;
}
};
31. Next Permutation
class Solution {
public:
void nextPermutation(vector<int>& nums) {
size_t len = nums.size();
int i = len - 1;
while (i > 0) {
if (nums[i] > nums[i-1]) {
int j = i;
while (j < len) {
if (nums[j] >nums[i-1]) ++j;
else break;
}
--j;
swap(nums[i-1], nums[j]);
reverse(nums.begin() + i, nums.end());
return;
}
--i;
}
reverse(nums.begin(), nums.end());
}
};
60. Permutation Sequence
The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3):
"123" "132" "213" "231" "312" "321"Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
class Solution {
public:
string getPermutation(int n, int k) {
vector<int> num(n);
string res;
long long accu_prod = 1;
for (size_t i = 1; i <= n; ++i) {
num[i-1] = i;
accu_prod *= i;
}
for(int i = 0, left = k - 1; i < n; ++i) {
accu_prod /= (n - i);
int index = left / accu_prod;
res += to_string(num[index]);
num.erase(num.begin() + index);
left -= index * accu_prod;
}
return res;
}
};
43. Multiply Strings
class Solution {
public:
string multiply(string num1, string num2) {
int len1 = num1.size();
int len2 = num2.size();
if (!len1 || !len2) return {};
string res(len1 + len2, '0');
int carry_in = 0;
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
for (int i = 0; i < len1; ++i) {
int j = 0;
for (; j < len2; ++j) {
int result = (num1[i] - '0') *(num2[j] - '0') + carry_in + (res[i + j] - '0');
res[i+j] = (result % 10) + '0';
carry_in = result / 10;
}
if (carry_in) res[i+j] += carry_in;
carry_in = 0;
}
reverse(res.begin(), res.end());
int i = 0;
for (; i < res.size(); ++i) {
if (res[i] != '0') break;
}
if (i == res.size()) i--;
res.erase(res.begin(), res.begin() + i);
return res;
}
};
67. Add Binary
Given two binary strings, return their sum (also a binary string).
For example, a = "11" b = "1" Return "100".
class Solution {
public:
string addBinary(string a, string b) {
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
string res;
int len1 = 0, len2 = 0;
int carry_in = 0;
while (len1<a.size() || len2 < b.size()) {
int sum = carry_in;
if (len1 < a.size()) sum += a[len1++] - '0';
if (len2 < b.size()) sum += b[len2++] - '0';
res += ((sum%2) + '0');
carry_in = sum / 2;
}
if (carry_in) res += "1";
reverse(res.begin(), res.end());
return res;
}
};
149. Max Points on a Line
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
class Solution {
public:
int maxPoints(vector<Point>& points) {
size_t len = points.size();
if (len <= 1) return len;
int max_num = 0;
int same = 0;
int vertical = 0;
int cur_max = 0;
for (size_t i = 0; i < len; ++i) {
unordered_map<long long, int> line_cnt;
same = 0;
vertical = 0;
for (size_t j= 0; j < len; ++j) {
if (i == j) continue;
if (points[i].x == points[j].x) {
if (points[i].y == points[j].y) same++;
else vertical++;
} else {
int dx = (points[i].x - points[j].x);
int dy = (points[i].y - points[j].y);
int divider = gcd(dx, dy);
if (divider == 0) line_cnt[divider]++;
else {
dx /= divider;
dy /= divider;
long long dxdy = dx + (static_cast<long long>(dy)<<32);
line_cnt[dxdy]++;
}
}
}
cur_max = 0;
for (auto kv : line_cnt) {
cur_max = max(cur_max, kv.second + same);
}
cur_max = max(vertical + same, cur_max) + 1;
max_num = max(cur_max, max_num);
}
return max_num;
}
private:
int gcd(int num1, int num2) {
while (num2) {
int temp = num2;
num2 = num1 % num2;
num1 = temp;
}
return num1;
}
// int gcd(int a, int b) {
// if (!b) return a;
// return (b, a % b);
// }
};
238. Product of Array Except Self
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> res(nums.size());
if (nums.size() <= 1) return res;
res[0] = 1;
for (size_t i = 1; i < nums.size(); ++i) {
res[i] = res[i - 1]*nums[i - 1];
}
int right_part = 1;
for (int i = nums.size() - 1; i >= 0; --i) {
res[i] *= right_part;
right_part *= nums[i];
}
return res;
}
};
254 Factor Combinations
Numbers can be regarded as product of its factors. For example,
8 = 2 x 2 x 2; = 2 x 4. Write a function that takes an integer n and return all possible combinations of its factors.
Note: Each combination's factors must be sorted ascending, for example: The factors of 2 and 6 is [2, 6], not [6, 2].
You may assume that n is always positive. Factors should be greater than 1 and less than n.
Examples: input: 1 output: []
input: 37 output: [] input: 12 output: [ [2, 6], [2, 2, 3], [3, 4] ] input: 32 output: [ [2, 16], [2, 2, 8], [2, 2, 2, 4], [2, 2, 2, 2, 2], [2, 4, 4], [4, 8] ]
class Solution_v2 {
public:
vector<vector<int>> getFactors(int n) {
dfs(n);
return ret;
}
void dfs(int n) {
int i = v.empty()? 2 : v.back();
for (; i <= n/i; i++) {
if (n % i == 0) {
v.push_back(i);
v.push_back(n/i);
ret.push_back(v);
v.pop_back();
dfs(n/i);
v.pop_back();
}
}
}
private:
vector<int> v;
vector<vector<int>> ret;
};
class Solution_v3 {
public:
vector<vector<int>> getFactors(int n) {
vector<vector<int>> res;
vector<int> slu;
function<void(int, int)> dfs = [&](int start, int num) {
if (num <= 1) {
if (slu.size() > 1) res.push_back(slu);
return;
}
for (int i = start; i <= num; ++i) {
if (num % i == 0) {
slu.push_back(i);
dfs(i, num/i);
slu.pop_back();
}
}
};
dfs(2, n);
return res;
}
};
258. Add Digits
Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.
For example:
Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.
Follow up: Could you do it without any loop/recursion in O(1) runtime?
class Solution {
public:
int addDigits(int num) {
if (num < 10) return num;
return (num - 10)%9 + 1;
}
};
263. Ugly Number
Write a program to check whether a given number is an ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.
Note that 1 is typically treated as an ugly number.
class Solution {
public:
bool isUgly(int num) {
if (num <= 0) return false;
while(num%30 == 0) num /= 30;
while(num%15 == 0) num /= 15;
while(num%6 == 0) num /= 6;
while(num%5 == 0) num /= 5;
while(num%3 == 0) num /= 3;
while(num%2 == 0) num /= 2;
return (num == 1);
}
};
264. Ugly Number II
Write a program to find the n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
Note that 1 is typically treated as an ugly number.
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> dp(n);
int next2 = 1, next3 = 1, next5 = 1, next = 1;
int index2 = 0, index3 = 0, index5 = 0;
for (int i = 0; i < n; ++i) {
next = min(next2, min(next3, next5));
dp[i] = next;
if (next == next2) {
next2 = dp[index2++] * 2;
}
if (next == next3) {
next3 = dp[index3++] * 3;
}
if (next == next5) {
next5 = dp[index5++] * 5;
}
}
return dp[n-1];
}
};
313. Super Ugly Number
Write a program to find the nth super ugly number.
Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.
Note: (1) 1 is a super ugly number for any given primes. (2) The given numbers in primes are in ascending order. (3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
using pair_t = pair<int, pair<int, int>>;
priority_queue<pair_t, vector<pair_t>, greater<pair_t>> pq;
vector<int> num(n);
num[0] = 1;
for (size_t i = 0; i < primes.size(); ++i) {
pq.push({primes[i], {0, primes[i]}});
}
for (int i = 1; i < n; ++i) {
auto cur = pq.top();
num[i] = cur.first;
while (!pq.empty() && pq.top().first == num[i]) {
auto next = pq.top(); pq.pop();
pq.push({next.second.second * num[++next.second.first], {next.second.first, next.second.second}});
}
}
return num[n-1];
}
};
273. Integer to English Words
Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.
For example, 123 -> "One Hundred Twenty Three" 12345 -> "Twelve Thousand Three Hundred Forty Five" 1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"
class Solution {
public:
string numberToWords(int num) {
unordered_map<int, string> num_to_word {
{0, "Zero"},
{1, "One"},
{2, "Two"},
{3, "Three"},
{4, "Four"},
{5, "Five"},
{6, "Six"},
{7, "Seven"},
{8, "Eight"},
{9, "Nine"},
{10, "Ten"},
{11, "Eleven"},
{12, "Twelve"},
{13, "Thirteen"},
{14, "Fourteen"},
{15, "Fifteen"},
{16, "Sixteen"},
{17, "Seventeen"},
{18, "Eighteen"},
{19, "Nineteen"},
{20, "Twenty"},
{30, "Thirty"},
{40, "Forty"},
{50, "Fifty"},
{60, "Sixty"},
{70, "Seventy"},
{80, "Eighty"},
{90, "Ninety"},
};
vector<string> words{"", "Thousand", "Million", "Billion"};
if (num_to_word.find(num) != num_to_word.end()) return num_to_word[num];
int index = 0;
string res = "";
while (num) {
string cur;
if (num % 1000) {
int threedigits = num % 1000;
cur += threeDightsToWords(threedigits, num_to_word);
if (index)
cur += " " + words[index];
}
// if (cur != "") cur += " ";
if (res != "" && cur != "") cur += " ";
res = cur + res;
num = num / 1000;
index++;
}
return res;
}
string threeDightsToWords(int num, unordered_map<int, string>& num_to_word) {
string res;
// cout << " output " << num << endl;
if (num < 0 || num > 999) return res;
if (num_to_word.find(num) != num_to_word.end()) return num_to_word[num];
if (num / 100) {
res += num_to_word[num / 100] + " " + "Hundred";
num %= 100;
}
if (num / 10) {
if (res != "") res += " ";
if (num_to_word.find(num) != num_to_word.end()) {
res += num_to_word[num];
return res;
} else {
res += num_to_word[num - num % 10];
}
num %= 10;
}
if (num) {
if (res != "") res += " ";
res += num_to_word[num];
}
return res;
}
};
321. Create Maximum Number
Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize your time and space complexity.
Example 1:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
return [9, 8, 6, 5, 3]Example 2:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
return [6, 7, 6, 0, 4]Example 3:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
return [9, 8, 9]
class Solution {
public:
vector<int> max_vector(vector<int> n, size_t k) {
while(n.size() > k) {
size_t i = 0;
size_t l = n.size();
for (i = 0; i < l -1; ++i) {
if (n[i] < n[i+1]) {
n.erase(n.begin() + i);
break;
}
}
if (i == l -1) n.erase(n.begin() + i);
}
return n;
}
bool compare(vector<int> &n1, size_t i, vector<int>& n2, size_t j) {
while(i < n1.size() && j < n2.size() && n1[i] == n2[j]) {
++i;
++j;
}
if (j == n2.size()) return true;
if (i < n1.size() && n1[i] > n2[j]) return true;
return false;
}
vector<int> merge(vector<int>& n1, vector<int>& n2, size_t k) {
vector<int> res(k, 0);
for (size_t i = 0, j = 0, r = 0; r < k; ++r) {
res[r] = compare(n1, i, n2, j) ? n1[i++] : n2[j++];
}
return res;
}
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
int m = int(nums1.size());
int n = int(nums2.size());
vector<int> ret(k, 0);
for (int i = max(0, k - n); i <= min(k, m); ++i) {
auto v1 = max_vector(nums1, i);
auto v2 = max_vector(nums2, k-i);
auto tmp = merge(v1, v2, k);
if (compare(tmp, 0, ret, 0)) ret = tmp;
}
return ret;
}
};
343. Integer Break
Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.
For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).
Note: you may assume that n is not less than 2.
class Solution {
public:
int integerBreak(int n) {
if (n < 2) return 0;
if (n == 2) return 1;
if (n == 3) return 2;
if (n == 4) return 4;
int res = 1;
while (n > 4) {
n -= 3;
res *= 3;
}
if (n) res *= n;
return res;
}
};
Get Part of Digits From a Power Result
string get_pow_digits(int m, int n, int k) {
if(k == 0 || m > 10 || n < 0) return "";
string ret(k,'0');
ret.back() = '1';
auto multiply = [](string& num1, int num2) {
if(num1.empty()) num1 = to_string(num2);
int carry = 0;
for(int i = (int)num1.size()-1; i >= 0; --i) {
int val = (num1[i] - '0') * num2 + carry;
num1[i] = (val % 10) + '0';
carry = val / 10;
}
};
for(int i = 1; i <= n; ++i) multiply(ret, m);
return ret;
}