【leetcode 力扣刷题】数学题之除法:哈希表解决商的循环节➕快速乘求解商

这篇具有很好参考价值的文章主要介绍了【leetcode 力扣刷题】数学题之除法:哈希表解决商的循环节➕快速乘求解商。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

166. 分数到小数

题目链接:166. 分数到小数
题目内容:
【leetcode 力扣刷题】数学题之除法:哈希表解决商的循环节➕快速乘求解商,力扣刷题,leetcode,散列表,算法,除法,溢出
题目是要我们把一个分数变成一个小数,并以字符串的形式返回。按道理,直接将分子numerator除以分母denominator就得到了小数,转换成string返回就好。题目要求里指出了特殊情况——小数部分如果有循环,就把循环节括在括号里

那么问题来了,怎么知道有没有循环呢。循环节就是一段循环出现的数字,我们即便是存下来小数部分的每一位数,也不能说有数字重复了就是循环节的开始,比如0.121113,我们不能在1第二次出现的时候就判断上一个1到这个1之前就是循环节。那么是以什么重复出现判断是有循环节呢? A➗B得到商为C,余数为R,计算小数部分时每后移一位将当前余数补0进行运算, 最终余数R==0,表示能够整除,直接将结果转换成string即可;对于有循环节的小数部分,出现重复余数时,表示有循环节。因为从该余数开始计算,一定会再变成这个余数,这样循环下去。那么这个余数第一次计算出的小数,到第二次出现这个余数对应的那位小数,之间的小数就是循环节。 【leetcode 力扣刷题】数学题之除法:哈希表解决商的循环节➕快速乘求解商,力扣刷题,leetcode,散列表,算法,除法,溢出
判断一个余数是否出现过,用hash表记录。由于同时要记录余数,以及余数出现的位置【以便确定循环节开始和结束位置】,因此用map。代码如下(C++):

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
    	//防止溢出,32位int转换成64位的long
        long _numerator = numerator;
        long _denominator = denominator;
        //如果分子为0,直接返回零
        if(_numerator == 0)
            return "0";
        //能够整除,直接返回
        if(_numerator % _denominator == 0) 
            return to_string(_numerator/_denominator);
		//不能整除的情况,ans表示结果字符串
        string ans;
        //异号先添加负号
        if(_numerator>0&&_denominator<0 || _numerator<0&&_denominator>0){
            ans.push_back('-');
        }
        //都变成绝对值,计算结果数值部分
        _numerator = abs(_numerator);
        _denominator = abs(_denominator);
		//整数部分为0
        if(_numerator < _denominator)
        	ans.push_back('0');
        //计算整数部分
        else{ 
            ans = ans + to_string(_numerator/_denominator);
            //numerator变成余数
            _numerator = _numerator % _denominator;
        }
		//添加小数点
        ans.push_back('.');     
        //map记录余数以及出现的位置
        unordered_map <long,int> remainder;
        int idx = ans.size();
        remainder.insert({_numerator,idx});
        while(_numerator){
            _numerator *= 10;
            ans = ans + to_string(_numerator/_denominator);
            _numerator = _numerator % _denominator; 
            //如果余数重复出现就break,有循环 
            if(remainder.count(_numerator))
                break;
            remainder.insert({_numerator,++idx});                
        }
        //如果余数不为0,就有循环,循环节部分添加()
        if(_numerator) {
            ans.insert(remainder[_numerator],"(");
            ans += ')';
        }
        return ans; 
    }
};

29. 两数相除

题目链接:29. 两数相除
题目内容:
【leetcode 力扣刷题】数学题之除法:哈希表解决商的循环节➕快速乘求解商,力扣刷题,leetcode,散列表,算法,除法,溢出
理解题意就是做整数除法,返回结果截取小数部分。比如-7/3 = -2,9/4 =2这样。问题在于两个地方:1、给的dividend和divisor,可能结果会溢出;2、不能使用乘法、除法和求余,但是要完成除法求得商。
对于第一个问题,单独考虑一些情况:

  • 只有在dividend = -2^31,且divisor = -1的时候,结果为2^31,会溢出;
  • 当dividend = 0 时,直接返回0;
  • 当divisor = 1 时,直接返回dividend;

