python_day_10:20180725

561. 数组拆分 I
给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从1 到 n 的 min(ai, bi) 总和最大。

思路：数组的长度是偶数，它一定可以被两个一组瓜分干净（没有剩余），现在要求这个分好的组合中，每个组较小的那个值取出来，总和最大。要知道每个组合中两个值，只有较小的那个值会被统计，较大的那个值是浪费掉的。所以，较大的值应该尽量接近较小的值，这样“浪费”的比例低一点。因此想到，先对原来的数组进行排序，然后序位临近的放在一组，取出较小值。这样因为整体浪费的比例是最少的，所以取出的总和反而是最大的。

 1 class Solution:
 2     def arrayPairSum(self, nums):
 3         """
 4         :type nums: List[int]
 5         :rtype: int
 6         """
 7         nums.sort()
 8         sumnum=0
 9         for i in range(0,len(nums),2):
10             sumnum+=nums[i]
11         return sumnum

118. 杨辉三角
给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

思路：杨辉三角的规律是，下一行由上一行产生，产生规则是相邻数字相加得到新数字。我设计的生成方法是，原来的行，两头+0，再通过两两邻数相加，获得新数列。这样保留了原来数列的两个端点数字不变。

 1 class Solution:
 2     def generate(self, numRows):
 3         if numRows==0:
 4             return []
 5         result=[[1]]
 6         a0=[1]
 7         i=0
 8         while i +1<numRows:
 9             a0=self.yanghui(a0)
10             result.append(a0)
11             i+=1
12         return result
13             
14         
15     def yanghui(self,number):
16         nums=number[:]
17         nums.insert(0,0)
18         nums.append(0)
19         result=[]
20         for i in range(len(nums)-1):
21             result.append(nums[i]+nums[i+1])
22         return result
23