专栏首页用户6811391的专栏模拟除法与匹配单词—— LeetCode 第 29、30 题记

模拟除法与匹配单词—— LeetCode 第 29、30 题记

今天遇到的是一道不用除号来实现除法运算的中等难度的题,和一道在字符串中检测匹配特定词语的困难级别的题。然而中等难度的,花费两个多小时才完成,困难的这道半个多小时。感觉遇到题目,有清晰的解题方向真的是太重要了,会节省很多误打误撞的时间。来,题目走起~

第一题

「第 29 题:两数相除」

给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去(truncate)其小数部分,例如:truncate(8.345) = 8 以及 truncate(-2.7335) = -2

示例 1:
输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3

示例 2:
输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2
#来源:力扣(LeetCode)
#链接:https://leetcode-cn.com/problems/divide-two-integers

提示:被除数和除数均为 32 位有符号整数;除数不为 0;假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−2^31, 2^31 − 1]。本题中,如果除法结果溢出,则返回 2^31 − 1。

思路尝试

因为题目不许直接使用乘除法,首先想到的就是建立个循环累加,记录累加多少次便是结果。操作过程中,会出现被除数和除数一正一负、全负、全正、有零的情况;全部解决后,又遇到提示中标注的数值范围情况;再到最后,因为累加的过程太繁琐、提交测试结果是超出时间限制。GG,一个小时白忙活。

直接累加不行,联想到我们手算除法时用到的竖式,相当于每次提出若干位来先进行局部除法,再逐位完成整个运算。那这里我们也模拟竖式除法的流程,在进行局部除法时采用累加来实现,这样即可不用乘除号来实现整个除法运算了。

代码实现

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
    	# 先定义通过累加计算除法结果的函数
    	# 该运算是假设 a 和 b 均为正数
        def div(a,b):
            count = 0
            adding = b
            while adding<= a:
                count+=1
                adding += b
            rest_part = a-adding+b
            # 返回商和余数
            return count,rest_part
		# 结果正负数标志
        negative = False
        # 被除数或除数为 0 的情况单独考虑
        if divisor==0:
            return None
        if dividend == 0:
            return 0
        # 若一正一负,结果为负
        if dividend >0 and divisor<0:
            negative = True
        if dividend <0 and divisor>0:
            negative = True
        # 将被除数和除数都取绝对值来保证均为正数参与运算
        divisor = abs(divisor)
        dividend = abs(dividend)
        
        # 将被除数和除数转化为字符串,方便从左开始取数字
        x =str(dividend)
        l_x = len(x)
        y = str(divisor)
        l_y = len(y)

		# result 以字符串形式存最终结果
        result =""
        # pre_str 用与运算中暂存每一步的余数
        pre_str = ""
        # 用与判断是否为竖式中次局部运算
        start = True
        # 比如 12345/23 ,我们会先提取被除数的前两位 12
        # 用 i 作为索引提取被除数中特定位置上的数字
        for i in range(l_y-1,l_x):
			# 如果是刚进入循环
            if start:
            	# 从头提取被除数前 i 位
                temp = x[:i+1]
                start = False
            else:
            	# 将上一次循环结果中的余数与下一位组合成新数
                temp = pre_str+x[i]
            # 调用我们先前定义的累加运算获取除法的商和余数
            p,q = div(int(temp),divisor)
            # 将每次得到的商转化位字符串保存到 result 中
            result+=str(p)
            # 得到的余数,要用于后续计算
            if q>0:
                pre_str = str(q)
            else:
                pre_str = ""
        # 若结果不为空,转化成整数
        if result:
            count = int(result)
        else:
            return 0
        
        # 正负标志判断        
        if negative:
            count = -count
		# 超出提示中的范围
        if count>2**31-1:
            return 2**31-1
		# 将结果返回
        return count

提交测试表现:

执行用时 : 44 ms, 在所有 Python3 提交中击败了 57.50% 的用户
内存消耗 : 13.8 MB, 在所有 Python3 提交中击败了 7.69% 的用户

观摩题解

参考了几份题解,好多是将十进制数字转化二进制位来考虑、运用到了位运算符:

