devbox
羊村懒王
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

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

作者：羊村懒王 | 2024-04-26 02:14:31

赞

踩

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

目录

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：  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution
  5. {
  6. public:
  7.     double myPow(double x, int n)
  8.     {
  9.         if (n == 0)
  10.             return 1;
  11.         if (n % 2 == 1)
  12.         {
  13.             double temp = myPow(x, n / 2);
  14.             return temp * temp * x;
  15.         }
  16.         else if (n % 2 == -1)
  17.         {
  18.             double temp = myPow(x, n / 2);
  19.             return temp * temp / x;
  20.         }
  21.         else
  22.         {
  23.             double temp = myPow(x, n / 2);
  24.             return temp * temp;
  25.         }
  26.     }
  27. };
  28.  
  29. int main()
  30. {
  31. 	Solution s;
  32. 	cout << s.myPow(2.00000, 10) << endl;
  33. 	cout << s.myPow(2.10000, 3) << endl;
  34. 	cout << s.myPow(2.0000, -2) << endl;
  35. 	
  36. 	return 0;
  37. }

代码2：  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution
  5. {
  6. public:
  7.     double helper(double x, int n)
  8.     {
  9.         if (n == 0)
  10.             return 1.0;
  11.         double y = helper(x, n / 2);
  12.         return n % 2 == 0 ? y * y : y * y * x;
  13.     }
  14.  
  15.     double myPow(double x, int n)
  16.     {
  17.         long long N = static_cast<long long>(n);
  18.         if (N == 0)
  19.             return 1;
  20.         return N > 0 ? helper(x, N) : 1. / helper(x, -N);
  21.     }
  22. };
  23.  
  24. int main()
  25. {
  26. 	Solution s;
  27. 	cout << s.myPow(2.00000, 10) << endl;
  28. 	cout << s.myPow(2.10000, 3) << endl;
  29. 	cout << s.myPow(2.0000, -2) << endl;
  30. 	
  31. 	return 0;
  32. }

代码3：  

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution
  5. {
  6. public:
  7.     double myPow(double x, int n)
  8.     {
  9.         if (n == INT_MIN)
  10.         {
  11.             double t = dfs(x, -(n / 2));
  12.             return 1 / t * 1 / t;
  13.         }
  14.         else
  15.         {
  16.             return n < 0 ? 1 / dfs(x, -n) : dfs(x, n);
  17.         }
  18.     }
  19.  
  20. private:
  21.     double dfs(double x, int n)
  22.     {
  23.         if (n == 0)
  24.         {
  25.             return 1;
  26.         }
  27.         else if (n == 1)
  28.         {
  29.             return x;
  30.         }
  31.         else
  32.         {
  33.             double t = dfs(x, n / 2);
  34.             return (n % 2) ? (x * t * t) : (t * t);
  35.         }
  36.     }
  37. };
  38.  
  39. int main()
  40. {
  41. 	Solution s;
  42. 	cout << s.myPow(2.00000, 10) << endl;
  43. 	cout << s.myPow(2.10000, 3) << endl;
  44. 	cout << s.myPow(2.0000, -2) << endl;
  45. 	
  46. 	return 0;
  47. }

输出：

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：   

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution
  5. {
  6. public:
  7.     string getPermutation(int n, int k)
  8.     {
  9.         string ans;
  10.         vector<bool> st(n + 1);
  11.         for (int i = 1; i <= n; i++)
  12.         {
  13.             int f = 1;
  14.             for (int j = n - i; j >= 1; j--)
  15.                 f *= j;
  16.             for (int j = 1; j <= n; j++)
  17.             {
  18.                 if (!st[j])
  19.                 {
  20.                     if (k <= f)
  21.                     {
  22.                         ans += to_string(j);
  23.                         st[j] = 1;
  24.                         break;
  25.                     }
  26.                     k -= f;
  27.                 }
  28.             }
  29.         }
  30.         return ans;
  31.     }
  32. };
  33.  
  34. int main()
  35. {
  36. 	Solution s;
  37. 	cout << s.getPermutation(3, 3) << endl;
  38. 	cout << s.getPermutation(4, 9) << endl;
  39. 	cout << s.getPermutation(3, 1) << endl;
  40. 	
  41. 	return 0;
  42. }

代码2：   

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution
  5. {
  6. public:
  7.     vector<string> res;
  8.     string getPermutation(int n, int k)
  9.     {
  10.         string track;
  11.         traverse(track, n);
  12.         return res[k - 1];
  13.     }
  14.     void traverse(string &track, int n)
  15.     {
  16.         if (track.size() == n)
  17.         {
  18.             res.push_back(track);
  19.             return;
  20.         }
  21.         for (int i = 1; i <= n; i++)
  22.         {
  23.             char c = i + '0';
  24.             if (find(track.begin(), track.end(), c) != track.end())
  25.                 continue;
  26.  
  27.             track.push_back(c);
  28.             traverse(track, n);
  29.             track.pop_back();
  30.         }
  31.     }
  32. };
  33.  
  34. int main()
  35. {
  36. 	Solution s;
  37. 	cout << s.getPermutation(3, 3) << endl;
  38. 	cout << s.getPermutation(4, 9) << endl;
  39. 	cout << s.getPermutation(3, 1) << endl;
  40. 	
  41. 	return 0;
  42. }

