關於數學的演算法2 ||LeetCode刷題總結：math

關於數學的演算法2 ||LeetCode刷題總結：math

來自專欄如何快速高效學習C++？

11、拆分整數，求最大積：Integer Break - LeetCode

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 and not larger than 58.

AC Code：

class Solution {public: int integerBreak(int n) { int res=0; int i=1; while(i++){ int biggerNum=n%i,small=n/i; int multi=pow(small+1,biggerNum)*pow(small,i-biggerNum); if(multi>res)res=multi; else break; } return res; }};

12、統計數位不同的數：Count Numbers with Unique Digits - LeetCode

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.

Example:

Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])

Credits:

Special thanks to @memoryless for adding this problem and creating all test cases.

思路：0~9的排列組合

class Solution {public: int countNumbersWithUniqueDigits(int n) { n = min(n,10); vector<int> dp(n + 1, 9); dp[0] = 1; for(int i = 2;i<=n;i++){ for(int x = 9; x >= 9 - i + 2;x--){ dp[i] *= x; } } int ans = 0; for(int i= 0;i<dp.size();i++) ans += dp[i]; return ans; }};

13、三個水杯倒水問題：Water and Jug Problem - LeetCode

You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.

If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.

Operations allowed:

• Fill any of the jugs completely with water.
• Empty any of the jugs.
• Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.

Example 1: (From the famous "Die Hard" example)

Input: x = 3, y = 5, z = 4Output: True

Example 2:

Input: x = 2, y = 6, z = 5Output: False

AC code：

