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--];
        }
    }
}
目录
相关文章
|
4天前
|
存储 算法 Java
算法系列之动态规划
动态规划(Dynamic Programming,简称DP)是一种用于解决复杂问题的算法设计技术。它通过将问题分解为更小的子问题,并存储这些子问题的解来避免重复计算,从而提高算法的效率。
18 4
算法系列之动态规划
|
26天前
|
存储 算法 Java
解锁“分享文件”高效密码:探秘 Java 二叉搜索树算法
在信息爆炸的时代,文件分享至关重要。二叉搜索树(BST)以其高效的查找性能,为文件分享优化提供了新路径。本文聚焦Java环境下BST的应用,介绍其基础结构、实现示例及进阶优化。BST通过有序节点快速定位文件,结合自平衡树、多线程和权限管理,大幅提升文件分享效率与安全性。代码示例展示了文件插入与查找的基本操作,适用于大规模并发场景,确保分享过程流畅高效。掌握BST算法,助力文件分享创新发展。
|
2月前
|
存储 人工智能 算法
解锁分布式文件分享的 Java 一致性哈希算法密码
在数字化时代,文件分享成为信息传播与协同办公的关键环节。本文深入探讨基于Java的一致性哈希算法,该算法通过引入虚拟节点和环形哈希空间,解决了传统哈希算法在分布式存储中的“哈希雪崩”问题,确保文件分配稳定高效。文章还展示了Java实现代码,并展望了其在未来文件分享技术中的应用前景,如结合AI优化节点布局和区块链增强数据安全。
|
2月前
|
算法 安全 Java
Java线程调度揭秘:从算法到策略,让你面试稳赢!
在社招面试中,关于线程调度和同步的相关问题常常让人感到棘手。今天,我们将深入解析Java中的线程调度算法、调度策略,探讨线程调度器、时间分片的工作原理,并带你了解常见的线程同步方法。让我们一起破解这些面试难题,提升你的Java并发编程技能!
88 16
|
12天前
|
算法 安全 调度
【动态规划篇】穿越算法迷雾:约瑟夫环问题的奇幻密码
【动态规划篇】穿越算法迷雾:约瑟夫环问题的奇幻密码
|
12天前
|
机器学习/深度学习 算法 测试技术
【动态规划篇】01 背包的逆袭:如何用算法装满你的 “财富背包”
【动态规划篇】01 背包的逆袭:如何用算法装满你的 “财富背包”
|
2月前
|
存储 监控 算法
剖析基于Java算法驱动的智能局域网管控之道
本文探讨了基于Java语言的局域网控制方案,结合链表数据结构与令牌桶算法,解决设备管理和流量调度难题。通过链表灵活存储网络设备信息,实现高效设备管理;令牌桶算法则精准控制流量,确保网络平稳运行。二者相辅相成,为校园、企业等局域网提供稳固高效的控制体系,保障业务连续性和数据安全。
|
2月前
|
算法 搜索推荐 Java
【潜意识Java】深度解析黑马项目《苍穹外卖》与蓝桥杯算法的结合问题
本文探讨了如何将算法学习与实际项目相结合,以提升编程竞赛中的解题能力。通过《苍穹外卖》项目,介绍了订单配送路径规划(基于动态规划解决旅行商问题)和商品推荐系统(基于贪心算法)。这些实例不仅展示了算法在实际业务中的应用,还帮助读者更好地准备蓝桥杯等编程竞赛。结合具体代码实现和解析,文章详细说明了如何运用算法优化项目功能,提高解决问题的能力。
75 6
|
2月前
|
算法 Java C++
【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题
本文介绍了经典的0/1背包问题及其动态规划解法。
57 5
|
6月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行