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

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

b90ac447efcc4bb993f982f0c3d262fe.gif

前言

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

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 做题思路

d9cf3d64f19244aa809d7d96420f2a70.png

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


d9cf3d64f19244aa809d7d96420f2a70.png

相关文章
|
7天前
|
机器学习/深度学习 存储 人工智能
图搜索算法详解
【5月更文挑战第11天】本文介绍了图搜索算法的基础知识,包括深度优先搜索(DFS)、广度优先搜索(BFS)和启发式搜索(如A*算法)。讨论了图搜索中的常见问题、易错点及避免方法,并提供了BFS和A*的Python代码示例。文章强调了正确标记节点、边界条件检查、测试与调试以及选择合适搜索策略的重要性。最后,提到了图搜索在路径规划、游戏AI和网络路由等领域的应用,并概述了性能优化策略。
15 3
|
7天前
|
机器学习/深度学习 存储 算法
数据结构与算法 动态规划(启发式搜索、遗传算法、强化学习待完善)
数据结构与算法 动态规划(启发式搜索、遗传算法、强化学习待完善)
16 1
|
6天前
|
算法 决策智能 索引
数据结构与算法 回溯
数据结构与算法 回溯
7 1
|
6天前
|
算法 搜索推荐 索引
数据结构与算法 搜索(下)
数据结构与算法 搜索(下)
11 0
|
6天前
|
缓存 算法 搜索推荐
数据结构与算法 搜索(上)
数据结构与算法 搜索(上)
9 1
|
6天前
|
数据采集 存储 算法
数据结构与算法 搜索
数据结构与算法 搜索
7 1
|
6天前
|
机器学习/深度学习 存储 人工智能
【AI 初识】人工智能中使用了哪些不同的搜索算法?
【5月更文挑战第2天】【AI 初识】人工智能中使用了哪些不同的搜索算法?
|
6天前
|
算法 搜索推荐 Java
图搜索算法详解
图搜索算法是用于在图结构中寻找特定节点或路径的算法。图是由节点(或顶点)和边组成的集合,节点代表对象,边代表节点之间的连接。图搜索算法广泛应用于各种领域,比如网络路由、社交媒体分析、推荐系统等。 V哥最近总是在多个地方都看到关于图搜索算法的讨论
|
7天前
|
算法 JavaScript
算法(分治、贪心、dp、回溯、分支限界)总结
算法(分治、贪心、dp、回溯、分支限界)总结
|
6天前
|
机器学习/深度学习 数据采集 算法
Python中基于网格搜索算法优化的深度学习模型分析糖尿病数据
Python中基于网格搜索算法优化的深度学习模型分析糖尿病数据