力扣C++｜一题多解之数学题专场（2）

古城微笑少年丶 2023-09-27 14:59 67阅读 0赞

![fe34a1c92c5f489689fd991ff5e0f559.png][]

**目录**

50. Pow(x, n)

60. 排列序列

66. 加一

67. 二进制求和

69. x 的平方根

--------------------

## 50. Pow(x, n) ##

实现 pow(x,n)，即计算 x 的 n 次幂函数（即x^n）。

**示例 1：**

输入：x = 2.00000, n = 10
    输出：1024.00000

**示例 2：**

输入：x = 2.10000, n = 3
    输出：9.26100

**示例 3：**

输入：x = 2.00000, n = -2
    输出：0.25000
    解释：2^(-2) = (1/2)^2 = 1/4 = 0.25

**提示：**

*  `-100.0 < x < 100.0`
 *  `-2^31 <= n <= 2^31-1`
 *  `-10^4 <= x^n <= 10^4`

**代码1：**

#include <bits/stdc++.h>
    using namespace std;
    
    class Solution
    {
    public:
        double myPow(double x, int n)
        {
            if (n == 0)
                return 1;
            if (n % 2 == 1)
            {
                double temp = myPow(x, n / 2);
                return temp * temp * x;
            }
            else if (n % 2 == -1)
            {
                double temp = myPow(x, n / 2);
                return temp * temp / x;
            }
            else
            {
                double temp = myPow(x, n / 2);
                return temp * temp;
            }
        }
    };
    
    int main()
    {
    	Solution s;
    	cout << s.myPow(2.00000, 10) << endl;
    	cout << s.myPow(2.10000, 3) << endl;
    	cout << s.myPow(2.0000, -2) << endl;
    	
    	return 0;
    }

**代码2：**

#include <bits/stdc++.h>
    using namespace std;
    
    class Solution
    {
    public:
        double helper(double x, int n)
        {
            if (n == 0)
                return 1.0;
            double y = helper(x, n / 2);
            return n % 2 == 0 ? y * y : y * y * x;
        }
    
        double myPow(double x, int n)
        {
            long long N = static_cast<long long>(n);
            if (N == 0)
                return 1;
            return N > 0 ? helper(x, N) : 1. / helper(x, -N);
        }
    };
    
    int main()
    {
    	Solution s;
    	cout << s.myPow(2.00000, 10) << endl;
    	cout << s.myPow(2.10000, 3) << endl;
    	cout << s.myPow(2.0000, -2) << endl;
    	
    	return 0;
    }

**代码3：**

#include <bits/stdc++.h>
    using namespace std;
    
    class Solution
    {
    public:
        double myPow(double x, int n)
        {
            if (n == INT_MIN)
            {
                double t = dfs(x, -(n / 2));
                return 1 / t * 1 / t;
            }
            else
            {
                return n < 0 ? 1 / dfs(x, -n) : dfs(x, n);
            }
        }
    
    private:
        double dfs(double x, int n)
        {
            if (n == 0)
            {
                return 1;
            }
            else if (n == 1)
            {
                return x;
            }
            else
            {
                double t = dfs(x, n / 2);
                return (n % 2) ? (x * t * t) : (t * t);
            }
        }
    };
    
    int main()
    {
    	Solution s;
    	cout << s.myPow(2.00000, 10) << endl;
    	cout << s.myPow(2.10000, 3) << endl;
    	cout << s.myPow(2.0000, -2) << endl;
    	
    	return 0;
    }

输出：

1024  
9.261  
0.25

--------------------

## 60. 排列序列 ##

给出集合 `[1,2,3,...,n]`，其所有元素共有 `n!` 种排列。

按大小顺序列出所有排列情况，并一一标记，当 `n = 3` 时, 所有排列如下：

1.  `"123"`
2.  `"132"`
3.  `"213"`
4.  `"231"`
5.  `"312"`
6.  `"321"`

给定 `n` 和 `k`，返回第 `k` 个排列。

**示例 1：**

输入：n = 3, k = 3
    输出："213"

**示例 2：**

输入：n = 4, k = 9
    输出："2314"

**示例 3：**

输入：n = 3, k = 1
    输出："123"

**提示：**

*  `1 <= n <= 9`
 *  `1 <= k <= n!`

**代码1：**

#include <bits/stdc++.h>
    using namespace std;
    
    class Solution
    {
    public:
        string getPermutation(int n, int k)
        {
            string ans;
            vector<bool> st(n + 1);
            for (int i = 1; i <= n; i++)
            {
                int f = 1;
                for (int j = n - i; j >= 1; j--)
                    f *= j;
                for (int j = 1; j <= n; j++)
                {
                    if (!st[j])
                    {
                        if (k <= f)
                        {
                            ans += to_string(j);
                            st[j] = 1;
                            break;
                        }
                        k -= f;
                    }
                }
            }
            return ans;
        }
    };
    
    int main()
    {
    	Solution s;
    	cout << s.getPermutation(3, 3) << endl;
    	cout << s.getPermutation(4, 9) << endl;
    	cout << s.getPermutation(3, 1) << endl;
    	
    	return 0;
    }

