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

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

返回 在應用上述步驟的任意數量的移動后，字典上最小的字符串。

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

輸出："aaabc"。

答案2023-05-21：

大體過程如下：

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

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

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

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

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

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

2.當 k = 1 時，時間復雜度為 O(n)，其中 n 是字符串 s 的長度。時間復雜度主要來自 DC3 算法的實現，該算法可以在 O(n) 的時間復雜度內計算一個字符串的后綴數組。空間復雜度為 O(n)，主要用于存儲后綴數組、排名和其他中間變量。

綜上所述，orderlyQueue 函數的時間復雜度為 O(nlogn) 或 O(n)，空間復雜度為 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算法實現
// 根據原算法Java代碼修改
type DC3 struct {
	sa   []int
	rank []int
}

// NewDC3 構造函數
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)
}

文章來源地址http://www.zghlxwxcb.cn/news/detail-453688.html

到了這里，關于2023-05-21：給定一個字符串 s 和一個整數 k 。你可以從 s 的前 k 個字母中選擇一個， 并把它加到字符串的末尾。 返回 在應用上述步驟的任意數量的移動后，字典上最小的字符串。 輸入：s的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！