<< 左移动运算符:运算数的各二进位全部左移若干位,由 << 右边的数字指定了移动的位数,高位丢弃,低位补0。

>> 右移动运算符:把">>"左边的运算数的各二进位全部右移若干位,>> 右边的数字指定了移动的位数

a << b 相当于 a * 2**b
a >> b 相当于 a // 2**b

大致思路就是将十进制的乘除问题转化到二进制的移位问题。这里先不深究,之后有机会接触多一些位运算再看。

第二题

「第 30 题:串联所有单词的子串」

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配,中间不能有其他字符,但不需要考虑 words 中单词串联的顺序。

示例 1:
输入:
  s = "barfoothefoobarman",
  words = ["foo","bar"]
输出:[0,9]
解释:
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。

示例 2:
输入:
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
输出:[]

#来源:力扣(LeetCode)
#链接:https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words

思路尝试

假设单词列表中有 n 个单词,每个单词长度 l,那么与之匹配的子串长度为 n*l。所以我们对字符串遍历,看该位能否构成该长度的子串。若可以,则取该子串前 l 位,检测是否为列表中的单词,若不是,可以进行下一位检测了。若是的话,则继续检测剩余子串构成的单词能否完全匹配。

代码实现

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        result = []
        # 空字符串或空列表特殊处理
        if s =="" or words==[]:
            return result
        # 单词个数
        word_num = len(words)
        # 单词长度
        l = len(words[0])
		# 遍历字符串
        for i in range(len(s)):
        	# 长度检测、首 n 位是否匹配单词检测
            if i+word_num*l<=len(s) and s[i:i+l] in words:
            	# 复制下列表,后续匹配过的单词会剔除
                word_copy = words[:]
				# 对子串遍历
                for j in range(word_num):
                	# 按单词长度提取子串
                    word = s[i+j*l:i+(j+1)*l]
                    # 若子串与单词匹配,则将列表中单词删除
                    if word in word_copy:
                        word_copy.remove(word)
                # 若最终列表被删空,则子串完全与列表匹配
                if word_copy==[]:
                	# 将该位索引添加到结果中
                    result.append(i)
        return result

提交测试表现:

执行用时 : 3444 ms, 在所有 Python3 提交中击败了 6.14% 的用户
内存消耗 : 13.7 MB, 在所有 Python3 提交中击败了 9.52% 的用户

比较惨,现在想来我对每一位都进行长度检测没必要,第一次出现不够长度时后续都不用做检测了。但感觉提升也不会特别多吧,我们继续看看题解。

观摩题解

有代码用到了“滑动窗口”,结合着代码来看下:

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        res = []
        write = []
        # 空列表处理
        if len(words) == 0:
            return []
        # 字符串长度不够情况处理
        if len(s) < len(words)*len(words[0]):
            return []
        dic = {}
        flag = 0
        # 将单词存到字典以及 write 列表中
        for i in words:
            try:
                dic[i]+=1
            except KeyError:
                dic[i]=1
                flag+=1
                write.append(i)
        
        # 设定窗口左右标
        left, right = 0, len(words)*len(words[0])
        # while 循环来将上述左右标圈定的窗口来移动
        while right<=len(s):
            n,start = 0,left
            per = len(words[0])
            # 生成 tag 字典,键值是所以单词,值为0
            tag = dict(zip(write,[0]*flag))
            # 根据单词个数来循环
            while n < len(words):
                # 若dic字典中有单词等长子串组成的单词
                if dic.get(s[start:start+per]):
                	# tag 字典中该单词数目小于 dic 字典
                    if tag[s[start:start+per]] < dic[s[start:start+per]]:
                    	# 为 tag 字典中记录加一
                        tag[s[start:start+per]] += 1
                        # 匹配成功单词个数加一
                        n+=1
                        # 调整匹配位置
                        start+=per
                    # 不能满足跳出 while 循环
                    else:
                        break
                else:
                    break
            # 如果执行到此 n 为单词数,说明上述循环完全执行,则将左索引记录
            if n == len(words):
                res.append(left)
            # 移动左右标
            left+=1
            right+=1
        # 返回结果
        return res
