英文学习

Trump Administration Plans $12 Billion In Farm Aid To Offset Tariffs


Words:
hog 猪
brunt 首当其冲
tariff
levies 征税
aluminum 铝
cave in 塌陷
beneficiary 受益人
bailout 救助
subsides 补助，塌陷
legume 豆类
crutch 拐杖 支撑

Subsets

78. Subsets

Example:

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Solution 1: think from previous result

Say we already have the subsets of [1,2], now we add 3 .
The only thing we need to do is add 3 to every previous result.
That's it.

def subsets(self, nums):
    ret = [[]]
    for num in nums:
        if not ret:
            ret.append(num)
        else:
            length = len(ret)
            for i in xrange(length):
                ret.append(ret[i][:])
                ret[-1].append(num)
    return ret

Solution 2: DFS

For each number, it could form a subset with it's subsequence.
for nothing: []
for 1: [1], [1,2],[1,2,3]
for 2: [2], [2,3]
for 3: [3]

class Solution(object):
    def subsets (self, nums):
        res = []
        self.dfs(nums, 0, [], res)
        return res
    
    def dfs(self, nums, index, path, res):
        res.append(path)
        for i in xrange(index, len(nums)):
            self.dfs(nums, i+1, path+[nums[i]], res)

90. Subsets II 

Input could contains duplicates
Example: [1,2,2], [5,5,5]
Sort the list first, nums[i] == nums[i-1] if nums[i] has duplicates

for [1,2] subsets [], [1], [2], [1,2]
next we add another 2, we only need to add it to [2] and [1,2] 
which is the start point of previous 2.

for[5,5] subsets [], [5], [5,5]
next we add 5, we only need to add it to [5,5] 
which is the start point of previous 5.
def subsetsWithDup(self, nums):       
    ret = [[]]
    nums.sort()
    lastIdx = 0

    for k, num in enumerate(nums):
        length = len(ret)
        idx = 0
        if k != 0 and nums[k] == nums[k-1]:
            idx = lastIdx
        lastIdx = len(ret)
        for i in xrange(idx, length):
            ret.append(ret[i][:])
            ret[-1].append(num)
    return ret

43. Multiply Strings

Multiply Strings

Solution 1:
     The Length is way larger than 64 bit integer, which length is 19
    
     Python3.5: Integers have unlimited precision, in most situations of industrial work, just use the simplest and most readable way to do it.

     Intuitively, multiply digit by digit, and add sum up. Use a String to store temporary result and 'add' it into result.

    Example: 13*34=13*4+13*30
    Here 13 is num1, 14 is num2, need to multiply in reverse order

 def multiply(self, num1, num2):
    if num1 == '0' or num2 == '0':
        return '0'
    revret = '' # store the result in reverse order for easy computation
    zeros='' #this is used for add 0 for next inner iteration
    for d1 in reversed(num1):
        tmp = ''
        offset = 0
        for d2 in reversed(num2):
            sum = int(d2)*int(d1)+offset
            tmp += str(sum%10)
            offset = sum/10
        if offset:
            tmp += str(offset)
        revret = self.addNumInReverse(revret, zeros+tmp)
        zeros+='0'
    return revret[::-1]
def addNumInReverse(num, tmp):

    if len(num) < len(tmp):
        t = tmp
        tmp = num
        num = t

    re = ""
    off = 0
    
    for i, n in enumerate(num):
        sum = off + int(n) + (int(tmp[i]) if i < len(tmp) else 0)
        re+=str(sum%10)
        off = sum/10                     
    if off:
        re += str(off)         
    return re

Solution 2:
Don't have to add it up in when they first multiplied together.   

          
Use array to store each multiplied result, add it up at last.                      

Maximum product length = len(A) + len(B)

def multiply(self, num1, num2):
    if num1 == '0' or num2 == '0':
        return '0'

    retval = [0]*(len(num1)+len(num2))
    num1 = list(reversed(num1))
    num2 = list(reversed(num2))
    k=0

    for i, d1 in enumerate(num1):
        for j, d2 in enumerate(num2):                
            retval[j+k] += int(d1)*int(d2)
        k+=1
    ret = ""
    off = 0

    for i in xrange(len(retval)):
        sum = retval[i] + off
        ret = str(sum%10) + ret
        off = sum/10
    if off:
        ret = off + ret