2023-05-21：給定一個字符串 s 和一個整數(shù) k 。你可以從 s 的前 k 個字母中選擇一個，

并把它加到字符串的末尾。

返回 在應(yīng)用上述步驟的任意數(shù)量的移動后，字典上最小的字符串。

輸入：s = "baaca", k = 3。

輸出："aaabc"。

答案2023-05-21：

大體過程如下：

1.當(dāng) k 大于 1 時，直接將字符串 s 中的字符按照字典序排序，得到排序后的字符串 s'，返回 s'。

2.當(dāng) k 等于 1 時，需要使用 DC3 算法對字符串 s 進行處理，得到其所有后綴排名，并找到排名最小的后綴起始位置 minRankIndex。

3.將字符串 s 的前 minRankIndex 個字符移動到字符串末尾，得到新的字符串 s'，返回 s'。

值得注意的是，DC3 算法是一種用于求解后綴數(shù)組的算法，可以在 O(n) 的復(fù)雜度內(nèi)計算一個字符串的后綴數(shù)組。在本題中，我們需要用到 DC3 算法來尋找字符串 s 所有后綴的排名，以便找到排名最小的后綴起始位置。

對于給定字符串 s 和整數(shù) k，orderlyQueue 函數(shù)的時間復(fù)雜度和空間復(fù)雜度分別如下：

1.當(dāng) k > 1 時，時間復(fù)雜度為 O(nlogn)，其中 n 是字符串 s 的長度。主要耗時在排序操作中，使用快速排序等算法可以達到 O(nlogn) 的復(fù)雜度?？臻g復(fù)雜度也為 O(nlogn)，主要用于存儲字符串?dāng)?shù)組的副本和排序結(jié)果。

2.當(dāng) k = 1 時，時間復(fù)雜度為 O(n)，其中 n 是字符串 s 的長度。時間復(fù)雜度主要來自 DC3 算法的實現(xiàn)，該算法可以在 O(n) 的時間復(fù)雜度內(nèi)計算一個字符串的后綴數(shù)組?？臻g復(fù)雜度為 O(n)，主要用于存儲后綴數(shù)組、排名和其他中間變量。

綜上所述，orderlyQueue 函數(shù)的時間復(fù)雜度為 O(nlogn) 或 O(n)，空間復(fù)雜度為 O(nlogn) 或 O(n)，具體取決于 k 的值。

go完整代碼如下：

package?main

import?(
????"fmt"
????"sort"
????"strings"
)

func?orderlyQueue(s?string,?k?int)?string?{
????if?k?>?1?{
????????sArr?:=?strings.Split(s,?"")
????????sort.Strings(sArr)
????????return?strings.Join(sArr,?"")
????}?else?{
????????s2?:=?s?+?s
????????n?:=?len(s2)
????????arr?:=?make([]int,?n)
????????for?i?:=?0;?i?<?n;?i++?{
????????????arr[i]?=?int(s2[i]?-?'a'?+?1)
????????}
????????dc3?:=?NewDC3(arr,?26)
????????n?=?n?>>?1
????????minRankIndex?:=?0
????????for?i?:=?1;?i?<?n;?i++?{
????????????if?dc3.rank[i]?<?dc3.rank[minRankIndex]?{
????????????????minRankIndex?=?i
????????????}
????????}
????????return?s[minRankIndex:]?+?s[0:minRankIndex]
????}
}

//?DC3算法實現(xiàn)
//?根據(jù)原算法Java代碼修改
type?DC3?struct?{
????sa???[]int
????rank?[]int
}

//?NewDC3?構(gòu)造函數(shù)
func?NewDC3(nums?[]int,?max?int)?*DC3?{
????dc3?:=?&DC3{}
????dc3.sa?=?dc3.sa0(nums,?max)
????dc3.rank?=?dc3.rank0()
????return?dc3
}

func?(dc3?*DC3)?sa0(nums?[]int,?K?int)?[]int?{
????n?:=?len(nums)
????arr?:=?make([]int,?n+3)
????copy(arr,?nums)
????return?dc3.skew(arr,?n,?K)
}