代码3：   

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution
  5. {
  6. public:
  7.     int th;
  8.     string ans;
  9.     string getPermutation(int n, int k)
  10.     {
  11.         string s;
  12.         vector<bool> vec(9, false);
  13.         this->th = 0;
  14.         backtrack(n, k, s, vec);
  15.         return ans;
  16.     }
  17.     bool backtrack(int n, int k, string &s, vector<bool> &vec)
  18.     {
  19.         if (s.length() == n)
  20.         {
  21.             if (++th == k)
  22.             {
  23.                 ans = s;
  24.                 return true;
  25.             }
  26.         }
  27.         for (char c = '1'; c <= '1' + n - 1; c++)
  28.         {
  29.             if (vec[c - '1'])
  30.                 continue;
  31.             s.push_back(c);
  32.             vec[c - '1'] = true;
  33.             if (backtrack(n, k, s, vec))
  34.                 return true;
  35.             s.pop_back();
  36.             vec[c - '1'] = false;
  37.         }
  38.         return false;
  39.     }
  40. };
  41.  
  42. int main()
  43. {
  44. 	Solution s;
  45. 	cout << s.getPermutation(3, 3) << endl;
  46. 	cout << s.getPermutation(4, 9) << endl;
  47. 	cout << s.getPermutation(3, 1) << endl;
  48. 	
  49. 	return 0;
  50. }

输出：

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：   

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution
  5. {
  6. public:
  7.     vector<int> plusOne(vector<int> &digits)
  8.     {
  9.         int len = digits.size() - 1;
  10.         for (int i = len; i >= 0; i--)
  11.         {
  12.             if ((digits[i] + 1 == 10 && i == len) || digits[i] >= 10)
  13.             {
  14.                 digits[i] = 0;
  15.                 if (i == 0)
  16.                 {
  17.                     digits.insert(digits.begin(), 1);
  18.                 }
  19.                 else
  20.                 {
  21.                     digits[i - 1] += 1;
  22.                 }
  23.             }
  24.             else
  25.             {
  26.                 if (i == len)
  27.                 {
  28.                     digits[i] += 1;
  29.                 }
  30.                 break;
  31.             }
  32.         }
  33.         return digits;
  34.     }
  35. };
  36.  
  37. int main()
  38. {
  39. 	Solution s;
  40. 	vector<int> sum;
  41. 	vector<vector<int>> digits = {{1,2,3},{4,3,2,1},{0},{9,9,9}};
  42. 	
  43. 	for (auto digit:digits){
  44. 		sum = s.plusOne(digit);
  45. 		copy(sum.begin(), sum.end(), ostream_iterator<int>(cout, " "));
  46. 		cout << endl;
  47. 	}
  48. 	
  49. 	return 0;
  50. }

代码2：   

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution
  5. {
  6. public:
  7.     vector<int> plusOne(vector<int> &digits)
  8.     {
  9.         int i = 0;
  10.         int size = digits.size();
  11.         for (i = size - 1; i >= 0; i--)
  12.         {
  13.             digits[i]++;
  14.             digits[i] = digits[i] % 10;
  15.             if (digits[i] != 0)
  16.                 return digits;
  17.         }
  18.         if (i == -1)
  19.         {
  20.             digits.insert(digits.begin(), 1);
  21.             digits[size] = 0;
  22.         }
  23.         return digits;
  24.     }
  25. };
  26.  
  27. int main()
  28. {
  29. 	Solution s;
  30. 	vector<int> sum;
  31. 	vector<vector<int>> digits = {{1,2,3},{4,3,2,1},{0},{9,9,9}};
  32. 	
  33. 	for (auto digit:digits){
  34. 		sum = s.plusOne(digit);
  35. 		copy(sum.begin(), sum.end(), ostream_iterator<int>(cout, " "));
  36. 		cout << endl;
  37. 	}
  38. 	
  39. 	return 0;
  40. }

