interview

interview_dp

1.分割等和子集

 1 class Solution(object):
 2     def canPartition(self, nums):
 3         if(sum(nums)&1):
 4             return False
 5         
 6         target=sum(nums)//2
 7 
 8         # dp[i]表示是否能从 nums中取出一些数字，其和为i
 9         dp=[False]*(target+1)
10 
11         dp[0]=True
12 
13         for num in nums:
14             for i in range(target,num-1,-1):
15                 dp[i]=dp[i] or dp[i-num]
16         
17         return dp[target]

2.coins change i

组成amount的最少硬币数

 1 class Solution(object):
 2     def coinChange(self, coins, amount):
 3         # dp[i]表示凑成金额i所需的最少硬币数
 4         # dp[i]=min(dp[i],dp[i-coins[j]] if i-coins[j]>=0)
 5         # dp[0]=0 
 6 
 7         dp=[float('inf') for j in range(amount+1)]
 8         dp[0]=0
 9 
10         for j in range(1,amount+1):
11             for i in range(len(coins)):
12                 if(j>=coins[i] and dp[j-coins[i]]!=float('inf')):
13                     dp[j]=min(dp[j],dp[j-coins[i]]+1)
14             
15         return dp[amount] if dp[amount]!=float('inf') else -1
16

3.1 coins change ii

组成amounts的所有可能数

 1 class Solution(object):
 2     def change(self, amount, coins):
 3         m=len(coins)
 4         n=amount
 5 
 6         dp=[[0]*(n+1)]*(m+1)
 7         dp[0][0]=1
 8 
 9         # 下面写法错误，没有任何硬币，所以无法组成
10         # for j in range(n+1):
11         #     if j %coins[0]==0:
12         #         dp[0][j]=1
13         
14         for i in range(1,m+1):
15             dp[i][0]=1
16 
17         for i in range(1,m+1):
18             for j in range(1,n+1):
19                 dp[i][j]=dp[i-1][j]+(dp[i][j-coins[i-1]] if j-coins[i-1]>=0 else 0)
20         
21         return dp[m][n]

def change(self, amount, coins):
        m=len(coins)
        n=amount

        # dp[i]表示组成i的组合数
        dp=[0]*(n+1)
        dp[0]=1

        for i in range(m):
            for j in range(coins[i],n+1):
                dp[j]=dp[j]+dp[j-coins[i]]
        
        return dp[amount]

3.2 coins change i

组成amount所需的最少硬币数

 1 class Solution(object):
 2     def coinChange(self, coins, amount):
 3         """
 4         :type coins: List[int]
 5         :type amount: int
 6         :rtype: int
 7         """
 8 
 9         m=len(coins)
10         n=amount
11 
12         # dp[j]表示组成amount j所需的最少硬币数
13         dp=[float('inf') for j in range(n+1)]
14 
15         dp[0]=0
16         for j in range(1,n+1):
17             for i in range(m):
18                 if(j>=coins[i]):
19                     dp[j]=min(dp[j],dp[j-coins[i]]+1)
20             
21         return dp[n] if dp[n]!=float('inf') else -1

4. 打家劫舍

 1 class Solution(object):
 2     def helper(self,nums):
 3         # dp[i]表示偷 前i个房子时 最高的金额数
 4         dp=[0]*len(nums)
 5         dp[0]=nums[0]
 6 
 7         for i in range(1,len(nums)):
 8             dp[i]=max(dp[i-1],nums[i]+(dp[i-2] if i-2>=0 else 0))
 9         
10         return dp[-1]
11 
12     def rob(self, nums):
13         if(len(nums)==0):
14             return 0
15 
16         if(len(nums)==1):
17             return nums[0]
18         
19         if(len(nums)==2):
20             return max(nums[0],nums[1])
21 
22         nums1=nums[:-1]
23         nums2=nums[1:]
24 
25         return max(self.helper(nums1),self.helper(nums2))

5.LIS

 1 class Solution(object):
 2     def lengthOfLIS(self, nums):
 3         n=len(nums)
 4         if(n==0 or n==1):
 5             return n
 6 
 7         dp=[1]*n
 8 
 9         for i in range(1,n):
10             for j in range(i):
11                 if(nums[j]<nums[i]):
12                     dp[i]=max(dp[j]+1,dp[i])
13         
14         return max(dp)

6.最大和连续子数组

 1 class Solution(object):
 2     def maxSubArray(self, nums):
 3         n=len(nums)
 4         if(n==0):
 5             return 0
 6 
 7         curSum=0          
 8         maxSum=float('-inf')
 9 
10         for i in range(n):
11             curSum+=nums[i]
12             maxSum=max(curSum,maxSum)
13 
14             if(curSum<0):
15                 curSum=0
16 
17 
18         return maxSum

7.众数

 1 class Solution(object):
 2     def majorityElement(self, nums):
 3         n=len(nums)
 4         if(n==0):
 5             return []
 6         
 7         if(n==1):
 8             return nums
 9 
10         res=[]
11 
12         num1=float('inf')
13         num2=float('inf')
14         cnt1=0
15         cnt2=0
16 
17         for i in range(n):
18             if(nums[i]==num1):
19                 cnt1+=1
20             elif(nums[i]==num2):
21                 cnt2+=1
22             elif(cnt1==0):
23                 num1=nums[i]
24                 cnt1=1
25             elif(cnt2==0):
26                 num2=nums[i]
27                 cnt2=1
28             else:
29                 cnt1-=1
30                 cnt2-=1
31   
32         cnt1,cnt2=0,0
33         for num in nums:
34             if(num==num1):
35                 cnt1+=1
36             elif(num==num2):
37                 cnt2+=1
38             
39         if(cnt1>n//3):
40             res.append(num1)
41         if(cnt2>n//3):
42             res.append(num2)
43 
44         return res

误区1：

num1和num2初始化为nums[0]。再执行循环。

假设数组中只有两个不相同的元素，那么结束循环时，num1和num2仍指向同一个元素