119 pascal's trinangle 2

2015-09-14 | 分类 leetcode | 标签 array

Given an index k, return the kth row of the Pascal's triangle.

For example, given k = 3, Return [1,3,3,1].

Note: Could you optimize your algorithm to use only O(k) extra space?

1

思路是根据前一行的值迭代计算下一行的值。空间复杂度是O(k)。 1 3 3 1 -> 1 4 6 4 1 具体内部实现可以使用list,java.util.ArrayList.add(int index, Integer element)的方法在增加元素后，将后续元素依次右移。也可以使用数组。注意当rowIndex = 0时，输出是[1]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 public List<Integer> getRow(int rowIndex) {
        ArrayList<Integer> row = new ArrayList<Integer>();
        for(int i = 0; i <= rowIndex; i++){
            row.add(0,1);
            for(int j = 1; j < row.size() -1; j++){
                row.set(j,row.get(j)+row.get(j+1));
            }
        }
        return row;
    }
    public List<Integer> getRow2(int rowIndex) {
        Integer[] row = new Integer[rowIndex+1];
        for(int i = rowIndex; i >= 0; i--){
            row[i] = 1;
            for(int j = i+1; j <= rowIndex-1; j++){
                row[j] = row[j]+row[j+1];
            }
        }
        return Arrays.asList(row);

<span class="o">}</span>
<span class="kd">public</span> <span class="n">List</span><span class="o">&lt;</span><span class="n">Integer</span><span class="o">&gt;</span> <span class="nf">getRow3</span><span class="o">(</span><span class="kt">int</span> <span class="n">rowIndex</span><span class="o">)</span> <span class="o">{</span>
    <span class="n">rowIndex</span><span class="o">++;</span>
    <span class="n">Integer</span><span class="o">[]</span> <span class="n">row</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Integer</span><span class="o">[</span><span class="n">rowIndex</span><span class="o">];</span>
    <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">rowIndex</span><span class="o">-</span><span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">i</span><span class="o">--){</span>
        <span class="n">row</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span>
        <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="o">;</span> <span class="n">j</span> <span class="o">&lt;=</span> <span class="n">rowIndex</span><span class="o">-</span><span class="mi">2</span><span class="o">;</span> <span class="n">j</span><span class="o">++){</span>
            <span class="n">row</span><span class="o">[</span><span class="n">j</span><span class="o">]</span> <span class="o">=</span> <span class="n">row</span><span class="o">[</span><span class="n">j</span><span class="o">]+</span><span class="n">row</span><span class="o">[</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="o">];</span>
        <span class="o">}</span>
    <span class="o">}</span>
    <span class="k">return</span> <span class="n">Arrays</span><span class="o">.</span><span class="na">asList</span><span class="o">(</span><span class="n">row</span><span class="o">);</span>

<span class="o">}</span><span class="w">

2 most votes

基本上都是这个思路。