AI 助理
备案控制台
开发者社区 云原生 文章 正文

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

2024-01-30 45
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 力扣C++｜一题多解之数学题专场（2）

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++
Serverless
存储
关键词：
C++二叉树
C++遍历
LeetCode一题
LeetCode c++
C++力扣
HannYang
目录
相关文章
nsu_xxy
|
4月前
|
索引
力扣随机一题 6/26 哈希表 数组 思维
力扣随机一题 6/26 哈希表 数组 思维
nsu_xxy
32 0
დ旧言~
|
3月前
|
存储 C++
【C++】二叉树进阶之二叉搜索树（下）
【C++】二叉树进阶之二叉搜索树（下）
დ旧言~
23 4
დ旧言~
|
3月前
|
Java 编译器 C++
【C++】二叉树进阶之二叉搜索树（上）
【C++】二叉树进阶之二叉搜索树（上）
დ旧言~
28 3
Eternity._
|
3月前
|
算法 C++
【C++高阶】高效搜索的秘密：深入解析搜索二叉树
【C++高阶】高效搜索的秘密：深入解析搜索二叉树
Eternity._
35 2
百锦再@新空间代码工作室
|
3月前
|
存储 算法 搜索推荐
C++ 补充之常用遍历算法
C++ 补充之常用遍历算法
百锦再@新空间代码工作室
34 1
nsu_xxy
|
4月前
力扣随机一题 哈希表 排序 数组
力扣随机一题 哈希表 排序 数组
nsu_xxy
30 1
GR鲸鱼
|
5月前
|
存储 算法 C语言
从C语言到C++_39(C++笔试面试题)next_permutation刷力扣
从C语言到C++_39(C++笔试面试题)next_permutation刷力扣
GR鲸鱼
46 5
nsu_xxy
|
4月前
|
算法 索引
力扣随机一题 位运算/滑动窗口/数组
力扣随机一题 位运算/滑动窗口/数组
nsu_xxy
32 0
nsu_xxy
|
4月前
力扣随机一题 6/28 数组/矩阵
力扣随机一题 6/28 数组/矩阵
nsu_xxy
37 0
nsu_xxy
|
4月前
|
Python
力扣随机一题 模拟+字符串
力扣随机一题 模拟+字符串
nsu_xxy
25 0