資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中查詢給定字串子串中最後一個不重複字元的查詢
在這個問題中，我們給定字串str和Q個查詢，每個查詢包含兩個整數。我們的任務是建立一個程式來解決C++中查詢給定字串子串中最後一個不重複字元的查詢。
問題描述
在每個查詢中，我們有兩個整數L和R。為了解決這些查詢，我們將從索引L到索引R獲取一個子字串。並找到子字串中最後一個不重複的字元。
讓我們舉個例子來理解這個問題：
輸入：str = “Tutorialspoint” Q = 2
query = {{4, 8}, {2, 6}}
輸出: -1 , -1
解釋
subStr[4...8] = “rials”。最後一個不重複的字元是s。但所有字元的頻率都是1。
subStr[2...6] = “toria”。最後一個不重複的字元是a。但所有字元的頻率都是1。
解決方案
為了解決這個問題，我們需要找到出現頻率為1的字元。一個簡單易行的方法是建立一個矩陣來計算charFreq[][]。為了解決子陣列查詢，我們將檢查所有字元的出現頻率，並返回頻率為1的最後一個字元。
示例
#include<bits/stdc++.h>
using namespace std;
int charFreq[256][1000] = {0};
void initialiseCharFrequency(string str, int n) {
charFreq[(int)str[0]][0] = 1;
for (int i = 1; i < n; i++) {
char ch = str[i];
for (int j = 0; j < 256; j++) {
char charToUpdate = (char)j;
if (charToUpdate == ch)
charFreq[j][i] = charFreq[j][i - 1] + 1;
else
charFreq[j][i] = charFreq[j][i - 1];
}
}
}
string returnCharFromString(char x) {
string s(1, x);
return s;
}
string lastUniqueChar(string str, int n, int start, int end) {
for (int i = end; i >= start; i--) {
char ch = str[i];
if ((charFreq[(int)ch][end] - charFreq[(int)ch][start - 1]) ==1)
return returnCharFromString(ch);
}
return "-1";
}
int main() {
string str = "TutorialsPoint";
int len = str.length();
int Q = 3;
int query[Q][2] = { { 2, 9 }, { 2, 3 }, { 0, 12 } };
initialiseCharFrequency(str, len);
for (int i = 0; i < Q; i++)
cout<<"\nFor Query "<<(i+1)<<": The last non-repeating character in the sub-string of a given string is "<<lastUniqueChar(str, len,query[i][0], query[i][1]);
}輸出
For Query 1: The last non-repeating character in the sub-string of a given string is P For Query 2: The last non-repeating character in the sub-string of a given string is o For Query 3: The last non-repeating character in the sub-string of a given string is n
更新於：2020年10月9日
138 次瀏覽
廣告