leetcode算法题解(Java版)-15-动态规划(斐波那契)
一、二叉树遍历
题目描述
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
思路
- 两种思路,都是递归。第一种是递归的判断每个节点的左右子树的深度是否只相差一以内。第二种做了剪枝处理,当判断到一个子树已经不满足时就返回结果。
代码
//思路一 /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public boolean isBalanced(TreeNode root) { if(root==null){ return true; } if(Math.abs(maxDepth(root.left)-maxDepth(root.right))>1){ return false; } //如果这个节点的左右子树高度差小于等于一,那就递归看它的左右子树节点是否合格 return isBalanced(root.left)&&isBalanced(root.right); } private int maxDepth(TreeNode root){ if(root==null){ return 0; } return Math.max(maxDepth(root.left),maxDepth(root.right))+1; } } //思路二 /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public boolean isBalanced(TreeNode root) { if(root==null){ return true; } return getHeight(root)!=-1; } private int getHeight(TreeNode root){ if(root==null){ return 0; } int left = getHeight(root.left); if(left==-1){ return -1; } int right = getHeight(root.right); if(right==-1){ return -1; } if(left-right>1||right-left>1){ return -1; } return 1+Math.max(left,right); } }
二、动态规划(斐波那契)
题目描述
A message containing letters fromA-Zis being encoded to numbers using the following mapping:
'A' -> 1 'B' -> 2 ... 'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message"12", it could be decoded as"AB"(1 2) or"L"(12).
The number of ways decoding"12"is 2.
思路
- 这题有点意思,和之前做过的一道动态规划题很相似。多了判断条件,难度稍微提高了一些。老样子,碰到动态规划,拿出dp数组,大概思路:
dp[i]=dp[i-1]+dp[i-2]
代码
public class Solution { public int numDecodings(String s) { int len = s.length(); if(len==0||s.charAt(0)=='0'){ return 0; } int [] dp = new int[len+1]; //dp[i]表示s字符前i个构成的子串的解码的种数 dp[0] = 1;//这个为了后面好计算,不理解可以到后面再回来看 dp[1] = 1; for(int i=1;i<len;i++){ String num = s.substring(i-1,i+1); if(Integer.valueOf(num)<=26&&s.charAt(i-1)!='0'){ dp[i+1]=dp[i+1-2]; } if(s.charAt(i)!='0'){ dp[i+1]+=dp[i+1-1]; } } return dp[len]; } }
三、排序
题目描述
Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note:
You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.
思路
- 不能开辟新空间,考虑从后往前插入A中。
代码
public class Solution { public void merge(int A[], int m, int B[], int n) { int i = m-1; int j = n-1; int index = m+n-1; while(i>=0&&j>=0){ A[index--]=A[i]>B[j]?A[i--]:B[j--]; } while(j>=0){ A[index--]=B[j--]; } } }
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
python svm pca实践二
继上一片的内容,这片来·讲一下sklearn来进行简单的人脸识别,这里用的方法是pca和svm 先导入必要的包和数据集 import numpy as np import matplotlib.pyplot as plt from scipy import stats from sklearn.decomposition import PCA from sklearn.svm import SVC from sklearn import datasets lfw_people = datasets.fetch_lfw_people(min_faces_per_person=70, \ resize=0.4) sklearn的人脸数据集包含5千多个不同人的人脸,但有些人的人脸只包含一张, n_samples, h, w = lfw_people.images.shape print('height and width of images:', h, w) # The images in X have been collapsed into a 1D array # just like f...
- 下一篇
JavaScript高级程序设计学习(四)之引用类型(续)
一、Date类型 其实引用类型和相关的操作方法,远远不止昨天的所说的那些,还有一部分今天继续补充。 在java中日期Date,它所属的包有sql包,也有util包。我个人比较喜欢用util包的。理由,顺手习惯,个人也觉得比较好用。sql的Date类用的不算多。也用过。 下面就进入正题吧,不单单在java,在js中也存在日期函数,或换言之,日期对象。 var now = new Date(); 通过now.getYear(),now.getMonth(),now.getMonth(),简单的翻译,可以理解为获得当前的年月日。 now翻译过来表示现在,之所以采取这样的命名,还是那就话,规范起见。 js获得的日期,通常情况要么通过字符串拼接,要么通过格式转换,达到自己想要的那样。 常用的格式转换方法如下: toDateString()——以特定于实现的格式显示星期几、月、日和年; toTimeString()——以特定于实现的格式显示时、分、秒和时区; toLocaleDateString()——以特定于地区的格式显示星期几、月、日和年; toLocaleTimeString...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- SpringBoot2整合Thymeleaf,官方推荐html解决方案
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题
- CentOS8编译安装MySQL8.0.19
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- CentOS7,CentOS8安装Elasticsearch6.8.6
- MySQL8.0.19开启GTID主从同步CentOS8
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- Windows10,CentOS7,CentOS8安装Nodejs环境