回文子字串 | Medium | LeetCode#647. Palindromic Substrings
題目敘述 題目難度： Medium 題目敘述： 給定字串 s，回傳 s 中有多少回文子字串，回文代表字串從前往後讀等於從後往前讀都是一樣的字串。 解法一開始的想法我的想法就是可以遞迴處理，每次可以讀取一段字串，之後用一個函數檢查是否是回文，如果是，就將字串加入結果列表， 12345678910111213s = "abc"a -> Check if palindromicab -> Check if palindromicabc -> Check if palindromicac -> Check if palindromicb -> Check if palindromicbc -> Check if palindromicc -> Check if palindromiclist = [a,b,c]return list.size() 但後續發現會有大量重複計算的問題，很容易會超時，因此改變成其他做法 我的解答錯誤做法1234567891011121314151617181920212223242526272...
兌換零錢 | Medium | LeetCode#322. Coin Change
題目敘述 題目難度： Medium 題目敘述： 給定一個整數陣列 coins，分別代表不同硬幣的面額，另外給定目標金額 amount，題目要求回傳，達到目標金額 amount 所需的 最少硬幣數量，如果 coins 中的面額無法達到目標金額就回傳 -1 解法一開始的想法首先假設今天陣列是 [1,2,5] 那對於 amount 每次可以選擇減1減2或減5，扣除完畢後下一輪又可以選擇要減1減2還是減5，直到最後如果 amount 為 0 則代表達到目標金額，如果扣除太多 amount < 0 就代表不能達到目標金額，這時候就需要回傳 -1。如果畫出這個想法的遞迴樹會像是下面這樣。 Step1 解法的遞迴樹 可以看到應該會有很多重複的計算，因此稍後也會有最佳化的空間在。 我的解答Step-112345678910111213141516int coinchangehelper(vector<int>& coins, int amount){ if(amount==0) return 0; if(amount <0) retu...
Kubernetes for DevOps 筆記 |【DevOps技能樹】
Basic解釋一下什麼是 Kubernetes 用於進行 容器編排和管理的平台，可用於容器的自動化部署和擴展 Kubernetes 的主要功能有哪些? Self-Healing: 使用 Health check 來檢查運行中的容器，並且做出對應行為 Ex.重啟容器 Load Balancing: 將請求分散給 cluster中不同的應用 Operations: Kubernetes 打包的應用程式可以使用Cluster的 API 來更新其狀態並根據 Event 和應用程式狀態變更觸發操作 Automated Rollout: 逐步對應用更新，並且在出現問題時可以Rollout Scaling: 基於自定義的條件進行水平擴展 Secrets：可用一種以私有方式儲存使用者名稱、密碼和服務端點的機制，而且並非每個使用Cluster的使用者都可以查看 可以用哪些方式來去跟 Kubernetes 的資源互動 可以用 kubectl 命令列工具去與 Kubernetes Cluster 進行互動。 在部署應用到 Kubernetes的時候，哪些 Kubernetes 物件最常使用到 D...
AWS for DevOps 筆記 |【DevOps技能樹】
Regions & AZsRegion: 一群橫跨多個不同地理位置的資料中心 Ex. us-east-1 Avaiable Zone(AZ): 每個 Region 下都有多個相互隔離的位置叫做AZ，一個AZ中可能會有一個或多個資料中心，具有獨立的網路系統以及供電。 us-east-1a, us-east-1b….etc Local Zone: 沒有實體的資料中心，通常會連接到某個AZ, Ex.台灣Local Zone 就是接到 ap-northeast-1，旨在提供服務給 edge location 以降低延遲。 AWS Outposts: 部署在客戶 On Premises 的實體伺服器，提供本地存取AWS服務 IAM在 AWS 環境中用於進行存取控制的服務。可以管理哪些使用者可以有權限存取哪些資源。 Security Best Practices: 不要用 Root User 來進行日常業務，請建立對應的 User 給與適當權限再進行業務 在 IAM 中下面是常見得術語和關係圖：IAM User, IAM Group, IAM Role, Permission p...
Python for DevOps 筆記 |【DevOps技能樹】
Basic Data Typesdata type 可以透過 type() 來獲取物件或變數的 data type 123>>> var = "This is a string">>> print(type(var))<class 'str'> Variables x valid x_y valid x-y invalid Python 變數並非 Case Sensitive VAR 不等於 var 當你在輸入 x=1 的時候會發生什麼事？ 其實就是創造一個整數物件其value為1 因此會在記憶體中分配一個固定大小的位址用來存放 1 而 x 這個名稱會指向用於該物件的 reference 123456>>> x =123>>> y =x>>> print(id(x))4298889392>>> print(id(y))4298889392 在 Python 中，變數是對物件的引用，這意味著變數名稱指向記憶體...
入室搶劫問題 | Medium | LeetCode#198. House Robber
題目敘述 題目難度: Medium 題目描述: 題目假設你是一個專業的竊賊，街上的屋子都有一筆現金，在街上挨家挨戶的入室竊盜，但如果你偷了相鄰兩間屋子就會觸發自動警報報警，你就會被抓。給定一個整數陣列 nums 代表街上每間屋子藏有的錢有多少，請回傳竊賊在不觸發警報的狀況下，可以偷到最大數目的金額。 解法一開始的想法我的想法就是，其實就是要找一個陣列 除了相鄰元素外彼此的相加的所有可能組合當中的最大和。舉例來說，給定 nums={2,7,9,3,1}，那非相鄰的所有可能組合如下： 123452,9,1 => 122,3 => 57,3 => 107,1 => 89, 1 => 10 這當中數值最大的和為 12，而因此有了下面的遞迴做法 錯誤解法12345678910111213class Solution {public: int robHelper(vector<int>& nums, int start) { if (start >= nums.size(...
最小成本爬樓梯問題 | Easy | LeetCode#746. Min Cost Climbing Stairs
題目敘述 題目難度: Easy 題目敘述: 題目給定一個整數陣列 cost，其中 cost[i] 代表通過第 i 階所需要的成本，一旦付完成本後，就可以再度選擇走一階還是兩階直到到達階梯頂端。題目也有說明，起點也可以選第一階 (index=0) 或者第二階 (index=1) 開始。這題的最終目標要求的是到達頂端所需要的最小成本是多少。 解法一開始的想法這題是基於 LeetCode 76. Climbing Stairs 的延伸問題。那這題根據題目給的例子，假設 cost=[10,15,20] 由於初始可以選第一階或第二階，而所有走法如下: 123410, 15, 20 = 45 (每次走一階)10,20 = 30 (先走一步再一次跨兩階)15, 20 = 35 (起點在第二階，然後再走一階)15 (起點在第二，然後一次走跨兩階) 因此要目前需要找出的遞迴關係是，對於任意階梯的最小成本是多少 其實在這個問題中就可以發現這是會有重疊的子問題，並且之後有機會對重複計算進行最佳化，因此可以用某些 D...
爬樓梯問題 | Easy | LeetCode#70. Climbing Stairs
題目敘述 題目難度：Easy 題目敘述：題目描述要爬階梯，需要 n 階可以到頂端，每次可以跨一步或是兩步，有多少種爬到頂端的方式? 解法一開始的想法首先要先思考這題的遞迴關係，任意階的步驟數，會是由什麼組成？ 這裡可以觀察到如果 n=1 也就是往上一層有幾種走法，答案就是 1 因為只能走一步，那 n=2 這時就可以選擇走兩次一步 [1,1] 或者是一次走兩步 [2]，也就是有兩種選擇，那若 n=3 呢？ 往上三階其實就是往上一階和往上兩街的組合，因此他們對應的走法數量也會是 n=1 和 n=2 的加總 1234n=1 | output1=1n=2 | output2=2n=3 = 2+1 | output= output1+ output2 因此可以總結遞回式為 $F(n) = F(n-1) + F(n-2)$，把它寫成程式如下： 123456int climbStairs(int n){ if(n<=0) return 0; if(n==1) return 1; if(n=2) return 2; return cli...
刷題知識整理 | 動態規劃 Dynamic Programming(DP)
前言從還沒開始刷題前就耳聞了DP題目的恐怖，因此想說在實際開始刷類似題目前整理一下DP的知識。 在閱讀網路資料的時候發現這篇文章解釋得很好，因此非常推薦先閱讀這篇 文章，作者有提到要理解 DP，耐心很重要，然後還需要熟悉遞迴，因為DP問題通常會用遞迴來解決 甚麼是 Dynamic Programming(DP)?這裡我必須提到上面那篇文章說的結論: Dynamic Programming 是一種用來幫助遞迴程式碼更加有效率的工具，所以文章作者也認為不該在面對一個問題的時候就先去識別這個問題是否是一個 DP問題，而是先判斷是否需要用到遞迴，而在遞迴的基礎上，會延伸思考到這個遞迴程式碼可能會很冗，因此有答案應該會有改善空間，而改善的方式就透過 Dynamic Programming DP 是用來改善現有 Solution 的方式 ! 接下來介紹使用這個工具的步驟，其中包含了4個步驟，這裡會用一個題目來逐步解釋 題目: LeetCode62. Unique Paths 這題中給了一個大小 m x n 的格子，有一個機器人在最左上角的位置，機器人每次執行可以往下或往右走一格，機...
重新排序鏈結 | Medium | LeetCode#143. Reorder List
題目敘述 題目難度: Medium 題目敘述: 題目給定一個 single linked list，L0 → L1 → … → Ln - 1 → Ln 請將這個 list 重組成 L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … 在這當中請不要改動節點值。 解法一開始的想法 由於排序看起來像是把一個 linked list 頭尾對折然後再交互連接，因此我的想法會是先找到鏈結的中間節點，再將其拆分成兩個 list，之後將後半部分的 list 進行反序排列，接著再跟前半部分的list交互排列。 我的解法12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), ne...
