2021-04-03：给定两个字符串str1和str2，想把str2整体插入到str1中的某个位置，形成最大的字典序，返回字典序最大的结果。
福大大 答案2021-04-03：
1.暴力法。
2.DC3算法。自然智慧想不到，需要练敏感度。
2.1.构造字符串。str = str1+最小字符+str2。
2.2.对str进行dc3算法，求出rank数组。
2.3.遍历0到str1长度，找到小于str2起始位置的序号。
2.4.根据序号算出bestSplit值。时间紧，先放一放。
2.5.根据bestSplit拆分str1，然后合并。返回str1左+str2+str1右。
代码用golang编写。代码如下：
package mainimport ( "fmt" "index/suffixarray" "math/rand" "time" "unsafe")func main() { rand.Seed(time.Now().Unix()) //YJWBRFKBMYQWFCRTSA //YTOFNTX cnt := 0 const TOTAL = 10000 for i := 0; i < TOTAL; i++ { s1 := newRandString() s2 := newRandString() fmt.Println("s1 = ", s1) fmt.Println("s2 = ", s2) ret1 := right(s1, s2) ret2 := maxC����,����ombine(s1, s2) fmt.Println("暴力的答案：", ret1) fmt.Println("DC3的答案：", ret2) if ret1 == ret2 { fmt.Println("正确") cnt++ } else { fmt.Println("错误") } fmt.Println("-------------") } fmt.Println("总数：", TOTAL) fmt.Println("正确：", cnt)}func newRandString() string { retLen := rand.Intn(20) + 5 ret := make([]byte, retLen) for i := 0; i < retLen; i++ { ret[i] = byte(rand.Intn(26) + 'A') } return string(ret)}func right(s1 string, s2 string) string { if len(s1) == 0 { return s2 } if len(s2) == 0 { return s1 } ans := s1 + s2 temp := "" best := len(s1) for i := 0; i < len(s1); i++ { temp = s1[0:i] + s2 + s1[i:] if temp > ans { ans = temp best = i } } fmt.Println("暴力best = ", best) return ans}// 正式方法 O(N+M) + O(M^2)// N : s1长度// M : s2长度func maxCombine(s1 string, s2 string) string { if len(s1) == 0 { return s2 } if len(s2) == 0 { return s1 } str1 := []byte(s1) str2 := []byte(s2) N := len(str1) M := len(str2) min := str1[0] max := str1[0] for i := 1; i < N; i++ { min = getMin(min, str1[i]) max = getMax(max, str1[i]) } for i := 0; i < M; i++ { min = getMin(min, str2[i]) max = getMax(max, str2[i]) } all := make([]byte, N+M+1) index := 0 for i := 0; i < N; i++ { all[index] = str1[i] - min + 2 index++ } all[index] = 1 index++ for i := 0; i < M; i++ { all[index] = str2[i] - min + 2 index++ } dc3 := NewFddSa(all) comp := N + 1 for i := 0; i < N; i++ { if dc3.Rank[i] < dc3.Rank[comp] { best := bestSplit(s1, s2, i) //best := i //这句代码是错的 fmt.Println("DC3的best = ", best) return s1[0:best] + s2 + s1[best:] } } return s1 + s2}func bestSplit(s1 string, s2 string, first int) int { N := len(s1) M := len(s2) end := N for i, j := first, 0; i < N && j < M; i, j = i+1, j+1 { if s1[i] < s2[j] { end = i break } } bestPrefix := s2 bestSplit := first for i, j := first+1, M-1; i <= end; i, j = i+1, j-1 { curPrefix := s1[first:i] + s2[0:j] if curPrefix >= bestPrefix { bestPrefix = curPrefix bestSplit = i } } if bestSplit != first { fmt.Println("注意，first = ", first, " ,bestSplit = ", bestSplit) } return bestSplit}func getMax(a byte, b byte) byte { if a > b { return a } else { return b }}func getMin(a byte, b byte) byte { if a < b { return a } else { return b }}type FddSa struct { Sa []int Rank []int}func NewFddSa(bytes []byte) *FddSa { ret := &FddSa{} ret.Rank = make([]int, len(bytes)) ret.Sa = make([]int, len(bytes)) index := suffixarray.New(bytes) p1 := uintptr(unsafe.Pointer(index)) //获取指针 p1 += 24 p2 := *(*[]int32)(unsafe.Pointer(p1)) //将指针转行成切片 for i := 0; i < len(bytes); i++ { ret.Sa[i] = int(p2[i]) //sa数组 ret.Rank[int(p2[i])] = i //rank数组 } return ret}执行结果如下：
左神java代码
评论