**代码2：**

#include <bits/stdc++.h>
    using namespace std;
    
    class Solution
    {
    public:
        vector<string> res;
        string getPermutation(int n, int k)
        {
            string track;
            traverse(track, n);
            return res[k - 1];
        }
        void traverse(string &track, int n)
        {
            if (track.size() == n)
            {
                res.push_back(track);
                return;
            }
            for (int i = 1; i <= n; i++)
            {
                char c = i + '0';
                if (find(track.begin(), track.end(), c) != track.end())
                    continue;
    
                track.push_back(c);
                traverse(track, n);
                track.pop_back();
            }
        }
    };
    
    int main()
    {
    	Solution s;
    	cout << s.getPermutation(3, 3) << endl;
    	cout << s.getPermutation(4, 9) << endl;
    	cout << s.getPermutation(3, 1) << endl;
    	
    	return 0;
    }

**代码3：**

#include <bits/stdc++.h>
    using namespace std;
    
    class Solution
    {
    public:
        int th;
        string ans;
        string getPermutation(int n, int k)
        {
            string s;
            vector<bool> vec(9, false);
            this->th = 0;
            backtrack(n, k, s, vec);
            return ans;
        }
        bool backtrack(int n, int k, string &s, vector<bool> &vec)
        {
            if (s.length() == n)
            {
                if (++th == k)
                {
                    ans = s;
                    return true;
                }
            }
            for (char c = '1'; c <= '1' + n - 1; c++)
            {
                if (vec[c - '1'])
                    continue;
                s.push_back(c);
                vec[c - '1'] = true;
                if (backtrack(n, k, s, vec))
                    return true;
                s.pop_back();
                vec[c - '1'] = false;
            }
            return false;
        }
    };
    
    int main()
    {
    	Solution s;
    	cout << s.getPermutation(3, 3) << endl;
    	cout << s.getPermutation(4, 9) << endl;
    	cout << s.getPermutation(3, 1) << endl;
    	
    	return 0;
    }

输出：

213  
2314  
123

--------------------

## 66. 加一 ##

给定一个由 **整数** 组成的 **非空** 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储**单个**数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

**示例 1：**

输入：digits = [1,2,3]
    输出：[1,2,4]
    解释：输入数组表示数字 123。

**示例 2：**

输入：digits = [4,3,2,1]
    输出：[4,3,2,2]
    解释：输入数组表示数字 4321。

**示例 3：**

输入：digits = [0]
    输出：[1]

**提示：**

*  `1 <= digits.length <= 100`
 *  `0 <= digits[i] <= 9`

**代码1：**

#include <bits/stdc++.h>
    using namespace std;
    
    class Solution
    {
    public:
        vector<int> plusOne(vector<int> &digits)
        {
            int len = digits.size() - 1;
            for (int i = len; i >= 0; i--)
            {
                if ((digits[i] + 1 == 10 && i == len) || digits[i] >= 10)
                {
                    digits[i] = 0;
                    if (i == 0)
                    {
                        digits.insert(digits.begin(), 1);
                    }
                    else
                    {
                        digits[i - 1] += 1;
                    }
                }
                else
                {
                    if (i == len)
                    {
                        digits[i] += 1;
                    }
                    break;
                }
            }
            return digits;
        }
    };
    
    int main()
    {
    	Solution s;
    	vector<int> sum;
    	vector<vector<int>> digits = {
       {1,2,3},{4,3,2,1},{0},{9,9,9}};
    	
    	for (auto digit:digits){
    		sum = s.plusOne(digit);
    		copy(sum.begin(), sum.end(), ostream_iterator<int>(cout, " "));
    		cout << endl;
    	}
    	
    	return 0;
    }

**代码2：**

#include <bits/stdc++.h>
    using namespace std;
    
    class Solution
    {
    public:
        vector<int> plusOne(vector<int> &digits)
        {
            int i = 0;
            int size = digits.size();
            for (i = size - 1; i >= 0; i--)
            {
                digits[i]++;
                digits[i] = digits[i] % 10;
                if (digits[i] != 0)
                    return digits;
            }
            if (i == -1)
            {
                digits.insert(digits.begin(), 1);
                digits[size] = 0;
            }
            return digits;
        }
    };
    
    int main()
    {
    	Solution s;
    	vector<int> sum;
    	vector<vector<int>> digits = {
       {1,2,3},{4,3,2,1},{0},{9,9,9}};
    	
    	for (auto digit:digits){
    		sum = s.plusOne(digit);
    		copy(sum.begin(), sum.end(), ostream_iterator<int>(cout, " "));
    		cout << endl;
    	}
    	
    	return 0;
    }

