Jerry's Blog

Recording what I learned everyday

View on GitHub


17 July 2019

Angular (32) -- NgRx

by Jerry Zhang

LeetCode Day 12: P118. Pascal’s Triangle (Easy)

题目

给一个正整数n，生成一个n层的杨辉三角数组。

Example:

Input: 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

我的思路：

一开始想一层一层算，后来想如果直接用二项式系数的公式算会不会更快。所以就用组合数公式计算了每个位置的值，然后填到每层数组中。

然而事实证明，因为每一层都要算，用公式还不如一层一层直接求和呢。。。

如果是只求第n层，那无疑我的算法会快很多，因为一层一层算，时间复杂度是n^2。直接用公式是n

我的代码：

public class E_118_PascalsTriangle {
    public static List<List<Integer>> generate(int numRows) {
        ArrayList<List<Integer>> outerList = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            ArrayList<Integer> innerList = new ArrayList<>();
            for (int j = 0; j < i + 1; j++) {
                long element = combinationNumber(i, j);
                innerList.add((int) element);
            }
            outerList.add(innerList);
        }
        return outerList;
    }

    private static long combinationNumber(int n, int m) {
        if (m < n / 2 + 1) {
            long temp = 1;
            for (long i = n; i > n - m; i--) {
                temp = temp * i;
            }
            for (long i = 1; i < m + 1; i++) {
                temp = temp / i;
            }
            return temp;
        } else {
            long temp = 1;
            for (long i = n; i > m; i--) {
                temp = temp * i;
            }
            for (long i = 1; i < n - m + 1; i++) {
                temp = temp / i;
            }
            return temp;
        }
    }

    public static void main(String[] args) {
        generate(25);
    }
}

坑：

一开始因为用了阶乘的公式来计算C(n, m)组合数，导致当n = 25时就超过整数的范围了。

于是费了很大的劲自己写了一个计算组合数的方法。Debug很多次才正确。

最优解：

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> A = new LinkedList<List<Integer>>();
        if (numRows <= 0)
            return A;
        LinkedList<Integer> temp = new LinkedList<Integer>();
        temp.add(1);
        A.add(temp);
        pro(A, 1, numRows);
        return A;
    }
    private void pro(List<List<Integer>> A, int i, int L){
        if (i >= L)
            return;
        ArrayList<Integer> toAdd = new ArrayList<Integer>();
        toAdd.add(1);
        List<Integer> prev = A.get(A.size()-1);
        for (int j = 1; j < prev.size(); j++){
            toAdd.add(prev.get(j-1)+prev.get(j));
        } 
        toAdd.add(1);
        A.add(toAdd);
        pro(A, i+1, L);
    }
}

Angular

Install NgRx

npm install --save @ngrx/store

Then, the most important things are Store, Reducers, and Actions.

Store and Reducer are tightly coupled together.

Create a reducer

Create a new file called shopping-list.reducer.ts in the shopping-list component.

import {Ingredient} from '../../shared/ingredient.model';
import * as ShoppingListActions from './shopping-list.actions';

const initialState = {
  ingredients: [
    new Ingredient('Apples', 5),
    new Ingredient('Tomatoes', 10)
  ]
};

export function shoppingListReducer(state = initialState,
                                    action: ShoppingListActions.AddIngredient) {
  switch (action.type) {
    case ShoppingListActions.ADD_INGREDIENT:
      return {
        ...state,
        ingredients: [...state.ingredients, action.payload]
      };
    default:
      return state;
  }
}

A Reducer takes two arguments, the state of that app and an action to be executed on this state. We can use a switch statement to check which action was passed in an run different code based on that. In the switch condition, we have to check the type of this action. Action is imported from @ngrx/store. As a developer, we can define which action we have in this application. It is simply a string. Here, we outsourced the string in anther action file and refer it as ShoppingListAction.ADD_INGREDIENT.

In each case, we have to return a new state.

Warning: Changing the state directly is totally wrong!

If we push a new ingredient like this in the method:

case ShoppingListActions.ADD_INGREDIENT:
      return {
        state.ingredients.push();
        return;
      };

This is totally wrong, because state changes with NgRx always have to be immutable, which means you must not edit the existing or the previous state. Instead, return a new object which will replace the old state. To not lose all the old data, copy the old state with the spread operator. Like this:

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

...state pulls out all the properties of the old state, and adds these properties to this new object.

Here, because all we have in the state is just an array of ingredient, called ingredients, we actually are copying the ingredients object first, then overwrite it.

In other apps, we may have many states. So always copy the old state then overwrite what you want to change.

Create an Action

Create a new file called shopping-list.actions.ts in the shopping-list folder.

import { Action } from '@ngrx/store';
import {Ingredient} from '../../shared/ingredient.model';

export const ADD_INGREDIENT = 'ADD_INGREDIENT';

export class AddIngredient implements Action {
  readonly type: string = ADD_INGREDIENT;

  constructor(public payload: Ingredient) {}
}

In this file, we export a constant firstly to avoid typo. Secondly, we created a class AddIngredient and implements Action from @ngrx/store.

Use the actions

Because we export more than one thing in the actions file, we can use an alias to group all the things from this actions file into one object when we use them in the reducer.

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

And now the case becomes ShoppingListActions.ADD_INGREDIENT. And also, we can use action.payload to refer to the ingredient we want to add.

Use the reducer and actions

To use everything we set up, we firstly need to import the StoreModule in the app.module.ts. We also need to tell NgRx what makes up our store, which reducers are involved. So we call forRoot and we pass in an action-reducer map.

imports: [
    BrowserModule,
    HttpClientModule,
    AppRoutingModule,
    StoreModule.forRoot({shoppingList: shoppingListReducer}),
    SharedModule,
    CoreModule
  ],

Here, the name shoppingList is defined by us.

Use the store

To use the StoreModule we just imported, inject the store in the ShoppingListComponent.

constructor(private slService: ShoppingListService,
              private loggingService: LoggingService,
              private store: Store<{shoppingList: {ingredients: Ingredient[]}}>) { }

Store is a generic type. The type is the structure we set up in the app module.

The key must be the key we set up in the app module, shoppingList. The type of the data stored in the shoppingList is what the reducer function returns.

Before we get ingredients from the shopping list service. Now, we want to get the ingredients from the store.

ingredients: Observable<{ingredients: Ingredient[]}> ;

ngOnInit() {
    this.ingredients = this.store.select('shoppingList');
    // this.ingredients = this.slService.getIngredients();
    // this.igChangeSub = this.slService.ingredientsChanged
    //   .subscribe(
    //     (ingredients: Ingredient[]) => {
    //       this.ingredients = ingredients;
    //     }
    //   );
    this.loggingService.printLog('Hello from shoppingList component.');
  }

We changed the ingredients to an observable, so we also need to modify our template.

*ngFor="let ingredient of (ingredients | async).ingredients; let i = index"

If you don’t want to use the pipe, you can also subscribe this observable in the component.

this.store.select('shoppingList').subscribe();

Dispatching the actions.

The shopping edit component is the place where we change the ingredients that are displayed.

We need to inject the store in the constructor.

constructor(private slService: ShoppingListService,
              private store: Store<{shoppingList: {ingredients: Ingredient[]}}>) { }

When we submit the new ingredient that we added in the onSubmit method, instead of calling addIngredient method from the service, we use the dispatch() method from the store and pass in a new object based on that action class.

this.store.dispatch(new ShoppingListActions.AddIngredient(newIngredient));

总结 In Conclusion:

tags: Angular