递归(dfs)

简介: 递归(dfs)

力扣21.合并两个有序链表

我们要相信dfs()一定能给我做到这个事情

重复子问题+宏观看待递归问题

1.找到重复的子问题->函数头的设计

合并两个有序链表

2.只关心某一个子问题在做什么事情-函数体的设计

选择较小的,然后连接剩下的两个部分 l1->next=dfs(l->next,l2)

3.return l1;

递归的出口 谁为空,返回另一个即可。

循环vs递归

递归的核心是找到一个重复的子问题,找到重复子问题

递归vs深度搜索dfs

递归展开图的顺序,其实细细一想就是深度优先搜索的顺序一样,递归的执行逻辑就是一颗树的深度优先(dfs)

当递归展开图很麻烦,用递归会比较好

当递归展开很简单,用循环就会很简单

中序遍历(只在二叉树中才有)

先序遍历vs后续遍历

本质都是深度优先遍历

这个题我之前使用循环做,得有20多行代码

递归的代码之美也体现在这里

力扣206反转链表(递归)

两种思想一致,只是视角不一致。

class Solution {
    public ListNode reverseList(ListNode head) {
     if(head==null||head.next==null) return head;
     ListNode newHead=reverseList(head.next);
     head.next.next=head;
     head.next=null;
     return newHead;
    }
}


力扣24.两两交换链表中的节点

这道题核心和反转链表都是相同,而且注意他是1和2是一组,所以说节点这方面也是把1和2放一起,只考虑12,要相信后面的事情一定能够完成

 public ListNode swapPairs(ListNode head) {
        if(head==null||head.next==null) return head;
       ListNode newhead=swapPairs(head.next.next);
        head.next.next=head;
          head.next=newhead;
        return head.next;
   
    }

是因为假如第一种写法返回的head.next已经被我后面的代码修改了,所以说head的next是不对的,但是下面这个写法是先保存了head.next这个节点,后面返回的时候就直接返回这个节点就可以了

力扣50.Pow(x,n)

快速幂

public static double myPow(double x, long n) {
        if (n == 0) {
            return 1.0;
        }
        if (n == 1) {
            return x;
        }
        if (n < 0) {
            x = 1 / x;
            n = -n;
        }
//这个快速幂有个问题-必须是一半一半的,因为假如是一个一个那么递归n-1这样那么就会出现栈溢出的问题,
        double tmp = 1.0;
        tmp = myPow(x, n / 2);
 
//一个一个%2这样只有两种结果,要么偶数,要么奇数,奇数就+1
        return n%2==0?tmp*tmp:tmp*tmp*x;
 
    }

但是在这个时候,我的脑子里突然涌出一个问题n%2==0,我们判断他是奇数还是偶数,是用来做这个的,但是我们奇数为什么不能是前一个而是后一个呢。

因为上面的代码是/2,假如n是21,他的tmp对应的是10,所以10+10+1,才能构成21,或者我可以这么理解,因为n/2是一个向下取整的数,所以此时n%2可以让他向上取整,也就是+1

因为假如正常做 例子 n=21 是要先/2 然后变成10+10+1   ,假如说我那个减法这么算就应该是,(21+1)/2,然后因为tmp代表的是x的11次幂,所以11+11最后需要减1

  public static double myPow(double x, long n) {
        if (n == 0) {
            return 1.0;
        }
        if (n == 1) {
            return x;
        }
        if (n < 0) {
            x = 1 / x;
            n = -n;
        }
        double tmp = 1.0;
        tmp = myPow(x, (n+1)/2);
 
 
        return n%2==0?tmp*tmp:tmp*tmp/x;
 
    }


相关文章
|
Web App开发 JavaScript 前端开发
使用vue快速开发一个带弹窗的Chrome插件
使用vue快速开发一个带弹窗的Chrome插件
494 0
使用vue快速开发一个带弹窗的Chrome插件
|
Prometheus 监控 安全
SpringBoot Actuator未授权访问漏洞的解决方法
SpringBoot Actuator未授权访问漏洞的解决方法Actuator 是 SpringBoot 提供的用来对应用系统进行自省和监控的功能模块,借助于 Actuator 开发者可以很方便地对应用系统某些监控指标进行查看、统计等。
28840 0
|
存储 域名解析 供应链
阿里云 OSS对象存储攻防
本文分为两个部分 第一部分介绍OSS对象存储攻防的方式 第二部分为真实漏洞案例
3244 0
阿里云 OSS对象存储攻防
|
缓存 Linux 开发工具
CentOS 7- 配置阿里镜像源
阿里镜像官方地址http://mirrors.aliyun.com/ 1、点击官方提供的相应系统的帮助 :2、查看不同版本的系统操作: 下载源1、安装wget yum install -y wget2、下载CentOS 7的repo文件wget -O /etc/yum.
250876 0
|
网络协议
【qt】TCP的监听 (设置服务器IP地址和端口号)
【qt】TCP的监听 (设置服务器IP地址和端口号)
655 0
|
10月前
|
传感器 人工智能 监控
智慧化工厂AI算法方案
智慧化工厂AI算法方案针对化工行业生产过程中的安全风险、效率瓶颈、环保压力和数据管理不足等问题,通过深度学习、大数据分析等技术,实现生产过程的实时监控与优化、设备故障预测与维护、安全预警与应急响应、环保监测与治理优化,全面提升工厂的智能化水平和管理效能。
1233 0
智慧化工厂AI算法方案
|
NoSQL 关系型数据库 MySQL
多机部署:打造内网服务器集群
在多机部署教程中,了解如何配置分布式应用如Laravel以使用Redis同步用户状态。关键步骤包括:修改MySQL的`bind-address`至内网IP,重启服务;同样修改Redis的`bind`,重启服务;以及调整Elasticsearch的`network.host`和`discovery.seed_hosts`,并重启。通过这些步骤,确保服务间能内网通信,实现多服务器状态同步。
386 2
|
安全 Java Maven
Maven重打包问题之Maven的打包机制对于ClassPath的顺序是如何解决的
Maven重打包问题之Maven的打包机制对于ClassPath的顺序是如何解决的
170 0
|
安全 前端开发 Java
安全同学讲Maven重打包的故事
经过去年的Log4j-core的治理工作,我们通过Maven的依赖仲裁机制,在蚂蚁集团静态代码扫描平台-STC 和资产威胁透视-哈勃2款产品的联动合作下,很好的完成了直接依赖和间接依赖场景下的治理工作。但路还很远,新的场景层出不穷,故事还远远没有结束,我们要做的事情还非常多。
249 12
|
人工智能 供应链
数字化转型获得成功的4个关键因素
数字化转型获得成功的4个关键因素