技術

  • |

    密碼學（2）： Modern Block Ciphers

    Byzttofficial

    Block Ciphers 可以譯作分組加密或者分塊加密。 常用 Block Ciphers 相提並論的加密方式是 Stream Ciphers，可譯作串流加密法。兩者都是替換式密碼（Substitution ciphers），都應用了可逆映射（reversible mapping）： Stream Ciphers 串流加密法是一種對稱密鑰密碼，其中明文數字與偽隨機密碼數字流（密鑰流）相結合。在實踐中，一個數字通常是一個 bit，與異或 （XOR）組合操作，把明文訊息逐個 bit 轉換成密文。 典型的 Stream Ciphers 是自動加密的 Vigenère 密碼和 Vernam 密碼。 較有名的 Stream Ciphers 是 RC4。 RC4 RSA DSI 擁有的專有密碼，由 Ron Rivest 設計，簡單但有效。密鑰大小可變，是一種面向字節的串流加密法。在 SSL/TLS、無線 WEP 中廣泛使用。密鑰形成所有 8-bit 的隨機排列，使用該排列來打亂輸入信息，一次處理一個字節。 RC4 Key Schedule: RC4 加解密： RC4 的安全性： Block Ciphers 明文區塊被視為一個整體，用於生成等長（64 / 128…

  • |

    做題筆記：Remove Duplicates from Sorted Array (Java)

    Byzttofficial

    今後 Easy 題若沒碰到非常精彩的就不每題都更了。 題目描述： 給定一個按非遞減順序排序的整數數組 nums，就地刪除重複項，使每個單獨的元素只出現一次。元素的相對順序應保持不變。 由於在某些語言中無法更改數組的長度，因此您必須將結果放在數組 nums 的前半部分。更正式地說，如果刪除重複項後有 k 個元素，則 nums 的前 k 個元素應持有最終結果。除了前 k 個元素之外，留下什麼都不重要。 將最終結果放入 nums 的前 k 個插槽後返回 k值。 Example 1: Example 2: Stack 解法： 自己還是只能想出來蠢方法，應該刷題量還遠遠不夠吧： 7 ms 利用順序的取巧方法： 1 ms

  • |

    做題筆記：Valid Parentheses (Java)

    Byzttofficial

    題目描述： 給定一個僅包含字符 ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ 和 ‘]’ 的字符串 s，確定輸入字符串是否有效。 有效的情況指： 前括號必須用相同類型的括號閉合。 前括號必須以正確的順序閉合。 Example 1: Example 2: Example 3: 暴力解法： 昨天半夜擼的，還是想不到什麼好點子： 79 ms，慘不忍睹。 Stack 解法： Hint 中已經提到，應該使用 Stack ： 2 ms

  • |

    做題筆記：Longest Common Prefix (Java)

    Byzttofficial

    還滿難的一道題。 題目描述： 編寫一個函數來查找字符串數組中最長的共有前綴字符串。 如果沒有共有前綴，則返回一個空字符串””。 Example 1: Example 2: Horizontal scanning: 自己嘗試的方法： 1 ms Vertical scanning: Solution 中提供的方法二： Divide and conquer: Solution 中提供的方法三： Binary search: Solution 中提供的方法四：

  • | |

    做題筆記：Roman to Integer (Java)

    Byzttofficial

    題目描述： 將羅馬數字轉換為整數，具體規則略。 Example 1: Example 2: Example 3: 自己的 Switch 暴力解法： 兜了好幾個圈…… 意外發生了，本地 IDE 能跑出正確答案，但是在 Leetcode 上跑不出來，我竟然為這種問題浪費了不少時間，最終也沒解決…… 正確精練的 Switch 解法： 6 ms 運用 Hashmap：

  • |

    做題筆記：Palindrome Number (Java)

    Byzttofficial

    題目描述： 給定一個整數 x，如果 x 是回文數，則返回 true。 回文數指一個整數向後讀和向前讀內容相同。 Example 1: Example 2: Example 3: 算術解法： 利用 Java 整數倒序計算： 9 ms，超過 87.67% 的答案。 轉換為 String 的解法： 進階要求 Follow Up 竟然問了一句 Could you solve it without converting the integer to a string? 原來我想到的已經是進階方法了，常規解法是轉換為 String： 19 ms，超過 19.48% 的答案。

  • |

    做題筆記：Two Sum (Java)

    Byzttofficial

    驚恐自己要找不到工作了，開始做題，記錄一下做題筆記。第一道，是刷題界的 Hello World —— Two Sum。 題目描述： 給定一個整數數組 nums 和一個整數 target，返回兩個數字的索引，使它們相加為 target。 假設每個輸入都只有一個解決方案，並且不會使用相同的元素兩次。 可以按任何順序返回答案。 Example 1: Example 2: Example 3: Foreach 暴力解法： 第一次刷題，算法小白，只想得到這種方式： 果不其然，106 ms，超過了10%的答案，好歹是通過了對吧…… 以前上課做作業時，都是秉持著能跑就行的態度，習慣很差，現在我開始認真考慮優化的問題了，也算是一大進步。 Hashmap 解法： 看了 discussion 之後，追求高效率，這道題是應該使用 Hashmap 的： 3 ms，超過85%的結果。

  • | |

    密碼學（1）：古典密碼

    Byzttofficial

    前言：一點廢話 程序猿的博客好像都是用來寫技術文的，只有我一直在鍵政，所以心血來潮想寫技術文試一試。我對 WordPress 加上目前正在使用的前端主題的表現並沒有信心，像代碼高亮之類的操作也無法處理得很好，所以準備先談談比較理論少代碼的密碼學這個主題，這也是個人比較有興趣的一個領域。 古典密碼（Classical cipher），顧名思義，就是歷史上曾使用的一些加密方式，大多已不再使用。不過介紹它們有助於我們了解密碼學的發展歷史以及認識一些基本的加密思路。古典密碼主要有替換式密碼和移項式密碼兩大類。 替換式密碼 替換式密碼（Substitution ciphers），意指明文中的內容通過字母或字母群系統性地替換為其他內容，形成密文。 凱撒密碼 凱撒密碼（Caesar cipher）是最為人熟知的一種替換式密碼，最早出現在 Gallic wars 中用於軍事目的。它還有另一個名字叫 Caesar shift，意思就很明顯了——通過移位（shift）來達成替換的目的。比如一串明文”ABC”，用”D”替代”A”、”E”替代”B”、”F”替代”C”，則會得到密文”DEF”，我們可以理解為，明文「右」移了三位得到了密文。 多說無益，直接看一個例子： 原文中的每個字母都向右移動了三位，從而產生了密文，替換過程遵循下表： 基於此，我們可以用數學方式表達明文與密文之間的關係： 凱撒密碼總共只有 25 種移位方法，很容易通過暴力（Brute Force）破解，簡簡單單枚舉所有可能的情況便能得到明文。 單表加密 單表加密（monoalphabetic cipher）嚴格定義上是凱撒密碼的母集，即凱撒密碼也是單表加密的一種。不過此處語境下的單表加密，是指對凱撒密碼的一種改良方式，它對整個明文進行替換，而不是替換逐個字母，這意味著單表加密需要一個與明文相同長度的密鑰。 雖然排列組合的可能性變得非常多，但仍然是風險很高的一種加密方式，因為在自然語言中一些詞的頻率必然會高於另外的詞，可以通過頻率分析（frequency analysis）進行破解。 維吉尼亞密碼 相較之下，維吉尼亞密碼（Vigenère Cipher）則是多表加密（polyalphabetic cipher）的一個典型例子，可以視之為多個凱撒密碼的組合，以下這個被稱為維吉尼亞方格的表格被應用在這種加密方法中： 此處簡單引用一下維基中使用到的例子： 波雷費密碼 波雷費密碼（Playfair cipher）是最為著名的一種多字母加密方法。它將明文視為單個整體的單元放在一幅圖中，並將整個單元轉換為密文圖，此處的「圖」通常是指一個 5×5 的矩陣。 選擇密鑰之後，將密鑰的字母逐個填入該 5×5 的矩陣內，字母不能重複，若遇重複則跳過。填完密鑰之後將剩餘的英文字母依順序填入，因為一共只有 25 個空間，一般會將 Q 去除或將 I 和 J 視作同一字（例子使用後者）。 加密時，應該把所有字母分為兩個一組，如果最後有一個字母落單，則添上 X 作為搭配。然後按以下規則，尋找每兩個字母對應的密文以實現加密： 現在假設明文是”Nice to…