天天看點

C++刷leetcode幾點注意事項

size() 傳回的無符号數

大概的場景如下:

由于有符号數和無符号數比較時,會當做無符号數比較,是以-1是 \(2^{31}-1\)

是以記得加上強制類型轉換

string類型參數,未修改是記得加引用

例如Leetcode 472. 連接配接詞,未加引用會逾時,而加上引用就176ms過

因為這題中,最多有1e5個字元串,每個字元串可能調用size次query,所有大量的拷貝會導緻逾時

統計是否出現而不是次數是,盡量用unordered_set

unordered_map比unordered_set慢,

例如 Leetcode 面試題 17.13. 恢複空格,用unordered_map花了1040ms,而unordered_set隻用了204ms

vector的resize可能會導緻逾時

例如我在Leetcode 336回文對中的送出 https://leetcode-cn.com/submissions/detail/252119270/,前者會逾時,後者不會

cpprefence中關于vector resize的複雜度描述:

Complexity Linear in the difference between the current size and count. Additional complexity possible due to reallocation if capacity is less than count

string的size()函數雖然是常數時間,但是也需要盡量少調用

同樣在Leetcode 336中,

正常寫法:https://leetcode-cn.com/submissions/detail/252119613/,1036 ms

減少size調用:https://leetcode-cn.com/submissions/detail/252119899/,568 ms

cpprefence說的是 Constant(since C++11)

個性簽名:時間會解決一切