Question :
Divide two integers without using multiplication, division and mod operator.
Anwser 1 :
class Solution {
public:
int divide(int dividend, int divisor) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int ret = 0;
if(dividend == 0 || divisor == 0) return 0;
int sign = 1; // 1 : positive; -1 : negative
if(dividend < 0) sign *= -1;
if(divisor < 0) sign *= -1;
long long tmpDiv = dividend;
long long divL = abs(tmpDiv);
long long tmpDivisor = divisor;
long long divisorL = abs(tmpDivisor);
while(divL >= divisorL){
int count = 1; // first: divL > divisorL
long long sum = divisorL; // long long, cal divisorL
while(sum + sum <= divL){
count += count;
sum += sum;
}
divL -= sum;
ret += count;
}
return sign * ret;
}
};
注意点:
1) 原理:累加除数,判断是否大于被除数
2) 设置符号位sign,判断符号
3) 对dividend和divisor都先转化成long long类型,防止负数转化成正整数时溢出
4) 除数之和sum,必须设置成long long,防止溢出(同2)
Anwser 2 :
class Solution {
public:
int divide(int dividend, int divisor) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
long long a = dividend;
long long b = divisor;
int sign = 1;
if(a < 0){
a = -a;
sign *= -1;
}
if(b < 0){
b = -b;
sign *= -1;
}
int d = 0;
while ( (b << d) <= a )
{
++d;
}
--d;
int res = 0;
for (int i = d; i >= 0; --i) {
if ( (b << i) <= a ) {
res += (1 << i); // high to low
a -= (b << i); // remaider
}
}
return sign * res;
}
};
Anwser 3:
class Solution {
private:
long long f[100];
public:
int bsearch(long long a[], int left, int right, long long key)
{
if (left > right)
return -1;
int mid = left + (right - left) / 2;
if (a[mid] == key)
return mid;
else if (a[mid] < key)
{
int pos = bsearch(a, mid + 1, right, key);
return pos == -1 ? mid : pos;
}
else
{
return bsearch(a, left, mid - 1, key);
}
}
int divide(int dividend, int divisor) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int sign = dividend < 0 ? -1 : 1;
if (divisor < 0)
sign *= -1;
long long div = dividend;
div = abs(div);
long long divisorL = divisor;
divisorL = abs(divisorL);
f[0] = divisorL;
int size = 1;
while(true)
{
if (f[size-1] >= div)
break;
f[size] = f[size-1] + f[size-1];
size++;
}
int num = 0;
long long sum = 0;
while(div > 0)
{
int pos = bsearch(f, 0, size - 1, div);
if (pos == -1)
break;
div -= f[pos];
num += (1 << pos);
}
return num * sign;
}
};
分享到:
相关推荐
自己写的一个完整的程序,包括main函数,在VS上面提交通过,但是放到leetcode上面会出现问题;只是作为一个参考,一起学习学习0.o!解决的问题有:第一:两个链表的最后一个值相加后进位的问题;第二:两个链表的...
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return ...
Leetcode two sum java 解法
先来看LeetCode-29上的Divide Two Integers题目要求: Divide two integers without using multiplication, division and mod operator. If it is overflow, return MAX_INT. 1 2 3 就是说不用乘法,除法,求模运算...
371 | [Sum of Two Integers](https://leetcode.com/problems/sum-of-two-integers/) | [C++](./C++/sum-of-two-integers.cpp) [Python](./Python/sum-of-two-integers.py) | _O(1)_ | _O(1)_ | Easy | LintCode | ...
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
Given an array of integers, find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where...
答案LeetCode_1_TwoSum LeetCode 问题:给定一个整数数组,找出两个数字,使它们相加为特定的目标数字。 函数 twoSum 应该返回两个数字的索引,使它们相加为目标,其中 index1 必须小于 index2。 请注意,您返回的...
Two-Sum leetcode两数之和代码 题目描述:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组...
Two Sum II - Input array is sorted LeetCode 344 Reverse String LeetCode 345 Reverse Vowels of a String 2 字符串 编号 题目 LeetCode 3 Longest Substring Without Repeating Characters LeetCode 13 Roman to...
There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). Java AC版本
vs code LeetCode 插件
大佬的leetcode刷题笔记(c++版本)
leetcode 两分球-2 问题1 () 问题2 () 问题3 ()
leetcode 两分球-1 问题1 () 问题2 () 问题3 ()
leetcode中文版
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
Leetcode\TwoSum\TwoSum.cs 问题: 业绩报告: 反转整数 代码: Leetcode\ReverseInteger\ReverseInteger.cs 问题: 业绩报告: 回文数 代码: Leetcode\PalindromeNumber\PalindromeNumber.cs 问题: 从排序数组中...
leetcode leetcode练习 twosum 问题 ;add two numbers问题;reverse integer问题;最大不重复子字符串长度问题;atoi问题;
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip