【算法系列篇】递归、搜索和回溯(二)

这篇具有很好参考价值的文章主要介绍了【算法系列篇】递归、搜索和回溯(二)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【算法系列篇】递归、搜索和回溯(二),算法,算法,递归

前言

前面为大家介绍了关于递归的知识,以及使用递归解决了几个问题,那么这篇文章将带大家巩固一下关于递归的知识。

1. 两两交换链表中的节点

https://leetcode.cn/problems/swap-nodes-in-pairs/description/

1.1 题目要求

给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。

示例 1:
【算法系列篇】递归、搜索和回溯(二),算法,算法,递归

输入:head = [1,2,3,4]
输出:[2,1,4,3]

示例 2:

输入:head = []
输出:[]

示例 3:

输入:head = [1]
输出:[1]

提示:

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {

    }
}

1.2 做题思路

这道题目其实可以使用非递归的方式来实现,但是我们可以使用递归的方式来加深一下递归的学习。

这个题目不复杂,比较简单,我们可以将 head 和 head.next 看成一部分,另外的节点看成另一部分,开始我们直接将后面部分的节点交给函数处理,相信它一定可以帮助我们完成两两节点的交换,当后面部分的节点交换完成之后,我们再交换 head 和 head.next 节点,然后再将这两个部分连接起来。

【算法系列篇】递归、搜索和回溯(二),算法,算法,递归

这是一种思路,我们也可以先交换前面部分,然后再交换后面部分。

【算法系列篇】递归、搜索和回溯(二),算法,算法,递归

上面两种思路其实都差不多的,只是先交换还是后交换的区别。

1.3 代码实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode l1 = swapPairs(head.next.next);
        ListNode ret = head.next;
        head.next.next = head;
        head.next = l1;
        return ret;
    }
}

【算法系列篇】递归、搜索和回溯(二),算法,算法,递归

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode curNext = head.next.next;
        ListNode ret = head.next;
        head.next.next = head;
        head.next = swapPairs(curNext);

        return ret;
    }
}

【算法系列篇】递归、搜索和回溯(二),算法,算法,递归

2. Pow(X,N)

https://leetcode.cn/problems/powx-n/

2.1 题目要求

实现 pow(x, n) ,即计算 x 的整数 n 次幂函数(即,xn )。

示例 1:

输入:x = 2.00000, n = 10
输出:1024.00000

示例 2:

输入:x = 2.10000, n = 3
输出:9.26100

示例 3:

输入:x = 2.00000, n = -2
输出:0.25000
解释:2-2 = 1/22 = 1/4 = 0.25

提示:

-100.0 < x < 100.0
-231 <= n <= 231-1
n 是一个整数
要么 x 不为零,要么 n > 0 。
-104 <= xn <= 104
class Solution {
    public double myPow(double x, int n) {

    }
}

2.2 做题思路

其实这道题也叫做快速幂,为什么叫做快速幂呢?给大家举个例子:假设我们要求2^8,普通的做法就是2x2x2x2x2x2x2x2,但是呢?2 ^ 8可以写成 2 ^ 4 x 2 ^ 4,而 2 ^ 4 又可以写成 2 ^ 2 x 2 ^ 2,2 ^ 2可以写成 2 x 2,2 可以写成 1 x 2。也就是说 2 ^ n 可以写成 2 ^ (n / 2) x 2 ^ (n / 2),我们每次只需要计算 2 ^ (n / 2) 的值及,就可以了,通过这种快速幂的方法,就可以大大节省计算的时间。

当幂为偶数的话就可以每次求 x 的 n / 2 次幂,但是如果幂数为奇数该怎么办呢?这也不复杂,当幂数为奇数的时候,我们只需要在 n / 2 次幂 x n / 2 次幂后面在乘上一个 x 就可以了。举个例子:2 ^ 5就可以写成 2 ^ 2 x 2 ^ 2 x 2。

2.3 代码实现

class Solution {
    public double myPow(double x, int n) {
    	//处理幂数的正负问题
        if (n < 0) return 1.0 / quickPow(x, n);
        else return quickPow(x, n);
    }

    private double quickPow(double x, int n) {
        if (n == 0) return 1.0;
        double t = quickPow(x, n / 2);
        //处理幂数的奇偶问题
        return n % 2 == 0 ? t * t : t * t * x;
    }
}

【算法系列篇】递归、搜索和回溯(二),算法,算法,递归

3. 计算布尔二叉树的值

https://leetcode.cn/problems/evaluate-boolean-binary-tree/

3.1 题目要求

给你一棵 完整二叉树 的根,这棵树有以下特征:

叶子节点 要么值为 0 要么值为 1 ,其中 0 表示 False ,1 表示 True 。
非叶子节点 要么值为 2 要么值为 3 ,其中 2 表示逻辑或 OR ,3 表示逻辑与 AND

计算 一个节点的值方式如下:

