Python Leetcode练习2(4.29/5.2作业)

90. Subsets II

题目概述:给定一个含有重复数字的集合,求出它的所有子集。注意这些子集中没有相同的两个集合。
思路很简单:首先先对给定的数字集合排序,然后记结果是ans = {∅}。然后遍历排序后的数字集合,完成以下操作:
①若当前数字与前一位数字是不相等的,则把ans中所有的集合拷贝出来,加入这一个数字,把得到的所有新的集合都加入到ans中;
②若当前数字与前一位数字是相等的,则把上一次新加入ans的集合拷贝出来,加入这一个数字,把得到的所有新的集合都加入到ans中。

以[1, 2, 2]为例。
第一轮,ans={∅},当前数字为1。没有前一个数字,可以看作当前数字与前一位数字不同,操作后得到ans = {∅, {1} };
第二轮,ans = {∅, {1} }, 当前数字为2,与前一个数字1不等。操作后得到 ans = {∅, {1}, {2}, {1, 2}};
第三轮,ans = {∅, {1}, {2}, {1, 2}},当前数字为2,与前一个数字2相等。操作后得到ans = {∅, {1}, {2}, {1, 2}, {2, 2}, {1, 2, 2}} (只是拓展了第二轮中新加入的两个集合{2}与{1, 2})。

时间复杂度为O(n^2)。
实现代码如下:

class Solution:
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()    #先排序
        ret = [[]]          #初始化答案,一开始只有一个空集
        start = 0
        end = 0
        for i in range(len(nums)):
            if (i >= 1 and nums[i] == nums[i - 1]):
                start = end  #记录前一次新加入的集合在ret中的下标
            else:
                start = 0
            end = len(ret)  #更新当前ret的长度
            for j in range(start, end):    # 对start~end的集合进行拓展
                ret.append(ret[j] + [nums[i]])
        return ret      

29. Divide Two Integers

题目概述:给出被除数与除数,在不使用乘法和除法的情况下计算他们的结果(取整)。默认计算时在32位整数下进行的。
只考虑正数相除的情况。
使用类似二分的方法计算。初始化sum为除数,每次对自身不断乘2(也就是自己加自己),并用变量k记录倍数(k从1开始也不断乘2),直到2*sum时比被除数要大时停止。商递增k,并从被除数中减去sum。重复之前的过程直到被除数小于商。
时间复杂度为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):  #解决符号问题
            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

你可能感兴趣的