Angular (33) -- NgRx

LeetCode Day 13: P119. Pascal’s Triangle II (Easy)

题目

给一个非负整数k<=33，求第index = k层的杨辉三角数组。

Example:

Input: 3
Output: [1,3,3,1]

我的思路：

昨天做过了，直接用昨天的代码。

当k = 30时又越界了。因为需要计算C(30,14)，就要算30 * 29 * 28 * 27 * … * 16，这个数即使是long也会越界。

于是我想进一步优化我的组合数算法。上面的那个乘积，其实还会再除以14！，所以其实最后的结果并没有那个大。

搜了一下用java求组合数的方法：

https://my.oschina.net/baoer1024/blog/62826

我的思路只停留在了方案一。。。方案三和方案四比较厉害，看不懂。

最后用了BigInteger，然后非常慢。。。

坑：

用阶乘数太大，越界。用BigInteger太慢。

我的代码：

import java.math.BigInteger;
class Solution {
    public List<Integer> getRow(int rowIndex) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < rowIndex + 1; i++) {
            int element = combinationNumber(rowIndex, i);
            list.add(element);
        }
        return list;
    }
    
    private int combinationNumber(int n, int m) {
        BigInteger bigInteger = new BigInteger("1");
        if (m < n / 2 + 1) {
            for (int i = n; i > n - m; i--) {
                bigInteger = bigInteger.multiply(BigInteger.valueOf(i));
            }
            for (int i = 1; i < m + 1; i++) {
                bigInteger = bigInteger.divide(BigInteger.valueOf(i));
            }
            return bigInteger.intValue();
        } else {
            for (long i = n; i > m; i--) {
                bigInteger = bigInteger.multiply(BigInteger.valueOf(i));
            }
            for (long i = 1; i < n - m + 1; i++) {
                bigInteger = bigInteger.divide(BigInteger.valueOf(i));
            }
            return bigInteger.intValue();
        }
    }
}

最优解：

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> result = new ArrayList<Integer>();
        result.add(1);
        int a = 1; 
        for(int i = 1; i <= rowIndex; i++){      
            a = (int)(a * (double)(rowIndex + 1 - i) / i);
            result.add(a);
        }
        return result;
    }
}

研究了半天，终于明白了。这个方法利用了每一行的组合数中，前后两个数的关系。比如C(6, 1)和C(6, 2)有什么关系呢？

C(6,1)是6的阶乘除以1的阶乘再除以5的阶乘；C(6,2)是6的阶乘除以2的阶乘再除以4的阶乘。

所以其实6的阶乘是永远不变的。唯一的变化就是两个分母，一个加了1，一个减了1。所以用前一个结果乘以一个数再除以一个数就得到了下一个数。

比如当n=6时，也就是求第七行： [1,6,15,20,15,6,1]

15就是用前一个数6，乘以5再除以2得到的。20就是用前一个数15，乘以4再除以3得到的。这里5，2，4，3都是递增递减的，可以通过找规律得出。

Angular

Multiple Actions

Step 1: Adding a new constant in action file

export const ADD_INGREDIENTS = 'ADD_INGREDIENTS';

Step 2: Adding a new class in action file

export class AddIngredients implements Action {
  readonly type = ADD_INGREDIENTS;

  constructor(public payload: Ingredient[]) {}
}

Step 3: Adding a new case in the reducer file

case ShoppingListActions.ADD_INGREDIENTS:
  return {
    ...state,
    ingredients: [...state.ingredients, ...action.payload]
  };

Step 4: Exporting an additional type in the action file

export type ShoppingListActions =
  | AddIngredient
  | AddIngredients
  | UpdateIngredient
  | DeleteIngredient
  | StartEdit
  | StopEdit;

Step 5: Dispatching the action in the recipes service file

import * as ShoppingListActions from '../shopping-list/store/shopping-list.actions';

constructor(private store: Store<fromShoppingList.AppState>) {
  }
  
addIngredientsToShoppingList(ingredients: Ingredient[]) {
    // this.slService.addIngredients(ingredients);
    this.store.dispatch(new ShoppingListActions.AddIngredients(ingredients));
  }