整数序列权重排序——基于深度优先搜索(DFS)以及记忆化搜索

提示：本文适合对算法设计感兴趣的道友一起互相学习，如有疑问，欢迎评论区或者私信讨论。

文章目录

前言
一、题目介绍
二、前置知识扩展
- 1.深度优先遍历
- - 1.1递归DFS
    - 1.1非递归DFS
- 2.@cache装饰器
- 3.range()函数
- 4.sorted()函数
三、解题思路及代码解读
- 1.思路分析
- 2.代码解读
总结

前言

力扣每日一题记录：

本文主要讲解了如何使用递归的方法进行深度遍历搜索来解决Collatz猜想（也称3n + 1猜想）。同时采用记忆化搜索的方法，使用python内置的@cache装饰器对自定义的递归函数def(…)进行缓存，从而减少递归函数中的重复运算。采用range(…)函数对自变量的整数序列的范围进行遍历，使用python内置的sorted函数对递归计算获得的结果进行排序，通过索引操作获得题目要求的对应位置上的元素值。

一、题目介绍

LeetCode 1507，算术评级：6

我们将整数 x 的权重定义为按照下述规则将 x 变成 1 所需要的步数：

如果 x 是偶数，那么 x = x / 2
如果 x 是奇数，那么 x = 3 * x + 1
比方说，x=3 的权重为 7 。因为 3 需要 7 步变成 1 （3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1）。

给你三个整数 lo， hi 和 k 。你的任务是将区间 [lo, hi] 之间的整数按照它们的权重升序排序，如果大于等于 2 个整数有相同的权重，那么按照数字自身的数值升序排序。

请你返回区间 [lo, hi] 之间的整数按权重排序后的第 k 个数。

示例 1：

1输入··：lo = 12, hi = 15, k = 2
2输出：13
3解释：12 的权重为 9（12 --> 6 --> 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1）
413 的权重为 9
514 的权重为 17
615 的权重为 17
7区间内的数按权重排序以后的结果为 [12,13,14,15] 。对于 k = 2 ，答案是第二个整数也就是 13 。
8注意，12 和 13 有相同的权重，所以我们按照它们本身升序排序。14 和 15 同理。
9

示例 2：

1输入：lo = 7, hi = 11, k = 4
2输出：7
3解释：区间内整数 [7, 8, 9, 10, 11] 对应的权重为 [16, 3, 19, 6, 14] 。
4按权重排序后得到的结果为 [8, 10, 11, 7, 9] 。
5排序后数组中第 4 个数字为 7 。
6

数据限制：

1- 1 <= lo <= hi <= 1000
2- 1 <= k <= hi - lo + 1
3

二、前置知识扩展

熟悉一些常用的内置函数以及数据结构算法对您的解题效率会有很大提升。

1.深度优先遍历

深度优先搜索（Depth-First Search，DFS）是一种用于遍历或搜索树或图的算法。它沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点 v 的所在边都已被探寻过，搜索将回溯到发现节点 v 的那条边的起始节点。这个过程一直进行到已发现从源节点可达的所有节点为止。

深度优先搜索算法通常分为递归和非递归两种。

1.1递归DFS

DFS 通常使用递归来实现。递归函数会沿着一条路径深入到尽可能深的节点，然后回溯到上一个节点，再深入到另一条路径。
“示例图”

例如：

1def dfs(graph, start, visited=None):
2    if visited is None:
3        visited = set()
4    visited.add(start)
5    print(start)  # 打印访问的节点
6    for next in graph[start] - visited:
7        dfs(graph, next, visited)
8    return visited
9
10# 示例图
11graph = {
12   
13   
14    'A': set(['B', 'C']),
15    'B': set([

《整数序列权重排序——基于深度优先搜索(DFS)以及记忆化搜索》是转载文章，点击查看原文。