由 LeetCode 1922 數學題,推導乘法同餘性質

最近在看到了 LeetCode 1922. Count Good Numbers 的題目後,發現幾乎是一題純數學的題目,需要理解 Modular Exponentiation(模冪運算)這個技巧才能夠順利解題。

想當初在學習非對稱式加密的核心技術 RSA 時,所接觸到的 Euler’s Theorem(歐拉定理)就大量用到模(Mod,取餘數)運算。

這次的題目正巧也需要對於模運算性質有所理解,才能得出有效率的解法。在理解完題意之後,結論是需要透過程式來計算以下算式:

$$
(5^x \cdot 4^y) \bmod (10^9 + 7)
$$

其中題目限制 $x, y \leq 10^{15}$,這也就意味 $5^x \cdot 4^y$ 的數值可能相當大,遠大於絕大部分的程式語言中單一變數能儲存的數字上限。

繼續閱讀

Merge Sort

題目

合併排序 Merge Sort,經典排序之一。將給定一串數字排序,時間複雜度的要求為 O(nlogn)

繼續閱讀

Infix Expression to Expression Tree

中序表達式轉後序表達式。

主要想處理的功能是:把算式多餘的 Parentheses(括號)給移除,例如:1+(2+3) 可變成:1+2+31*(2+3) 則不變。

剛開始看感覺還好,開始做了之後才發現好像遠沒想像的簡單,用一般字串處理,頂多搭配個 Stack 來做,好像很多情況沒有辦法做到,因此有個想法,將 Infix 的表達式(就是我們一般看四則運算的方式)轉成 Postfix,因為 Postfix 就不含括號。

繼續閱讀