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)
個性簽名:時間會解決一切