#作者:my10yuan
#链接:https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/solution/hua-dong-chuang-kou-zi-dian-jian-suo-ji-shu-by-wu-/

测试表现有明显提高:

执行用时 : 980 ms, 在所有 Python3 提交中击败了 42.78% 的用户
内存消耗 : 13.9 MB, 在所有 Python3 提交中击败了 9.52% 的用户

所谓滑动窗口,其实是用两个变量控制截取子串的左右位置,将该截取的部分控制到与所有单词长度等长,形成一个“窗口”,检测窗口内的子串是否满足题意,之后移动该窗口继续下一位置的检测。

同时,该代码中对匹配单词列表的过程中,使用到了字典来记录每个单词的数目,并以此来检测子串中个数是否超出等,这个还是挺值得借鉴的。

结论

今天的两道题收获挺多的!

第一题带来的收获首先是在解决问题时,可以联想生活中我们其它手算的便捷方法,然后用代码在这些过程中予以实现;此外,十进制问题的解决可以向二进制方向靠拢,通过位运算来协助解决,这部分我接触得太少,之后要专门学习下。

第二题则是观摩学习了这份滑动窗口加字典的代码,结合代码对滑动窗口有了更清晰的认识,匹配列表元素时也学到了可以建立字典来记录个数做比较这种操作。

今天效率不高,题目费时、研究别的解法也是有些慢,对 25、26 题的补充要继续推迟下了,明天争取搞定。

本文分享自微信公众号 - TTTEED(TEDxPY),作者:TED

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-04-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python 版 LeetCode 刷题笔记 #3 无重复字符的最长子串

    今天这题目乍一看,在字符串中找来遍历即可,但实际操作下来,还是有些复杂的,也配得上其中等难度的定位了。

    TTTEED
  • Python print 玩转“点阵字”

    学习python3第一句大概率是 print(“hello world”) 吧?既然可以逐行逐个地输出字符,那么把字符组成汉字应该也不难吧?经过一番搜索与尝试,...

    TTTEED
  • Python易容术

    前两天看到篇介绍英伟达StyleGAN生成逼真假脸的文章,其源码正是通过Python和Tensorflow实现的,利用AI生成并不存在的头像图,来感受下:

    TTTEED
  • 用高仿面具试验人脸识别系统,微信、支付宝、机场安检统统被骗

    面部识别技术已被广泛视为一种安全工具,政府和公司等都在广泛使用,但事实证明,这项技术并不可靠。人工智能公司Kneron的研究人员周四表示,他们能够使用一张高仿真...

    AiTechYun
  • 美团点评助推校园食品安全建设,张川强调餐饮企业要承担社会责任

    8月10日,由美团点评支持的“企业共治 校园行”高峰论坛,在清华大学蒙民伟多功能厅举办。

    聚焦商讯
  • request+goquery+mahonia实现自动抓取网页数据

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/hotqin888/article/det...

    hotqin888
  • 完结篇:Openshift实战视频展示系列5&6&1

    针对Openshift,大卫的同事任龙飞归纳了六个使用场景,并录制了六个视频。此外,如果有朋友想参与Openshift技术讨论,可以留下微信号,我会添加然后拉进...

    魏新宇
  • 基础知识:if条件、while循环、fo

    1、实现用户输入用户名和密码,当用户名为 seven 且 密码为 123 时,显示登陆成功,否则登陆失败!

    py3study
  • 这些优化技巧可以避免我们在 JS 中过多的使用 IF 语句

    最近在重构代码时,我发现早期的代码使用太多的 if 语句,其程度是我从未见过的。这就是为什么我认为分享这些简单的技巧是非常重要的,这些技巧可以帮助我们避免过多的...

    前端小智@大迁世界
  • 我在近期求职中遇到的前端面试问题及其解法

    在今天的文章中,我想跟大家聊聊自己最近在 COVID-19 疫情下的求职经历中遇到的问题。另外,我还把自己的准备工作整理成一份资源清单供大家参考。

    深度学习与Python

扫码关注云+社区

领取腾讯云代金券