YoungForest's blog

LeetCode weekly contest 117

发表于 2018-12-30 更新于 2026-04-28 分类于 LeetCode Disqus：

今天参加LeetCode weekly contest 117, 采取了不同的策略：边做题边写博客总结。期望这样可以真实地记录所思所想，提高写博客的效率。因为之前2次，事后写博客总是耽误几天时间才写完。

965. Univalued Binary Tree

一道很简单、很弱智的题目，直接DFS/BFS即可。因为BFS在遇到异常节点的时候可以直接返回，更方便。我选择了BFS实现。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isUnivalTree(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if root == None: return True
        univalue = root.val
        queue = [root]
        
        while len(queue) > 0:
            node = queue.pop(0)
            if node.left != None: queue.append(node.left)
            if node.right != None: queue.append(node.right)
            if node.val != univalue: return False
            
        return True

967. Numbers With Same Consecutive Differences

第二题也是一道十分弱智的题目，直接搜索即可。需要注意的地方是，N == 1 和 K == 0时的特殊处理。

from functools import reduce

class Solution:
    def numsSameConsecDiff(self, N, K):
        """
        :type N: int
        :type K: int
        :rtype: List[int]
        """
        if N == 1:
            return [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
        ret = []
        hashmap = {}
        for i in range (10):
            hashmap[i] = []
            if K == 0:
                hashmap[i].append(i)
            else:
                if i + K <= 9:
                    hashmap[i].append(i + K)
                if i - K >= 0:
                    hashmap[i].append(i - K)
        
        
        def helper(n, digits):
            if n == N:
                ret.append(reduce(lambda x, y: x * 10 + y, digits))
                return
            for i in hashmap[digits[n-1]]:
                digits.append(i)
                helper(n+1, digits)
                digits.pop()
                
        for i in range(1, 10):
            digits = [i]
            helper(1, digits)
            
        return ret

966. Vowel Spellchecker

由于前2题用brute search都解决了，本题我也上来就直接干。结果TLE了，因为暴力法的时间复杂度为O(MN)，M = len(wordlist), N = len(queries)。
怎样才能进一步降低时间复杂度呢？我脑子中闪过的第一个词是单词书(Tire)，最近刚在算法第四版中学到这一技术。时间复杂度为O(max(N * wordlist中最长单词的长度, M), 不出意料的话，可以AC，现在已经11:46了。应该写不完了，让我先看一下第4题吧。

class Solution:
    def spellchecker(self, wordlist, queries):
        """
        :type wordlist: List[str]
        :type queries: List[str]
        :rtype: List[str]
        """
        wordlist_replace_vowel = []
        vowel = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']
        word_lower = []
        for word in wordlist:
            word_lower.append(word.lower())
            temp = list(word)
            for i in range(len(temp)):
                if temp[i] in vowel:
                    temp[i] = '0'
            wordlist_replace_vowel.append(''.join(temp).lower())
            
        ret = []
        for query in queries:
            flag = 0
            match = ''
            temp = list(query)
            for i in range(len(temp)):
                if temp[i] in vowel:
                    temp[i] = '0'
            query_replace_vowel = ''.join(temp).lower()
            query_lower = query.lower()
            
            for wi, word in enumerate(wordlist):
                if flag < 4 and word == query:
                    match = word
                    flag = 4
                    break
                if flag  < 3 and word_lower[wi] == query_lower:
                    match = word
                    flag = 3
                if flag < 2 and wordlist_replace_vowel[wi] == query_replace_vowel:
                    match = word
                    flag = 2
            
            ret.append(match)
            
        return ret

阅读全文 »

LeetCode weekly contest 116

发表于 2018-12-26 更新于 2026-04-28 分类于 LeetCode Disqus：

又到周末LeetCode weekly contest的时候了，这次战果不佳。原因主要是，二三题都想做出来，结果都没有做出来。如果把时间都集中于第二题，应该也还是能AC的。

961. N-Repeated Element in Size 2N Array

这道题总觉得之前在LeetCode上已经做过了，还记得solution的方向。
思路是这样的，既然有一半的元素是一样的，我们随机抽取2个元素，判断是否相等就可以了。从概率上来讲，虽然有永远算不出来的概率，但在实际应用中效果很好。

import random

class Solution:
    def repeatedNTimes(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        while True:
            s = random.sample(A, 2)
            if s[0] == s[1]:
                return s[0]

962. Maximum Width Ramp

或许是最近dp学的有点多，遇见道题目就想着空间换时间。殊不知，忘记了dp的用武之地：
When should we look for a Dynamic Programming solution to a problem?

最优解结构
重叠子问题
找了半天最优解结构和重叠子问题：
dp[x] = max[dp[x] + x - k] for all A[x] >= A[k],
发现时间复杂度和brute search一样，都是O(n^2)呀！

真是dp学魔怔了，忘记了其他更基础的算法。其实这道题用简单的排序就能解决。
排序可以避免二次循环，将复杂度从O(n^2)降为O(n logn)。

class Solution:
    def maxWidthRamp(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        min_value = math.inf
        ret = 0
        for i in sorted(range(len(A)), key=A.__getitem__):
            min_value = min(min_value, i)
            ret = max(ret, i - min_value)
            
        return ret

Solution中还有一种利用二分查找的方法，我觉得很巧妙。
关键点在于注意到，对于j1 < j2, A[j1] <= A[j2], 此时，我们总是倾向于选择j2的。所以，对于这样的输入[6,0,8,2,1,5]，maximum width ramp的A[j] 一定会出现在[5, 8]中。对于i的选择，就需要遍历一遍了。那么A[j]是[5, 8]中的哪一个呢？就需要根据A[i]就行二分查找了，选择比A[i]恰好大一点的A[j]。

阅读全文 »

LeetCode weekly contest 115

发表于 2018-12-19 更新于 2026-04-28 分类于 LeetCode Disqus：

有些日子没有参加LeetCode的weekly contest了，最近由于准备一月末的Google电话面试，需要重新把算法捡起来。复习算法书是一部分，另一手就是准备刷题啦。由于时间有限，LeetCode的weekly contest不失为一个更好的选择。因为contest有时间限制，和实际面试更像。
weekly contest时长为1个半小时，4道不同难度的题目，每周末10点半开始(之前是9点半，可能是因为美国冬令时的原因，所以后沿了一小时)。
和之前一样，只完成了2道题目，第三道题有些思路(后来证明不对)，第四题看了下题目，果断放弃。
下面分享4道题目的思路和Solution，当然后2道是之后补题的。

958. Check Completeness of a Binary Tree

判断一颗树是否是完全树。
关于树的题目，递归、BFS、DFS是常用手段，可以很快发现，BFS最适合解决该题目。
一旦发现某个结点缺少child，就将no_child置为True，之后再搜索的时候，其他节点就不能有child了。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isCompleteTree(self, root: TreeNode) -> bool:
        no_child = False
        myqueue = collections.deque()
        if root:
            myqueue.append(root)
        
        while len(myqueue) > 0:
            node = myqueue.popleft()
            if no_child:
                if node.left != None or node.right != None:
                    return False
            else:
                if node.left != None:
                    myqueue.append(node.left)
                else:
                    no_child = True
                if node.right != None:
                    if no_child:
                        return False
                    else:
                        myqueue.append(node.right)
                else:
                    no_child = True
                    
        return True

时间复杂度：O(n), n 为节点数，因为在BFS中每个节点都要被遍历到(至少在完全树中，非完全树会提前退出)；
空间复杂度：O(n), BFS要用到一个队列，队列中最多要存一层的节点。

这道题的难度更像Easy，Medium真是高估了。

957 Prison Cells After N Days

状态转移的题目，可以直接模拟。但缺点是但N太大时，会TLE。
不难发现，Cells的状态最多有2^6 = 64种，所以在状态转移时，必然会出现循环。所以只要保存之前遇到的状态，如果再次遇到，就可以直接模掉循环长度了。
把状态转移打印出来，很快就可以发现，14是一个很神奇的数，每隔14必循环。所以最后的实现很多人都是直接mod 14了事。

时间复杂度: O(1),
空间复杂度: O(1).

class Solution:
    def prisonAfterNDays(self, cells, N):
        """
        :type cells: List[int]
        :type N: int
        :rtype: List[int]
        """
        last_day = cells
        new_day = [0] * 8
        N = N % 14 + 14
        
        for i in range(1, 7):
            if last_day[i-1] == last_day[i+1]:
                new_day[i] = 1
            else:
                new_day[i] = 0
        new_day[0] = 0
        new_day[7] = 0
        last_day[0] = 0
        last_day[7] = 0
        last_day, new_day = new_day, last_day
        
        for _ in range(1, N):
            for i in range(1, 7):
                if last_day[i-1] == last_day[i+1]:
                    new_day[i] = 1
                else:
                    new_day[i] = 0
            last_day, new_day = new_day, last_day
            
        return last_day

阅读全文 »

2018年终总结与 2019新年展望

发表于 2018-12-12 更新于 2026-04-28 分类于 dairy Disqus：

Merry Christmas!

离2019年还有5天，2018年就要结束了。一年过的真快呀。不知道你的2018年怎么样呀？一年前制定的新年计划实现了多少呢？

我曾在2017年的新年计划中写下这样一段话：

最近刚读了蔡东藩的五代史, 了解五代混乱的历史, 感叹大多数主子昏庸误国, 英明的主子也多少有瑕疵的同时, 也将心比心, 自己是否是一个英明的帝王. 答案却是否定的. 我是一个懒惰的人, 没有意志力的人, 不喜欢批评, 只喜欢表扬. 如果把自己放在帝王的位置上, 一定是个亡国之君了. 想想还是很可怕的.

当时真的是处于人生中一个非常没有自信的阶段。大三的寒假，刚刚被编译虐了一学期，面临未来人生道路的选择，自己完全没有信心把握自己的未来，甚至对人生的职业规划完全没有一个清楚的认识。现在近2年过去了(当时是农历新年写的)，不敢说我的境遇好了多少，但起码对未来，对自己有了更清醒的认识。自信心也逐渐建立起来了。
现在如果重新回答17年时的问题，我会有不一样的答案。

将心比心, 自己是否是一个英明的帝王。
我想，我可能会成为宋仁宗那样的君主。虽然在唐宗宋祖、秦皇汉武看来，完全没有帝王的权威。但宋仁宗是真正的仁主，他在位的40年，北宋人才辈出，经济也发展到古中国的顶峰。他是一个读书人所期待的最理想的皇帝。感兴趣的同学可以更多地了解一下那个时代，那个皇帝。类似的帝王还有汉文帝、明孝宗。“仁”是他们的共同特点，也是我给自己的一个很高的评价。

回顾与展望

新的一年，既要坚持既往好的传统，又要摒弃坏的习惯，培养好的习性。

坚持一切以找一份好的工作为中心。

2018年我为此着实付出了不少努力，包括3次实习和多次实习面试。
3次实习分别是，17年9月到今年3月的偶数科技的云平台开发工程师，4月到6月在快手的推荐系统算法工程师，还有11月到目前的文远知行数据平台开发工程师。3次实习极大地让我接触到业界的需求和实际工作，提高了我的代码能力，最重要的是，帮助我更好地认识自己，从而作出合理的职业规划。
实习面试有：快手、face++、Microsoft、小红书、景驰、商汤。成功率大概只有一半，而且成功与否更多地和对方缺人程度相关。

阅读全文 »

商汤见习计算机视觉实习生

发表于 2018-12-09 更新于 2026-04-28 分类于 interview Disqus：

上周给在商汤实习的同学发了简历，和HR约了本周四的面试，周五就又接到HR的电话，商议Offer的事宜。不得不说，商汤招聘的效率还是很高的。这也从另一个侧面反应出，其十分缺人手的事实。很多商汤的同学都在询问我，有没有其他的同学可以推荐过来实习。
商汤校友被誉为“北航实验室”。因为其招聘了大量的北航实习生，正式员工很多也是实习生直接转正的，本科的时候，就有几乎一个班都在那里实习。
而我面试的时候，推我的是我的一个一直在那里实习的同学，一面的面试官是我大三编译实验课的助教，二三面的面试官也都是我的本科同学。可以说，如果你是北航的学生，那么进入商汤会比其他学校容易很多。

我面的组是"商汤研究院基础技术与工具组“，算是在研究院里偏工程的组了。总体的面试过程还是很硬核，很高能的。好几次我都以为自己不行了，好在面试官及时给出一些hint，帮助我走下去。下面，我记录一下3个面试的流程。

一面

一面面试官是此组的lead，今年刚刚毕业转正。我一直觉得他很眼熟，后来和同学交流过后才想起来，这不是2年前检查我编译实验的助教哥哥嘛！

因为是lead给自己招人，所以一面总体上节奏很紧，内容也很充实。依次问了我职业规划、项目经历和2道算法题。
职业规划主要是与将来实习工作内容相关，从超级硬核的嵌入式和操作系统，到优化深度学习框架和库，再到优化计算机视觉的策略和算法。
项目经历主要问了我的2次实习和毕业设计，并问了我对之前的哪部分工作和实习最感兴趣。我当然把之前的实习都表扬了一边，然后再比较出自己对快手的实习最喜欢了。从和面试官的问答过程中我感受到，他对面试者是否真的想做某件工作、是否对其感兴趣很看重。

算法题有2道：

给出一个01串，给出0和1数目相等的最长子串的长度。比如’00100110011’的最长字串的长度为10.
有1-n个路灯，对其进行n次操作，第i次操作为将编号是i的倍数的路灯状态取反。初始状态为都灭，问对于给定的n，最后有几盏灯是亮的。

都不算很难的题目，虽然没能一下子解决，但最后都在面试官的hint下成功解决了。表现的不算太好，也不算很差。想解法的时候一度感觉自己要凉了，要丢人了。好在问题本身不是很难，经过更多的思考和尝试还是解答出来了。只有第一道题要求手写代码了，我用Python很快写完了。我用二维列表实现的桶，面试官指出，用Map难道不是更优雅吗？第二题解法过于简单，没必要写代码。

经验总结就是，虽然我代码能力还行，LeetCode也刷了有100道Easy难度的题目，但并没有形成自己的一套解题的流程，也没有对于每一类问题的归纳总结，可以快速地找出合适的算法。
更多的是依靠灵感和尝试。比如第一道题，我最开始一筹莫展，但再尝试几次后，偶然想到可以先把前缀和计算出来(遇0减一，遇1加一)，之后就迎刃而解了。和LeetCode上一些字符串比较的问题很像。
这种依靠灵感和尝试的解决方案，首先不是每次都奏效，如果状态不好，可能就不行了；其次是不靠谱，做题的时候心里没谱，对于题目能不能成功解决心惊胆战的。
所以，在面对未来更多的面试和dream job之前，形成自己稳定可靠的解题流程是必要的。

二面

阅读全文 »

突破百度云限速

发表于 2018-11-05 更新于 2026-04-28 Disqus：

最近因为英语学习的需要，经常到百度云上下载一些大文件。众所周知，百度云对下载进行了限速，不开他家的会员的话，下载速度只有几十k/s。实在不能忍，遂搜索了限速破解工具，下载速度达到了15M/s，哈哈。在此分享给大家。
不过需要注意的是，由于百度云也会更新限速机制，防止大家滥用。所以如果本文的方法失效的话，也不足为奇，还可以在网上寻找其他更新的方法。要相信广大程序员的力量。
截止至2018年11月5日，此方法是可行的。

阅读全文 »

日常 | 去景驰实习前发些牢骚

发表于 2018-10-28 更新于 2026-04-28 分类于 Life Disqus：

版权归作者所有，任何形式转载请联系作者。
作者：YoungForest（来自豆瓣）
来源：https://www.douban.com/note/694767558/

最近总有一种感受，自己无法掌控自己的生活和人生。

首先，快快乐乐的活着和努力成为别人期望的样子到底哪个更重要些？现在我更认可后者。我从小就是别人家的孩子，很乖、很听话。不玩电子游戏、不早恋、不打架，学习成绩好。但是这样的日子开心吗？不见得。现在即使大学都毕业了，早已泯然众人了，仍然免不了越来越活成别人期望的样子，甚至自己也认为这样的生活好像更有意义一些。说到底，我还是一个“社会”中的人。需要父母、同学、老师、朋友的肯定才能继续走下去。

其次，读了研究生后，我的生活一点也不开心。因为要上很多我不想上的课，为了那个不知道究竟有什么用的破航的学位证。还有，有了导师后，很多时候还需要应付导师。我并不是一个“会办事”和会“阳奉阴违”应付老师的人。所以很多时候，需要花时间做老师要求的，但自己不想做也看不到好处的事情。比如说写论文（水会论文而已，不知道有什么用），去景驰搬砖（每月才发1k，连吃饭都不够）。

最后，motivation。我做事的motivation总是不够，在加上自己比较懒，许多事情竟然就做不成了。比如说考英语，比如说找一份很好的实习。这些事情明明做好了长期看好处还是很大的，然而还是motivation和passion不足。我现在好像对什么都提不起兴趣了，竟然只想浑浑噩噩。真是太可怕了。

吐槽归吐槽。我还是会全力以赴去实习的，然后不断地试着去掌控自己的生活和人生，利用零碎时间去成为自己想成为的人。

p.s. 为什么说是零碎时间呢？我们现在课程压力已经很大了，我又要去实习，整块的时间可以说已经很少了。

阅读全文 »

LeetCode #380 Insert Delete GetRandom O(1)

发表于 2018-10-26 更新于 2026-04-28 Disqus：

此题的重点在于理解“average O(1) time”，这是也是时间复杂度分析中的一个重要概念"amortized"。
在算法第4版中，很多数据结构的操作的分析都是用的这个方法。所以，“amortized time complexity"常常和对应的数据结构的操作相对应。我5月时面试旷世科技的时候，第二题问的是构造一个维护最大值的队的数据结构，最后要求操作的时间复杂度是“amortized O(1)"。很遗憾，当时我对“amortized"这一概念还不熟悉，对最差情况下的时间复杂度分析的倒是可以，虽然在面试官的引导下最后得出正确答案，但可想而知，最后的结果是no hire。

Description: https://leetcode.com/problems/insert-delete-getrandom-o1/description/
Solution: None
Difficulty: Medium

answer

关键点在于，利用hashmap查找效率为O(1),ArrayList很方便用下标来产生随机数。

class RandomizedSet:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.array = []
        self.index_map = {}
        

    def insert(self, val):
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        :type val: int
        :rtype: bool
        """
        if val in self.index_map:
            return False
        
        self.index_map[val] = len(self.array)
        self.array.append(val)
        
        return True
        

    def remove(self, val):
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        :type val: int
        :rtype: bool
        """
        if val not in self.index_map:
            return False
        
        self.array[self.index_map[val]] = self.array[-1]
        self.index_map[self.array[-1]] = self.index_map[val]
        self.array.pop()
        self.index_map.pop(val)
        
        return True
        

    def getRandom(self):
        """
        Get a random element from the set.
        :rtype: int
        """
        rnd = random.randint(0, len(self.array)-1)
        
        return self.array[rnd]
        


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

阅读全文 »

LeetCode #15 3Sum

发表于 2018-10-25 更新于 2026-04-28 Disqus：

这道很经典的题目我恰好在面试“景驰”的时候遇到过，当时是二面的Eric问的。我没做过这道题，但与之关联的2Sum做过（毕竟是LeetCode的首题，大概很多人都做过）。而且算法第4版中讨论算法复杂度的时候，用的也是一样的问题（细节可能不同，比如要求了结果中没有重复的triplet…），当时还有些印象。顺利地写出了O(n^2)时间复杂度的Solution，虽然事后发现有些小bug，比如list的sort是inplace的。但无伤大雅。
今天我把面试时的solution整理了一下，submit后竟然Time Limit Exceeded了。

Description: https://leetcode.com/problems/3sum/description/
Solution: None
Difficulty: Medium

面试时的solution

class Solution:
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        mymap = {}
        results = set()
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if - nums[i] - nums[j] in mymap:
                    a = [- nums[i] - nums[j], nums[i], nums[j]]
                    a.sort()
                    results.add(tuple(a))
            mymap[nums[i]] = i
        
        re = []
        for a in results:
            re.append(list(a))
        return re

解决超时问题

reference[https://fizzbuzzed.com/top-interview-questions-1/]

总的思想是，O(n^2)的时间复杂度已经不能再低了。更多的是尝试一些小的技巧，降低时间复杂度中的常数。

先排序

class Solution:
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        mymap = set()
        results = set()
        for i in range(len(nums)):
            if i > 1 and nums[i] == nums[i-2]:
                continue
            for j in range(i + 1, len(nums)):
                if j != i + 1 and nums[j] == nums[j-1]:
                    continue
                if - nums[i] - nums[j] in mymap:
                    a = [- nums[i] - nums[j], nums[i], nums[j]]
                    a.sort()
                    results.add(tuple(a))
            mymap.add(nums[i])
        
        re = []
        for a in results:
            re.append(list(a))
        return re

增加了排序，和2层循环中的判断，使得重复的triplet出现的次数更少(result.add(tuple(a))被执行的次数更少)。
观察之前TLE的Test case可以发现，leetcode卡了重复的triplet这块。python set.add操作的时间复杂度为O(1)，所以还是被卡了常数。

阅读全文 »

LeetCode 29 Divide Two Integer

发表于 2018-10-23 更新于 2026-04-28 分类于 LeetCode Disqus：

有4周时间没有刷LeetCode了，理由一方面是紧迫感下降，另一方面是行动力不足。
最近又有一场面试要准备，小红书视频组的算法实习生。
一面看机器学习的知识，防止重蹈快手面试的覆辙；另一面回顾自己的代码能力，果然4周不刷题，连代码都写不好了。作为未来的程序员，代码能力不好怎么行呢？还是要重新有规划的开始刷leetcode的。

Description: https://leetcode.com/problems/divide-two-integers/description/
Solution: 无
Difficulty: Medium

brute approach

直接暴力，用减法代替除法。不出所料，果然超时。
时间复杂度：O(m)，m为商的绝对值。
空间复杂度：O(1), 除常量外，并未申请额外空间。

class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
        if (divisor == 1) return dividend;
        if (dividend == 0) return 0;
        
        boolean positive = true;
        if (Integer.signum(dividend) + Integer.signum(divisor) == 0) positive = false;
        
        int count = 0;
        int originalDividend = dividend;
        
        while (true) {
            dividend = positive ? dividend - divisor : dividend + divisor;
            if (Integer.signum(dividend) == 0) {
                count = positive ? count + 1 : count - 1;
                break;
            }
            if (Integer.signum(dividend) + Integer.signum(originalDividend) == 0) break;
            count = positive ? count + 1 : count - 1;
        }
        
        return count;
    }
}

模拟除法笔算

public class Solution {
    public int divide(int dividend, int divisor) {
		if(dividend==Integer.MIN_VALUE && divisor==-1) return Integer.MAX_VALUE;
        if(dividend > 0 && divisor > 0) return divideHelper(-dividend, -divisor);
        else if(dividend > 0) return -divideHelper(-dividend,divisor);
        else if(divisor > 0) return -divideHelper(dividend,-divisor);
        else return divideHelper(dividend, divisor);
    }
    
    private int divideHelper(int dividend, int divisor){
        // base case
        if(divisor < dividend) return 0;
        // get highest digit of divisor
        int cur = 0, res = 0;
        while((divisor << cur) >= dividend && divisor << cur < 0 && cur < 31) cur++;
        res = dividend - (divisor << cur-1);
        if(res > divisor) return 1 << cur-1;
        // 每次调用都只计算出来商里为1的一位
        return (1 << cur-1)+divide(res, divisor);
    }
}

阅读全文 »