c++-c++编程基础之leetcode题解第29题两数相除.zip资源-CSDN下载

共2个文件

md：1个

cpp：1个

需积分: 50 100 浏览量 2024-04-07 05:28:40 上传评论收藏 2KB ZIP 举报

在C++编程中，LeetCode是一个非常受欢迎的在线平台，用于练习和提升编程技能，特别是算法和数据结构。第29题"两数相除"是这个平台上的一道经典问题，它涉及到数值计算和基本的编程逻辑。让我们深入探讨这个问题以及如何用C++来解决它。题目描述：给定两个整数`dividend`（被除数）和`divisor`（除数），不使用乘法、除法和取模运算符，计算它们相除的商。注意，`dividend`和`divisor`都是32位有符号整数，这意味着它们可以是正数、负数或零，并且结果也应是一个32位整数。解题思路： 1. **迭代法**：我们可以使用迭代的方法，每次将较大的数减去较小数的若干倍，直到较大数小于较小数。在此过程中记录下减了多少次，这就是商。 2. **位操作法**：利用位操作可以更高效地实现除法。我们可以判断`dividend`是否为负数，`divisor`是否为正数，根据这些信息确定结果的符号。然后，我们可以通过不断地左移`divisor`并检查它是否大于等于`dividend`来找到除法的结果。以下是一个使用迭代法的C++解决方案： ```cpp int divide(int dividend, int divisor) { bool isNegative = (dividend < 0) ^ (divisor < 0); long long absDividend = labs(dividend); long long absDivisor = labs(divisor); long long result = 0; while (absDividend >= absDivisor) { long long temp = absDivisor; long long multiple = 1; while (absDividend >= (temp << 1)) { temp <<= 1; multiple <<= 1; } absDividend -= temp; result += multiple; } return isNegative ? -result : result; } ``` 在这个代码中，我们首先检查了两个数的符号，然后将它们转换为绝对值进行计算，最后再根据原始符号决定返回值的正负。在迭代过程中，我们不断尝试将`divisor`左移，直到它不再大于等于`dividend`，这样可以快速逼近正确的商。 C++语言特性： - `labs()`函数是C++库中的一个函数，用于计算一个长整型变量的绝对值。 - 符号判断：`(dividend < 0) ^ (divisor < 0)`使用异或操作符`^`来判断结果的正负。如果两个操作数中有一个是负数，异或结果为1，表示结果是负数；如果两个操作数都是正数或负数，异或结果为0，表示结果是正数。 - 左移运算符`<<`：用于将二进制数向左移动指定的位数，相当于乘以2的幂。在LeetCode上，这样的题解可以帮助你提高对C++语言的理解，尤其是位操作和数值计算的掌握，同时锻炼了你的算法思维。通过不断解决这样的问题，你可以提升自己的编程能力和问题解决能力。

资源推荐

资源详情

资源评论

收起资源包目录

c++_c++编程基础之leetcode题解第29题两数相除.zip （2个子文件）

c++_c++编程基础之leetcode题解第29题两数相除

s1.cpp 856B

README.md 2KB

# [29. Divide Two Integers (Medium)](https://leetcode.com/problems/divide-two-integers/) Given two integers <code>dividend</code> and <code>divisor</code>, divide two integers without using multiplication, division and mod operator. Return the quotient after dividing <code>dividend</code> by <code>divisor</code>. The integer division should truncate toward zero. Example 1: <pre>Input: dividend = 10, divisor = 3 Output: 3</pre> Example 2: <pre>Input: dividend = 7, divisor = -3 Output: -2</pre> Note: <ul> <li>Both dividend and divisor will be 32-bit signed integers.</li> <li>The divisor will never be 0.</li> <li>Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231,  231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.</li> </ul> **Companies**: [Facebook](https://leetcode.com/company/facebook), [Microsoft](https://leetcode.com/company/microsoft), [Oracle](https://leetcode.com/company/oracle) **Related Topics**: [Math](https://leetcode.com/tag/math/), [Binary Search](https://leetcode.com/tag/binary-search/) ## Solution 1. ```cpp // OJ: https://leetcode.com/problems/divide-two-integers/ // Author: github.com/lzl124631x // Time: O(logD) where D is |dividend| // Space: O(1) class Solution { public: int divide(int dividend, int divisor) { if (!divisor) return 0; // divide-by-zero error bool pos1 = dividend > 0, pos2 = divisor > 0, pos = !(pos1^pos2); if (pos1) dividend = -dividend; if (pos2) divisor = -divisor; int q = 0, d = divisor, t = 1; while (t > 0 && dividend < 0) { if (dividend - d <= 0) { dividend -= d; q -= t; if ((INT_MIN >> 1) < d) { t <<= 1; d <<= 1; } } else { d >>= 1; t >>= 1; } } return pos? -q : q; } }; ```

评论收藏

内容反馈