資料結構
網路
關係資料庫管理系統 (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 次瀏覽
