模拟除法与匹配单词—— 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 题的补充要继续推迟下了，明天争取搞定。