用 Java 刷 Leetcode 學演算法 - Binary Search - Leetcode 1898

續前篇: 用 Java 刷 Leetcode 學演算法 - Binary Search - 2 - Leetcode 1894

Leetcode 1898. Maximum Number of Removable Characters

做到這題會發現, 他和一般的數字比大小不一樣, 但也是用二分搜尋法. 

left 是符合條件的

right 是不符合條件的. 

要找符合條件的最大 left 值.

我們可以設計一個泛型函式: biggestMeet()

NJBinarySearch.java

NJSearchAble.java

這樣這題我們就只要寫成底下這樣即可: 

Solution - Github 程式

定義一個 class 是 NJSearchAble 的, 並提供 ifMeet function. 

ifMeet() 在這題就是判斷 用該 k 值後是否仍是 substring

這樣主程式只要使用如下即可

另外 Leetcode 這題設計還算巧妙. 

如果不用 Binary Search, 而是依序一個個檢查的話, 時間會超過. 

目前這方法

和底下這個: doocs-leetcode 的 比較

還快了一點. ( 其實 Leetcode 在不同時間環境下跑, 或有不同, 所以可以大致同個時段跑不同程式來比較, 而絕對的% 參考即可.

 

另外 Github 上的這個 TheAlgorithms 

整理的也相當不錯, 可以參考.