ETH官方钱包

前往
大廳
主題

[leetcode]552. Student Attendance Record II

???\~O_O~/??? | 2021-08-28 12:00:01 | 巴幣 0 | 人氣 234

題目: 552. Student Attendance Record II
難度: Hard
目前下列解法的時間複雜度: O(lg(n))


題目說明

稍微小複雜的狀態轉移。


解法: dp

1. 把DFA(deterministic finite automaton)做好,隨狀態更新各個狀態的數字。
2. 由於每次只看前一次dp表的內容,所以記答案的格子只需要狀態數*2。
3. 化成矩陣連乘的形式使用矩陣快速冪。


source code

或是4. 另外跑 n=1~10萬 的答案,然後直接寫進程式裡, O(1) 查表。

創作回應

相關創作

更多創作