如果节点是个叶子节点,那么节点的 值 为它本身,即 True 或者 False 。
否则,计算 两个孩子的节点值,然后将该节点的运算符对两个孩子值进行 运算 。
返回根节点 root 的布尔运算值。

完整二叉树 是每个节点有 0 个或者 2 个孩子的二叉树。

叶子节点 是没有孩子的节点。

示例 1:
【算法系列篇】递归、搜索和回溯(二),算法,算法,递归

输入:root = [2,1,3,null,null,0,1]
输出:true
解释:上图展示了计算过程。
AND 与运算节点的值为 False AND True = False 。
OR 运算节点的值为 True OR False = True 。
根节点的值为 True ,所以我们返回 true 。

示例 2:

输入:root = [0]
输出:false
解释:根节点是叶子节点,且值为 false,所以我们返回 false 。

提示:

树中节点数目在 [1, 1000] 之间。
0 <= Node.val <= 3
每个节点的孩子数为 0 或 2 。
叶子节点的值为 0 或 1 。
非叶子节点的值为 2 或 3 。
/**
 * Definition for a binary tree node.
 * public 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;
 *     }
 * }
 */
class Solution {
    public boolean evaluateTree(TreeNode root) {

    }
}

3.2 做题思路

这道题目的意思就是如果遇到的节点是一个叶子节点的话,如果当前节点的值为0的话就返回False,为1的话就返回True;如果当前节点不是叶子节点的话,就需要根据这个节点的父亲节点的值与这个节点的兄弟节点进行操作,如果父亲节点是2的话,就进行 | 操作,3就进行 & 操作。

一般遇到二叉树就会想到递归,这道题也不例外。我们先将根节点的左树交给函数,让函数帮助我们进行布尔值的计算,然后再将根节点的右树交给函数进行布尔值的运算,最后将左右子树的值与根节点表示的值进行 | 或者 & 运算。

【算法系列篇】递归、搜索和回溯(二),算法,算法,递归

3.3 代码实现

/**
 * Definition for a binary tree node.
 * public 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;
 *     }
 * }
 */
class Solution {
    public boolean evaluateTree(TreeNode root) {
    	//当root为null时返回true
        if (root == null) return true;
        //遇到叶子节点根据节点的值返回
        if (root.left == null && root.right == null) {
            if (root.val == 0) return false;
            else return true;
        }
        boolean l = evaluateTree(root.left);
        boolean r = evaluateTree(root.right);
        if (root.val == 2) return l | r;
        else return l & r;
    }
}

【算法系列篇】递归、搜索和回溯(二),算法,算法,递归

4. 求根节点到叶结点数字之和

https://leetcode.cn/problems/sum-root-to-leaf-numbers/

4.1 题目要求

给你一个二叉树的根节点 root ,树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字:

例如,从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

示例 1:
【算法系列篇】递归、搜索和回溯(二),算法,算法,递归

输入:root = [1,2,3]
输出:25
解释:
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此,数字总和 = 12 + 13 = 25

示例 2:

【算法系列篇】递归、搜索和回溯(二),算法,算法,递归

输入:root = [4,9,0,5,1]
输出:1026
解释:
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此,数字总和 = 495 + 491 + 40 = 1026

提示:

树中节点的数目在范围 [1, 1000] 内
0 <= Node.val <= 9
树的深度不超过 10
/**
 * Definition for a binary tree node.
 * public 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;
 *     }
 * }
 */
class Solution {
    public int sumNumbers(TreeNode root) {

    }
}

4.2 做题思路

这道题目也不难,只要能理解二叉树的的前序遍历就可以了,这道题目其实就是二叉树的前序遍历。我们先将根节点的左子树交给函数得到左子树上从根节点到各个叶子节点路径上的数字之和,然后将根节点的右子树上的从根节点到各个叶子节点路径上的数字之和,然后返回左子树和右子树返回值的和。

4.3 代码实现

/**
 * Definition for a binary tree node.
 * public 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;
 *     }
 * }
 */
class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

	//n用来记录当前路径上该节点之前的各个节点的和
    private int dfs(TreeNode root, int n) {
        if (root == null) return 0;
        //遇到一个节点就将当前节点的值加在n上
        n = n * 10 + root.val;
        //遇到叶子节点就说明当前节点的值计算完成,就返回路径上所以数字和
        if (root.left == null && root.right == null) return n;
		//分别计算根节点左右子树上根节点到叶子节点路径上数字和
        int l = dfs(root.left, n);
        int r = dfs(root.right, n);

		//返回左子树和右子树所有路径上数字和
        return l + r;
    }
}

【算法系列篇】递归、搜索和回溯(二),算法,算法,递归文章来源地址https://www.toymoban.com/news/detail-753484.html