class Solution {public: int gcd(int x, int y){return (!x||!y)?0:y%x==0?x:gcd(y%x,x);} bool canMeasureWater(int x, int y, int z) { if(!gcd(x,y))return z == 0 || z==x || z==y;//如果x、y中存在0，那麼只有z == 0 || z==x || z==y 三種情況可以滿足 return (x + y >= z) && (z % gcd(x,y)) == 0;//如果x、y之和大於z，且x、y的最大公約數是z的因數，則可滿足 }};

14、驗證一個數是否為平方數：Valid Perfect Square - LeetCode

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:

Input: 16Returns: True

Example 2:

Input: 14Returns: False

思路：折半查找法：

class Solution {public: bool isPerfectSquare(int num) { if (num == 1) return true; long x = num / 2, t = x * x; while (t > num) { x /= 2; t = x * x; } for (int i = x; i <= 2 * x; ++i) { if (i * i == num) return true; } return false; }};

15、關於取模的的公式：Super Pow - LeetCode

Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

Example1:

a = 2b = [3]Result: 8

Example2:

a = 2b = [1,0]Result: 1024

思路: 需要用到的數學知識

1. a^b % 1337 = (a%1337)^b % 1337

2. xy % 1337 = ((x%1337) * (y%1337)) % 1337, 其中xy是一個數字如:45, 98等等

class Solution { const int base = 1337; int powmod(int a, int k) //a^k mod 1337 where 0 <= k <= 10 { a %= base; int result = 1; for (int i = 0; i < k; ++i) result = (result * a) % base; return result; }public: int superPow(int a, vector<int>& b) { if (b.empty()) return 1; int last_digit = b.back(); b.pop_back(); return powmod(superPow(a, b), 10) * powmod(a, last_digit) % base; }};

16、分塊求和優化演算法：Rotate Function - LeetCode

Given an array of integers A and let n to be its length.

Assume Bk to be an array obtained by rotating the array A k positions clock-wise, we define a "rotation function" F on A as follow:

F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1].

Calculate the maximum value of F(0), F(1), ..., F(n-1).

Note:

n is guaranteed to be less than 105.

Example:

A = [4, 3, 2, 6]F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.

分塊求和：

class Solution {public: int maxRotateFunction(vector<int>& A) { if (A.size() == 0) return 0; long long allsum = 0; long long sum2 = 0; for (int i = 0; i < A.size(); i++) {//注意到其和是階梯狀的數值相加，可以整體求和得到sum2後可以不一個個相加減 allsum += A[i] * i; sum2 += A[i]; } long long result = allsum; for (int i = 0; i < A.size(); i++) { allsum -= sum2; allsum += A[i]; allsum += A[i] * int(A.size() - 1); result = max(allsum, result); } return result; }};

還是分塊求和：Continuous Subarray Sum - LeetCode

Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.

Example 1:

Input: [23, 2, 4, 6, 7], k=6Output: TrueExplanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

Example 2:

Input: [23, 2, 6, 4, 7], k=6Output: TrueExplanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.

AC Code：

class Solution {public: bool checkSubarraySum(vector<int>& nums, int k) { vector<int>arr(nums); arr.insert(arr.begin(),0); for(int i=1;i<(int)arr.size();i++)arr[i]+=arr[i-1]; for(int i=2;i<(int)arr.size();i++){ for(int j=0;j<=i-2;j++){ int sub=arr[i]-arr[j]; if(0==k&&sub==0)return true; else if(k==0)continue; else if(sub%k==0)return true; } } return false; }};

17、把一個數變成1需要幾步？：Integer Replacement - LeetCode

Given a positive integer n and you can do operations as follow

1. If n is even, replace n with n/2.
2. If n is odd, you can replace n with either n + 1 or n - 1.

What is the minimum number of replacements needed for n to become 1?

Example 1:

Input:7Output:4Explanation:7 -> 8 -> 4 -> 2 -> 1or7 -> 6 -> 3 -> 2 -> 1

Example 2:

Input:8Output:3Explanation:8 -> 4 -> 2 -> 1

利用記憶化搜索節省時間：

class Solution { unordered_map<long long,int>m; int helper(long long n){ if(m.find(n)!=m.end())return m[n]; if(1==n||0==n){ m[n]=0; return 0; }else if(0==n%2){ m[n]=1+helper(n/2); return m[n]; }else { m[n]=1+min(helper(n+1),helper(n-1)); return m[n]; } }public: int integerReplacement(int n) { return helper((long long)n); }};

18、加即是減：Minimum Moves to Equal Array Elements - LeetCode

Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n - 1 elements by 1.

Example:

Input:[1,2,3]Output:3Explanation:Only three moves are needed (remember each move increments two elements):[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]

// a move is incrementing n - 1 elements by 1 which is equal to substrate 1 element by 1 class Solution {public: int minMoves(vector<int>& nums) { int sum=0,minNum=INT_MAX; for(int i=0;i<(int)nums.size();i++){ if(nums[i]<minNum)minNum=nums[i]; sum+=nums[i]; } return sum-nums.size()*minNum; }};

19、中位數優於平均數：Minimum Moves to Equal Array Elements II - LeetCode

Given a non-empty integer array, find the minimum number of moves required to make all array elements equal, where a move is incrementing a selected element by 1 or decrementing a selected element by 1.

You may assume the arrays length is at most 10,000.

Example:

Input:[1,2,3]Output:2Explanation:Only two moves are needed (remember each move increments or decrements one element):[1,2,3] => [2,2,3] => [2,2,2]

思路：

∑s∈S|s?x| is minimal if x is equal to the median.

//why median is better than average?//https://math.stackexchange.com/questions/113270/the-median-minimizes-the-sum-of-absolute-deviations-the-l-1-normclass Solution {public: int minMoves2(vector<int>& nums) { if(nums.empty())return 0; sort(nums.begin(),nums.end()); int medium=0; if(nums.size()%2==0){ medium=(nums[nums.size()/2]+nums[(nums.size()-1)/2])/2; }else{ medium=nums[nums.size()/2]; } /* if(nums.empty())return 0; int sum=0; for(int i:nums)sum+=i; int medium=sum/(int)nums.size();*/ int res=0; for(int i=0;i<(int)nums.size();i++){ res+=abs(nums[i]-medium); } return res; }};

20、複數的加減法：Complex Number Multiplication - LeetCode

Given two strings representing two complex numbers.

You need to return a string representing their multiplication. Note i^2 = -1 according to the definition.

Example 1

Input: "1+1i", "1+1i"Output: "0+2i"Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.

Example 2:

Input: "1+-1i", "1+-1i"Output: "0+-2i"Explanation: (1 - i) * (1 - i) = 1 + i2 - 2 * i = -2i, and you need convert it to the form of 0+-2i.

AC Code：

class Solution {public: string complexNumberMultiply(string a, string b) { int a1=a.find(+),a2=a.find(i),b1=b.find(+),b2=b.find(i); string asubstr1=a.substr(0,a1),asubstr2=a.substr(a1+1,a2-a1-1),bsubstr1=b.substr(0,b1),bsubstr2=b.substr(b1+1,b2-b1-1); int n=stoi(asubstr1)*stoi(bsubstr1)-stoi(asubstr2)*stoi(bsubstr2); int ni=stoi(asubstr1)*stoi(bsubstr2)+stoi(asubstr2)*stoi(bsubstr1); string s=to_string(n)+"+"+to_string(ni)+"i"; return s; }};//the use of substr(start,longth)and int convert to string

PS：

廣告時間啦~

理工狗不想被人文素養拖後腿？不妨關注微信公眾號：

推薦閱讀：