資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學統計從給定陣列中交換字串對的第一個字元後可以獲得的新字串對的數量
在這個問題中，我們需要選擇字串對並交換它們的第一個字元。之後，我們需要計算新對的總數。我們可以透過交換每對的第一個字元並檢查它是否存在於陣列中來解決這個問題。
解決這個問題的有效方法是使用雜湊表資料結構。
問題陳述 – 我們給定一個包含 N 個字串的陣列。我們可以從所有陣列元素中取出任意兩個字串，並交換兩個字串的第一個字元。我們需要計算新生成的字串對的總數，這些字串對不在陣列中。
示例
輸入 – array[] = {"should", "would", "can"};
輸出 – 3
解釋 – 新生成的字串對可以是 "could" 和 "wan"。另一個對可以是 "whould" 和 "sould"。第三個對可以是 "san" 和 "chould"。
輸入 – array[] = {"demo", "test"};
輸出 – 1
解釋 – 不存在於陣列中的新生成的字串對是 "temo" 和 "dest"。
方法一
在這種方法中，我們將使用兩個巢狀迴圈來獲取陣列元素的所有對。之後，我們將交換兩對的第一個字元。接下來，我們將使用第三個巢狀迴圈來檢查陣列是否包含該對。
演算法
定義變數 ‘cnt’ 並初始化為 0，以儲存對的總數。
使用兩個巢狀迴圈遍歷字串陣列並獲取每對陣列元素。
獲取當前對的兩個字串。
如果兩個字串的第一個字元不相等，則交換它們。
定義變數 ‘isFirst’ 和 ‘isSecond’，並初始化為 false，以跟蹤新生成的字串是否出現在陣列中。
使用第三個巢狀迴圈檢查新生成的字串是否在陣列中。根據陣列中的字串更新 ‘isFirst’ 和 ‘isSecond’ 變數的值。
如果兩個字串都不在陣列中，則將 ‘cnt’ 的值增加 1。
返回 ‘cnt’ 變數的值。
示例
#include <iostream>
using namespace std;
// function to find the count of pairs of strings that can be formed by swapping the first character of the strings
int newStringPairs(string array[], int len){
// Stores the count of pairs
int cnt = 0;
// Get all the pairs of strings
for (int i = 0; i < len; i++){
for (int j = i + 1; j < len; j++){
// store single pair of strings
string first = array[i], second = array[j];
// If both strings' first characters are not equal, swap them.
if (first[0] != second[0]){
swap(first[0], second[0]);
bool isFirst = false;
bool isSecond = false;
// Check whether the strings are present in the array or not
for (int k = 0; k < len; k++){
if (array[k] == first){
isFirst = true;
}
if (array[k] == second){
isSecond = true;
}
}
// If both the strings are present in the array, then increment the cnt by 1
if (isFirst == false && isSecond == false){
cnt++;
}
}
}
}
return cnt;
}
int main(){
string array[] = {"should", "would", "can"};
int N = sizeof(array) / sizeof(array[0]);
cout << "Total number of new pairs we can generate by swapping the first characters of given strings is " << newStringPairs(array, N);
return 0;
}
輸出
Total number of new pairs we can generate by swapping the first characters of given strings is 3
時間複雜度 – O(N^3)，因為我們使用了三個巢狀迴圈。
空間複雜度 – O(1)
方法二
在這種方法中，我們將使用 map 資料結構將所有陣列值儲存到 map 中。之後，我們可以檢查 map 是否包含新生成的字串。如果不是，我們可以將計數器值增加 1。
演算法
定義變數 ‘cnt’
遍歷字串陣列，並將所有陣列值儲存到 map 中。
使用兩個巢狀迴圈獲取陣列元素的所有對。
獲取字串對並將它們儲存在 ‘first’ 和 ‘second’ 變數中。
如果兩個字串的第一個字元不相等，則交換它們。
在 map 中檢查它是否包含新生成的字串。如果不是，則將 ‘cnt’ 的值增加 1。
返回 ‘cnt’ 值。
示例
#include <iostream>
#include <unordered_map>
using namespace std;
// function to find the count of pairs of strings that can be formed by swapping the first character of the strings
int newStringPairs(string array[], int len){
// to store the total number of new pairs
int cnt = 0;
// add all strings to the array map
unordered_map<string, int> str_map;
for (int i = 0; i < len; i++){
str_map[array[i]]++;
}
//find all pairs of strings that can be formed by swapping the first character of the strings
for (int i = 0; i < len; i++){
for (int j = i + 1; j < len; j++){
// get the current pair of strings
string first = array[i];
string second = array[j];
// If the first character of both strings is not the same, then swap them
if (first[0] != second[0]){
swap(first[0], second[0]);
// If both strings are not present in the map, then the increment count
if (str_map[first] == 0 && str_map[second] == 0){
cnt++;
}
}
}
}
return cnt;
}
int main(){
string array[] = {"should", "would", "can"};
int N = sizeof(array) / sizeof(array[0]);
cout << "Total number of new pairs we can generate by swapping the first characters of given strings is " << newStringPairs(array, N);
return 0;
}
輸出
Total number of new pairs we can generate by swapping the first characters of given strings is 3
時間複雜度 – O(N^2)，因為我們使用了兩個巢狀迴圈。
空間複雜度 – O(N)，因為我們使用 map 來儲存所有陣列元素。
我們學習了透過交換任何陣列元素的第一個字元來生成的新對的總數。我們在第二種方法中優化了時間複雜度，但第一種程式碼在空間複雜度方面更好。
84 次瀏覽