func?(dc3?*DC3)?skew(nums?[]int,?n?int,?K?int)?[]int?{
????n0?:=?(n?+?2)?/?3
????n1?:=?(n?+?1)?/?3
????n2?:=?n?/?3
????n02?:=?n0?+?n2
????s12?:=?make([]int,?n02+3)
????sa12?:=?make([]int,?n02+3)
????for?i,?j?:=?0,?0;?i?<?n+(n0-n1);?i++?{
????????if?i%3?!=?0?{
????????????s12[j]?=?i
????????????j++
????????}
????}
????dc3.radixPass(nums,?s12,?sa12,?2,?n02,?K)
????dc3.radixPass(nums,?sa12,?s12,?1,?n02,?K)
????dc3.radixPass(nums,?s12,?sa12,?0,?n02,?K)

????name?:=?0
????c0?:=?-1
????c1?:=?-1
????c2?:=?-1
????for?i?:=?0;?i?<?n02;?i++?{
????????if?nums[sa12[i]]?!=?c0?||?nums[sa12[i]+1]?!=?c1?||?nums[sa12[i]+2]?!=?c2?{
????????????name++
????????????c0?=?nums[sa12[i]]
????????????c1?=?nums[sa12[i]+1]
????????????c2?=?nums[sa12[i]+2]
????????}
????????if?sa12[i]%3?==?1?{
????????????s12[sa12[i]/3]?=?name
????????}?else?{
????????????s12[sa12[i]/3+n0]?=?name
????????}
????}
????if?name?<?n02?{
????????sa12?=?dc3.skew(s12,?n02,?name)
????????for?i?:=?0;?i?<?n02;?i++?{
????????????s12[sa12[i]]?=?i?+?1
????????}
????}?else?{
????????for?i?:=?0;?i?<?n02;?i++?{
????????????sa12[s12[i]-1]?=?i
????????}
????}

????s0?:=?make([]int,?n0)
????sa0?:=?make([]int,?n0)
????for?i,?j?:=?0,?0;?i?<?n02;?i++?{
????????if?sa12[i]?<?n0?{
????????????s0[j]?=?3?*?sa12[i]
????????????j++
????????}
????}
????dc3.radixPass(nums,?s0,?sa0,?0,?n0,?K)

????sa?:=?make([]int,?n)
????for?p,?t,?k?:=?0,?n0-n1,?0;?k?<?n;?k++?{
????????i?:=?sa12[t]
????????if?i?<?n0?{
????????????i?=?i*3?+?1
????????}?else?{
????????????i?=?(i-n0)*3?+?2
????????}
????????j?:=?sa0[p]
????????if?i?<?n-1?&&?j?<?n-1?{
????????????if?nums[i]?<?nums[j]?||?(nums[i]?==?nums[j]?&&?nums[i+1]?<?nums[j+1])?||
????????????????(nums[i]?==?nums[j]?&&?nums[i+1]?==?nums[j+1]?&&?nums[i+2]?<=?nums[j+2])?{
????????????????sa[k]?=?i
????????????????t++
????????????????if?t?==?n02?{
????????????????????k++
????????????????????for?;?p?<?n0;?p++?{
????????????????????????sa[k]?=?sa0[p]
????????????????????????k++
????????????????????}
????????????????}
????????????}?else?{
????????????????sa[k]?=?j
????????????????p++
????????????????if?p?==?n0?{
????????????????????k++
????????????????????for?;?t?<?n02;?t++?{
????????????????????????i?:=?sa12[t]
????????????????????????if?i?<?n0?{
????????????????????????????sa[k]?=?i*3?+?1
????????????????????????}?else?{
????????????????????????????sa[k]?=?(i-n0)*3?+?2
????????????????????????}
????????????????????????k++
????????????????????}
????????????????}
????????????}
????????}?else?{
????????????if?nums[i]?<?nums[j]?||?(nums[i]?==?nums[j]?&&?nums[i+1]?<=?nums[j+1])?{
????????????????sa[k]?=?i
????????????????t++
????????????????if?t?==?n02?{
????????????????????k++
????????????????????for?;?p?<?n0;?p++?{
????????????????????????sa[k]?=?sa0[p]
????????????????????????k++
????????????????????}
????????????????}
????????????}?else?{
????????????????sa[k]?=?j
????????????????p++
????????????????if?p?==?n0?{
????????????????????k++
????????????????????for?;?t?<?n02;?t++?{
????????????????????????i?:=?sa12[t]
????????????????????????if?i?<?n0?{
????????????????????????????sa[k]?=?i*3?+?1
????????????????????????}?else?{
????????????????????????????sa[k]?=?(i-n0)*3?+?2
????????????????????????}
????????????????????????k++
????????????????????}
????????????????}
????????????}
????????}
????}
????return?sa
}

func?(dc3?*DC3)?radixPass(nums?[]int,?input?[]int,?output?[]int,?offset?int,?n?int,?k?int)?{
????cnt?:=?make([]int,?k+1)
????for?i?:=?0;?i?<?n;?i++?{
????????cnt[nums[input[i]+offset]]++
????}
????for?i,?sum?:=?0,?0;?i?<?len(cnt);?i++?{
????????t?:=?cnt[i]
????????cnt[i]?=?sum
????????sum?+=?t
????}
????for?i?:=?0;?i?<?n;?i++?{
????????output[cnt[nums[input[i]+offset]]]?=?input[i]
????????cnt[nums[input[i]+offset]]++
????}
}

func?(dc3?*DC3)?rank0()?[]int?{
????n?:=?len(dc3.sa)
????ans?:=?make([]int,?n)
????for?i?:=?0;?i?<?n;?i++?{
????????ans[dc3.sa[i]]?=?i
????}
????return?ans
}

func?main()?{
????s?:=?"baaca"
????k?:=?3
????result?:=?orderlyQueue(s,?k)
????fmt.Println(result)
}


福大大架構(gòu)師每日一題

java當(dāng)死，golang當(dāng)立。最新面試題，涉及golang，rust，mysql，redis，云原生，算法，分布式，網(wǎng)絡(luò)，操作系統(tǒng)。

516篇原創(chuàng)內(nèi)容

公眾號