刷題常用技巧(一)-位元運算

前言

最近因為開始刷題,跟當初想像的刷題有些不同,發現在刷了幾題下來,其實是有些核心的邏輯是可以應用在不少題目上,想要把到目前為止在思考時常可以用到的一些技巧陸陸續續的記錄下來,除了幫助自己未來複習,也希望可以幫助正在刷題的人。

常用技巧

以下簡單介紹的技巧通常都是因為題目有條件限制,例如時間複雜度O(n)、空間複雜度O(1)或是只能in place修改等等所衍伸出來的技巧,不只在運算上可以有更好的效率,有時候也可以用更簡潔的方式來完成題目的要求。常見的技巧如下:

位元運算子法 (Bitwise operator)

會用到這個方法主要是刷到一題"Sum of Two Integers”,題目要求給定兩個數字,透過演算法後要能回傳兩數字相加後的值,但前提是不能用+/-運算子。而位元運算子法就能很好的解決這個問題,其核心概念我認為主要是將目標數透過二進位(不是0就是1)進行邏輯判斷從而達到加減的效果。以前述的例子即是透過XOR (^)的方法來達到1和0的相加效果,如下圖:

而透過AND(&)的方法來達到1和1進位的效果,如下圖:

總結來說,當數字轉換成二進位後,拿兩數做判斷只會有四種狀況,分別是(1)0碰到0 (2)1碰到0 (3)0碰到1 (4)1碰到1,而讓給定的兩數做XOR判斷即可以將前三種方法完美達到加法的效果。但因為第一種及第四種狀況都會回傳0,無法分辨是哪種狀況要進位,此時利用AND就可以很好補足此問題,AND只有在第四種狀況會回傳1,意即可知道在哪裡需要進位(<<),透過兩者不斷互相搭配即可達到加法效果。此例題我的解法如下:

var getSum = function(a, b) {
let total = a ^ b
let carry = a & b
while (carry) {
carry <<= 1
let carry2 = carry & total
let total2 = carry ^ total
carry = carry2
total = total2
}
return total
};

還有一些其他在運算過程中可以用到位元運算子的概念,例如判斷a,b兩數是否相等就可以用a^b,若兩數完全相等則會回傳0,可放入if條件判斷中。還有一些例如判斷是否是四的倍數,二進位數字中有幾個1等等方法,若有興趣可以參考這篇討論(連結)。

下一篇會討論雙指針法 (Two Pointer)的原理以及一些應用的題目。

1992, 學習科技|研究投資|環境工程技師|成功大學環境工程學系|台灣大學環境工程研究所|水處理行業工作兩年半|想要用科技打造自己的企業,過自己想過的生活。

1992, 學習科技|研究投資|環境工程技師|成功大學環境工程學系|台灣大學環境工程研究所|水處理行業工作兩年半|想要用科技打造自己的企業,過自己想過的生活。