LeetCode 53 118 119

题53 从给定数组中取出总和最大的子数组（此解参考讨论区）

153. Maximum Subarray
2Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

1int maxSubArray(int* nums, int numsSize){
2    int result = nums[0], s = nums[0];
3    for (int i=1; i<numsSize; i++) {
4        s += nums[i];
5        if (s < nums[i]) s = nums[i];
6        if (s > result) result = s;
7    }
8    return result;
9}

题118 杨辉三角一

1118. Pascal's Triangle
2Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.

杨辉三角

1    1
2   1 1
3  1 2 1
4 1 3 3 1
51 4 6 4 1
6   ...

不妨用 a_i,j 来指表示第 i 行，第 j 个元素，那么 a_i,j = a_i-1,j-1 + a_i-1,j 其中 i >= 0, 0 < j < i ( j = 0 或 j = i 时 a_ij = 1)

那么对于代码实现，我的方法是：

• 初始化第一行 1
• 从第二行开始，循环变量 i 作为行索引，该行起始元素置为 1
• 循环变量 j 作为列索引，值从1开始遍历到 i-1，每个元素的值为上一行的两个元素之和
• j 循环结束之后，该行末尾元素置1
• i 循环结束之后将结果返回

 1import java.util.*;
 2
 3class Solution {
 4    public List<List<Integer>> generate(int numRows) {
 5
 6        if (numRows < 1) return new Vector();
 7
 8        Vector outer =  new Vector();
 9        Vector init = new Vector();
10        init.add(1);
11        outer.add(init);
12
13        for (int i=1; i<numRows; i++) {
14            Vector last = (Vector) outer.lastElement();
15            Vector inner = new Vector();
16            inner.add(1);
17            for (int j=0; j+1<last.size(); j++) {
18                inner.add((int)last.get(j)+(int)last.get(j+1));
19            }
20            inner.add(1);
21            outer.add(inner);
22        }
23
24        return outer;
25    }
26}

题119 杨辉三角二

1119. Pascal's Triangle II
2Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal's triangle.
3
4Note that the row index starts from 0.

这一题承接上一题，目标是返回给定行数的杨辉三角值。

我的做法比较简单粗暴：使用上一题生成杨辉三角，直到需要返回的那一行时终止循环，返回该行数值。

这一题有更加快速的方法，可以根据给定行数直接生成这一行的杨辉三角数值，数学排列组合中的组合和杨辉三角也存在对应关系。可以参考这一题的讨论区。

 1import java.util.*;
 2
 3class Solution {
 4    public List<Integer> getRow(int rowIndex) {    
 5        Vector outer =  new Vector();
 6        Vector init = new Vector();
 7        init.add(1);
 8        outer.add(init);
 9
10        if (rowIndex == 0) return init;
11
12        Vector inner = new Vector();
13        for (int i=1; i<=rowIndex; i++) {
14            Vector last = (Vector) outer.lastElement();
15            inner = new Vector();
16            inner.add(1);
17            for (int j=0; j+1<last.size(); j++) {
18                inner.add((int)last.get(j)+(int)last.get(j+1));
19            }
20            inner.add(1);
21            outer.add(inner);
22        }
23
24        return inner;
25    }
26}