題目連結(jié)：
題目意譯：
你被給定一個(gè)索引值從 0 開始的二元字串 s 以及兩個(gè)整數(shù) minJump 以及 maxJump 。一開始，你站在索引值 0 的位置，其值等於 '0'。你可以從索引值 i 移動(dòng)到索引值 j 如果以下條件滿足：
i + minJump ≦ j ≦ min(i + maxJump, s.length - 1) 且
s[j] == '0'。
回傳真（True）如果可以抵達(dá) s 中的索引值 s.length - 1 之位置；反之，回傳假（False）。
限制：
2 ≦ s.length ≦ 105
s[i] is either '0' or '1'.
s[0] == '0'
1 ≦ minJump ≦ maxJump < s.length
範(fàn)例測(cè)資：
範(fàn)例 1：
輸入： s = "011010", minJump = 2, maxJump = 3
輸出： true
解釋：
第一步中，從索引值 0 移動(dòng)到索引值 3 。
第二步中，從索引值 3 移動(dòng)到索引值 5 。
範(fàn)例 2：
輸入： s = "01101110", minJump = 2, maxJump = 3
輸出： false
解題思維：
仿照這題，我們從 s 的結(jié)尾往回推看是否能從起點(diǎn)到達(dá)結(jié)尾。當(dāng)然如果結(jié)尾的字元不等於 '0'，則我們絕對(duì)不可能從起點(diǎn)到達(dá)終點(diǎn)（移動(dòng)到此位置的條件無法滿足）。
我們定義一個(gè)陣列 D[i] 代表我們是否能從位置 i 移動(dòng)到結(jié)尾的位置。一開始，很顯然地 D[s.length - 1] = 真。可以看到其他位置 i
如果 D[i + minJump] 、 D[i + minJump + 1] 、 …… 、 D[i + maxJump] 之一為真，則 D[i] 也為真；
反之， D[i] 為假。
因此我們從 i = s.length - minJump - 1 的位置開始（因?yàn)榭梢钥吹?s.length - minJump 到結(jié)尾前一格都無法跳到結(jié)尾）維護(hù)一個(gè)滑動(dòng)視窗（Sliding Window，其概念曾經(jīng)出現(xiàn)於這題只是當(dāng)時(shí)沒有提及此名詞）。而該滑動(dòng)視窗的用意為統(tǒng)計(jì)該視窗所涵蓋到的區(qū)間有多少位置可到結(jié)尾，即對(duì)應(yīng)到 D[i + minJump] + D[i + minJump + 1] + …… + D[i + maxJump] 。
而當(dāng)視窗的左側(cè)往左移動(dòng)時(shí)，內(nèi)容將變?yōu)?D[i + minJump - 1] 、 D[i + minJump + 1] 、 …… 、 D[i + maxJump - 1] ，比起移動(dòng)前多了 D[i + minJump - 1] 但是少了 D[i + maxJump] （所以可以看到視窗的內(nèi)容很好更新）。
例如
s = "011010", minJump = 2, maxJump = 3
一開始
s = 011010
D = 000001
然後我們從藍(lán)色位置開始往左，而滑動(dòng)視窗 SW 以橘色表示：
s = 011010
D = 000001
因?yàn)?SW 內(nèi)有位置可以抵達(dá)終點(diǎn)且當(dāng)前位置為 '0'，因此
s = 011010
D = 000101
s = 011010
D = 000001
雖然 SW 內(nèi)有位置可以抵達(dá)終點(diǎn)但當(dāng)前位置為 '1'，因此
s = 011010
D = 000101
s = 011010
D = 000001
雖然 SW 內(nèi)有位置可以抵達(dá)終點(diǎn)且當(dāng)前位置為 '1'，因此
s = 011010
D = 000101
s = 011010
D = 000001
因?yàn)?SW 內(nèi)有位置可以抵達(dá)終點(diǎn)且當(dāng)前位置為 '0'，因此
s = 011010
D = 100101
因?yàn)?D[0] 為真，所以我們可以從起點(diǎn)抵達(dá)結(jié)尾。而其他的測(cè)資也是類似的情形。
此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
