two pointer
Two Pointer 的產生源自於一個核心問題，如何有效處理陣列或者序列中的配對、區間以及範圍搜尋問題。 最初，我們在遇到需要在陣列中尋找配對或者子陣列的問題時，最直觀的方式便是使用雙重迴圈 (nested loops)。例如，在一個陣列中找到兩個數的和等於目標值： 1234567for(int i = 0; i < arr.len(); i++){ for(int j = i + 1; j < arr.len(); j++){ for(arr[i] + arr[j] == target){ return [i, j]; } }} 但是雙重迴圈的方式，導致的後果就是時間複雜度為 $O(n^2)$ 相比於暴力解法的「盲目搜尋」，Two Pointer 提供了一種「有方向性的搜尋」策略。 兩者差異在於，暴力解需要檢查所有可能組合，two pointer 需要根據問題特性，有策略性的縮小搜尋範圍。 Key PointTwo Pointer 的產生基於對...
Trapping Rain Water
Trapping Rain WaterProblem DescriptionGiven n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining. Approach: Two PointersIntuitionThe key insight is that at any position, the water level is dtermined the minimum of the maximum heights to its left and right. We can use two pointers moving towards each other from both ends. Algorithm Initialize two pointer left and right at the beginning and each of the array. Ke...
Number of Visible People in a Queue
Number of Visible People in a Queue題目敘述There are n people standing in a queue, and they numbered from 0 to n - 1 in left to right order. You are given an array heights of distinct integers where heights[i] represents the height of the i person. A person can see another person to their right in the queue if everybody in between is shorter than both of them. More formally, the ith person can see the j person if i < j and min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], ..., h...
K8s Development Tool
Kubernetes 是現在最常被使用的容器編排平台 (container orchestration platform)，對於想要在 local 環境開發的開發者，選擇一套能夠模擬 Kubernetes 行為的工具，來進行本地的測試開發，變得越來越重要。 像是 Kind 和 Minikube 等工具就提供了方便的解決方式。該篇文章中會提及每一種工具所著重的地方在哪裡，而我們需要根據怎樣的情景選擇對應的工具進行開發。 接下來針對以下四套不同的開源軟體 kind, Minikube, k3s, kubeadm 進行介紹 kind 介紹 kind is a tool for running local Kubernetes clusters using Docker container “nodes”. kind was primarily designed for testing Kubernetes itself, but may be used for local development or CI. kind 是 Kubernetes 底下的一個子專案，他的全名是 Kube...
Word Break
Word Break題目敘述Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Note that the same word in the dictionary may be reused multiple times in the segmentation. Example1Input: s = “leetcode”, wordDict = [“leet”,”code”]Output: trueExplanation: Return true because “leetcode” can be segmented as “leet code”. Example 2:Input: s = “applepenapple”, wordDict = [“apple”,”pen”]Output:...
Longest Common Subsequence
Longest Common Subsequence題目敘述Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0. DefinitionsSubsequenceA subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters. For example, “ace” is a subsequence of “abcde”. Common SubsequenceA common subsequence of two strings is a subsequence that...
