极客时间-算法训练营 3.2

一 序

 本文属于极客时间-算法训练营 学习笔记。

对应章节：极客时间-算法训练营 学习笔记 3递归的实现、特性以及思维要点

二 70Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps Example 2:

Input: 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step 这个题目，覃超老师没有太多展开去讲：

强调了一点，寻找规律。就是利用数学归纳法来找到题目隐藏的斐波那契数列。

设f(n)表示爬n阶楼梯的不同方法数，进而分析出：

   f(n) = f(n-1)+f(n-2).

三种解法：

 只有递归：不过

1）使用递归+缓存。

2）使用数组，来实现动态规划。

3） 直接利用函数公式（前提数学好）

感兴趣的可以看看：https://blog.csdn.net/bohu83/article/details/102528611

三 22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[ "((()))", "(()())", "(())()", "()(())", "()()()" ]

这个题目，覃超老师亲自示范了解题思路。

我记录下：

1是读题：生成N对匹配括号。列出所有可能。熟悉的同学可以直接跳过了。

切到IDE里面：

先不考虑合法匹配的问题，问题简化成再2*N的长度填充括号。

套用了递归的模板：

public void recur(int level,int param){ //递归终结条件 if(level>MAX_LEVEL){ return; } //处理当前层 process(level,param); //下探到下一层 recur(level:level+1,newParam); //清理当前层 //reverse the current level status if needed } ———————————————— 版权声明：本文为博主「bohu83」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/bohu83/article/details/107094970

递归函数的参数：当前level,最大层数，当前字符串 

public class Code22 { public static void main(String[] args) { Code22 code = new Code22(); code.generateParenthesis(3); } public List<String> generateParenthesis(int n) { generate(0,2*n,""); return null; } public void generate(int level,int max,String s){ //终止 if(level>=max){ System.out.println(s); return; } // this level String s1 = s+"("; String s2 =s+")"; // next level generate(level+1,max,s1); generate(level+1,max,s2); } }

输出结果：

(((((( ((((() (((()( (((()) ((()(( ((()() ((())( ((())) (()((( (()(() (()()( (()()) (())(( (())() (()))( (()))) ()(((( ()((() ()(()( ()(()) ()()(( ()()() ()())( ()())) ())((( ())(() ())()( ())()) ()))(( ()))() ())))( ())))) )((((( )(((() )((()( )((()) )(()(( )(()() )(())( )(())) )()((( )()(() )()()( )()()) )())(( )())() )()))( )()))) ))(((( ))((() ))(()( ))(()) ))()(( ))()() ))())( ))())) )))((( )))(() )))()( )))()) ))))(( ))))() )))))( ))))))

再判断括号是否合法 ：

 左括号不能》n 右括号 左括号个数》右括号的个数

这个两个条件就能覆盖了题目的要求。

因此，修改题目的递归函数，改为左括号数，右括号数、N，

public List<String> generateParenthesis(int n) { generate(0,0,n,""); return null; } public void generate(int left,int right,int n,String s){ //终止 if(left>=n && right>=left){ System.out.println(s); return; } // this level // next level if(left<n) {//左括号能添加 generate(left + 1, right,n, s + "("); } if(left>right) {//右括号能添加 generate(left ,right+1, n, s + ")"); } }

这里输出的就是合法的了：

((())) (()()) (())() ()(()) ()()()

这里对比之前，就发现少了无效的结果，也就是使用逻辑判断提前减去不合法的分支。所谓的”剪枝“。

当然，本地做完了，需要再LeetCode补充完代码，输出结果

所以关键的是：怎么梳理思路写递归。怎么确定参数。

好了，讲完这个例子，超哥有blabla说了一通实际生活中递归的应用，脑洞大开，吧黑客帝国的场景都搬出来了。

有没有道家的一生二，二生三，三生万物的感觉。

最后，强调关注下LeetCode国际站，

先看官方题解，再看most votes. 可以关注下自己的语言： 更容易理解。

养成一种习惯，就是喜欢看别人的代码，要是简洁易懂就好好学习，练会学会。没几行就实现了不是很好懂的，也算提升自己的代码理解能力。怎么着都有好处。

超哥强调的这种悟道、有感觉就是这个意思。简单来说，你知道去哪里学习别人的好代码，也自我培养不断练习学习的习惯，那肯定有收获嘛。

如果不明白，就反复多看几遍视频。

 

四 98. Validate Binary Search Tree

问题：

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.The right subtree of a node contains only nodes with keys greater than the node's key.Both the left and right subtrees must also be binary search trees.

 

Example 1:

2 / \ 1 3 Input: [2,1,3] Output: true

Example 2:

5 / \ 1 4   / \   3 6 Input: [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4.

问题是校验一颗树是否是二叉搜索树。

条件就是左子树比根节点小，右子树比根节点大。

常规思路会去套用递归。

递归的判断的就是边界。没听超哥讲，做了半小时，各种翻车。

有一个容易陷入的误区就是：之比较左节点右节点，而是要比较整个左子树、右子树。

就是这个常规思路就是参照定义：来确定递归的参数：当前节点以及最小、最大值。

左子树范围就是（min,当前节点val),右子树范围就是（当前节点val,max）

实际做的时候各种边界问题：比如这个

[2147483647]

还是需要反复练习。

覃超老师，后来提到了利用二叉树中序遍历，结果是升序的。来验证。

这个还没做，待补充。