leetcode算法题解(Java版)-15-动态规划(斐波那契)-阿里云开发者社区

开发者社区> 开发与运维> 正文

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--];
        }
    }
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章