第70题 难度:简单 题目爬楼梯
package _70爬楼梯;
/*
方法三:动态规划
算法
不难发现,这个问题可以被分解为一些包含最优子结构的子问题,即它的最优解可以从其子问题的最优解来有效地构建,我们可以使用动态规划来解决这一问题。
第 i 阶可以由以下两种方法得到:
算法
不难发现,这个问题可以被分解为一些包含最优子结构的子问题,即它的最优解可以从其子问题的最优解来有效地构建,我们可以使用动态规划来解决这一问题。
第 i 阶可以由以下两种方法得到:
在第 (i−1) 阶后向上爬一阶。
在第 (i−2)阶后向上爬 2 阶。
所以到达第 3 阶的方法总数就是到第 (i−1)) 阶和第 (i−2)阶的方法数之和。
令 dp[i] 表示能到达第 i 阶的方法总数:
dp[i]=dp[i−1]+dp[i−2] */
public class Solution { public int climbStairs(int n) { if(n==1) return 1; int first=1; int second=2; for(int i=3;i<=n;i++) { int third=first+second; first=second; second=third; } return second; } }
第107题 难度:简单 题目:二叉树的层次遍历
重点:如何记住层次遍历,每一层的最后一个元素,也可以来保存是第几层,图的广度优先也可以类似
package _107二叉树的层次遍历; import java.util.Collection; import java.util.Iterator; import java.util.List; import java.util.*; class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public class Solution { public static List<List<Integer>> levelOrderBottom(TreeNode root) { //用一个相当于二维数组一样的表来存储每一层的元素 //题目要求倒着存储每一层的元素,故采用栈来反转 List<List<Integer>> lists=new ArrayList<List<Integer>>() ; Queue<TreeNode> Q=new LinkedList<TreeNode>(); //指向每一层最后一个元素 TreeNode last=root; //临时指向每一层最后一个元素 TreeNode tmp=root; Q.add(root); TreeNode T; //存放一层的元素 List<Integer> list1=new ArrayList<>(); Stack<List<Integer>> S=new Stack<>(); while(Q.isEmpty()==false) { T=Q.poll(); //将访问的元素,放入 list1.add(T.val); //将左右结点放入队列中,同时tmp指向 if(T.left!=null) { Q.add(T.left); tmp=T.left; } if(T.right!=null) { Q.add(T.right); tmp=T.right; } //队列弹出的元素是这一层最后一个元素,更改last指向新的最后一个元素tmp //同时申请下一层的空间 if(T==last) { S.push(list1); last=tmp; list1=new ArrayList<>(); } } //将栈中每一层弹出,放入lists中 while(S.isEmpty()==false) { lists.add(S.pop()); } return lists; } }