到了这里,关于【算法系列篇】递归、搜索和回溯(二)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 递归、搜索与回溯算法(专题六:记忆化搜索)

    目录 1. 什么是记忆化搜索(例子:斐波那契数) 1.1 解法一:递归 1.2 解法二:记忆化搜索 1.2.1 记忆化搜索比递归多了什么? 1.2.2 提出一个问题:什么时候要使用记忆化搜索呢? 1.3 解法三:动态规划 1.3.1 先复习一下动态规划的核心步骤(5个),并将动态规划的每一步对应

    2024年01月20日
    浏览(47)
  • 递归、搜索与回溯算法(专题二:深搜)

    往期文章(希望小伙伴们在看这篇文章之前,看一下往期文章) (1)递归、搜索与回溯算法(专题零:解释回溯算法中涉及到的名词)【回溯算法入门必看】-CSDN博客 (2)递归、搜索与回溯算法(专题一:递归)-CSDN博客  深搜是实现递归的一种方式,接下来我们之间从题

    2024年01月20日
    浏览(80)
  • 【C++】递归,搜索与回溯算法入门介绍和专题一讲解

    个人主页:🍝在肯德基吃麻辣烫 我的gitee:C++仓库 个人专栏:C++专栏 从本文开始进入递归,搜索与回溯算法专题讲解。 递归就是函数自己调用自己。 递归的本质是: 主问题:—相同的子问题 子问题:—相同的子问题 通过: 1)通过递归的细节展开图(前期可以,过了前期

    2024年02月09日
    浏览(37)
  • 专题一:递归【递归、搜索、回溯】

    什么是递归 函数自己调用自己的情况。 为什么要用递归 主问题-子问题        子问题-子问题 宏观看待递归 不要在意细节展开图,把函数当成一个黑盒,相信这个黑盒一定能完成任务。  如何写好递归   分析跟上一题差不多,不详解。 实现 pow(x, n) ,即计算  x  的整

    2024年02月07日
    浏览(43)
  • 专题二:二叉树的深搜【递归、搜索、回溯】

    深度优先遍历 (DFS,全称为DepthFirstTraversal),是我们树或者图这样的数据结构中常用的⼀种遍历算法。这个算法会尽可能深的搜索树或者图的分⽀,直到⼀条路径上的所有节点都被遍历完毕,然后再回溯到上⼀层,继续找⼀条路遍历。 在⼆叉树中,常⻅的深度优先遍历为:

    2024年02月07日
    浏览(39)
  • 递归回溯两个例题:1.数组组合 2.在矩阵中搜索单词

    题目1:组合 给定两个整数 n 和 k ,返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 输入:n = 4, k = 2 输出: [   [2,4],   [3,4],   [2,3],   [1,2],   [1,3],   [1,4], ]  解题思路: 1.定义一个temp数组,存放临时的组合结果 2.两种选择:1.选择当前元素2.不选

    2024年02月15日
    浏览(42)
  • 算法与数据结构——递归算法+回溯算法——八皇后问题

    八皇后问题是一个经典的回溯算法问题,目的是在8×8的国际象棋棋盘上放置八个皇后,使得没有皇后可以互相攻击(即没有两个皇后在同一行、同一列或同一对角线上)。 回溯算法是一种解决问题的算法,它通过尝试所有可能的解决方案来解决问题。在八皇后问题中,计算

    2024年02月09日
    浏览(52)
  • 算法 矩阵最长递增路径-(递归回溯+动态规划)

    牛客网: BM61 求矩阵的最长递增路径 解题思路: 1. 遍历二维矩阵每个位置,max求出所有位置分别为终点时的最长路径 2. 求某个位置为终点的最长路径时,使用动态规划dp对已经计算出的位置进行记录 3. 处理某个位置的最长路径时,如果dp[i][j]位置已有值,则直接返回即可,否则

    2024年02月07日
    浏览(41)
  • 【算法】递归、回溯、剪枝、dfs 算法题练习(组合、排列、总和问题;C++)

    后面的练习是接着下面链接中的文章所继续的,在对后面的题练习之前,可以先将下面的的文章进行了解👇: 【算法】{画决策树 + dfs + 递归 + 回溯 + 剪枝} 解决排列、子集问题(C++) 思路 题意分析 :要求根据给出的数字,算出合法的括号组成个数。根据题目,我们可以总

    2024年02月22日
    浏览(48)
  • DSt:数据结构的最强学习路线之数据结构知识讲解与刷题平台、刷题集合、问题为导向的十大类刷题算法(数组和字符串、栈和队列、二叉树、堆实现、图、哈希表、排序和搜索、动态规划/回溯法/递归/贪心/分治)总

    Algorithm:【算法进阶之路】之算法面试刷题集合—数据结构知识和算法刷题及其平台、问题为导向的十大类刷题算法(数组和字符串、链表、栈和队列、二叉树、堆、图、哈希表、排序和搜索、回溯算法、枚举/递归/分治/动态规划/贪心算法)总结 目录 相关文章

    2024年02月08日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包