备案控制台
探索云世界
开发者社区 云原生 文章 正文

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

2024-01-30 28
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 力扣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
存储
关键词：
LeetCode c++
C++二叉树
C++遍历
力扣C++
C++力扣
HannYang
目录
相关文章
LightOf
|
1月前
|
Go C++
【力扣】2696. 删除子串后的字符串最小长度（模拟 栈 C++ Go实现栈）
【2月更文挑战第18天】2696. 删除子串后的字符串最小长度（模拟 栈 C++ Go实现栈）
LightOf
34 6
七月巫山晴
|
1月前
|
C++
两种解法解决 LeetCode 27. 移除元素【C++】
两种解法解决 LeetCode 27. 移除元素【C++】
七月巫山晴
24 2
阿辉不一般
|
17天前
|
算法 Java C语言
C++和Java中的随机函数你玩明白了吗？内附LeetCode470.rand7()爆改rand10()巨详细题解，带你打败LeetCode%99选手
C++和Java中的随机函数你玩明白了吗？内附LeetCode470.rand7()爆改rand10()巨详细题解，带你打败LeetCode%99选手
阿辉不一般
18 0
认真学习的小雅兰.
|
存储 编译器 Linux
标准库中的string类（中）+仅仅反转字母+字符串中的第一个唯一字符+字符串相加——“C++”“Leetcode每日一题”
标准库中的string类（中）+仅仅反转字母+字符串中的第一个唯一字符+字符串相加——“C++”“Leetcode每日一题”
认真学习的小雅兰.
27 0
LightOf
|
1月前
|
Go C++
【力扣】2645. 构造有效字符串的最小插入数（动态规划 贪心 滚动数组优化 C++ Go）
【2月更文挑战第17天】2645. 构造有效字符串的最小插入数（动态规划 贪心 滚动数组优化 C++ Go）
LightOf
31 8
HannYang
|
3月前
|
Linux 监控 Shell
Linux 终端命令之文件浏览(4) head, tail
Linux 终端命令之文件浏览(4) head, tail
HannYang
30 0
Linux 终端命令之文件浏览(4) head, tail
懒懒学c
|
6天前
|
存储 编译器 C语言
c++的学习之路：5、类和对象（1）
c++的学习之路：5、类和对象（1）
懒懒学c
21 0
懒懒学c
|
6天前
|
C++
c++的学习之路：7、类和对象（3）
c++的学习之路：7、类和对象（3）
懒懒学c
19 0
杭电码农-NEO
|
4天前
|
设计模式 Java C++
【C++高阶(八)】单例模式&特殊类的设计
【C++高阶(八)】单例模式&特殊类的设计
杭电码农-NEO
17 3
杭电码农-NEO
|
4天前
|
编译器 C++
【C++基础(八)】类和对象(下)--初始化列表,友元,匿名对象
【C++基础(八)】类和对象(下)--初始化列表,友元,匿名对象
杭电码农-NEO
16 0

热门文章

最新文章

  • 1
    代码随想录算法训练营第五十六天 | LeetCode 647. 回文子串、516. 最长回文子序列、动态规划总结
  • 2
    力扣刷题日常（一）
  • 3
    标准库中的string类（中）+仅仅反转字母+字符串中的第一个唯一字符+字符串相加——“C++”“Leetcode每日一题”
  • 4
    【力扣经典面试题】80. 删除有序数组中的重复项 II
  • 5
    C++和Java中的随机函数你玩明白了吗？内附LeetCode470.rand7()爆改rand10()巨详细题解，带你打败LeetCode%99选手
  • 6
    从Proto到C++：探索Protocol Buffers的强大转换机制
  • 7
    代码随想录算法训练营第六十天 | LeetCode 84. 柱状图中最大的矩形
  • 8
    【力扣】94. 二叉树的中序遍历、144. 二叉树的前序遍历、145. 二叉树的后序遍历
  • 9
    每日一题：LeetCode-209. 长度最小的子数组（滑动窗口）
  • 10
    【C/C++ 数据库 sqlite3】SQLite C语言API返回值深入解析
  • 1
    【C++】—— c++11之智能指针
    45
  • 2
    【C++】—— C++11之线程库
    36
  • 3
    【C++】—— C++11之可变参数模板
    28
  • 4
    【C++】—— c++11新的类功能
    27
  • 5
    【C++】—— C++11新特性之 “右值引用和移动语义”
    30
  • 6
    【C++】—— c++11新特性之 lambda
    25
  • 7
    【C++】容器篇（五）—— map和set的基本介绍
    35
  • 8
    【C++】容器篇（四）—— queue的基本介绍以及模拟实现
    28
  • 9
    【C++】容器篇（三）—— stack的基本介绍及其模拟实现
    25
  • 10
    【C++】容器篇（二）——List的基本概述以及模拟实现
    31

    • 相关课程

    更多
  • C++ 入门教程开发文档
  • 天池leetcode编程基础课
  • 天池leetcode编程习题讲解

    • 相关电子书

    更多
  • 使用C++11开发PHP7扩展
  • GPON Class C++ SFP O;T Transce
  • GPON Class C++ SFP OLT Transce
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）