数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学JavaScript程序：常数时间内查询字符串旋转和第K个字符
给定字符串的旋转是指以顺时针或逆时针方向移动给定字符串的字符若干索引。在这里，我们将实现一个JavaScript程序，用于在常数时间内查询给定字符串的旋转和第k个字符。在本文中，我们将实现正确的代码并解释每个步骤。
问题介绍
在给定的问题中，我们得到一个包含一些字符的字符串。我们得到一些有限的查询，每个查询包含两个数字或整数。第一个整数表示我们必须旋转字符串的次数（在这个问题中，我们只是以顺时针方向旋转字符串或字符串的右旋转），而第二个整数表示在第一个整数指定的右旋转次数后，存在于给定值处的字符，我们必须返回该字符。
例如：
Given string: "abcdef" Query1: 3 4 Result: 3rd rotation of the above string is: defabc, character at 4th index is: 'b'. Query2: 6 2 Result: 6th rotation of the above string is: abcdef, character at 2nd index is: 'c'.
我们已经看到了例子，现在让我们进入方法和代码实现部分。
方法
在这个问题中，我们首先必须旋转给定次数的字符串，然后找到给定索引处的字符。
在介绍方法之前，我们必须讨论一些要点：
在这个问题中，字符串旋转的方向没有指定，即字符串是向左旋转还是向右旋转。因此，我们将假设是右旋转。
如果我们旋转任何数组或字符串与其长度相同的次数，那么我们将得到完全相同的数组。这意味着如果我们取旋转给定整数与字符串长度的模，我们将得到所需的相同旋转次数。
问题中规定我们必须在O(1)常数时间内给出解决方案，因此我们将仅实现有效的方法，并简单介绍一下朴素的方法。
在朴素的方法中，我们可以取当前给定旋转次数与字符串大小的模，并获得该旋转，并将所需索引的字符作为结果返回。但这将使给定代码的时间复杂度为O(Q*N)，其中Q是查询数，N是字符串的大小。
高效方法
如果我们从数学上检查，每个旋转都可以通过在给定字符串之后添加相同的字符串来找到。例如：
如果给定的字符串是：“abcdef”，我们之后添加相同的字符串，结果将是：abcdefabcdef，这意味着在每次完整旋转之后，我们将在索引之间获得一个新字符串。因此，我们可以使用数学公式在O(1)时间内回答每个查询。
示例
// function to answer queries
function valueAtIndex(str, rotation, position){
// getting size of the given string
var n = str.length
// actual posisiton is
var pos = (position + rotation) %n;
console.log("Character present at index " + position + " after " + rotation + " number of rotations is: " + str[pos]);
}
// defining the string
var str = "abcdef"
// quries array
var queries = [[3,4], [6,2]];
// travesing over the queries
for(var i =0; i < queries.length; i++){
valueAtIndex(str, queries[i][0], queries[i][1]);
}
时间和空间复杂度
上述代码的时间复杂度为O(Q)，其中Q是被问到的查询数量，因为每个查询的答案都在O(1)时间内给出。上述代码的空间复杂度为O(1)，因为我们没有在上述代码中使用任何额外的空间。
结论
在本教程中，我们实现了一个JavaScript程序，用于在常数时间内查询给定字符串的旋转和第k个字符。我们通过在当前字符串之后添加相同的给定字符串来生成一个数学概念，以便在O(1)时间内回答所有查询，从而使代码的时间复杂度为O(Q)，空间复杂度为O(1)。
119 次浏览
