數學一直是將抽象問題轉化為有形問題的主要工具，從而使解決方案更容易。讓我們從 LeetCode 中解決這個問題：
給定一個字串 s，找出不重復字符的最長子串的長度。
示例 1：
輸入：s = "abcabcbb" 輸出：3 解釋：答案是 "abc"，長度為 3。
示例 2：
輸入：s = "bbbbb" 輸出：1 解釋：答案是 "b"，長度為 1。
有沒有一種方法可以對這類問題或數學方程的任何問題進行建模？
uj5u.com熱心網友回復：
這是一個計算時間（O（n））線性的解決方案。
為方便起見，我假設這些字母都是小寫的。
假設字串如下。
str = 'abacbdcb'
首先創建一個散列，其鍵是字母表中的小寫字母，鍵“k”的值是字串中最后一次“看到”字母“k”的字串的索引（待定義）。最初所有值都是nil，表示沒有看到任何字符。
idx_last_seen = {"a"=>nil, "b"=>nil, "c"=>nil,..., "z"=>nil}
創建一個陣列longest，其中包含一個值為 的元素1：
longest = [1]
longest[i]將是以 index 結尾的最長非重復字串的長度i。
索引 i = 0
初始化字串索引并更新idx_last_seen：
i = 0
idx_last_seen[str[i]] = i
所以現在
idx_last_seen #=> {"a"=>0, "b"=>nil, "c"=>nil,..., "z"=>nil}
索引 i = 1
增加字串索引并在該索引處記錄字串中的字符：
i = 1 #=> 1
c = str[i] #=> 'b'
We wish to now compute longest[i].
idx_last_seen[c] = idx_last_seen['b'] #=> nil
As idx_last_seen has no key c, c has not been seen before. Therefore, we append longest with the last element of longest plus 1.
longest << (longest[-1] 1)
#=> [1, 2]
Here longest[-1] denotes the last element of longest.
This tells us that the length of the longest non-repeating string ending at index 0 is 1 and the longest non-repeating string ending at index 1 is 2.
Update idx_last_seen:
idx_last_seen[str[i]] = i
idx_last_seen
#=> {"a"=>0, "b"=>1, "c"=>nil,..., "z"=>nil}
Index i = 2
i = 1 #=> 2
c = str[i] #=> 'a'
j = idx_last_seen[c] = idx_last_seen['a'] #=> 0
j = 0 means that 'a' was last seen at index 0. Therefore the longest string ending at index 2 equals
i - j #=> 2
so we append 2 to longest and update idx_last_seen:
longest << i - j
#=> [1, 2, 2]
idx_last_seen[c] = i
idx_last_seen #=> {"a"=>2, "b"=>1, "c"=>nil,..., "z"=>nil}
Index i = 3
i = 1 #=> 3
c = str[i] #=> 'c'
idx_last_seen[c] = idx_last_seen['c'] #=> nil
so c has not been seen before. Therefore:
longest << (longest[-1] 1)
#=> [1, 2, 2, 3]
Update idx_last_seen
idx_last_seen[c] = i
idx_last_seen #=> {"a"=>2, "b"=>1, "c"=>3, "d"=>nil,..., "z"=>nil}
Wrapping up
Continuing in this way we obtain the following results.
01234567
'abacbdcb' longest
1 'a'
2 'ab'
2 'ba'
3 'bac'
3 'acb'
4 'acbd'
3 'bdc'
3 'dcb'
3 'dab'
2 'ba'
3 'bac'
Each number on the diagonal equals the the length of the maximum non-repeating string that ends at the character of the string that is in the same column above; that is, they are the elements of longest. I've already shown the calculations for the first four indices. The string shown to the right of the each number on the diagonal is the associated longest non-repeating string ending at the associated index.
We see that the longest non-repeating string ends at the index i for which longest[i] is maximum, here 4, the string 'acbc'.
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/435887.html