90. Subsets II

題目概述：給定一個(gè)含有重復(fù)數(shù)字的集合棍丐，求出它的所有子集。注意這些子集中沒(méi)有相同的兩個(gè)集合虫腋。
思路很簡(jiǎn)單：首先先對(duì)給定的數(shù)字集合排序骄酗，然后記結(jié)果是ans = {?}。然后遍歷排序后的數(shù)字集合悦冀，完成以下操作：
①若當(dāng)前數(shù)字與前一位數(shù)字是不相等的趋翻，則把a(bǔ)ns中所有的集合拷貝出來(lái)，加入這一個(gè)數(shù)字盒蟆，把得到的所有新的集合都加入到ans中踏烙；
②若當(dāng)前數(shù)字與前一位數(shù)字是相等的，則把上一次新加入ans的集合拷貝出來(lái)历等，加入這一個(gè)數(shù)字讨惩，把得到的所有新的集合都加入到ans中。

以[1, 2, 2]為例寒屯。
第一輪荐捻，ans={?}，當(dāng)前數(shù)字為1寡夹。沒(méi)有前一個(gè)數(shù)字处面，可以看作當(dāng)前數(shù)字與前一位數(shù)字不同，操作后得到ans = {?, {1} }菩掏；
第二輪魂角，ans = {?, {1} }， 當(dāng)前數(shù)字為2智绸，與前一個(gè)數(shù)字1不等野揪。操作后得到 ans = {?, {1}, {2}, {1, 2}}访忿；
第三輪，ans = {?, {1}, {2}, {1, 2}}斯稳，當(dāng)前數(shù)字為2海铆，與前一個(gè)數(shù)字2相等。操作后得到ans = {?, {1}, {2}, {1, 2}, {2, 2}, {1, 2, 2}} （只是拓展了第二輪中新加入的兩個(gè)集合{2}與{1, 2}）挣惰。

時(shí)間復(fù)雜度為O(n^2)游添。
實(shí)現(xiàn)代碼如下:

class Solution:
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()    #先排序
        ret = [[]]          #初始化答案，一開(kāi)始只有一個(gè)空集
        start = 0
        end = 0
        for i in range(len(nums)):
            if (i >= 1 and nums[i] == nums[i - 1]):
                start = end  #記錄前一次新加入的集合在ret中的下標(biāo)
            else:
                start = 0
            end = len(ret)  #更新當(dāng)前ret的長(zhǎng)度
            for j in range(start, end):    # 對(duì)start~end的集合進(jìn)行拓展
                ret.append(ret[j] + [nums[i]])
        return ret      

29. Divide Two Integers

題目概述：給出被除數(shù)與除數(shù)通熄，在不使用乘法和除法的情況下計(jì)算他們的結(jié)果（取整）。默認(rèn)計(jì)算時(shí)在32位整數(shù)下進(jìn)行的找都。
只考慮正數(shù)相除的情況唇辨。
使用類似二分的方法計(jì)算。初始化sum為除數(shù)能耻，每次對(duì)自身不斷乘2（也就是自己加自己）赏枚，并用變量k記錄倍數(shù)（k從1開(kāi)始也不斷乘2），直到2*sum時(shí)比被除數(shù)要大時(shí)停止晓猛。商遞增k饿幅，并從被除數(shù)中減去sum。重復(fù)之前的過(guò)程直到被除數(shù)小于商戒职。
時(shí)間復(fù)雜度為O((logn)^2)
代碼如下：

class Solution:
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        MAX = 2147483647
        MIN = -2147483648
        if (dividend < 0 and divisor > 0) or (dividend > 0 and divisor < 0):  #解決符號(hào)問(wèn)題
            sign = -1
        else:
            sign = 1
        dividend = abs(dividend)
        divisor = abs(divisor)
        ans = 0
        while (dividend >= divisor):
            sum = divisor
            k = 1
            while (sum + sum < dividend):
                sum += sum
                k += k
            ans += k
            dividend = dividend - sum
            
        ans = ans * sign
        if (ans < MIN or ans > MAX): #越界返回2^31-1
            ans = MAX
        return ans