Angular (31) -- NgRx

LeetCode Day 11: P112. Path Sum (Easy)

题目

给一个二叉树和一个数sum。这个数字是几个数的和。求是否有一条从根到叶的路径，使得这条路径上所有的数加起来等于sum。

我的思路：

把所有路径遍历一次，看有没有等于23的。

我的代码：

public class E_112_PathSum {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        List<Integer> list = sum(root);
        for (Integer integer : list) {
            if (integer == sum) {
                return true;
            }
        }
        return false;
    }

    private List<Integer> sum(TreeNode node) {
        if (node == null) {
            return null;
        }
        if (node.left == null && node.right == null) {
            ArrayList<Integer> sums = new ArrayList<>();
            sums.add(node.val);
            return sums;
        }
        if (node.left == null) {
            List<Integer> right = sum(node.right);
            return right.stream().map(integer -> node.val + integer).collect(Collectors.toList());
        }
        if (node.right == null) {
            List<Integer> left = sum(node.left);
            return left.stream().map(integer -> node.val + integer).collect(Collectors.toList());
        }
        List<Integer> left = sum(node.left).stream().map(integer -> node.val + integer).collect(Collectors.toList());
        List<Integer> right = sum(node.right).stream().map(integer -> node.val + integer).collect(Collectors.toList());
        left.addAll(right);
        return left;
    }
}

用了一个辅助方法，每个node都返回一个List，记录下所有可能的和。最后挨个比较。可能由于用了List, Stream等语法，慢得惨不忍睹。。。

最优解：

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null) return false;
        return helper(root, sum);
    }
    
    public boolean helper(TreeNode root, int sum){
        if(root == null) return sum == 0;
        if(root.left == null && root.right == null) return sum - root.val == 0;
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

辅助方法：

如果树是空的，就判断sum是否等于0。

如果左右子树都是空的，那就判断该节点的值是否等于sum。

最后，反向调用主方法，如果左子树或右子树有任意一个，有一条路径的和等于sum减去当前值，就返回true。非常巧妙！

Angular

Introduction to NgRx

It can help us with state management in big applications.

What is state?

All the data that controls what’s visible on the screen is Application State. This application state is lost whenever your application is refreshed, because all we have in an Angular app is just JavaScript.

Typically we use a backend to solve this persistent state problem. State is not just data like stored exercises or recipes, state could also be “this app is currently waiting for some data to be fetched”. Basically, any data, any information that controls what should be visible on the screen is a state.

For example, the isLoading property is a local state that may display a spinner on the screen. We also save states in the storage service.

What’s the problem with this approach?

The bigger your app gets and the more complex your state gets, the state management may become a nightmare.

We already used RXJS to solve it partly. RxJS allows us to create a streamline state management. Using Subjects, we can react to user events or to application events like some data fetching by using Observables. We already have a pretty clear stream of data. But this can be tricky because it forced you providing a good structure and a clean setup and ensuring that all services and all pieces of state are implemented in a good way.

Problems with RxJS:

• State can be updated anywhere.
• State is mutable.
• Handling side effects is unclear

What is Redux?

Redux is a state management pattern. It’s also a library that helps you implement that pattern into any application.

Only one central store in the entire application that holds your application state. The components and services can still communicate with each other, but they receive their state from that store. So that store is the single source of truth.

If we want to change a state, for example we want to add a new item in a data list, then, we dispatch an action. An action is a JavaScript Object with an identifier and a payload. Actions are sent to reducer. A reducer is a JavaScript function that get the current state from the store, and take the action as a input to update the state.

• This update is immutable, only changing the copy.

The reducer returns a new state. Then this state is forwarded to the store and overwrite the old state.

NgRx is Angular’s implementation of Redux.