代码3：   

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution
  5. {
  6. public:
  7.     vector<int> plusOne(vector<int> &digits)
  8.     {
  9.         int len = digits.size() - 1;
  10.         for (; len > 0 && digits[len] == 9; --len)
  11.         {
  12.             digits[len] = 0;
  13.         }
  14.         if (len == 0 && digits[0] == 9)
  15.         {
  16.             digits[0] = 0;
  17.             digits.insert(digits.begin(), 1);
  18.         }
  19.         else
  20.         {
  21.             ++digits[len];
  22.         }
  23.         return digits;
  24.     }
  25. };
  26.  
  27. int main()
  28. {
  29. 	Solution s;
  30. 	vector<int> sum;
  31. 	vector<vector<int>> digits = {{1,2,3},{4,3,2,1},{0},{9,9,9}};
  32. 	
  33. 	for (auto digit:digits){
  34. 		sum = s.plusOne(digit);
  35. 		copy(sum.begin(), sum.end(), ostream_iterator<int>(cout, " "));
  36. 		cout << endl;
  37. 	}
  38. 	
  39. 	return 0;
  40. }

输出：

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：

  1. #include <iostream>
  2. #include <string>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. class Solution
  7. {
  8. public:
  9. 	string addBinary(string a, string b) {
  10. 	    string result;
  11. 	    int carry = 0;
  12. 	    int i = a.length() - 1, j = b.length() - 1;
  13. 	    
  14. 	    while (i >= 0 || j >= 0 || carry != 0) {
  15. 	        int sum = carry;
  16. 	        if (i >= 0) {
  17. 	            sum += a[i--] - '0';
  18. 	        }
  19. 	        if (j >= 0) {
  20. 	            sum += b[j--] - '0';
  21. 	        }
  22. 	        
  23. 	        result.push_back(sum % 2 + '0');
  24. 	        carry = sum / 2;
  25. 	    }
  26. 	    
  27. 	    reverse(result.begin(), result.end());
  28. 	    return result;
  29. 	}
  30. };
  31.  
  32. int main()
  33. {
  34. 	Solution s;
  35. 	cout << s.addBinary("11", "1") << endl;
  36. 	cout << s.addBinary("1010", "1011") << endl;
  37. 	cout << s.addBinary("1111", "11111") << endl;
  38. 	cout << s.addBinary("1100", "110111") << endl;
  39. 	
  40. 	return 0;
  41. }

代码2：  

  1. #include <iostream>
  2. #include <string>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. class Solution
  7. {
  8. public:
  9.     string addBinary(string a, string b)
  10.     {
  11.         int sum = 0;
  12.         string res;
  13.         int p = 0;
  14.         int i = a.length() - 1, j = b.length() - 1;
  15.         
  16.         while (i >= 0 || j >= 0 || sum != 0)
  17.         {
  18.             if (i >= 0) {
  19.                 sum += a[i--] - '0';
  20.             }
  21.             if (j >= 0) {
  22.                 sum += b[j--] - '0';
  23.             }
  24.             
  25.             p = sum % 2;
  26.             sum /= 2;
  27.             
  28.             res += to_string(p);
  29.         }
  30.         
  31.         reverse(res.begin(), res.end());
  32.         return res;
  33.     }
  34. };
  35.  
  36. int main()
  37. {
  38.     Solution s;
  39.     cout << s.addBinary("11", "1") << endl;
  40.     cout << s.addBinary("1010", "1011") << endl;
  41.     cout << s.addBinary("1111", "11111") << endl;
  42.     cout << s.addBinary("1100", "110111") << endl;
  43.     
  44.     return 0;
  45. }

代码3：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution
  5. {
  6. public:
  7.     string addBinary(string a, string b)
  8.     {
  9.         if (b.size() > a.size())
  10.         {
  11.             string temp = b;
  12.             b = a;
  13.             a = temp;
  14.         }
  15.         int i = a.size() - 1;
  16.         int j = b.size() - 1;
  17.         if (i != j)
  18.         {
  19.             for (int k = 0; k < i - j; k++)
  20.                 b = "0" + b;
  21.         }
  22.         int count = 0;
  23.         for (int k = i; k >= 0; k--)
  24.         {
  25.             if (a[k] - '0' + b[k] - '0' + count == 0)
  26.             {
  27.                 a[k] = '0';
  28.                 count = 0;
  29.             }
  30.             else if (a[k] - '0' + b[k] - '0' + count == 1)
  31.             {
  32.                 a[k] = '1';
  33.                 count = 0;
  34.             }
  35.             else if (a[k] - '0' + b[k] - '0' + count == 3)
  36.             {
  37.                 a[k] = '1';
  38.                 count = 1;
  39.             }
  40.             else
  41.             {
  42.                 a[k] = '0';
  43.                 count = 1;
  44.             }
  45.         }
  46.         if (count == 1)
  47.             a = '1' + a;
  48.         return a;
  49.     }
  50. };
  51.  
  52. int main()
  53. {
  54. 	Solution s;
  55. 	cout << s.addBinary("11", "1") << endl;
  56. 	cout << s.addBinary("1010", "1011") << endl;
  57. 	cout << s.addBinary("1111", "11111") << endl;
  58. 	cout << s.addBinary("1100", "110111") << endl;
  59. 	
  60. 	return 0;
  61. }