**代码3：**

#include <bits/stdc++.h>
    using namespace std;
    
    class Solution
    {
    public:
        vector<int> plusOne(vector<int> &digits)
        {
            int len = digits.size() - 1;
            for (; len > 0 && digits[len] == 9; --len)
            {
                digits[len] = 0;
            }
            if (len == 0 && digits[0] == 9)
            {
                digits[0] = 0;
                digits.insert(digits.begin(), 1);
            }
            else
            {
                ++digits[len];
            }
            return digits;
        }
    };
    
    int main()
    {
    	Solution s;
    	vector<int> sum;
    	vector<vector<int>> digits = {
       {1,2,3},{4,3,2,1},{0},{9,9,9}};
    	
    	for (auto digit:digits){
    		sum = s.plusOne(digit);
    		copy(sum.begin(), sum.end(), ostream_iterator<int>(cout, " "));
    		cout << endl;
    	}
    	
    	return 0;
    }

输出：

1 2 4  
4 3 2 2  
1  
1 0 0 0

--------------------

## 67. 二进制求和 ##

给你两个二进制字符串，返回它们的和（用二进制表示）。

输入为 **非空** 字符串且只包含数字 `1` 和 `0`。

**示例 1:**

输入: a = "11", b = "1"
    输出: "100"

**示例 2:**

输入: a = "1010", b = "1011"
    输出: "10101"

**提示：**

*  每个字符串仅由字符 `'0'` 或 `'1'` 组成。
 *  `1 <= a.length, b.length <= 10^4`
 *  字符串如果不是 `"0"` ，就都不含前导零。

**代码1：**

#include <iostream>
    #include <string>
    #include <algorithm>
    using namespace std;
    
    class Solution
    {
    public:
    	string addBinary(string a, string b) {
    	    string result;
    	    int carry = 0;
    	    int i = a.length() - 1, j = b.length() - 1;
    	    
    	    while (i >= 0 || j >= 0 || carry != 0) {
    	        int sum = carry;
    	        if (i >= 0) {
    	            sum += a[i--] - '0';
    	        }
    	        if (j >= 0) {
    	            sum += b[j--] - '0';
    	        }
    	        
    	        result.push_back(sum % 2 + '0');
    	        carry = sum / 2;
    	    }
    	    
    	    reverse(result.begin(), result.end());
    	    return result;
    	}
    };
    
    int main()
    {
    	Solution s;
    	cout << s.addBinary("11", "1") << endl;
    	cout << s.addBinary("1010", "1011") << endl;
    	cout << s.addBinary("1111", "11111") << endl;
    	cout << s.addBinary("1100", "110111") << endl;
    	
    	return 0;
    }

**代码2：**

#include <iostream>
    #include <string>
    #include <algorithm>
    using namespace std;
    
    class Solution
    {
    public:
        string addBinary(string a, string b)
        {
            int sum = 0;
            string res;
            int p = 0;
            int i = a.length() - 1, j = b.length() - 1;
            
            while (i >= 0 || j >= 0 || sum != 0)
            {
                if (i >= 0) {
                    sum += a[i--] - '0';
                }
                if (j >= 0) {
                    sum += b[j--] - '0';
                }
                
                p = sum % 2;
                sum /= 2;
                
                res += to_string(p);
            }
            
            reverse(res.begin(), res.end());
            return res;
        }
    };
    
    int main()
    {
        Solution s;
        cout << s.addBinary("11", "1") << endl;
        cout << s.addBinary("1010", "1011") << endl;
        cout << s.addBinary("1111", "11111") << endl;
        cout << s.addBinary("1100", "110111") << endl;
        
        return 0;
    }

**代码3：**

#include <bits/stdc++.h>
    using namespace std;
    
    class Solution
    {
    public:
        string addBinary(string a, string b)
        {
            if (b.size() > a.size())
            {
                string temp = b;
                b = a;
                a = temp;
            }
            int i = a.size() - 1;
            int j = b.size() - 1;
            if (i != j)
            {
                for (int k = 0; k < i - j; k++)
                    b = "0" + b;
            }
            int count = 0;
            for (int k = i; k >= 0; k--)
            {
                if (a[k] - '0' + b[k] - '0' + count == 0)
                {
                    a[k] = '0';
                    count = 0;
                }
                else if (a[k] - '0' + b[k] - '0' + count == 1)
                {
                    a[k] = '1';
                    count = 0;
                }
                else if (a[k] - '0' + b[k] - '0' + count == 3)
                {
                    a[k] = '1';
                    count = 1;
                }
                else
                {
                    a[k] = '0';
                    count = 1;
                }
            }
            if (count == 1)
                a = '1' + a;
            return a;
        }
    };
    
    int main()
    {
    	Solution s;
    	cout << s.addBinary("11", "1") << endl;
    	cout << s.addBinary("1010", "1011") << endl;
    	cout << s.addBinary("1111", "11111") << endl;
    	cout << s.addBinary("1100", "110111") << endl;
    	
    	return 0;
    }

