# 第七十二周ARTS总结

# Algorithm

Binary Tree Inorder Traversal (opens new window)

0ms | 100.00% Run time
37.3MB | 47.05% Memory

// 递归方式实现
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();

    if (root == null) {
        return ans;
    }

    if (root.left != null) {
        inorderRecursive(root.left, ans);
    }

    ans.add(root.val);

    if (root.right != null) {
        inorderRecursive(root.right, ans);
    }

    return ans;
}

private void inorderRecursive(TreeNode treeNode, List<Integer> ans) {
    if (treeNode.left != null) {
        inorderRecursive(treeNode.left, ans);
    }

    ans.add(treeNode.val);

    if (treeNode.right != null) {
        inorderRecursive(treeNode.right, ans);
    }
}

// 迭代方式实现
public List<Integer> inorderTraversal2(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.push(root);

        while (stack.peek() != null) {
        TreeNode cur = stack.peek();

        // 左树入栈
        if (cur.left != null) {
        stack.push(cur.left);
        cur.left = null;
        continue;
        }

        ans.add(cur.val);
        stack.pop();

        // 右树入栈
        if (cur.right != null) {
        stack.push(cur.right);
        }
        }

        return ans;
}

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

# Review

Welcome you are visitor number 12345 (opens new window)

# Tip

如果某个View的fitsSystemWindows设为true，那么该View的padding属性将由系统设置，用户在布局文件中设置的padding会被忽略。系统会为该View设置一个paddingTop，值为statusbar的高度
可通过setOnApplyWindowInsetsListener来对fitsSystemWindows个性化
SNAPSHOT的用途：假如A模块依赖了SNAPSHOT的B模块，则每次编译的时候都会去找最新的版本
算法思想
- 递归算法
  - 优缺点
    - 优点：实现简单易上手
    - 缺点：递归太深，容易发生栈溢出
  - 适用场景
    - 数据的定义是按递归定义的（菲波那切数列）
    - 问题解法按递归算法实现（回溯）
    - 数据的结构形式是按递归定义的（树的遍历，图的搜索）
- 分治算法
  - 适用场景
    - 原始问题可以分成多个相似的子问题
    - 子问题可以很简单的求解
    - 原始问题的解是子问题的合并
    - 各个子问题是相互独立的
- 贪心算法
  - 适用场景
    - 原问题复杂度过高
    - 求全局最优解的数学模型难以建立或计算量过大
    - 没有太大必要一定要求出全局最优解，“比较优”就可以
- 回溯算法
  - 适用场景：用于解决广度的搜索问题，即从一组可能的解中选择一个满足要求的解
  - 经典案例
    - 深度优先搜索
    - 0-1背包问题
    - 正则表达式匹配
    - 八皇后
    - 数独
    - 全排列
- 动态规划
  - 经典案例
    - 爬楼梯问题
    - 背包问题
    - 硬币找零
    - 图的全源最短路径问题
    - 最长公共子序列
- 枚举算法
卡顿监控
- Looper.getMainLooper().setMessageLogging(printer)
- Gradle Plugin + ASM

暂无内容

← 第七十一周ARTS总结第七十三周ARTS总结 →

# 第七十二周ARTS总结

# Algorithm

# Review

# Tip

# Share