首页 > 编程语言 >算法总结

算法总结

时间:2022-08-31 22:57:23浏览次数:47  
标签:总结 curr int prefix 算法 TreeNode root 节点

1.经典的青蛙跳台阶

package com.chenghaixiang.fist.P5;

/**
 * @author 程海翔
 * @school 石家庄铁道大学
 */
public class P5 {

}
class Solution{
    public int fib(int n){
        if(n==1){
            return 1;
        }
        //没有台阶也是一种跳法
        if(n==0){
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        //动态规划
//        int arr[]=new int[n+1];
//        arr[0] = 1;
//        arr[1] = 1;
//        arr[2] = 2;
//        for (int i=3;i<n+1;i++){
//            arr[i]=arr[i-1]+arr[i-2];
//        }
//        return arr[n];

        //递归
        return fib(n-1)+fib(n-2);
    }
}
View Code

2.向下的路径节点之和

给定一个二叉树的根节点 root ,和一个整数 targetSum ,求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。

题解:

package com.chenghaixiang.jianzhi2.day17;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 程海翔
 * @school 石家庄铁道大学
 */
public class Office50 {
}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
//给定一个二叉树的根节点 root ,和一个整数 targetSum ,求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
//
//路径 不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。
class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        HashMap<Integer,Integer> prefix=new HashMap<>();
        // 表示前缀和为0的节点为空,有一个空。否则若pre_i = targetSum,将错过从root到i这条路径。
        prefix.put(0,1);
        return dfs(root,prefix,0,targetSum);
    }

    int dfs(TreeNode root, Map<Integer,Integer> prefix,int curr,int targetsum){
        if(root==null){
            return 0;
        }
        int ret=0;
        //前缀和
        curr+=root.val;

        //看是否满足curr-targetsum,
        //举例:1->3->4,curr是8,targetsum是7,因为之前1的前缀和为1,8-7满足,即root到p(i)的前缀和为x,p(i+1)到p(n)的前缀和为targetsum,x+targetsum为curr
        ret=prefix.getOrDefault(curr-targetsum,0);
        //添加前缀和进去路径
        prefix.put(curr,prefix.getOrDefault(curr,0)+1);
        ret+=dfs(root.left,prefix,curr,targetsum);
        ret+=dfs(root.right,prefix,curr,targetsum);
        // 路径退缩,去掉不再在路径上的当前结点的前缀和。
        prefix.put(curr,prefix.getOrDefault(curr,0)-1);

        return ret;
    }
}
View Code

 

标签:总结,curr,int,prefix,算法,TreeNode,root,节点
From: https://www.cnblogs.com/chenghaixiang/p/16644824.html

相关文章

  • 数电第一周总结_CC
    数电第一周总结重点:Verilog建模方式结构级建模:需基于电路原理图modulemux(inputdata0,inputdata1,inputsel,outp......
  • 前端也该刷点算法题——双指针解“链表”题也太香了叭!
    双指针解“链表”题也太香了叭!同步双指针1查找链表中倒数第k个节点剑指Offer22.链表中倒数第k个节点思路:假设链表的长度为n,不难得出倒数第k个节点即为整数第n+......
  • 面试高频,屡试不爽的mysql索引特性总结
    (1)FROM子句组装来自不同数据源的数据(2)WHERE子句基于指定的条件对记录进行筛选(3)GROUPBY子句将数据划分为多个分组(4)使用聚合函数进行计算(5)......
  • 【CV算法基础】ASMS(adaptive scale meanshift)算法理解
        参考1. ASMS算法(adaptivescalemeanshift);2. 基于YOLOv3和ASMS的目标跟踪算法;3.github_asms;完......
  • 【CV算法基础】GIoU算法理解
    几种IoU的理解IoUIOU是用来衡量两个边界框的重叠程度的。 GIoU论文的地址为:https://arxiv.org/abs/1902.09630github代码地址:https://github.com/generalized-iou这......
  • 【ML算法基础】匈牙利算法理解
    前言匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法,匈牙利算法(HungarianAlgorithm)与KM算法(Kuhn-MunkresAlgorithm)是做多目标跟踪的小伙伴很容易在论文......
  • 【CV算法基础】FocalLoss理解
     作者提出focalloss的出发点也是希望one-stagedetector可以达到two-stagedetector的准确率,同时不影响原有的速度。既然有了出发点,那么就要找one-stagedetector的准确......
  • Java方法总结
    什么是方法何谓方法就是一个方法只完成一个功能,这样利于后期的扩展例子:publicstaticvoidmain(String[]args){  System.out.println(add(1,2));}pub......
  • 一致性哈希算法 consistent hashing
     在了解一致性哈希算法之前,最好先了解一下缓存中的一个应用场景,了解了这个应用场景之后,再来理解一致性哈希算法,就容易多了,也更能体现出一致性哈希算法的优点,那么,我们先......
  • AI智能分析网关包含哪些深度学习算法?如何赋能场景应用?
    AI深度学习技术正在呈现飞速增长的状态,有数据分析预测,到2030年,AI有望实现13万亿美元的市场规模。尤其是伴随着智慧城市、智能交通、工业互联网、生产制造等应用场景对视频......