**代码4：**

#include <bits/stdc++.h>
    using namespace std;
    
    class Solution
    {
    public:
        string addBinary(string a, string b)
        {
            string result = "", rr = "";
            char aa, bb;
            int l1 = a.length(), l2 = b.length(), i = l1 - 1, j = l2 - 1, carry = 0, sum = 0;
            while (true)
            {
                if (i < 0)
                    aa = '0';
                else
                    aa = a[i];
                if (j < 0)
                    bb = '0';
                else
                    bb = b[j];
                sum = (aa - '0') + (bb - '0') + carry;
                result += ((sum % 2) + '0');
                carry = sum / 2;
                j--;
                i--;
                if (i < 0 && j < 0)
                {
                    if (carry == 1)
                        result += "1";
                    break;
                }
            }
            int l3 = result.length();
            for (int i = l3 - 1; i >= 0; i--)
                rr += result[i];
            return rr;
        }
    };
    
    int main()
    {
    	Solution s;
    	cout << s.addBinary("11", "1") << endl;
    	cout << s.addBinary("1010", "1011") << endl;
    	cout << s.addBinary("1111", "11111") << endl;
    	cout << s.addBinary("1100", "110111") << endl;
    	
    	return 0;
    }

输出：

100  
10101  
101110  
1000011

--------------------

## 69. x 的平方根 ##

实现 `int sqrt(int x)` 函数。

计算并返回 *x* 的平方根，其中 *x* 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

**示例 1:**

输入: 4
    输出: 2

**示例 2:**

输入: 8
    输出: 2
    说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

**代码1：**

#include <bits/stdc++.h>
    using namespace std;
    
    class Solution
    {
    public:
        int mySqrt(int x)
        {
            long long i = 0;
            long long j = x / 2 + 1;
            while (i <= j)
            {
                long long mid = (i + j) / 2;
                long long res = mid * mid;
                if (res == x)
                    return mid;
                else if (res < x)
                    i = mid + 1;
                else
                    j = mid - 1;
            }
            return j;
        }
    };
    
    int main()
    {
    	Solution s;
    	cout << s.mySqrt(4) << endl;
    	cout << s.mySqrt(8) << endl;
    	
    	cout << s.mySqrt(121) << endl;
    	cout << s.mySqrt(120) << endl;
    	cout << s.mySqrt(122) << endl;
    	
    	return 0;
    }

**代码2：**

#include <bits/stdc++.h>
    using namespace std;
    
    class Solution
    {
    public:
        int mySqrt(int x)
        {
            if (x == 0)
                return 0;
            double last = 0;
            double res = 1;
            while (res != last)
            {
                last = res;
                res = (res + x / res) / 2;
            }
            return int(res);
        }
    };
    
    int main()
    {
    	Solution s;
    	cout << s.mySqrt(4) << endl;
    	cout << s.mySqrt(8) << endl;
    	cout << s.mySqrt(121) << endl;
    	cout << s.mySqrt(120) << endl;
    	cout << s.mySqrt(122) << endl;
    	
    	return 0;
    }

**代码3：**

#include <iostream>
    #include <math.h>
    using namespace std;
    
    class Solution
    {
    public:
    	int mySqrt(int x) {
    	    if (x <= 1) {
    	        return x;
    	    }
    	
    	    int left = 1;
    	    int right = x;
    	    while (left <= right) {
    	        int mid = left + (right - left) / 2;
    	        if (mid == x / mid) {
    	            return mid;
    	        } else if (mid < x / mid) {
    	            left = mid + 1;
    	        } else {
    	            right = mid - 1;
    	        }
    	    }
    	
    	    return right;
    	}
    };
    
    int main()
    {
    	Solution s;
    	cout << s.mySqrt(4) << endl;
    	cout << s.mySqrt(8) << endl;
    	cout << s.mySqrt(121) << endl;
    	cout << s.mySqrt(120) << endl;
    	cout << s.mySqrt(122) << endl;
    	
    	return 0;
    }

输出：

2  
2  
11  
10  
11

另： cmath或者math.h库中有现成的函数 sqrt()

--------------------

相关阅读： [力扣C++｜一题多解之数学题专场（1）][C_1]

[fe34a1c92c5f489689fd991ff5e0f559.png]: https://img-blog.csdnimg.cn/fe34a1c92c5f489689fd991ff5e0f559.png
[C_1]: https://mp.csdn.net/mp_blog/creation/editor/131730669