Re: [閒聊] 每日LeetCode
※ 引述《sustainer123 (caster)》之銘言：
: C code
: ------------------
: #include <string.h>
: bool isSubsequence(char * s, char * t){
: int m=0;
: int j=0;
: for(int i=0; i<strlen(s); i++){
: for(; j<strlen(t); j++){
: if(s[i] == t[j]){
: j++;
: m++;
: break;
: }
: }
: if(i == m){
: return 0;
: }
: }
: return 1;
: }
: -------------------
還有一個小問題是 for 迴圈裡的 strlen()
像是 for (int i = 0; i < strlen(s); i++) { /* ... */ }
每次跑到 i < strlen(s) 這裡時，會又要去執行一遍 strlen(s)
上面的程式最差情況可能會變成 O(n^2)
當然如果編譯器夠聰明的話有可能幫你優化掉
但最好還是不要冒這個風險，因為編譯器必須要知道
1. s 不會改指向其他人
2. s 指到的東西也不會改變
缺一個都不行。可以寫成
for (int i = 0, n = strlen(s); i < n; i++) {
/* ... */
}
之類的，或是也可以用 C 字串以 '\0' 結尾的特性，改成
for (int i = 0; s[i]; i++) {
/* ... */
}
至於上面的程式到底會不會重複跑 strlen()
首先要先知道 LeetCode 用的編譯版本和參數
可以在選語言那邊點左邊的 (i)
會跳出詳細的說明
https://i.imgur.com/9RDAnUl.png
可以看到是用 gcc 8.2 配上 gnu11
基本上就是 C11 加上一堆奇怪的 GNU extension
優化等級是 -O1
拿到 https://godbolt.org/ 之類的地方編譯
可以發現，外層的 strlen(s) 只會跑一次
但內層的 strlen(t) 會跑 strlen(s) 次
甚至我改 -O3 或改成 const char * const t 都沒用
看來 gcc 的這個優化只有對當下這層迴圈有效
但我用 clang 編就能只跑一次 = =
但因為 s 長度 <= 100 所以還是能在時間內就是了
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1672339302.A.D6C.html
推
12/30 02:43,
2年前
, 1F
12/30 02:43, 1F
推
12/30 03:25,
2年前
, 2F
12/30 03:25, 2F
推
12/30 04:53,
2年前
, 3F
12/30 04:53, 3F
推
12/30 11:00,
2年前
, 4F
12/30 11:00, 4F
推
12/30 11:01,
2年前
, 5F
12/30 11:01, 5F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 166 之 719 篇)：