Вопрос. Даны два целых числа dividend
и divisor
. Разделите два целых числа без использования операций умножения, деления и модификатора.
Верните частное после деления dividend
на divisor
.
Целочисленное деление должно усекаться до нуля.
Пример 1:
Input: dividend = 10, divisor = 3 Output: 3
Пример 2:
Input: dividend = 7, divisor = -3 Output: -2
Примечание.
- И делимое, и делитель будут 32-битными целыми числами со знаком.
- Делитель никогда не будет равен 0.
- Предположим, что мы имеем дело со средой, которая может хранить целые числа только в диапазоне 32-битных целых чисел со знаком: [−231, 231 − 1]. Для решения этой задачи предположим, что ваша функция возвращает 231 − 1, когда результат деления переполняется.
Полностью вопрос можно посмотреть здесь.
Подход 1. Как обычно, начнем с чего-то прямолинейного и наивного. Умножение - это многократное сложение. Отсюда мы можем прийти к следующему коду —
//Approach 1: //RunTime: Time Limit Exceeded //Memory usage: N/A class Solution { public int divide(int dividendI, int divisorI) { int sign = 1; int signD = 1; double dividend = dividendI; double divisor = divisorI; if(divisor<0){ sign = -1; divisor*=-1; } if(dividend<0){ signD = -1; dividend*=-1; } int q = 0; if(divisor==1){ double result = dividend*sign*signD; if(result>Integer.MAX_VALUE || result<Integer.MIN_VALUE){ return Integer.MAX_VALUE; } return (int)result; } while(dividend>=divisor){ dividend-=divisor; q++; } return q*sign*signD; } }
Очевидно, нам предстоит долгий путь.
Подход 2. После нескольких часов тяжелого труда нам стало лучше . Еще в школе, помните, как мы делали деление в столбик. Следующий код делает именно это для нас —
//Approach 2: //Runtime: 1ms //Memory usage: 32.5MB class Solution { public int divide(int dividend, int divisorI) { int signDs = getSign(divisorI); int signDd = getSign(dividend); double divisor = (double)divisorI * signDs; double q = 0; double rem = 0; char[] chars = String.valueOf(dividend).toCharArray(); for(char c : chars){ if(c=='-'){ continue; } rem = rem * 10 + (c - '0'); int tempQ = 0; while(rem>=divisor){ tempQ++; rem-=divisor; } q=q*10 + tempQ; } if(q*signDs*signDd > Integer.MAX_VALUE){ return Integer.MAX_VALUE; } return (int)(q*signDs*signDd); } private int getSign(int num){ if(num<0){ return -1; } return 1; } }
Больше постов ищите здесь.
Удачи и Чао!