1. AI技术聚合首页
  2. IT

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

乘风 • • IT • 阅读 94

目录

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）

文章出处登录后可见！

已经登录？立即刷新

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
乘风的头像乘风管理团队
0
上一篇 2023年12月14日
下一篇 2023年12月14日

相关推荐

此站出售，如需请站内私信或者邮箱！