对于第二个问题,乘法的本质是加法,可以用快速乘这个方法,用加法来完成乘法操作。除法的本质是减法,而加减是一样的,因此也能用快速乘来完成。 因此本题的重点是快速乘。
另外还需要注意dividend和divisor的符号问题,两个数有四种符号组合,同为正、同为负、一正一负、一负一正,只有在异号的情况下,结果才为负。 确定结果负号后,数值部分计算,就可以将两个数变成都是正的。但此题当dividend 或者 divisor是-2^31时,变成正数就会溢出,因此统一变成负数

快速乘

快速乘,即用加法来实现乘法,但是不是一个一个加,而是将数字每次翻倍,成倍成倍的加。7*5可以看成是7+7+7+7+7,5的二进制表示是(101),7+7+7+7+7组合一下,等于1*[(7+7)+(7+7)] + 0*(7+7) + 1*7,即第一次是+7,之后是+(7+7),再下一轮是+[(7+7)+(7+7)],每一轮要加的是上一轮的2倍,这个两倍直接用add = add + add来实现,也不需要乘法。每一轮还需要乘以倍数的二进制表达式中对应位的数值【即0或者1】。代码模板如下(C++):

int quick_mul(int x, int n){
	int ans = 0; 
	int add = x;
	while(n){
		if(n&1) //末位为1
		//【实际上由于n的右移操作,这一步是在看对应位是否为1
		//比如5 = 101,第一次循环101,末位为1,加上7
		//第二次10,末位为0,应该加7+7,实际加0
		//第三次1,末位为1,加上(7+7)+(7+7)】
			ans += add;  //结果ans加上当前的数add
		add += add; //add翻倍
		n >>= 1; //n右移一位
	}
	return ans;
}

解法一:快速乘变种

快速乘是在知道了一个数要乘以几之后快速求解答案的过程,除法是要去求被除数是除数的几倍,因此不能直接使用快速乘,但是可以借用快速乘中数字加倍的思想,快速找到商。 判断dividend里面还能不能有一个完整的divisor,是需要|dividend| >= |divisor|,因为都变成了负数,即dividend <= divisor就证明dividend里面有至少一个divisor,商还能加上一部分。那么dividend里面有多少个divisor需要去试,先试有1个【add = divisor】,然后试有2个【add = add + add】,然后试有4个【继续add = add + add】,然后试有8个……这样循环下去,直到某个数使得dividend > add + add了,就说明add + add里面倍数太大了,应该是add里面的倍数。之后dividend减去当前add,剩下的继续去找里面有几个divisor。
这里需要注意判断dividend < add + add,可能有溢出:当add 在-2^31 ~ -2^30之间,add+add小于-2^31,就溢出了,所以应该改成dividend - add < add。
完整代码如下(C++):

class Solution {
public:
    int divide(int dividend, int divisor) {
        //特殊情况
        if(dividend == 0) return 0;
        if(divisor == 1) return dividend;
        //可能溢出的情况
        if(dividend == INT_MIN && divisor == -1) return INT_MAX;
        if(divisor == INT_MIN){
            return dividend == INT_MIN ? 1:0;
        }
        //防止溢出,正数变复数
        int rev = 1;
        if(dividend > 0){
            dividend = -dividend;
            rev = -rev;
        }
        if(divisor > 0){
            divisor = -divisor;
            rev = -rev;
        }

        int ans = 0;   
        //被除数和除数都为负数,被除数小于等于除数商才大于0    
        while(dividend <= divisor){
            int add = divisor;
            int result = 1;
            while(dividend - add <= add){
                result <<= 1; //当前商翻倍
                add <<= 1;    //翻倍
            }  
            ans += result;  //加上部分结果
            dividend -= add;  //剩余部分继续求商       
        }
        return ans*rev; //乘以符号翻转
    }
};

这里在dividend更新成dividend - add后,add又变成divisor从1倍开始尝试,这其实是多余的,可以将add+=add整翻倍过程的数值记录起来,优化代码(C++):

