Skip to content

Latest commit

 

History

History
 
 

Week_03

README.md

学习笔记

第七课 泛型递归、树的递归

递归 Recursion

  • 递归-循环
  • 通过函数体来进行的循环

Java代码模板

    public void recur(int level, int param) {

        // terminator
        // 递归终结条件
        if (level > MAX_LEVEL) {
            // process result
            return;
        }

        // process current logic
        // 处理当前层
        process(level, param);

        // drill down
        // 下探到下一层
        recur(level + 1, newParam);

        // restore current status
        // 清理当前层
    }

思维要点

  1. 不要人肉进行递归（最大误区）
  2. 找到最近最简方法，将其拆解成可重复解决的问题（重复子问题）
  3. 数学归纳法思维

第八课 分治、回溯

分治 Divide&Conquer

代码模板

    private static int divide_conquer(Problem problem,) {
        // recursion terminator
        if (problem == NULL) {
            int res = process_last_result();
            return res;
        }

        // prepare data
        data = prepare_dara(problem);
        subProblems = split_problem(problem);

        // conquer subproblems
        res0 = divide_conquer(subProblems[0]);
        res1 = divide_conquer(subProblems[1]);
        // ...

        // process and generate the final result
        result = process_result(res0, res1);

        // revert the current level states

        return result;
    }

回溯 Backtracking

回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。 回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况:

  • 找到一个可能存在的正确的答案;
  • 在尝试了所有可能的分步方法后宣告该问题没有答案。 在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。

实战题目&作业

0823 Sun

题目编号 题目名称 难度 类型 #1 #2 #3 #4 #5
297 serialize-and-deserialize-binary-tree Hard Recursion 0823/0823 0823/0823 0824/0824 0831/0831
98 validate-binary-search-tree Medium Recursion 0823/0823 0823/0823 0824/0825 0831/0831
104 maximum-depth-of-binary-tree Easy Recursion 0823/0823 0823/0823 0824/0824 0831/0831
111 minimum-depth-of-binary-tree Easy Recursion 0823/0823 0823/0823 0824/0824 0831/0831

0824 Mon

题目编号 题目名称 难度 类型 #1 #2 #3 #4 #5
236 lowest-common-ancestor-of-a-binary-tree Medium Recursion 0824/0824 0824/0824 0825/0825 0901/0902
105 construct-binary-tree-from-preorder-and-inorder-traversal Medium Recursion 0824/0824 0824/0824 0825/0825 0901/0902
77 combinations Medium Recursion 0824/0824 0824/0824 0825/0825 0901/0902
226 invert-binary-tree Easy Recursion 0824/0824 0824/0824 0825/0825 0901/0902

0825 Tue

题目编号 题目名称 难度 类型 #1 #2 #3 #4 #5
51 n-queens Hard Backtracking 0825/0825 0825/0825 0826/0826 0902/0906
46 permutations Medium Recursion 0825/0825 0825/0825 0826/0826 0902/0906
47 permutations-ii Medium Recursion 0825/0825 0825/0825 0826/0826 0902/0906
169 majority-element Easy DivideConquer 0825/0825 0825/0825 0826/0826 0902/0906

0826 Wed

题目编号 题目名称 难度 类型 #1 #2 #3 #4 #5
78 subsets Medium Backtracking 0826/0826 0826/0826 0827/0827 0903/0905
50 powx-n Medium Divide&Conquer 0826/0826 0826/0826 0827/0827 0903/0905
17 letter-combinations-of-a-phone-number Medium Backtracking 0826/0826 0826/0826 0827/0827 0903/0905
455 assign-cookies Easy Greedy 0826/0826 0826/0826 0827/0827 0903/0905

预习题目

0827 Thu

题目编号 题目名称 难度 类型 #1 #2 #3 #4 #5
102 binary-tree-level-order-traversal Medium DFS&BFS 0827/0827 0827/0827 0828/0829 0904/0904
55 jump-game Medium Greedy 0827/0827 0827/0827 0828/0828 0904/0904
122 best-time-to-buy-and-sell-stock-ii Easy Greedy 0827/0827 0827/0827 0828/0828 0904/0904

0828 Fri

Have a day off;

0829 Sta

题目编号 题目名称 难度 类型 #1 #2 #3 #4 #5
69 sqrtx Easy BinarySearch 0829/0829 0829/0829 0830/0830 0906/0906
367 valid-perfect-square Easy BinarySearch 0829/0829 0829/0829 0830/0830 0906/0906
剑指Offer05 替换空格 Easy Array 0829/0829 0829/0829 0830/0830 0906/0906
剑指Offer06 从尾到头打印链表 Easy Stack 0829/0829 0829/0829 0830/0830 0906/0906