【学习报告】《LeetCode零基础指南》(第九讲) 简单递归
目录
一、练习题目
172. 阶乘后的零
1342. 将数字变成 0 的操作次数
LCP 44. 开幕式焰火
397. 整数替换
938. 二叉搜索树的范围和
剑指 Offer 55 - I. 二叉树的深度
226. 翻转二叉树
剑指 Offer II 110. 所有路径
二、答题总结
一、练习题目
172. 阶乘后的零
给定一个整数 n ，返回 n! 结果中尾随零的数量。
提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1
示例 1：
输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0
示例 2：输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0
示例 3：输入：n = 0
输出：0
class Solution { public int trailingZeroes(int n) { if(n < 5) { return 0; } return n / 5 + trailingZeroes(n/5); }}1342. 将数字变成 0 的操作次数
给你一个非负整数 num ，请你返回将它变成 0 所需要的步数。 如果当前数字是偶数，你需要把它除以 2 ；否则，减去 1 。
示例 1：
输入：num = 14
输出：6
解释：
步骤 1) 14 是偶数，除以 2 得到 7 。
步骤 2） 7 是奇数，减 1 得到 6 。
步骤 3） 6 是偶数，除以 2 得到 3 。
步骤 4） 3 是奇数，减 1 得到 2 。
步骤 5） 2 是偶数，除以 2 得到 1 。
步骤 6） 1 是奇数，减 1 得到 0 。
示例 2：输入：num = 8
输出：4
解释：
步骤 1） 8 是偶数，除以 2 得到 4 。
步骤 2） 4 是偶数，除以 2 得到 2 。
步骤 3） 2 是偶数，除以 2 得到 1 。
步骤 4） 1 是奇数，减 1 得到 0 。
示例 3：输入：num = 123
输出：12
class Solution { public int numberOfSteps(int num) { int sum=0; while(num!=0){ if(num%2==1){ num -= 1; sum++; }else if(num%2==0){ num /= 2; sum++; } } return sum; }}222. 完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例 1：
输入：root = [1,2,3,4,5,6]
输出：6
示例 2：输入：root = []
输出：0
示例 3：输入：root = [1]
输出：1
/ * Definition for a binary tree node. * 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; * } * } */class Solution { public int countNodes(TreeNode root) { return root == null ? 0 : countNodes(root.left) + countNodes(root.right) + 1; }}LCP 44. 开幕式焰火
「力扣挑战赛」开幕式开始了，空中绽放了一颗二叉树形的巨型焰火。
给定一棵二叉树 root 代表焰火，节点值表示巨型焰火这一位置的颜色种类。请帮小扣计算巨型焰火有多少种不同的颜色。示例 1：
输入：root = [1,3,2,1,null,2]
输出：3
解释：焰火中有 3 个不同的颜色，值分别为 1、2、3
示例 2：
输入：root = [3,3,3]
输出：1
解释：焰火中仅出现 1 个颜色，值为 3
/ * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { Set set = new HashSet(); public int numColor(TreeNode root) { if(root == null) return 0; set.add(root.val); numColor(root.left); numColor(root.right); return set.size(); }}397. 整数替换
给定一个正整数 n ，你可以做如下操作：
如果 n 是偶数，则用 n / 2替换 n 。
如果 n 是奇数，则可以用 n + 1或n - 1替换 n 。
返回 n 变为 1 所需的 最小替换次数 。示例 1：
输入：n = 8
输出：3
解释：8 -> 4 -> 2 -> 1
示例 2：输入：n = 7
输出：4
解释：7 -> 8 -> 4 -> 2 -> 1
或 7 -> 6 -> 3 -> 2 -> 1
示例 3：输入：n = 4
输出：2
class Solution { public int integerReplacement(int n) { return (int)func((long)n); } public long func(long n){ if(n ==1) return 0; if(n%2==0){ return 1 + func(n/2); }else { return 1 + Math.min(func(n+1),func(n-1)); } }}938. 二叉搜索树的范围和
给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。
示例 1：
输入：root = [10,5,15,3,7,null,18], low = 7, high = 15
输出：32
示例 2：输入：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
输出：23
/ * Definition for a binary tree node. * 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; * } * } */class Solution { public int rangeSumBST(TreeNode root, int L, int R) { if (root == null) return 0; if(root.val >= L && root.val <= R) { //当前节点再两数之间，把自身值加到结果里取，并往左右子节点递归 return root.val + rangeSumBST(root.left, L ,R) + rangeSumBST(root.right, L , R); } else if(root.val < L){ //当前节点小于L，往右子节点寻找 return rangeSumBST(root.right, L, R); } else { //当前节点大于R，往左子节点寻找 return rangeSumBST(root.left, L, R); } }}剑指 Offer 55 - I. 二叉树的深度
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例如：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
/ * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public int maxDepth(TreeNode root) { return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; }}226. 翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
示例 2：输入：root = [2,1,3]
输出：[2,3,1]
示例 3：输入：root = []
输出：[]
/ * Definition for a binary tree node. * 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; * } * } */class Solution { public TreeNode invertTree(TreeNode root) { if(root==null){ return null; } TreeNode temp=root.right; root.right=root.left; root.left=temp; invertTree(root.left); invertTree(root.right); return root; } }剑指 Offer II 110. 所有路径
给定一个有 n 个节点的有向无环图，用二维数组 graph 表示，请找到所有从 0 到 n-1 的路径并输出（不要求按顺序）。
graph 的第 i 个数组中的单元都表示有向图中 i 号节点所能到达的下一些结点（译者注：有向图是有方向的，即规定了 a→b 你就不能从 b→a ），若为空，就是没有下一个节点了。
示例 1：
输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3
示例 2：输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]
输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
示例 3：输入：graph = [[1],[]]
输出：[[0,1]]
示例 4：输入：graph = [[1,2,3],[2],[3],[]]
输出：[[0,1,2,3],[0,2,3],[0,3]]
示例 5：输入：graph = [[1,3],[2],[3],[]]
输出：[[0,1,2,3],[0,3]]
class Solution { List<List> ans = new ArrayList(); // 回溯的结果集 public List<List> allPathsSourceTarget(int[][] graph) { Deque deque = new ArrayDeque(); // 每一个回溯结果的路径 deque.add(0); // 注意这里首先需要将节点0压入队列，方便后续回溯算法的处理 allPathPro(graph,0,deque); // 调用回溯算法 return ans; } // 回溯算法的函数基本上是不需要返回值的，因为符合条件的结果都会保存在 ans 中 public void allPathPro(int[][] graph, int index, Deque deque){ // 首先要确定递归函数的返回值， 当遍历到最后一个节点的时候，说明当前路径能到最后一个节点，将当前路劲添加到结果集中，并reeturn if (index == graph.length - 1){ ans.add(new ArrayList(deque)); return; } //开始进行回溯算法，回溯算法的具体流程去看别人的图解 for (int i = 0; i < graph[index].length; i++) { deque.add(graph[index][i]); //将当前节点压入队列 allPathPro(graph, graph[index][i], deque); // 递归调用 deque.removeLast(); //回溯，弹出刚刚压入的节点 } return; }}二、答题总结
今天的题直接给我做emo了，前面的题还好，越往后越难过，救命！可能是没学二叉树的原因，直接看不懂题目意思了，唉，学校确实没讲，但是你不会自学吗！！？？最近先学一下基本，蓝桥要考的算法，必须要学！！【代码是在lc题解里找的我大概能看懂的】
