2. Add Two Numbers https://leetcode.com/problems/add-two-numbers/description/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode result(-);
ListNode* current = &result;
int add = ;
while(l1!=NULL || l2!=NULL){
int val1 = ;
int val2 = ;
if(l1!=NULL){
val1 = l1->val;
l1 = l1->next;
}
if(l2!=NULL){
val2 = l2->val;
l2 = l2->next;
}
current->next = new ListNode((val1+val2+add)%);
add = (val1+val2+add)/;
current = current->next;
}
if(add == )
current->next = new ListNode();
return result.next;
}
};
7. Reverse Integer https://leetcode.com/problems/reverse-integer/description/
class Solution {
public:
int reverse(int x) {
int res = ;
while(x!=){
if(res>INT_MAX/||res<INT_MIN/){
return ;
}
res = res* + x%;
x = x/;
}
return res;
}
};
8. String to Integer (atoi) https://leetcode.com/problems/string-to-integer-atoi/description/
class Solution {
public:
int myAtoi(string str) {
long result = ;
int indicator = ;
for(int i = ; i<str.size();)
{
i = str.find_first_not_of(' ');
if(str[i] == '-' || str[i] == '+')
indicator = (str[i++] == '-')? - : ;
while(''<= str[i] && str[i] <= '')
{
result = result* + (str[i++]-'');
if(result*indicator >= INT_MAX) return INT_MAX;
if(result*indicator <= INT_MIN) return INT_MIN;
}
return result*indicator;
}
return ;
}
};
学习怎么将代码写得优雅
9. Palindrome Number https://leetcode.com/problems/palindrome-number/description/
class Solution {
public:
bool isPalindrome(int x) {
if(x<|| (x!= &&x%==)) return false;
int sum=;
while(x>sum)
{
sum = sum*+x%;
x = x/;
}
return (x==sum)||(x==sum/);
}
};
bool isPalindrome(int x) {
if(x<)
return false;
int y = x,z=;
while(y){
z*=;
z+=(y%);
y=y/;
}
if(x==z)
return true;
return false;
}
优化方法、倒置整个数或是只倒置一半
12. Integer to Roman https://leetcode.com/problems/integer-to-roman/description/
class Solution {
public:
string intToRoman(int num) {
string M[] = {"", "M", "MM", "MMM"};
string C[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
string X[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
string I[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
return M[num/] + C[(num%)/] + X[(num%)/] + I[num%];
}
};
13. Roman to Integer https://leetcode.com/problems/roman-to-integer/description/
class Solution {
public:
int romanToInt(string s) {
map<char,int> m = {{'I',},{'V',},{'X',},{'L',},{'C',},{'D',},{'M',}};
int result = ;
int i=;
for(;i<s.size()-;i++){
if(m[s[i]]<m[s[i+]]){
result = result + m[s[i+]] - m[s[i]];
i = i+;
}else{
result = result + m[s[i]];
}
}
if(i == s.size()-)
result = result+m[s[i]];
return result;
}
};
29. Divide Two Integers https://leetcode.com/problems/divide-two-integers/description/
class Solution {
public:
int divide(int dividend, int divisor) {
long long m = abs((long long)dividend), n = abs((long long)divisor), res = ;
int sign = ((dividend < ) ^ (divisor < )) ? - : ;
while (m >= n) {
long long t = n, p = ;
while (m >= (t << )) {
p <<= ;
t <<= ;
}
res += p;
m -= t;
}
if (res == (long long)INT_MAX+ && sign==) return INT_MAX;
return sign > ? res : -res;
}
};
如果是INT_MIN除以-1，则会溢出，必须返回INT_MAX
学习一下代码的简洁写法
43. Multiply Strings https://leetcode.com/problems/multiply-strings/description/
class Solution {
public:
string mul(string s, char c) {
int add = ;
for (int i = s.size() - ; i >= ; i--) {
int r = ((s[i] - '')*(c - '') + add) % ;
add = ((s[i] - '')*(c - '') + add) / ;
s[i] = r + '';
}
if (add != )
s.insert(s.begin(), add + '');
return s;
}
string add(string num1, string num2) {
string result = "";
int pos1 = num1.size() - ;
int pos2 = num2.size() - ;
int add = ;
while (pos1 >= || pos2 >= ) {
int n1 = ;
int n2 = ;
if (pos1 >= ) {
n1 = num1[pos1--]-'';
}
if (pos2 >= ) {
n2 = num2[pos2--]-'';
}
int r = (n1 + n2 + add) % ;
add = (n1 + n2 + add) / ;
result.insert(result.begin(),r+'');
}
if(add!=)
result.insert(result.begin(), add + '');
return result;
}
string multiply(string num1, string num2) {
string result = "";
for (int i = ; i < num2.size(); i++) {
result = add(result,mul(num1, num2[i]));
result.insert(result.end(), '');
}
result.erase(result.end()-);
int pos = ;
while(pos<result.size()&&result[pos]==''){
pos++;
}
result.erase(result.begin(),result.begin()+pos);
if(result == "")
return "";
return result;
}
};
50. Pow(x, n) https://leetcode.com/problems/powx-n/description/
class Solution {
public:
double myPow(double x, int n) {
if(n==) return ;
if(n==) return x;
if(n==-) return 1.0/x;
double tmp = myPow(x, n/);
if(n%==) {
return tmp*tmp;
}
if(n>) {
return tmp*tmp*x;
}
return tmp*tmp/x;
}
};
60. Permutation Sequence https://leetcode.com/problems/permutation-sequence/description/
class Solution {
public:
int getn(int n) {
int result = ;
for (int i = ; i <= n; ++i)
result = result * i;
return result;
}
string getPermutation(int n, int k) {
--k;
map<int, int> m = { {,},{,},{,},{,},{,},{,},{,},{,},{,} };
string result = "";
for (int i = ; i <= n; ++i) {
int pos;
//除的方式到最后两项就不成立了,当剩余两项的时候，直接赋值
if (n - i > )
pos = k / (getn(n - i)) + ;
else if (n - i == )
pos = k + ;
else if (n - i == )
pos = ;
int j = ;
//寻找第pos个数，如果遇到map中第二个数为0，则表示该数已经被用过了
for (; j < pos; ++j) {
if (m[j+] == )
++pos;
}
result += to_string(j);
m[j] = ;
if(n - i > )
k = k % getn(n - i);
}
return result;
}
};
66. Plus One https://leetcode.com/problems/plus-one/description/
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int i=digits.size()-;
for(;i>=;i--){
if(digits[i] == ){
digits[i] = ;
}else{
digits[i] = digits[i]+;
break;
}
}
if(i == -)
digits.insert(digits.begin(),);
return digits;
}
};
67. Add Binary https://leetcode.com/problems/add-binary/description/
class Solution {
public:
string addBinary(string a, string b) {
string ret = "";
int carry = ;
for (int i = a.size() - , j = b.size() - ; i >= || j >= ; i--, j--) {
int m = (i >= && a[i] == '');
int n = (j >= && b[j] == '');
ret = to_string((m + n + carry) & 0x1) + ret;
carry = (m + n + carry) >> ;
}
return carry ? '' + ret : ret;
}
};
69. Sqrt(x) https://leetcode.com/problems/sqrtx/description/
class Solution {
public:
int mySqrt(int x) {
long long pos1 = ;
long long pos2 = x;
long long result = x;
while(pos1<pos2){
long long middle = (pos1+pos2)/+;
if(middle*middle == result)
return middle;
else if(middle*middle < result){
pos1 = middle;
}else{
pos2 = middle-;
}
}
return pos1;
}
};
166. Fraction to Recurring Decimal https://leetcode.com/problems/fraction-to-recurring-decimal/description/
class Solution {
public:
string fractionToDecimal(int numerator, int denominator) {
if (!numerator) return "";
string res;
if (numerator < ^ denominator < ) res += '-';
long numer = numerator < ? (long)numerator * (-) : (long)numerator;
long denom = denominator < ? (long)denominator * (-) : (long)denominator;
long integral = numer / denom;
res += to_string(integral);
long rmd = numer % denom;
if (!rmd) return res;
res += '.';
rmd *= ;
unordered_map<long, long> mp;
while (rmd) {
long quotient = rmd / denom;
if (mp.find(rmd) != mp.end()) {
res.insert(mp[rmd], , '(');
res += ')';
break;
}
mp[rmd] = res.size();
res += to_string(quotient);
rmd = (rmd % denom) * ;
}
return res;
}
};
168. Excel Sheet Column Title https://leetcode.com/problems/excel-sheet-column-title/description/
class Solution {
public:
string convertToTitle(int n) {
string res;
char tmp;
while (n) {
n -= ;
tmp = 'A' + n % ;
res = tmp + res;
n /= ;
}
return res;
}
};
171. Excel Sheet Column Number https://leetcode.com/problems/excel-sheet-column-number/description/
class Solution {
public:
int titleToNumber(string s) {
int result = ;
int times = ;
for (int i = s.size() - ; i >= ; i--) {
result = result + (s[i] - 'A' + )*pow(, times++);
}
return result;
}
};
172. Factorial Trailing Zeroes https://leetcode.com/problems/factorial-trailing-zeroes/description/
class Solution {
public:
int trailingZeroes(int n) {
int result = ;
for (long long t = ; t <= n; t= t*) {
result += n / t;
}
return result;
}
};
204. Count Primes https://leetcode.com/problems/count-primes/description/
class Solution {
public:
int countPrimes(int n) {
bool* isPrime = new bool[n];
for(int i = ; i < n; i++){
isPrime[i] = true;
}
for(int i = ; i*i < n; i++){
if (!isPrime[i])
continue;
for(int j = i * i; j < n; j += i){
isPrime[j] = false;
}
}
int count = ;
for (int i = ; i < n; i++) {
if (isPrime[i]) count++;
}
return count;
}
};
223. Rectangle Area https://leetcode.com/problems/rectangle-area/description/
class Solution {
public:
int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
int area1 = abs(D-B)*abs(C-A);
int area2 = abs(H-F)*abs(G-E);
if(C<E || A>G || H<B || F>D)
return area1+area2;
int lengthright = min(C,G);
int lengthleft = max(A,E);
int hightop = min(D,H);
int highbuttom = max(F,B);
int area3 = abs(lengthright-lengthleft)*abs(hightop-highbuttom);
return area1+area2-area3;
}
};
231. Power of Two https://leetcode.com/problems/power-of-two/description/
class Solution {
public:
bool isPowerOfTwo(int n) {
return n > && !(n & (n - ));
}
};
258. Add Digits https://leetcode.com/problems/add-digits/description/
class Solution {
public:
int addDigits(int num) {
while(num>=){
int result = ;
while(num>){
result = result + num%;
num = num/;
}
num = result;
}
return num;
}
};
263. Ugly Number https://leetcode.com/problems/ugly-number/description/
class Solution {
public:
bool isUgly(int num) {
if(num == ) return false;
while(num!=){
bool div = false;
if(num%==){
num = num/;
div = true;
}
if(num%==){
num = num/;
div = true;
}
if(num%==){
num = num/;
div = true;
}
if(div==false)
return false;
}
return true;
}
};
264. Ugly Number II https://leetcode.com/problems/ugly-number-ii/description/
class Solution {
public:
int nthUglyNumber(int n) {
if (n<=) return -;
vector<int> q(n);
int t2(),t3(),t5();
q[]=;
for (int i=;i<n;++i){
q[i]=min(q[t2]*,min(q[t3]*,q[t5]*));
if (q[i]==q[t2]*) ++t2;
if (q[i]==q[t3]*) ++t3;
if (q[i]==q[t5]*) ++t5;
}
return q[n-];
}
};
思路记住，维护3个pos，分别表示乘以3个质数后大于当前最大uglynumber的最小数，之后需要更新pos
279. Perfect Squares https://leetcode.com/problems/perfect-squares/description/
两种动态规划的思路
class Solution {
public:
int numSquares(int n) {
vector<int> dp(, );
while (dp.size() <= n) {
int m = dp.size(), val = INT_MAX;
for (int i = ; i * i <= m; ++i) {
val = min(val, dp[m - i * i] + );
}
dp.push_back(val);
}
return dp.back();
}
};
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n + , INT_MAX);
dp[] = ;
for (int i = ; i <= n; ++i) {
for (int j = ; i + j * j <= n; ++j) {
dp[i + j * j] = min(dp[i + j * j], dp[i] + );
}
}
return dp.back();
}
};
313. Super Ugly Number https://leetcode.com/problems/super-ugly-number/description/
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
vector<int> index(primes.size(), );
vector<int> v = { };
for (int i = ; i<n-; i++) {
int mi = INT_MAX;
for (int i = ; i<primes.size(); i++) {
mi = min(mi, primes[i] * v[index[i]]);
}
v.push_back(mi);
for (int i = ; i<primes.size(); i++) {
while (primes[i] * v[index[i]]<=mi)
index[i]++;
}
}
return v.back();
}
};
319. Bulb Switcher https://leetcode.com/problems/bulb-switcher/description/
class Solution {
public:
int bulbSwitch(int n) {
return sqrt(n);
}
};
326. Power of Three https://leetcode.com/problems/power-of-three/description/
class Solution {
public:
bool isPowerOfThree(int n) {
if(n==) return false;
while(n%==){
n = n/;
}
if(n==) return true;
else return false;
}
};
343. Integer Break https://leetcode.com/problems/integer-break/description/
class Solution {
public:
int integerBreak(int n) {
int result = ;
if (n <= )
return n == ? : n-;
while (n > ) {
result *= ;
n -= ;
}
return result * n;
}
};
357. Count Numbers with Unique Digits https://leetcode.com/problems/count-numbers-with-unique-digits/description/
class Solution {
public:
int permutation(int n, int r)
{
if(r == )
{
return ;
}else{
return n * permutation(n - , r - );
}
}
int countNumbersWithUniqueDigits(int n) {
int sum = ;
if(n > )
{
int end = (n > )? : n;
for(int i = ; i < end; i++)
{
sum += * permutation(, i);
}
}
return sum;
}
};
365. Water and Jug Problem https://leetcode.com/problems/water-and-jug-problem/description/
class Solution {
public:
bool canMeasureWater(int x, int y, int z) {
return z == || (x + y >= z && z % gcd(x, y) == );
}
int gcd(int x, int y) {
return y == ? x : gcd(y, x % y);
}
};
367. Valid Perfect Square https://leetcode.com/problems/valid-perfect-square/description/
class Solution {
public:
bool isPerfectSquare(int num) {
if(int(sqrt(num))*int(sqrt(num)) == num)
return true;
else
return false;
}
};
368. Largest Divisible Subset https://leetcode.com/problems/largest-divisible-subset/description/
class Solution {
public:
vector<int> largestDivisibleSubset(vector<int>& nums) {
if(nums.size()==) return vector<int>();
sort(nums.begin(), nums.end());
vector<int> v(nums.size(),);
vector<int> path(nums.size(), );
int maxnum = ;
int maxpos = ;
for (int i = ; i < nums.size(); i++) {
for (int j = ; j < i; j++) {
if (nums[i] % nums[j] == && v[i] < v[j] + ) {
v[i] = v[j] + ;
path[i] = j;
if (v[i] > maxnum) {
maxnum = v[i];
maxpos = i;
}
}
}
}
vector<int> result;
for (int i = ; i < maxnum; i++) {
result.push_back(nums[maxpos]);
maxpos = path[maxpos];
}
return result;
}
};
动态规划，n的子集的个数用v[n]表示，等于之前能被整除的最大数代表的子集+1，每次i渠道一个新值，就在前面寻找所有能被该数整除的数j，v[j]表示该数的子集数
还用到了path来保存路径
372. Super Pow https://leetcode.com/problems/super-pow/description/
class Solution {
const int base = ;
int powmod(int a, int k) //a^k mod 1337 where 0 <= k <= 10
{
a %= base;
int result = ;
for (int i = ; i < k; ++i)
result = (result * a) % base;
return result;
}
public:
int superPow(int a, vector<int>& b) {
if (b.empty()) return ;
int last_digit = b.back();
b.pop_back();
return powmod(superPow(a, b), ) * powmod(a, last_digit) % base;
}
};
8
9
29
50
60
66
69
204
231
264
279
313
319
357
368