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

08-11

來自專欄如何快速高效學習C++？1 人贊了文章

1、不用加法如何實現a+b？：Sum of Two Integers - LeetCode

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example:

Given a = 1 and b = 2, return 3.

思路：使用門電路構成加法器的原理

class Solution {public: int getSum(int a, int b) { if(a&b)return getSum(a^b,(a&b)<<1); else return a^b; }};

2、不用乘法和除法如何實現除法？：Divide Two Integers - LeetCode

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero.

//Basic idea: a/b = e^(ln(a))/e^(ln(b)) = e^(ln(a)-ln(b))class Solution {public: int divide(int dividend, int divisor) { if (dividend==0) return 0; if (divisor==0) return INT_MAX; long long res=double(exp(log(fabs(dividend))-log(fabs(divisor)))); if ((dividend<0)^(divisor<0)) res=-res; if (res>INT_MAX) res=INT_MAX; return res; }};

3、大數乘法：Multiply Strings - LeetCode

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

Input: num1 = "2", num2 = "3"Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"Output: "56088"

AC code：

class Solution {public: string multiply(string num1, string num2) { string sum(num1.size() + num2.size(), 0); for (int i = num1.size() - 1; 0 <= i; --i) { int carry = 0; for (int j = num2.size() - 1; 0 <= j; --j) { int tmp = (sum[i + j + 1] - 0) + (num1[i] - 0) * (num2[j] - 0) + carry; sum[i + j + 1] = tmp % 10 + 0; carry = tmp / 10; } sum[i] += carry; } size_t startpos = sum.find_first_not_of("0"); if (string::npos != startpos) { return sum.substr(startpos); } return "0"; }};

4、大數加法：Add Two Numbers - LeetCode

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

簡單回憶一下小學知識：加法是怎麼手工計算的

從低位到高位：

sumBit=(Abit+Bbit+Carry)%10 得到結果的一位數字
Carry=(Abit+Bbit)/10 檢查是否進位

最後還需要檢查一下Carry進位是否為1，如果為1則結果的最高位還得添上1。

通過這樣的方式，我們可以用string或者鏈表來表示超過long long 表示範圍的大數。

class Solution {public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode preHead(0), *pointer = &preHead;//創建頭結點 int carry=0; while(l1||l2||carry) { int num=(l1?l1->val:0)+(l2?l2->val:0)+carry;//相加 pointer->next=new ListNode(num%10); carry=num/10;//檢查有無進位 pointer=pointer->next; l1=l1?l1->next:l1;//檢查是否其中一個鏈表到頭了 l2=l2?l2->next:l2; } return preHead.next; }};

鏈表反過來了怎麼辦？用Stack：https://leetcode.com/problems/add-two-numbers-ii/description/

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up:

What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)Output: 7 -> 8 -> 0 -> 7

AC code：

class Solution {public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { stack<ListNode*>s1,s2,s; while(l1){s1.push(l1);l1=l1->next;}//將鏈表l1壓入棧中 while(l2){s2.push(l2);l2=l2->next;}//將鏈表l2壓入棧中 int carry=0; while(!s1.empty()||!s2.empty()||carry){//進行加法運算，結果結點保存在棧中 int a=s1.empty()?0:s1.top()->val; int b=s2.empty()?0:s2.top()->val; if(!s1.empty())s1.pop(); if(!s2.empty())s2.pop(); int val=a+b+carry; carry=val/10;val%=10; ListNode*temp=new ListNode(val); s.push(temp); }//將棧中的結點重構成鏈表 ListNode pre(-1);ListNode*p=&pre; while(!s.empty()){ p->next=s.top();s.pop();p=p->next; } return pre.next; }};

如果數字是用string表示的呢？：Add Strings - LeetCode

Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.

Note:

The length of both num1 and num2 is < 5100.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

class Solution {public: string addStrings(string num1, string num2) { string res; int carry=0; for(int i=(int)num1.size()-1,j=num2.size()-1;i>=0||j>=0;j--,i--){ int bit=(i>=0?num1[i]-0:0)+(j>=0?num2[j]-0:0)+carry; carry=bit/10; bit%=10; res+=to_string(bit); } if(carry)res+=to_string(carry); for(int i=0;i<((int)res.size()>>1);i++){ swap(res[i],res[(int)res.size()-1-i]); } return res; }};

如果是二進位加法怎麼辦？：Add Binary - LeetCode

Given two binary strings, return their sum (also a binary string).

The input strings are both non-empty and contains only characters 1 or 0.

Example 1:

Input: a = "11", b = "1"

Output: "100"

Example 2:

Input: a = "1010", b = "1011"

Output: "10101"

class Solution {public: string addBinary(string a, string b) { if(a.empty()&&b.empty())return "0"; int carry=0; string res; for(int i=(int)a.size()-1,j=(int)b.size()-1;i>=0||j>=0;i--,j--){ int bit=(i>=0?a[i]-0:0)+(j>=0?b[j]-0:0)+carry; carry=bit/2; bit%=2; res+=to_string(bit); } if(carry)res+="1"; for(int i=0;i<(int)res.size()/2;i++){ swap(res[i],res[(int)res.size()-i-1]); } return res; }};

5、羅馬數字轉化為阿拉伯數字：https://leetcode.com/problems/roman-to-integer/description/

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol ValueI 1V 5X 10L 50C 100D 500M 1000

For example, two is written as II in Roman numeral, just two ones added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.

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) { int sum=0; if(s.indexOf("IV")!=-1){sum-=2;} if(s.indexOf("IX")!=-1){sum-=2;} if(s.indexOf("XL")!=-1){sum-=20;} if(s.indexOf("XC")!=-1){sum-=20;} if(s.indexOf("CD")!=-1){sum-=200;} if(s.indexOf("CM")!=-1){sum-=200;} char c[]=s.toCharArray(); int count=0; for(;count<=s.length()-1;count++){ if(c[count]==M) sum+=1000; if(c[count]==D) sum+=500; if(c[count]==C) sum+=100; if(c[count]==L) sum+=50; if(c[count]==X) sum+=10; if(c[count]==V) sum+=5; if(c[count]==I) sum+=1; } return sum; }}

