更新时间:2022-04-16 23:34:24
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[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.
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--];
}
}
}