題目連結:
題目意譯:
你被給定一個索引值從 0 開始數的字串 num,代表著一個非負整數。
在一次操作中,你可以從 num 中選定任一個位數數字並將其刪除。注意到如果你將 num 所有位數刪光光後,num 會變成 0。
回傳讓 num 變「特別」最少所需的操作數。
一個整數 x 是「特別的」,代表著其值可以被 25 整除。
限制:
1 ≦ num.length ≦ 100
num 只由數字 '0' 到 '9' 組成。
num 不包含任何前導零。
範例測資:
範例 1:
輸入: num = "2245047"
輸出: 2
解釋: 刪除位數 num[5] 和 num[6]。最終數字為 "22450",因其可被 25 整除所以是特別的。
可以證明 2 是得到一個特別數字的最少所需操作數。
範例 2:
輸入: num = "2908305"
輸出: 3
解釋: 刪除位數 num[3] 、 num[4] 和 num[6]。最終數字為 "2900",因其可被 25 整除所以是特別的。
可以證明 3 是得到一個特別數字的最少所需操作數。
範例 3:
輸入: num = "10"
輸出: 1
解釋: 刪除位數 num[0]。最終數字為 "0",因其可被 25 整除所以是特別的。
可以證明 1 是得到一個特別數字的最少所需操作數。
解題思維:
首先,觀察一個數字要被 25 整除的條件——其值應以 00 、 25 、 50 或是 75 作為結尾。
由於把 num 的位數全部刪光光會自動變成 "0",因此直接最少至少可以在 num.length 次操作內做到。而接著我們就是讓 num 試試看變成分別以 00 、 25 、 50 或 75 作為結尾。
首先是 00 的情況:
很明顯地,如果 num 的位數裡有至少 2 個 0 存在,則我們必定可以讓 00 作為其結尾;反之,則不可並直接到下一個情況即可。
那如果多於 2 個 0,那要選哪兩個呢?首先,第一個 0 應當要選最右側的那一個。這樣一來只需要刪掉最少的位數便可以到數字結尾;同理,第二個 0 要選第一個 0 以外最靠右的那一個。
而中間刪掉的位數個數即是「第一個 0 離結尾還隔多少數字」加上「第二個 0 與第一個 0 之間有多少不是 0 的數字」。
而其它情況也是同理。
因此所求即為上述四種結尾的情況加上預設的全部刪光光的策略中刪除的位數最少者。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。