WEEK 5

leetcode:

11

class Solution(object):
   def maxArea(self, height):
       """
       :type height: List[int]
       :rtype: int
       """
       nums = height
       left = 0
       right = len(nums) -1
       area = []
       while left < right:
           area.append(min([nums[left],nums[right]]) * (right-left))
           if nums[left] <= nums[right]:
               left += 1
           else:
               right -= 1

       return max(area)

思路：用左右两个指针往中间夹逼

image.png image.png

class Solution(object):
    def intToRoman(self, num):
        out = []
        def getN (num,str1):
            if num == 0:
                out.append(str1)
                return 
            if num >= 1000:
                getN(num-1000,str1+'M')
            elif num >= 900:
                getN(num-900,str1+"CM")
            elif num >= 500:
                getN(num-500,str1+"D")
            elif num >=400:
                getN(num-400,str1+"CD")
            elif num>=100:
                getN(num-100,str1+'C')
            elif num>=90:
                getN(num-90,str1+"XC")
            elif num >= 50:
                getN(num-50,str1+"L")
            elif num>=40:
                getN(num-40,str1+"XL")
            elif num >= 10:
                getN(num-10,str1+"X")
            elif num == 9:
                out.append(str1+"IX")
                return 
            elif num >=5:
                getN(num-5,str1+"V")
            elif num == 4:
                out.append(str1+"IV")
                return
            else:
                getN(num-1,str1+"I")
        getN(num,'')
        return out[0]

采用递归配合if判断

image.png
image.png

class Solution(object):
    def isValidSudoku(self, board):
        seti = []
        # 检查行
        flag1 = 0
        for i in board:
            for j in i:
                if j != '.':
                    seti.append(int(j))
            i = list(set(seti))
            if len(i) != len(seti):
                print(i)
                flag1 = 1
            seti = []
        # 检查列：
        rotated = list(zip(*board[::-1]))# 翻转
        flag2 = 0
        seti = []
        for i in rotated:
            for j in i:
                if j != '.':
                    seti.append(int(j))
            i = list(set(seti))
            if len(i) != len(seti):
                print(i)
                flag2 = 1
            seti = []

        # 检查块：
        flag3 = 0
        # 分块
        start = [[0,0],[0,3],[0,6],[3,0],[3,3],[3,6],[6,0],[6,3],[6,6]]
        fenkuai = []
        for item in start:
            kuai = []
            x = item[0]
            y = item[1]
            endx = x+2
            endy = y+2
            while x <= endx:
                while y <= endy:
                    kuai.append(board[x][y])
                    y+=1
                y = item[1]
                x+=1
            fenkuai.append(kuai)
        print(fenkuai)
        
        seti = []
        for i in fenkuai:
            for j in i:
                if j != '.':
                    seti.append(int(j))
            i = list(set(seti))
            if len(i) != len(seti):
                print(i)
                flag3 = 1
            seti = []


        if flag1==0 and flag2==0 and flag3==0:
            return True
        else:
            return False

1、先判断每行是否有重复的，利用的是set去重后比较长度来判断，
2、然后翻转二维list，重复上述过程 1
3、把各个分块当作一行，9个分块就是9行。对分好块后的二维list执行过程 1

image.png
image.png

class Solution(object):
    def combinationSum(self, candidates, target):
        nums = candidates
        out = []
        def choose(tar,i,sum,tmp):
            if sum > tar or i == len(nums):
                return
            if sum == tar:
                out.append(tmp)
                return
            choose(tar,i,sum+nums[i],tmp+[nums[i]])
            choose(tar,i+1,sum,tmp)
        choose(target,0,0,[])
        return out

利用递归来解决

image.png image.png

class Solution(object):
    def plusOne(self, digits):
        mystr = ''
        for i in digits:
            mystr += str(i)
        mynum = int(mystr)
        mynum += 1
        mystr2 = str(mynum)
        list2 = list(mystr2)
        for i in range(len(list2)):
            list2[i] = int(list2[i])
        digits =list2
        return digits

1、转成字符相加成字符串
2、转成int加一
3、再转成str的list
4、把str的list转成int 的list

image.png
image.png

class Solution(object):
    def hammingWeight(self, n):

        flag = 0
        while n!= 0:
            if n%2 == 1:
                flag += 1
            n = n/2
        return flag

image.png 350题目描述

class Solution(object):
    def intersect(self, nums1, nums2):
        mydict = {}
        out = []
        if len(nums1) <= len(nums2):
            miniNum = nums1
            maxNum = nums2
        else:
            miniNum = nums2
            maxNum = nums1

        for item in miniNum:
            if mydict.get(item,'no') == 'no': #没有
                mydict[item] = 1
            else:
                mydict[item] += 1

        for item in maxNum:
            if mydict.get(item,'no') == 'no':
                pass
            else:
                if mydict[item] != 0:
                    out.append(item)
                    mydict[item] -= 1

        return out

先找出两个list中那个比较短，然后把短的这个记录进dict中，再循环长的list，看值是否在dict中。

image.png