1樓：一鯨
// DFS with trimming
function
minimalConcat
(strings
)解釋一波思路：
第一反應是排序後連線，但明顯不對，因為每個字串長度不等，如 ['cb', 'c']，正解為 'cb/c' 而非 'c/cb'。
第二個思路，換個排序規則行不行？其實，無論用任何排序規則都是不行的，因為 S1 . S2 > S2 .
S1 並不能推出 S1 . S3 . S2 > S2 .
S3 . S1，例如 S1 = 'c', S2 = 'cb', S3 = 'a'。 S1 .
S2 = 'ccb' > 'cbc' = S2 . S1。而 S1 .
S3 . S2 = 'cacb' < 'cbac' = S2 . S3 .
S1。這意味著兩個串之間沒有必然的順序。
第三個思路，用 Trie 做貪心行不行？似乎也不行，因為貪心到 Trie 的 terminal 節點，下步有兩個方向：繼續向下，或返回根節點。不一定能貪心出乙個最優策略。
沒辦法，只能老老實實做搜尋，好在這個題目有明顯的剪枝方法，就是把當前的字串按字典序跟已知的下限解做比較。如果已經超了，直接剪掉。
但這個做法仍然有毛病，對於極端 case：['a', 'aa', 'aaa', 'aaaa'剪枝失效，還是會超時。有時間再想想還有沒有更好的解法。
2樓：悽臨雨
其中COMPARE比較函式，需要特別編寫
對於原始序列Origin=
排序結果應為Sorted =
簡單的理解即把每個元素無限迴圈然後與其他比較:
234123412341234123412341……
234234234234……
2323232323……
234523452345……
44444444……
設我們需要的COMPARE為運算子《，在按《排序的陣列上其性質有
① [i] 《 [i+正數] 或 [i]等價[i+正數]
② [i][i+1] 《 [i][i+1+正數] 或 [i][i+1]等價[i][i+1+正數]
對於某個i，若[i+1]等價[i]，那麼[i][i]等價[i][i+1]
對於某個i，若[i+1]比[i]多乙個極小值，那麼[i][i+1]比[i][i]多乙個極小值，且沒有任何乙個[i+1+正數x][i+1+正數x] 比 [i+1][i+1] 更靠近[i][i]
可以發現，將[i][i][i]…… 和 [j][j][j]…… 做字典序判斷，即我們所需的《運算。
如何實現a、b分別無限迴圈的字典序判斷:
對於 COMPARE(a,b)，若a,b 長度相同，則普通地strcmp;
若不同，則令字元索引 Ia在[0，len(a))間無限環繞，Ib在[0,len(b))間無限環繞，逐個比較字元若不同則得出結果，若相同且Ia == len(a)，Ib = len(b)則我們可以發現aaaaaa…… == bbbbbbbb……這種特殊情況，比如121212 等價於 1212， 123123 等價於123，此時取較長者為《運算的較小值。
3樓：C十十20年
類似於乙個奧賽題：拼接若干整數形成乙個最大整數。假定兩個串之間的大小是可以比較的（不能用strcmp函式），使用氣泡排序公升序排序，然後從頭至尾連線所有串即可。
而寫乙個類似於strcmp的函式最關鍵：設串1長m，串2長n，求m和n的最小公倍數p；將串1複製共p／m份拼接成串一，串2複製共p／n份拼接成串二，再用strcmp比較串一和串二即可。其實沒必要複製拼接比較，兩個串的字元迴圈比較即可，這兩個方法是等價的，只不過記憶體需求不一樣。
2021 03 20 給定乙個二維陣列matrix，其中的值不是0就是1，返回全部由 如何解答呢？
mathe 我們可以先考慮計算每個1它左邊包含自身連續的1的數目 如果它本身為0，那麼計數也設定為0 比如對於矩陣 0110111 1100011 1110011 0111100 計數結果為 0120123 1200012 1230012 0123400 然後依次分析每一列 比如第一列有兩個連續的1...
2021 04 04 給定乙個非負陣列arr，和乙個正數m。 返回arr的所有子串行 如何解答呢？
Joker 先求字首和。掃瞄字首和陣列 Sum i Sum i m 插入到 Set 裡面 同時求 Sum i m 和 Sum i m m 的upper bound 就是比它大的最小 Set 中元素 upper bound 對應乙個 Sum j 用這個 Sum i Sum j m 更新答案。更新答案的...
2021 05 12 給定乙個陣列arr，只能對arr中的乙個子陣列排序， 但是想讓 如何解答呢？
找到最小下標 使得 arr i 1 eeimg 1 找到最大下標 使得 arr j eeimg 1 找到 的時間複雜度是 若 不存在，則說明陣列已經排好序了，結果是 下面假設 均存在且容易看出 假設 求出 的時間複雜度是 只要 且 b eeimg 1 就令 然後令 遞減，直到 或者 只要 且 就令 ...