LeetCode开心刷题十六天——29. Divide Two Integers*

超、凢脫俗 2023-08-17 15:14 90阅读 0赞

From now on,I grade the questions I've done,\* less means more difficult

\*\*\* done by myself

\*\*need see answer,but I can reappear it

\*need see answer&hard to reappear

29. Divide Two Integers

Medium

7003349FavoriteShare

Given two integers `dividend` and `divisor`, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing `dividend` by `divisor`.

The integer division should truncate toward zero.

Example 1:

Input: dividend = 10, divisor = 3
    Output: 3

Example 2:

Input: dividend = 7, divisor = -3
    Output: -2

Note:

*  Both dividend and divisor will be 32-bit signed integers.
 *  The divisor will never be 0.
 *  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.

Accepted

202,728

Submissions

1,254,885

The main problem of this question is boundary problem.Use of special operator such as INT\_MAX ,^(xor)

greatly simplfied the code.Now I will paste my code and analyse some mistake point

#include<algorithm>
    #include <iostream>
    #include <map>
    #include <queue>
    #include <vector>
    
    using namespace std;
    
    class Solution
    {
    public:
        int divide(int divided,int divisor)
        {
            long long m=abs((long long)divided),n=abs((long long)divisor);
            //cout<<m<<" "<<n<<endl;
            long long res=0,p=1,t=n;
            if(m<n) return 0;
            while(m>(t<<1))
            {
                t<<=1;
                p<<=1;
            }
            res+=p+divide(m-t,n);
            //cout<<"res"<<res<<endl;
            if((divided>0)^(divisor>0)) res=-res;
            //at first,I only write following sentence
            return (res>INT_MAX)?INT_MAX:res;
    
        }
    };
    
    int main()
    {
       int a,b,res;
       cin>>a>>b;
       Solution s;
       res=s.divide(a,b);
        cout<<res<<endl;
        return 0;
    }

1.First thing is clarify each step;

whether the current function has a return value;if it has which variable should we use to get this value?

My fault is put this directly.this need a variable=?:

(res>INT_MAX)?INT_MAX:res;
    
    2.Really understand what substitution mean,I use m,n to replace divide divisor during operational process
    make it abs and long long.But when you write a code ,when you feel you need one to replace then i define one,
    but if we directly see the answer,The bad thing is we directly see the replace variable even before we understand
    why we need this ,if we cannot make it clear,things like recursion can go wrong.
    PS:this following sentence meets my requirements perfectly.xor opperation >><< operation ,they are not commonly
    used but they can greatly simplify calculations.

if((divided>0)^(divisor>0)) res=-res;

转载于:https://www.cnblogs.com/Marigolci/p/11155239.html