我嘗試編寫程序，給定一個(gè)由 ascii[az] 范圍內(nèi)的小寫字母組成的字符串，并確定包含該字符串中所有字母的最小子字符串的長(zhǎng)度。但由于超時(shí)我被終止了。我怎樣才能改善 sulotion？我試過(guò)： public static int shortestSubstring(string s){ int n = s.Length; int max_distinct = max_distinct_char(s, n); int minl = n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { String subs = null; if (i < j) subs = s.Substring(i, s.Length - j); else subs = s.Substring(j, s.Length - i); int subs_lenght = subs.Length; int sub_distinct_char = max_distinct_char(subs, subs_lenght); if (subs_lenght < minl && max_distinct == sub_distinct_char) { minl = subs_lenght; } } } return minl; } private static int max_distinct_char(String s, int n) { int[] count = new int[NO_OF_CHARS]; for (int i = 0; i < n; i++) count[s[i]]++; int max_distinct = 0; for (int i = 0; i < NO_OF_CHARS; i++) { if (count[i] != 0) max_distinct++; } return max_distinct; }}
3 回答
達(dá)令說(shuō)
TA貢獻(xiàn)1821條經(jīng)驗(yàn) 獲得超6個(gè)贊
我相信這個(gè)問(wèn)題有一個(gè) O(n) 的解決方案如下：
我們首先遍歷字符串，找出其中有多少個(gè)不同的字符。在此之后，我們將表示子字符串左右索引的兩個(gè)指針初始化為 0。我們還保留一個(gè)數(shù)組，用于計(jì)算子字符串中當(dāng)前存在的每個(gè)字符的數(shù)量。如果沒(méi)有包含所有字符，我們?cè)黾佑抑羔樢垣@得另一個(gè)字符。如果包含所有字符，我們?cè)黾幼笾羔樢员憧赡艿玫礁〉淖哟?。由于左指針或右指針在每一步都?huì)增加，因此該算法應(yīng)該在 O(n) 時(shí)間內(nèi)運(yùn)行。
不幸的是，我不懂 C#。但是，我已經(jīng)編寫了一個(gè) Java 解決方案（希望它具有類似的語(yǔ)法）。我沒(méi)有對(duì)此進(jìn)行嚴(yán)格的壓力測(cè)試，所以我可能錯(cuò)過(guò)了一個(gè)邊緣案例。
import java.io.*;
public class allChars {
? ? public static void main (String[] args) throws IOException {
? ? ? ? BufferedReader br = new BufferedReader (new InputStreamReader(System.in));
? ? ? ? String s = br.readLine();
? ? ? ? System.out.println(shortestSubstring(s));
? ? }
? ? public static int shortestSubstring(String s) {
? ? ? ? //If length of string is 0, answer is 0
? ? ? ? if (s.length() == 0) {
? ? ? ? ? ? return 0;
? ? ? ? }
? ? ? ? int[] charCounts = new int[26];
? ? ? ? //Find number of distinct characters in string
? ? ? ? int count = 0;
? ? ? ? for (int i = 0; i < s.length(); i ++) {
? ? ? ? ? ? char c = s.charAt(i);
? ? ? ? ? ? //If new character (current count of it is 0)
? ? ? ? ? ? if (charCounts[c - 97] == 0) {
? ? ? ? ? ? ? ? //Increase count of distinct characters
? ? ? ? ? ? ? ? count ++;
? ? ? ? ? ? ? ? //Increase count of this character to 1
? ? ? ? ? ? ? ? //Can put inside if statement because don't care if count is greater than 1 here
? ? ? ? ? ? ? ? //Only care if character is present
? ? ? ? ? ? ? ? charCounts[c - 97]++;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? int shortestLen = Integer.MAX_VALUE;
? ? ? ? charCounts = new int[26];
? ? ? ? //Initialize left and right pointers to 0
? ? ? ? int left = 0;
? ? ? ? int right = 0;
? ? ? ? //Substring already contains first character of string
? ? ? ? int curCount = 1;
? ? ? ? charCounts[s.charAt(0)-97] ++;
? ? ? ? while (Math.max(left,right) < s.length()) {
? ? ? ? ? ? //If all distinct characters present
? ? ? ? ? ? if (curCount == count) {
? ? ? ? ? ? ? ? //Update shortest length
? ? ? ? ? ? ? ? shortestLen = Math.min(right - left + 1, shortestLen);
? ? ? ? ? ? ? ? //Decrease character count of left character
? ? ? ? ? ? ? ? charCounts[s.charAt(left) - 97] --;
? ? ? ? ? ? ? ? //If new count of left character is 0
? ? ? ? ? ? ? ? if (charCounts[s.charAt(left) - 97] == 0) {
? ? ? ? ? ? ? ? ? ? //Decrease count of distinct characters
? ? ? ? ? ? ? ? ? ? curCount --;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? //Increment left pointer to create smaller substring
? ? ? ? ? ? ? ? left ++;
? ? ? ? ? ? }
? ? ? ? ? ? //If not all characters present
? ? ? ? ? ? else {
? ? ? ? ? ? ? ? //Increment right pointer to get another character
? ? ? ? ? ? ? ? right ++;
? ? ? ? ? ? ? ? //If character is new (old count was 0)
? ? ? ? ? ? ? ? if (right < s.length() && charCounts[s.charAt(right) - 97]++ == 0) {
? ? ? ? ? ? ? ? ? ? //Increment distinct character count
? ? ? ? ? ? ? ? ? ? curCount ++;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return shortestLen;
? ? }
}
忽然笑
TA貢獻(xiàn)1806條經(jīng)驗(yàn) 獲得超5個(gè)贊
我希望我理解正確，這是獲取最小字符串的代碼。
string str = "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Donec dictum elementum condimentum. Aliquam commodo ipsum enim. Vivamus tincidunt feugiat urna.";
char[] operators = { ' ', ',', '.', ':', '!', '?', ';' };
string[] vs = str.Split(operators);
string shortestWord = vs[0];
for (int i = 0; i < vs.Length; i++)
{
if (vs[i].Length < shortestWord.Length && vs[i] != "" && vs[i] != " ")
{
shortestWord = vs[i];
}
}
Console.WriteLine(shortestWord);
胡子哥哥
TA貢獻(xiàn)1825條經(jīng)驗(yàn) 獲得超6個(gè)贊
這似乎是一個(gè)O(n^2)問(wèn)題。這并不理想；然而，我們可以做幾件事來(lái)避免測(cè)試不能成為有效候選者的子字符串。
我建議返回子字符串本身，而不是它的長(zhǎng)度。這有助于驗(yàn)證結(jié)果。
public static string ShortestSubstring(string input)
我們首先計(jì)算 ['a' .. 'z'] 范圍內(nèi)每個(gè)字符的出現(xiàn)次數(shù)。我們可以'a'從一個(gè)字符中減去得到它從零開始的索引。
var charCount = new int[26];
foreach (char c in input) {
charCount[c - 'a']++;
}
最短的可能子字符串等于輸入中不同字符的數(shù)量。
int totalDistinctCharCount = charCount.Where(c => c > 0).Count();
要計(jì)算子字符串中不同字符的數(shù)量，我們需要以下布爾數(shù)組：
var hasCharOccurred = new bool[26];
現(xiàn)在，讓我們測(cè)試從不同位置開始的子字符串。totalDistinctCharCount最大起始位置必須允許子字符串至少與（最短的可能子字符串）一樣長(zhǎng)。
string shortest = input;
for (int start = 0; start <= input.Length - totalDistinctCharCount; start++) {
...
}
return shortest;
在這個(gè)循環(huán)中，我們有另一個(gè)循環(huán)來(lái)計(jì)算子字符串的不同字符。請(qǐng)注意，我們直接處理輸入字符串以避免創(chuàng)建大量新字符串。我們只需要測(cè)試比之前找到的任何最短字符串都短的子字符串。因此內(nèi)循環(huán)用作Math.Min(input.Length, start + shortest.Length - 1)限制。循環(huán)內(nèi)容（代替...上面代碼片段中的）：
int distinctCharCount = 0;
// No need to go past the length the previously found shortest.
for (int i = start; i < Math.Min(input.Length, start + shortest.Length - 1); i++) {
int chIndex = input[i] - 'a';
if (!hasCharOccurred[chIndex]) {
hasCharOccurred[chIndex] = true;
distinctCharCount++;
if (distinctCharCount == totalDistinctCharCount) {
shortest = input.Substring(start, i - start + 1);
break; // Found a shorter one, exit this inner loop.
}
}
}
// We cannot omit characters occurring only once
if (charCount[input[start] - 'a'] == 1) {
break; // Start cannot go beyond this point.
}
// Clear hasCharOccurred, to avoid creating a new array evey time.
for (int i = 0; i < 26; i++) {
hasCharOccurred[i] = false;
}
進(jìn)一步的優(yōu)化是，當(dāng)我們?cè)谳斎胱址?( charCount[input[start] - 'a'] == 1) 的起始位置遇到只出現(xiàn)一次的字符時(shí)，我們會(huì)立即停止。由于輸入的每個(gè)不同字符都必須出現(xiàn)在子字符串中，因此該字符必須是子字符串的一部分。
我們可以在控制臺(tái)打印結(jié)果
string shortest = ShortestSubstring(TestString);
Console.WriteLine($"Shortest, Length = {shortest.Length}, \"{shortest}\"");
- 3 回答
- 0 關(guān)注
- 169 瀏覽
添加回答
舉報(bào)
0/150
提交
取消