//记录add翻倍过程中,比dividend小的数值
 while (add.back() >= dividend - add.back()) {
	add.push_back(add.back() + add.back());
}
int ans = 0;
for (int i = add.size() - 1; i >= 0; --i) {
	//dividend比add[i]更小,add里面的倍数能够加载商里面
	if (add[i] >= dividend) {
		//下标是i,对应的倍数是2^i,可以用左移i位来实现
		ans += (1 << i);
		//dividend减去对应的add
		dividend -= add[i];
	}
}

解法二: 二分查找 + 快速乘

还有一种办法是尝试每一个n,看当前的n*divisor和dividend的关系,因为dividend和divisor都变成了负数,因此dividend < n*divisor才能满足条件,n继续增大去比较。这里的n*divisor就用上述的快速乘去实现——需要改动一点,就是最后返回dividend 和 n*divisor 大小关系。
n是0到2^31-1之间的一个数,要找到合适的n,可以用二分法,相较于依次挨个比较,时间复杂度更优,代码如下(C++):

class Solution {
public:
    bool quick_mul(int divisor, int n, int dividend){
        int ans = 0;
        int add = divisor;
        while(n){
        	//末位为1,要加上一部分
            if(n&1){
            	//如果计算过程中发现ans更小,就说明n太大了,直接返回false
                if(dividend - add > ans )   
                    return false;
                ans += add;
            }
            //如果当前不是最后一位,还要循环几轮
            if(n!=1){
            	//而下一轮要用到的add已经比dividend更小【里面包括的divisor的倍数更多】
            	//直接终止,返回false
                if(dividend - add > add)
                    return false;
                add += add;
            }
            n >>= 1;
        }
        return true;
    }

    int divide(int dividend, int divisor) {
        //特殊情况
        if(dividend == 0) return 0;
        if(divisor == 1) return dividend;
        //可能溢出的情况
        if(dividend == INT_MIN && divisor == -1) return INT_MAX;
        if(divisor == INT_MIN){
            return dividend == INT_MIN ? 1:0;
        }
        //防止溢出,正数变复数
        int rev = 1;
        if(dividend > 0){
            dividend = -dividend;
            rev = -rev;
        }
        if(divisor > 0){
            divisor = -divisor;
            rev = -rev;
        }

        int ans = 0, left = 1, right = INT_MAX;
        //二分查找的过程
        while(left <= right){
            int mid = left + ((right - left)>>1);
            if (quick_mul(divisor, mid, dividend)){
                ans = mid; //当前的mid是dividend <= mid * dividor,先赋值给and
                if(mid == INT_MAX)
                    break;
                left = mid + 1;
            }
            else{

                right = mid - 1;
            }
        } 
        return ans*rev; //乘以符号翻转
    }
};

二分查找过程是官方题解,但是我不太理解为什么一定要and = mid这一步赋值,直接返回mid是不对的……
解释:在-7/3这个情况下,结果是-2;left一直为1,right一直减小到3,此时mid = 2,对应quick_mul返回true,left = 3;此时仍然满足循环条件,mid 更新为 3 ,但是此时quick_mul返回的是false。也就是一个quick_mul返回true的mid可能是答案,需要记录,之后如果还有mid满足条件就更新。但是满足条件后mid可能还会更新,但更新后可能就不满足条件了。因此直接返回mul是不正确的。文章来源地址https://www.toymoban.com/news/detail-689476.html

