資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學根據字串與另一個數組元素的最大公約數 (GCD) 對字串陣列進行排序
在這個問題中，我們得到了兩個字串陣列。我們需要替換array1的值來排序array1。為了替換array1的值，我們可以取array1當前字串與array2中任何字串的最大公約數 (GCD)。
字串的GCD與數字的GCD非常相似。為了解決這個問題，我們可以找到一個字典序大於array1中第i個索引的字串和array2中第j個索引的字串的GCD的GCD字串。
問題陳述 – 我們得到了包含字串的array1和array2，陣列的長度分別為len1和len2。我們需要透過將array1的每個元素替換為arra1[i]和array2[j]的GCD來排序array1，其中0 <= i < len1，且0 <= j < len2。如果無法透過替換array1的元素來排序陣列，則需要列印-1。
注意 – 兩個字串的GCD是最小的字串，當我們多次將其自身連線起來時，應該能夠得到這兩個字串。
示例
輸入 – array1 = {"aaaa", "point", "sku"}, array2 = {"pointpoint", "skuskusku"};
輸出 – 是
解釋 – 結果陣列是 [“”, “point”, “sku”]，它按升序排序。
“aaaa”與array2中兩個元素的GCD都是空字串。
“point”與“pointpoint”的GCD是“point”。
“sku”和“pointpoint”的GCD是空字串，它不大於前一個元素。因此，我們可以考慮“sku”和“skuskusku”的GCD，它是“sku”。
輸入 – array1 = {"aacde", "acac", "aaaa"}, array2 = {"aa", "ac"};
輸出 – 否
解釋 – 我們可以得到的GCD結果陣列是 [“”, “ac”, “aa”]，它不是按字典序排序的。
方法 1
在這種方法中，我們將array1的每個元素與array2的每個元素的GCD。之後，我們將替換字典序最小的GCD，它大於陣列中當前索引之前的元素。
我們可以根據其長度的GCD來找到兩個字串的GCD。
演算法
用空字串初始化“prev”變數以儲存之前的字串
使用迴圈遍歷array1以替換每個元素。
在迴圈中將當前字串儲存在“current”變數中。此外，定義“flag”變數並將其設定為true，以跟蹤我們是否找到第一個大於“prev”元素的GCD元素。
現在，開始遍歷array2，因為我們需要將當前元素與array2的每個元素的GCD。
在迴圈中，執行getStringGCD()函式以獲得兩個字串的GCD。
在getStringGCD()函式中，獲取兩個陣列的長度並使用__gcd()方法找到它們的gcd。
用空字串初始化str1和str2。將前“gcd”個字元從字串a附加到str1，並將前“gcd”個字元從字串b附加到str2。
如果兩個字串中的前“gcd”個字元相等，則表示存在GCD，我們需要繼續下一步。
初始化temp1和temp2字串。
將第一個字串附加到temp1，“(len2 / gcd)”次。
將第二個字串附加到temp2，“(len1 / gcd)”次。
如果temp1和temp2相等，則返回“str1”，即兩個字串的GCD。
如果GCD元素大於“prev”變數的值，“flag”為true，則用gcd元素更新當前元素的值。同時，將“flag”設定為false。
如果“gcdElement”大於“prev”且“flag”為“false”，則用“current”和“gcdElement”的最小值更新“current”的值。
用“current”更新“i”的值，用“i”更新“prev”。
執行isArraySorted()函式以檢查結果陣列是否按升序排序。
在isArraySorted()函式中，遍歷陣列並檢查所有第i個索引處的元素在字典序上是否小於第(i+1)個索引處的元素。
如果排序則返回array1。否則，返回空列表。
示例
#include <bits/stdc++.h>
using namespace std;
// function to get the gcd of two strings
string getStringGCD(string a, string b){
// finding the gcd of the lengths of the strings
int len1 = a.length(), len2 = b.length();
int gcd = __gcd(len1, len2);
// Initializing the strings
string str1 = "", str2 = "";
// Create two different strings of length gcd from the given strings
for (int i = 0; i < gcd; i++) {
// append total gcd characters from a[i] to str1
str1.push_back(a[i]);
}
for (int i = 0; i < gcd; i++) {
// // append total gcd characters from b[i] to str2
str2.push_back(b[i]);
}
// If the two strings are equal, then the gcd exists (The initial part of the string is the same)
if (str1 == str2) {
// Initialize two temporary strings
string temp1 = "", temp2 = "";
// append the string a to temp1 len2/gcd times, and string b to temp2 len1/gcd times to make length of both strings equal.
for (int i = 1; i <= (int)(len2 / gcd); i++) {
temp1 += a;
}
for (int i = 1; i <= (int)(len1 / gcd); i++) {
temp2 += b;
}
// If temp1 and temp2 are equal, then the gcd exists (The final part of the string is the same)
if (temp1 == temp2)
return str1;
}
// return an empty string if gcd does not exist
return " ";
}
// function to check whether the array is sorted or not
bool isArraySorted(vector<string> array) {
// Traverse the array
for (int i = 0; i < array.size() - 1; i++) {
// If we find any string at index i is greater than or equal to the next string, then the array is not sorted
if (array[i] >= array[i + 1])
return false;
}
// If the array is sorted, then return true.
return true;
}
// function to sort the array if possible
vector<string> sortStrings(vector<string> array1, vector<string> array2) {
// Previous string
string prev = "";
// Iterate through the array
for (string &i : array1) {
// Initialize the current string
string current = i;
// flag to find the first string greater than the prev
bool flag = true;
// Iterate through the array2
for (string j : array2){
// Get the gcd of I and j strings
string gcdElement = getStringGCD(i, j);
// If the Gcd element is greater than prev and the flag is true
if (gcdElement > prev && flag) {
// Update the current string
current = gcdElement;
// set flag to false
flag = false;
}
// If gcdElement > prev and flag is false
if (gcdElement > prev){
// Update the current string
current = min(current, gcdElement);
}
}
// Update array1[i] by current
i = current;
// Update prev by array1[i]
prev = i;
}
// check is array1[] is sorted in ascending order
if (isArraySorted(array1)) {
return array1;
}
// Sorted order is not possible
vector<string> ans;
return ans;
}
int main() {
vector<string> array1 = {"aacde", "acac", "aaaa"};
vector<string> array2 = {"aa", "ac"};
vector<string> ans = sortStrings(array1, array2);
// If the size of ans is 0, then it is not possible to sort the array
if (ans.size() == 0) {
cout << "It is not possible to sort the array in ascending order.";
} else {
cout << "The array of strings after replacing with their GCD in the sorted order is: ";
for (string str : ans) {
cout << str << ", ";
}
}
return 0;
}
輸出
It is not possible to sort the array in ascending order.
時間複雜度 – O(len1 * len2 * log(min(len3, len4)))，其中len1是array1的長度，len2是array2的長度。len3是array1中任何字串的最大長度，len4是array2中任何字串的最大長度。
空間複雜度 – O(1)，因為我們沒有使用任何常量空間。
68 次檢視
