判斷回文串最快速的函式應該怎麼寫?

時間 2021-09-10 03:29:36

1樓:猥瑣的民工

我來試寫乙個

intf3

(string&s

)if(*

pleft

!=*pright

)return

false

;while

(pleft

)return

true;}

2樓:好個蓋碗茶

我把題主的兩種方法略作修改(避免頻繁呼叫s.size()),順便再加上我隨便搞的乙個優化方法,在我本機跑了一遍benchmark結果如下(其中F1是題主的方法1,F2是題主的方法2,F3是我隨便YY的乙個方法)。可以暫時得出結論:

題主的兩種方法在O2優化級別及以上差距不大,但是還有一些常數提公升空間,例如我YY的方法三就是其中一種。

-O2BenchmarkTimeCPU IterationsBM_F139151 ns 39059 ns 17830

BM_F239526 ns 39379 ns 17077

BM_F323793 ns 23671 ns 28290

-O3BenchmarkTimeCPU IterationsBM_F139176 ns 39087 ns 18025

BM_F238868 ns 38805 ns 18084

BM_F318162 ns 18129 ns 38476

這三個函式的實現如下

static bool F1(const std::string &s)

static bool F2(const std::string &s)

static bool F3(const std::string &s)

3樓:摺紙

個人傾向於第二種更優,因為第一種在 for() 內部反覆呼叫 string 的 size() 函式,這在 OI 中是一件較為影響程式效率的做法(即使吸了氧),由於本人知識有限,無法從更多角度進行分析了......

4樓:友誼樹下

將 i,j 代換為字串指標理論上比訪問下標要快(也許編譯器給你優化好了).

不過這個函式非常簡單, 是 O(n) 計算量, 沒有必要做大的優化.(又不是 O(n^3)的矩陣乘法...)

字寫的極度醜 練什麼書最快 怎麼練能快速見效

額額 書寫醜最大問題是不整齊,就是個章法問題,單字不用練了,抓緊時間練習章法,再醜的單字,只要能書寫非常整齊,也會具有美感和藝術。 北岸實用硬筆書法 題主沒上圖還真不知道極度醜具體是什麼情況。因為醜是相當於你自己的審美標準而言的。而且,即便是真醜,那也有N種醜法,最好發圖看一下,到底是筆畫問題 結構...

25歲的副連職排長,怎麼才能最快速度離開部隊?

吉言 其實如果現在想出來實際上只有義退或者病退兩條路可選,幹齡2年轉業基本沒可能,除非有大關係。而且以這個身份轉業積分很低的。 CNisBest 我還是在30歲的尾巴趕到前倉皇的逃離了部隊,哪怕再有很短時間就夠線解決副營,哪怕現在的單位已經是上下班通勤週六日全休,也沒有絲毫動搖我一分一毫,人,總是要...

沒有胎壓監測的車輛怎麼簡單快速的判斷輪胎狀況?

德國馬牌輪胎 很多原車不帶胎壓監測的車主會為愛車選擇後期加裝實現胎壓監測功能的儀器,這些儀器大致可以分成3類 OBD型 外接型和內建型。OBD型 內部裝有OBD晶元的監測儀插在車輛的OBD介面,能夠讀出四輪ABS感測器的數值。當四輪胎壓相同時,它們的轉速一致 而當某個輪氣壓變少時,輪子的直徑就變小,...