到了这里,关于【leetcode 力扣刷题】数学题之除法:哈希表解决商的循环节➕快速乘求解商的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • CF1781 D. Many Perfect Squares [数学题]

    传送门:CF [前题提要]:一道有意思的数学题 直接想这道题是不好想的(博主当时就完全没有思路).那么 考虑将一个大问题分解成一个小问题想一下(感觉这种思考方式在CF题中还是挺常见的) ,考虑如果同时存在多个完全平方数,那么必然满足存在 两个完全平方数 .而当我们确定了

    2024年02月20日
    浏览(35)
  • 一道经典的小学数学题,和它背后的贪心算法(35)

    小朋友们好,大朋友们好! 我是猫妹,一名爱上Python编程的小学生。 欢迎和猫妹一起,趣味学Python。 今日主题 这个五一小长假,你玩得怎么样? 今天,咱们先做一道经典的小学数学题,抛砖引玉,然后了解下贪心算法。 一个地主临终前留下了遗嘱,将自己的11头牛分给三

    2024年02月02日
    浏览(41)
  • 使用python语解决一个小学数学题----鸡兔同笼问题

    问: 鸡(chicken)和兔子(rabbit)被关进一只笼子里,已知头(head)一共有40个,腿(leg)一共有120个,请问笼子里有几只鸡,几只兔子? [root@localhost /]# vim 1.py 编辑: head = 40 leg = 120 for chicken in range(0,head): rabbit = head - chicken if chicken * 2 + rabbit * 4 == 120: print chicken print rabbit [

    2023年04月08日
    浏览(38)
  • 华为云天筹AI求解器:智能世界是道迷人的数学题

    二战期间,盟军要为规模空前庞大、结构无比复杂的潜艇与舰船规划路线,制定运输策略,于是军方请来了数学家帮助破解这个复杂的管理难题。一门横跨数学与管理学的全新学科体系——运筹学(Operational Research)就这样诞生了。 中国翻译家从“运筹帷幄之中,决胜千里之

    2024年02月13日
    浏览(37)
  • 深度学习实战44-Keras框架下实现高中数学题目的智能分类功能应用

    大家好,我是微学AI ,今天给大家介绍一下深度学习实战44-Keras框架实现高中数学题目的智能分类功能应用,该功能是基于人工智能技术的创新应用,通过对数学题目进行智能分类,提供个性化的学习辅助和教学支持。该功能的实现可以通过以下步骤:首先,采集大量的高中数

    2024年02月15日
    浏览(54)
  • 【leetcode 力扣刷题】汇总区间//合并区间//插入区间

    题目链接:228.汇总区间 题目内容: 看题目真是没懂这个题到底是要干啥……实际上题目要求的 恰好覆盖数组中所有数字 的 最小有序 区间范围列表,这个最小是指一个区间范围小。比如能够覆盖{2,3,4,6}的区间可以是[2,6],但是5在区间内,却不在数组内,因此这个区间不是最

    2024年02月10日
    浏览(37)
  • leetcode 力扣刷题 旋转矩阵(循环过程边界控制)

    下面的题目的主要考察点都是,二维数组从左上角开始顺时针(或者逆时针)按圈遍历数组的过程。顺时针按圈遍历的过程如下: 对于每一圈,分为四条边 ,循环遍历就好。这时,对于 四个角 的元素的处理,可以将四条边的遍历分为以下两种情况: 第一种:每条边都从对

    2024年02月12日
    浏览(48)
  • 【leetcode 力扣刷题】移除链表元素 多种解法

    题目链接:203.移除链表元素 题目内容: 理解题意:就是单纯的删除链表中所有值等于给定的val的节点。上一篇博客中介绍了链表的基础操作,在删除链表中节点时,需要注意的是头节点: 如果没有虚拟头节点,那么对头节点的删除需要做不同的处理,head = head-next; 如果有

    2024年02月12日
    浏览(48)
  • 【leetcode 力扣刷题】链表基础知识 基础操作

    在数据结构的学习过程中,我们知道线性表【一种数据组织、在内存中存储的形式】是线性结构的,其中线性表包括顺序表和链表。数组就是顺序表,其各个元素在内存中是连续存储的。 链表则是由 数据域 和 指针域 组成的 结构体 构成的,数据域是一个节点的数据,指针域

    2024年02月12日
    浏览(39)
  • 【leetcode 力扣刷题】回文串相关题目(KMP、动态规划)

    题目链接:5. 最长回文子串 题目内容: 题目就是要我们找s中的回文子串,还要是最长的。其实想想,暴力求解也行……就是遍历所有的子串,同时判断是不是回文串,是的话再和记录的最大长度maxlen比较,如果更长就更新。时间复杂度直接变成O(n^3)。 优化的点在于,假设子

    2024年02月09日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包