029两数相除

红太狼 2021-12-21 06:51 213阅读 0赞

1 #pragma once
      2 #include "000库函数.h"
      3 /******************自解***********************/
      4 //虽然很快通过，但不满足题中不允许使用除法的要求   36ms
      5 class Solution {
      6 public:
      7     int divide(int dividend, int divisor) {
      8         if (divisor == 0)return 0;
      9         double i = (double)dividend / (double)divisor;
     10         if ((i < -1 * pow(2, 31)) || (i > pow(2, 31) - 1))return pow(2, 31) - 1;
     11         else return (int)i;
     12     }
     13 };
     14 //超出时长
     15 class Solution {
     16 public:
     17     int divide(int dividend, int divisor) {
     18         if (divisor == 0)return 0;
     19         int flag = 1;
     20         double k = (double)dividend;
     21         if (k < 0) {
     22             k *= -1;//防止此处溢出
     23             flag *= -1;
     24         }
     25         double t = (double)divisor;
     26         if (t < 0) {
     27             t *= -1;
     28             flag *= -1;
     29         }
     30         double i= 0;
     31         double n = t;
     32         while (k >= t+t) {
     33             i += 2;
     34             t += n;
     35             k -= n;
     36 
     37         }
     38         if (k >= t)
     39             ++i;
     40         i *= flag;
     41         if ((i < -1 * pow(2, 31)) || (i > pow(2, 31) - 1))return pow(2, 31) - 1;
     42         else return (int)i;
     43     }
     44 };
     45 /*********************博客答案***************************/
     46 //采用移位运算  36ms
     47 class Solution {
     48 public:
     49     int divide(int dividend, int divisor) {
     50         if (divisor == 0 || (dividend == INT_MIN && divisor == -1)) return INT_MAX;
     51         long long m = abs((long long)dividend), n = abs((long long)divisor), res = 0;
     52         int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
     53         if (n == 1) return sign == 1 ? m : -m;
     54         while (m >= n) {
     55             long long t = n, p = 1;
     56             while (m >= (t << 1)) {
     57                 t <<= 1;
     58                 p <<= 1;
     59             }
     60             res += p;
     61             m -= t;
     62         }
     63         return sign == 1 ? res : -res;
     64     }
     65 };
     66 
     67 class Solution {
     68 public:
     69     int divide(int dividend, int divisor) {
     70         long long m = abs((long long)dividend), n = abs((long long)divisor), res = 0;
     71         if (m < n) return 0;
     72         while (m >= n) {
     73             long long t = n, p = 1;
     74             while (m > (t << 1)) {
     75                 t <<= 1;
     76                 p <<= 1;
     77             }
     78             res += p;
     79             m -= t;
     80         }
     81         if ((dividend < 0) ^ (divisor < 0)) res = -res;
     82         return res > INT_MAX ? INT_MAX : res;
     83     }
     84 };
     85 //使用递归  36ms
     86 class Solution {
     87 public:
     88     int divide(int dividend, int divisor) {
     89         long long res = 0;
     90         long long m = abs((long long)dividend), n = abs((long long)divisor);
     91         if (m < n) return 0;
     92         long long t = n, p = 1;
     93         while (m > (t << 1)) {
     94             t <<= 1;
     95             p <<= 1;
     96         }
     97         res += p + divide(m - t, n);
     98         if ((dividend < 0) ^ (divisor < 0)) res = -res;
     99         return res > INT_MAX ? INT_MAX : res;
    100     }
    101 };
    102 
    103 
    104 void T029() {
    105     Solution s;
    106     cout << s.divide(10, 3) << endl;
    107     cout << s.divide(7, -3) << endl;
    108 }

转载于:https://www.cnblogs.com/zzw1024/p/10530514.html