6、如何實現sqrt(x)：Sqrt(x) - LeetCode

Implement int sqrt(int x).
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
Example 1:
Input: 4
Output: 2
Example 2:
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since
the decimal part is truncated, 2 is returned.

利用牛頓法：

class Solution {public: int mySqrt(int x) { double g=1; while(1){ double g2=(g+x/g)/2; if(abs(g2-g)<0.1)return (int)g2; else g=g2; } return g; }};

7、如何實現Pow(x,n)：Pow(x, n) - LeetCode

Implement pow(x, n), which calculates x raised to the power n (xn).

Example 1:
Input: 2.00000, 10
Output: 1024.00000
Example 2:
Input: 2.10000, 3
Output: 9.26100
Example 3:
Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

class Solution {public: double myPow(double x, int n) { if(n<0){ return (1/x)*myPow(1/x,-(n+1)); } if(n==0)return 1; if(n%2==0){ double temp=myPow(x,n/2); return temp*temp; }else{ double temp=myPow(x,n/2); return x*temp*temp; } }};

8、尋找所有小於n的質數：Count Primes - LeetCode

Count the number of prime numbers less than a non-negative number, n.

Example:
Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

class Solution {public: int countPrimes(int n) { if(n<=2)return 0; vector<int>prime(1,2); for(int i=3;i<n;i+=2){ bool flag=true; int lim=sqrt(i); for(int r=0;prime[r]<=lim&&r<(int)prime.size();r++){ if(0==i%prime[r]){ flag=false; break; } } if(flag)prime.push_back(i); } return (int)prime.size(); }};

拓展連接：質數能幫你賺錢？| 尋找質數的最高效演算法

9、如何找出最多的共線點數：Max Points on a Line - LeetCode

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Example 1:

Input: [[1,1],[2,2],[3,3]]Output: 3Explanation:^|| o| o| o +------------->0 1 2 3 4

AC code：

/** * Definition for a point. * struct Point { * int x; * int y; * Point() : x(0), y(0) {} * Point(int a, int b) : x(a), y(b) {} * }; *///代碼原理：http://www.cnblogs.com/grandyang/p/4579693.htmlclass Solution {public: int maxPoints(vector<Point>& points) { int res = 0; for (int i = 0; i < points.size(); ++i) { int duplicate = 1; for (int j = i + 1; j < points.size(); ++j) { int cnt = 0; long long x1 = points[i].x, y1 = points[i].y; long long x2 = points[j].x, y2 = points[j].y; if (x1 == x2 && y1 == y2) {++duplicate; continue;} for (int k = 0; k < points.size(); ++k) { int x3 = points[k].x, y3 = points[k].y; if (x1 * y2 + x2 * y3 + x3 * y1 - x3 * y2 - x2 * y1 - x1 * y3 == 0) {//即使三個點中有重合的點，也可以判斷出來。 ++cnt; } } res = max(res, cnt); } res = max(res, duplicate); } return res; }};

10、找到第n大的丑數：Ugly Number II - LeetCode

Write a program to find the n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.
Example:

Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
Note:
1 is typically treated as an ugly number.
n does not exceed 1690.

用優先隊列：

class Solution {public: #define ll long long int nthUglyNumber(int n) { vector<int>primes{2,3,5}; priority_queue<ll,vector<ll>,greater<ll> >pq; unordered_set<ll>s; pq.push(1);s.insert(1); int res=0; for(int rank=1;;rank++){ ll top=pq.top();pq.pop(); if(n==rank){res=top;break;} for(int i=0;i<(int)primes.size();i++){ ll temp=top*primes[i]; if(s.find(temp)==s.end()){ s.insert(temp); pq.push(temp); } } } return res; }};

用指針法：

class Solution {public: int nthUglyNumber(int n) { if(n <= 0) return false; // get rid of corner cases if(n == 1) return true; // base case int t2 = 0, t3 = 0, t5 = 0; //pointers for 2, 3, 5 vector<int> k(n); k[0] = 1; for(int i = 1; i < n ; i ++) { k[i] = min(k[t2]*2,min(k[t3]*3,k[t5]*5)); if(k[i] == k[t2]*2) t2++; if(k[i] == k[t3]*3) t3++; if(k[i] == k[t5]*5) t5++; } return k[n-1]; }};

用set：

class Solution {public: long nthUglyNumber(int n) { set<long> pq; pq.insert(1); int count = 0; long t = 1; while (count < n) { set<long>::iterator it = pq.begin(); t = *it; pq.erase(it); pq.insert(t * 2); pq.insert(t * 3); pq.insert(t * 5); count++; } return t; }};

PS：

廣告時間啦~

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

歡迎掃碼關注~