代码4：   

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution
  5. {
  6. public:
  7.     string addBinary(string a, string b)
  8.     {
  9.         string result = "", rr = "";
  10.         char aa, bb;
  11.         int l1 = a.length(), l2 = b.length(), i = l1 - 1, j = l2 - 1, carry = 0, sum = 0;
  12.         while (true)
  13.         {
  14.             if (i < 0)
  15.                 aa = '0';
  16.             else
  17.                 aa = a[i];
  18.             if (j < 0)
  19.                 bb = '0';
  20.             else
  21.                 bb = b[j];
  22.             sum = (aa - '0') + (bb - '0') + carry;
  23.             result += ((sum % 2) + '0');
  24.             carry = sum / 2;
  25.             j--;
  26.             i--;
  27.             if (i < 0 && j < 0)
  28.             {
  29.                 if (carry == 1)
  30.                     result += "1";
  31.                 break;
  32.             }
  33.         }
  34.         int l3 = result.length();
  35.         for (int i = l3 - 1; i >= 0; i--)
  36.             rr += result[i];
  37.         return rr;
  38.     }
  39. };
  40.  
  41. int main()
  42. {
  43. 	Solution s;
  44. 	cout << s.addBinary("11", "1") << endl;
  45. 	cout << s.addBinary("1010", "1011") << endl;
  46. 	cout << s.addBinary("1111", "11111") << endl;
  47. 	cout << s.addBinary("1100", "110111") << endl;
  48. 	
  49. 	return 0;
  50. }

输出： 

100
10101
101110
1000011 

69. x 的平方根

实现 int sqrt(int x) 函数。

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

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

示例 1:

输入: 4
输出: 2

示例 2:

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

代码1：   

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution
  5. {
  6. public:
  7.     int mySqrt(int x)
  8.     {
  9.         long long i = 0;
  10.         long long j = x / 2 + 1;
  11.         while (i <= j)
  12.         {
  13.             long long mid = (i + j) / 2;
  14.             long long res = mid * mid;
  15.             if (res == x)
  16.                 return mid;
  17.             else if (res < x)
  18.                 i = mid + 1;
  19.             else
  20.                 j = mid - 1;
  21.         }
  22.         return j;
  23.     }
  24. };
  25.  
  26. int main()
  27. {
  28. 	Solution s;
  29. 	cout << s.mySqrt(4) << endl;
  30. 	cout << s.mySqrt(8) << endl;
  31. 	
  32. 	cout << s.mySqrt(121) << endl;
  33. 	cout << s.mySqrt(120) << endl;
  34. 	cout << s.mySqrt(122) << endl;
  35. 	
  36. 	return 0;
  37. }

代码2：   

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Solution
  5. {
  6. public:
  7.     int mySqrt(int x)
  8.     {
  9.         if (x == 0)
  10.             return 0;
  11.         double last = 0;
  12.         double res = 1;
  13.         while (res != last)
  14.         {
  15.             last = res;
  16.             res = (res + x / res) / 2;
  17.         }
  18.         return int(res);
  19.     }
  20. };
  21.  
  22. int main()
  23. {
  24. 	Solution s;
  25. 	cout << s.mySqrt(4) << endl;
  26. 	cout << s.mySqrt(8) << endl;
  27. 	cout << s.mySqrt(121) << endl;
  28. 	cout << s.mySqrt(120) << endl;
  29. 	cout << s.mySqrt(122) << endl;
  30. 	
  31. 	return 0;
  32. }

代码3：   

  1. #include <iostream>
  2. #include <math.h>
  3. using namespace std;
  4.  
  5. class Solution
  6. {
  7. public:
  8. 	int mySqrt(int x) {
  9. 	    if (x <= 1) {
  10. 	        return x;
  11. 	    }
  12. 	
  13. 	    int left = 1;
  14. 	    int right = x;
  15. 	    while (left <= right) {
  16. 	        int mid = left + (right - left) / 2;
  17. 	        if (mid == x / mid) {
  18. 	            return mid;
  19. 	        } else if (mid < x / mid) {
  20. 	            left = mid + 1;
  21. 	        } else {
  22. 	            right = mid - 1;
  23. 	        }
  24. 	    }
  25. 	
  26. 	    return right;
  27. 	}
  28. };
  29.  
  30. int main()
  31. {
  32. 	Solution s;
  33. 	cout << s.mySqrt(4) << endl;
  34. 	cout << s.mySqrt(8) << endl;
  35. 	cout << s.mySqrt(121) << endl;
  36. 	cout << s.mySqrt(120) << endl;
  37. 	cout << s.mySqrt(122) << endl;
  38. 	
  39. 	return 0;
  40. }

输出：

2
2
11
10
11

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

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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/488397
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号