C++ 中的欢乐跳跳糖序列

乔利跳线序列是数学中的一个概念，非常迷人。它 all about 序列中连续数字之间绝对差值。如果给定的序列包含从 1 到 n-1 的所有数字作为绝对差值，且只出现一次，则该序列被称为乔利跳线。通常，这个想法用于编程竞赛，以衡量人们在面对逻辑问题和处理不同类型信息时的思维方式。

与算术或几何序列不同，算术或几何序列任意两项之间有公差或公比，而乔利跳线序列则不一定如此。因此，这意味着每次我们得到乔利跳线序列中的一些数字时，我们都必须考虑各种绝对差值，即使它们是重复的。然而，要确定这样的列表是否具有某种模式，所有不同的绝对差值都必须存在。

举个例子就会明白。考虑一个数字列表 1,4,2,3，按此顺序。

这些数字的绝对差值是什么？

• 我们可以观察到集合 {3,2,1} 与 [1,3] 相同，即。如果我们按升序排列集合，我们就得到列表。如果我们继续下去，我们会发现我们的集合包含了从 1 到 n-1 的所有数字。
• 现在，让我们以不是乔利跳线的数字模式为例，看看是什么让它们失败。
• 出现相同的数字： 例如，1,1,1,1,1 或 9,7,9,7,9，无论一个数字（在这种情况下是 1 或 9）出现多少次，都不可能得出不同的绝对值。
• 缺少数字： 如果我们有 1,3，无论如何尝试计算绝对差值，它都只会是 1，因为列表中没有其他数字。
• 除了 1 之外的任何其他数字丢失，例如 1,2，都会使得难以得出绝对差值 2。
• 我们不关心绝对差值的出现顺序，即 {1,3} 与 {3,1} 相同。
• 我们可以得出结论，要使一个序列成为乔利跳线，所有绝对差值都必须存在且不重复。

解决这个问题的难点在于能够快速确定所有必需的差值是否存在。我们可以使用哈希集或布尔数组来跟踪，而不是逐个检查每个可能的差值是否在数组中。这样，我们的解决方案将更聪明、更快，并且占用更少的内存。

约束和观察

为了判断给定的序列是否为乔利跳线，需要考虑序列的某些条件和属性。序列包含 n 个整数，当 n=1（n 的最小可能值）时，它总是乔利序列，因为没有两个（连续）数字可以进行比较。但对于其他 n 值（n > 1），如果连续数字的所有绝对差值恰好取 1 到 n-1 的每个值一次，则该序列为乔利序列。

长度为 n 的任何序列最多可以有 (n-1) 个差值。要成为乔利序列，这 (n-1) 个差值必须是不同的，并且应在 1 到 n-1 的范围内。如果缺少任何必需的差值或存在任何额外的差值，则该序列不是乔利序列。

例如，让我们考虑这个序列：1 4 2 3

连续项之间的差值是 {3 2 1}，注意我们可以获得从 1 到 (4-1 = 3) 的每个值。因此，这个序列是乔利序列。

现在，如果我们修改上面的序列，例如：1 4 2 6

连续项之间的差值是 {3, 2 ,4}；注意现在我们在集合中找不到值 ‘1’。此外，还有一个额外的差值 ‘4’。因此，这个序列不是乔利序列。

从上面的例子可以看出，要判断给定的序列是否为乔利序列，我们不需要序列中的数字，我们只需要差值，但以一种特定的方式，如上所述。

方法

为了确定一个序列是否是乔利跳线，我们将以一种非常结构化的形式进行。如果 n = 1，我们知道该序列是乔利序列，因为我们可以通过测试序列的第一个元素立即得出结论。否则，我们取连续元素的绝对差值并将它们放入集合或布尔数组中。之后，我们检查集合是否包含 1 到 n-1 的所有整数。如果包含，则该序列为乔利序列，否则不是。

分步方法的概要如下

• 因此，如果 n = 1，则返回“乔利”，因为这个单元素序列总是有效的。
• 创建一个布尔数组或哈希集来存储初始化的差值。
• 计算序列中连续元素之间的绝对差值，并遍历序列。
• 尝试检查每个差值是否在范围 [1, n-1] 内，以及是否出现重复。
• 所有元素都已处理完毕，我们希望确保所有必需的差值都存在。
• 如果任何差值丢失或差值无效，则返回“非乔利”；否则返回“乔利”。
• 通过这种方法，我们得到 O(n) 的时间复杂度，因为每个元素只处理一次，因此它可以高效地处理大量元素。由于使用了布尔数组或哈希集，检查和插入差值的时间复杂度为 O(1)。

示例

让我们举一个例子来说明 C++ 中的乔利跳线。

输出

Sequence: 1 4 2 3 
Result: Jolly

Sequence: 1 4 2 6 
Result: Not Jolly

Sequence: 10 20 30 40 
Result: Not Jolly

Sequence: 5 
Result: Jolly

Sequence: 3 1 4 2 
Result: Jolly

Sequence: 1 3 2 4 6 
Result: Not Jolly

Sequence: 100 101 102 103 
Result: Jolly

Sequence: 9 8 7 6 5 4 3 2 1 
Result: Jolly

Sequence: 1 100 
Result: Not Jolly

Sequence: 1 2 4 7 11 
Result: Not Jolly   

结论

总而言之，乔利跳线序列是一个引人入胜的问题，它处理序列的连续项之间的绝对差值。它有一个条件：这些差值必须恰好包含从 1 到 n-1 的所有数字一次。由于其与普通的算术和几何级数的独特性，它非常值得研究。

我们可以通过查看它是否总是满足约束条件来检查序列是否为乔利序列。为此，当 n > 1 时需要一种方法，同时也要确保差值是唯一的。按顺序思考会花费太多时间，但如果我们从不同角度思考，我们可以找到一个解决方案。

如果我们强制检查所有可能的差值，那将非常昂贵（在性能方面）。但我们已经知道，从 1 到 n-1 的所有值都应该恰好出现一次。所以一件显而易见的事情是，我们可以假设一个布尔值的数组（或哈希集），标记已访问的索引，最后检查所有是否为“true”或“false”。

该实现采用单遍算法，遍历序列，计算绝对差值并检查其是否存在。如果任何必需的差值丢失或存在任何本应存在的额外差值，则认为它是乔利序列。这种技术的优点是它能够快速处理大量输入。

通过使用不同的测试用例，我们确保了我们的方法适用于所有不同类型的列表。这使得我们的解决方案强大而可靠。如果使用以特定方式组织信息的数据结构和为特定问题设计的算法，许多与数字相关的谜题都可以高效地解决。