Posted on

Ubuntu 18.04的apt update更新失敗

錯誤訊息

W: Failed to fetch http://repo.mysql.com/apt/ubuntu/dists/bionic/InRelease The following signatures couldn’t be verified because the public key is not available: NO_PUBKEY 467B942D3A79BD29 W: Some index files failed to download. They have been ignored, or old ones used instead.

問題原因

這個錯誤訊息是說您的系統在嘗試從 http://repo.mysql.com/apt/ubuntu/dists/bionic/ 的軟體庫中下載軟體索引時發生了問題。這可能是由於網路連線中斷或是軟體庫網址變更所導致。

訊息中提到的 “NO_PUBKEY 467B942D3A79BD29” 表示您的系統沒有此軟體庫的公鑰,導致無法驗證下載的軟體索引是否是正確的。

解決方案

要解決這個問題,您可以試著更新系統的軟體庫並且安裝相關的公鑰。在終端機中執行以下指令:

sudo apt-key adv --keyserver hkp://keyserver.ubuntu.com:80 --recv-keys 467B942D3A79BD29
sudo apt-get update

這個指令會從 Ubuntu 的公鑰伺服器中下載指定的公鑰,並且更新系統的軟體庫。完成後,您可以再次嘗試安裝所需的軟體,看看問題是否已經解決了。

Posted on

wordpress 永久連結設定失效

故障的可能原因

  1. .htaccess 檔案不正常:進入 WordPress 的管理後台,點擊「設定」→「連結」,然後按下「儲存變更」。這樣 WordPress 會重新生成 .htaccess 檔案。如果這個步驟沒有解決問題,可以手動在 WordPress 安裝目錄中找到 .htaccess 檔案,並且檢查它是否存在。
  2. 確認 WordPress 是否在正確的網址上運行:如果您的 WordPress 安裝在子目錄或子網域下,請確認永久連結設定正確設定到子目錄下這一點。
  3. 伺服器是否支援永久連結:如果您的伺服器不支援永久連結,則 WordPress 將無法使用它們。(設定方式請見下一篇)
  4. 確認您的主題是否有任何問題:某些 WordPress 主題可能會干擾永久連結的正常運作。嘗試暫時更換到 WordPress 默認主題並再次測試永久連結。

在Apache2支持永久連結

要啟用 Apache2 的 mod_rewrite 模組,您需要將以下內容添加到 Apache2 的設定檔案中:

LoadModule rewrite_module modules/mod_rewrite.so

這個設定通常會加入到 mods-enabled 目錄中的一個設定檔案中。例如,您可以創建一個名為 rewrite.load 的檔案,並將上面的設定添加到這個檔案中。請按照以下步驟進行操作:

  1. 進入 mods-enabled 目錄:
cd /etc/apache2/mods-available
  1. 創建一個名為 rewrite.load 的檔案:
sudo touch rewrite.load
  1. 打開這個檔案並添加以下內容:
LoadModule rewrite_module modules/mod_rewrite.so
  1. 儲存並關閉檔案。
  2. 重新啟動 Apache2 伺服器,以使更改生效:
sudo service apache2 restart

啟用rewrite功能

若您的 /etc/apache2/mods-available 目錄下已經有了 rewrite.load 設定檔案,您可以透過建立符號連結方式來啟用 mod_rewrite 模組。

請按照以下步驟:

  1. 進入到 /etc/apache2/mods-enabled 目錄:
cd /etc/apache2/mods-enabled
  1. 建立 rewrite.load 的符號連結:
sudo ln -s /etc/apache2/mods-available/rewrite.load
  1. 重新啟動 Apache2 伺服器,以使更改生效:
sudo service apache2 restart

執行完上述步驟後,Apache2 的 mod_rewrite 模組即會啟用。您可以再次檢查 /etc/apache2/mods-enabled 目錄,確保 rewrite.load 的符號連結已經建立。若您需要停用 mod_rewrite,則可以刪除這個符號連結即可。

Posted on

在K8S內ksoftirqd耗費大量CPU

問題描述

我們在K8S內架設串流伺服器,在做loadtest時發現,當流量變高之後,K8S用來管理線程的cadvisor所調用的ksoftirqd會占掉非常大的CPU使用率,並導致整個worker node變得緩慢。

相關的問題說明請見: Debugging network stalls on Kubernetes

形成原因

這是因為當使用 Kubernetes 的 NodePort 來公開一個服務時,它將在每個工作節點上開放一個端口,以便外部可以連接到該端口,並將流量轉發到服務的後端 Pod 上。當流量高峰期間,可能會導致節點的 CPU 負載增加,並導致大量的 IRQ 請求,這是因為每個數據包都會觸發一次 IRQ 請求。

IRQ 是中斷請求的簡寫,是一種處理設備 I/O 操作的機制。當設備有 I/O 操作時,它會觸發一個中斷請求,通知操作系統或應用程序需要處理這個 I/O 操作。在網絡通信中,每個數據包都會觸發一次 IRQ 請求,因此當流量高峰期間,大量的 IRQ 請求可能會導致節點的 CPU 負載增加,從而影響應用程序的性能。

為了減輕這個問題,您可以考慮使用負載均衡器來替代 NodePort,將流量分發到多個節點上,從而分散 CPU 負載。您還可以考慮對節點進行調優,以提高節點的性能和吞吐量。例如,可以調整節點的 CPU 和內存資源配額,優化網絡配置,減少網絡延遲等。此外,也可以嘗試使用更高效的網絡協議,如 UDP 協議,以減少 CPU 負載。

IRQ是甚麼

IRQ(Interrupt Request)是計算機系統中的中斷請求,它是用來通知 CPU 執行特定的操作的信號。中斷請求通常由外部設備發出,例如鍵盤、鼠標、網卡、磁盤控制器等,這些設備需要與 CPU 進行通信,以便進行數據傳輸、讀寫、處理等操作。

IRQ 的實現通常涉及到硬件和軟件兩個方面。在硬件方面,通常需要在主板上預留一些專門的中斷請求線(IRQ lines),用於連接各種外設和 CPU,以便它們之間進行數據傳輸和通信。一般來說,一個計算機系統會有多個 IRQ lines,每個 IRQ line 對應一個外設或者一組相關的外設。

在軟件方面,操作系統需要通過中斷控制器來管理各個 IRQ lines,以便在接收到外設發出的中斷請求時,及時地響應並處理。一般來說,中斷控制器會將中斷請求轉發給 CPU,CPU 再執行相應的中斷處理程序來處理中斷請求。

IRQ是計算機硬件的設計決定。當網絡適配器(NIC)接收到數據包時,它會發送一個中斷請求(IRQ)給處理器,通知處理器需要處理這個數據包。處理器收到 IRQ 後,會停止當前的任務,並開始處理中斷請求。處理完中斷請求後,處理器會返回到之前的任務繼續執行。.

網絡適配器是什麼

網絡適配器,也稱為網絡接口卡(Network Interface Card,NIC),是計算機中用於實現網絡通信的硬件設備之一。它通常安裝在計算機主板上,負責接收和發送網絡數據包。網絡適配器可以連接到不同類型的網絡,例如以太網、Wi-Fi、藍牙等,以實現不同的網絡通信方式。

網絡適配器在計算機中的作用是將數據轉換為網絡能夠識別和傳輸的格式,例如將數據包封裝成以太網幀,以便在以太網上進行傳輸。同時,網絡適配器也負責監控網絡上的數據流量,並在需要時觸發 IRQ 請求,通知處理器需要處理數據包。

網絡適配器的性能對網絡通信的效率和吞吐量有很大影響。在高性能計算環境中,通常會選擇高速的網絡適配器,例如 10GbE、40GbE、100GbE 等,以滿足大規模數據傳輸的需求。

為什麼在K8S的IQR會比一般Linux主機更明顯

當一般主機傳輸大量流時,也會產生網絡適配器的 IRQ 請求。但是,這種情況下的 IRQ 請求通常可以被系統有效地處理,並不會對 CPU 的負載產生太大的影響。這是因為一般主機的網絡適配器通常採用了更為先進的中斷卸載技術,如 RSS(Receive Side Scaling)、RPS(Receive Packet Steering)等,可以將 IRQ 請求在多個 CPU 核心上進行分配,從而有效地提高系統的網絡吞吐量。

在 Kubernetes 中,由於每個節點上的 Pod 分佈不確定,因此無法像一般主機那樣進行有效的中斷卸載。此外,由於網絡流量是從 NodePort 直接傳輸到 Pod,中間可能還需要經過多個網絡層,從而增加了系統的網絡負載。因此,在高負載情況下,使用 NodePort 公開服務可能會導致大量 IRQ 請求,從而增加 CPU 的負載。為了解決這個問題,可以考慮使用負載均衡器等技術,將流量轉發到多個節點上,以降低單個節點的負載。

解決方法

由於我們所架設的伺服器為串流伺服器,原本在一般的Linux主機裡面,我們會使用NGINX去做反向代理,讓主機知道現在的連接目標為串流,如下面這個nginx.conf的範例

http {
    include       mime.types;
    default_type  application/octet-stream; #設定所傳輸的格式為串流
    sendfile        on;
}

這樣子當有人透過http去拉取串流時,NIC就會採取長連接的方式去處理這條串流,但是,因為現在我們將串流伺服器移到K8S裡面去,連線請求處理的地方會在worker node所在的NIC上去處理,而不是在串流服務的POD去處理的。因此,即便我們在POD裡面設定連線方式為串流,在worker node上面也是不知道這件事情的。

所以我們會必須要在K8S的ingress裡面去做進一步的設定,第一步要先了解自己的K8S的ingress是用甚麼實作的,例如像我們的K8S是用kubernetes/ingress-nginx實作的

設定介紹: NGINX Configuration

這邊會有三個方式去實作

  1. ConfigMap:使用 Configmap 在 NGINX 中設置全局配置。
  2. Annotations:如果您想要特定 Ingress 規則的特定配置,請使用它。
  3. 自定義模板:當需要更具體的設置時,如open_file_cache,調整監聽選項,rcvbuf或者當無法通過 ConfigMap 更改配置時。

以下是一個使用 types 設置 MIME 類型的示例:

apiVersion: networking.k8s.io/v1
kind: Ingress
metadata:
  name: my-ingress
  annotations:
    nginx.ingress.kubernetes.io/server-snippet: |
      types {
        text/html                             html htm shtml;
        text/css                              css;
        text/xml                              xml;
        image/gif                             gif;
        image/jpeg                            jpeg jpg;
        application/javascript               js;
        application/atom+xml                  atom;
        application/rss+xml                   rss;
        text/mathml                           mml;
        text/plain                            txt;
        text/vnd.sun.j2me.app-descriptor      jad;
        text/vnd.wap.wml                      wml;
        text/x-component                      htc;
        image/png                             png;
        image/tiff                            tif tiff;
        image/vnd.wap.wbmp                    wbmp;
        image/x-icon                          ico;
        image/x-jng                           jng;
        image/x-ms-bmp                        bmp;
        image/svg+xml                         svg svgz;
        image/webp                            webp;
        application/font-woff                 woff;
        application/font-woff2                woff2;
        application/vnd.ms-fontobject         eot;
        application/x-font-ttf                ttc ttf;
        application/x-httpd-php               php;
        application/x-shockwave-flash         swf;
        application/json                      json;
        application/octet-stream              flv; #這邊可以設定MINE TYPE
      }
spec:
  rules:
    - host: example.com
      http:
        paths:
          - path: /
            pathType: Prefix
            backend:
              service:
                name: my-service
                port:
                  name: http

這樣子就可以正確的於ingress處理串流的連接了!

相關官方說明: Annotations – Ingress-Nginx ControllerCustom Headers – Ingress-Nginx Controller

Posted on

最大子序列和問題

概念解釋

最大子序列和問題(Maximum Slice Problem)是指在一個給定的整數序列中,找到一個連續子序列,使得子序列的和最大。

例如,在序列[-2, 1, -3, 4, -1, 2, 1, -5, 4]中,最大的子序列為[4, -1, 2, 1],其和為6。

這個問題在實際應用中經常出現,比如在股票交易中,尋找一段時間內股票價格的最大漲幅,或者在信號處理中,尋找一段時間內信號的最大能量。

最大子序列和問題可以通過暴力枚舉和動態規劃兩種方法解決。暴力枚舉的時間複雜度為O(n^2),動態規劃的時間複雜度為O(n)。其中,動態規劃是更加高效和常用的方法。

下面介紹一下動態規劃的解法思路:

設f[i]表示以第i個元素結尾的最大子序列和,那麼有:

f[i] = max(f[i-1] + nums[i], nums[i])

其中,nums是原始的整數序列,可以看出,f[i]的值只與f[i-1]和nums[i]有關。

狀態轉移方程表示以第i個元素結尾的最大子序列和要么是以第i-1個元素結尾的最大子序列和加上nums[i]得到,要么是只包含第i個元素。

最終的結果就是max(f[0], f[1], …, f[n-1])。

這個算法只需要遍歷一遍整個序列,時間複雜度為O(n),是一個線性算法。因此,在解決最大子序列和問題時,動態規劃是一個高效的解法。

解題思路

假設我們有一個整數序列 nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4],我們要找到一個連續子序列,使得子序列的和最大。

  1. 定義一個狀態數組 f,其中 f[i] 表示以第 i 個元素結尾的最大子序列和。初始時,f[0] = nums[0]。
  2. 現在開始遍歷整個序列,對於每個元素 nums[i],我們需要計算以它為結尾的最大子序列和 f[i]。
    對於 i = 1,我們有:f[1] = max(f[0] + nums[1], nums[1]) = max(-2 + 1, 1) = 1
    對於 i = 2,我們有:f[2] = max(f[1] + nums[2], nums[2]) = max(1 – 3, -3) = -2
  3. 以此類推,我們繼續遍歷整個序列,計算出所有的 f[i]。最後,最大的子序列和即為 max(f[0], f[1], …, f[n-1])。
function maxSubarray(nums) {
  if (!nums || nums.length === 0) {
    return 0;
  }
  let maxSum = nums[0];
  let curSum = nums[0];
  for (let i = 1; i < nums.length; i++) {
    curSum = Math.max(nums[i], curSum + nums[i]);//要不要包含前面的
    maxSum = Math.max(maxSum, curSum);//要不要包含自己
  }
  return maxSum;
}

解題練習 – MaxProfit

題目連結: MaxProfit

function solution(A) {
    if(A.length <= 1){
        return 0
    }
    var diff = []
    var current_diff = 0
    for (var i = 1; i < A.length; i++) {
        current_diff = A[i] - A[i - 1]
        diff.push(current_diff)
    }
    var max_sum = diff[0]
    var curr_sum = diff[0]
    for (var i = 1; i < diff.length; i++) {
        curr_sum = Math.max(diff[i], curr_sum + diff[i]);
        max_sum = Math.max(curr_sum, max_sum);
    }
    return max_sum < 0 ? 0:max_sum
}

https://app.codility.com/demo/results/training4F3SK7-QSS/

解題練習 – MaxSliceSum

題目連結: MaxSliceSum

function solution(A) {
    if(A.length == 0) return 0
    var cur_sum = A[0]
    var max_sum = A[0]
    for(var i=1;i<A.length;i++){
        cur_sum = Math.max(A[i], cur_sum+A[i])
        max_sum = Math.max(max_sum, cur_sum)
    }
    return max_sum
}

https://app.codility.com/demo/results/trainingX4VPNP-3QU/

Posted on

Leader – Dominator解題紀錄

題目內容

題目頁面: https://app.codility.com/programmers/lessons/8-leader/dominator/

Leader概念教學

在LeetCode中,”Leader”通常指的是一個數組中出現次數超過數組長度一半的元素。因為這種元素在數組中出現的次數比其他元素都多,所以被稱為”Leader”。

LeetCode中的一些問題會要求你尋找數組中的Leader或者判斷數組中是否存在Leader。解決這些問題的一種常見方法是使用摩爾投票算法(Moore Voting Algorithm)。

摩爾投票算法的基本思想是遍歷數組,對於當前遍歷到的元素,如果它和當前候選元素相同,則將計數器加一,否則將計數器減一。當計數器為零時,更換當前的候選元素。最後剩下的候選元素就是可能的Leader,需要再次遍歷數組來驗證它是否真的是Leader。

需要注意的是,摩爾投票算法的前提是數組中一定存在Leader,如果數組中不存在Leader,那麼算法得出的結果可能是錯誤的。

摩爾投票算法

摩爾投票算法是一種快速尋找數組中出現次數超過一半的元素的方法,其基本思想已經在之前的回答中進行了介紹。這裡再介紹一下摩爾投票算法的實現方法。

假設我們要在數組中尋找出現次數超過一半的元素,可以使用一個計數器count和一個候選元素candidate來輔助實現。初始時,將count和candidate分別設為0和null。

遍歷數組,對於每一個元素:

  1. 如果count為0,將candidate設置為當前元素;
  2. 如果當前元素和candidate相同,將count加1;
  3. 如果當前元素和candidate不同,將count減1;
  4. 遍歷結束後,candidate就是可能的超過一半的元素,但需要再次遍歷數組來驗證它是否真的出現次數超過一半。

它的時間複雜度是O(n)

解題紀錄

function solution(A) {
    var candidate = 0
    var count = 0
    for(var i=0;i<A.length;i++){
        if(count == 0){
            candidate = A[i]
            count++
        }else if(candidate == A[i]){
            count++
        }else {
            count--
        }
    }
    var idx = []
    for(var i=0;i<A.length;i++){
        if(A[i] == candidate){
            idx.push(i)
        }
    }
    //console.log(idx)
    return idx.length > A.length/2 ? idx[0]:-1
}

https://app.codility.com/demo/results/trainingNPG8GS-3QA/

EquiLeader題目內容

題目連結: https://app.codility.com/programmers/lessons/8-leader/equi_leader/

解題想法

  1. 找出過半的那個數字
  2. 使用前綴和的方式去計算從0到現在的Leader的加總
  3. 計算在某個點的前面、後面是否有占全部長度的一半

我的解題

function solution(A) {
    var candidate = 0
    var count = 0
    for(var i=0;i<A.length;i++){
        if(count == 0){
            candidate = A[i]
            count++
        }else if(candidate == A[i]){
            count++
        }else {
            count--
        }
    }
    var amount_list = []
    var currentCount = 0
    for(var i=0;i<A.length;i++){
        if(A[i] == candidate){
            currentCount++
        }
        amount_list.push(currentCount)
    }
    var equi_leaders = 0
    for(var i=0;i<amount_list.length;i++){
        if(amount_list[amount_list.length-1]-amount_list[i] > (amount_list.length-i-1)/2 && amount_list[i] > (i+1)/2){
            equi_leaders++
        }
    }
    return equi_leaders
}
Posted on

Stacks and Queues – StoneWall解題紀錄

題目內容

題目頁面: https://app.codility.com/programmers/lessons/7-stacks_and_queues/stone_wall/

題目解釋

在這個例子中,最後要建造的牆的寬度是 N = 9 米,高度在不同的位置上是不同的。牆的左端高度是 H[0] = 8,右端高度是 H[8] = 8。

這道題的目標是計算構建牆所需的最小石塊數,因此我們需要找到一種方法來計算構建牆所需的石塊數。我們可以使用一個堆疊來維護已經堆疊的石塊,然後從左到右遍歷數組,將石塊一層一層地堆疊起來。當當前高度高於前面高度時,應該添加一個新石塊。在堆疊石塊時,我們應該儘可能地重複使用現有的石塊,以減少新石塊的使用量。

你要建造一堵石牆,牆長 N 公尺,而牆的厚度是恆定的,但不同的位置高度不同。牆的高度由一個長度為 N 的正整數數組 H 指定。H[i] 表示牆的左端到右側 i 公尺處的高度。特別地,H[0] 是牆的左端高度,H[N-1] 是牆的右端高度。

石牆應由長方體石塊建造,所有面都是矩形。你的任務是計算構建牆所需的最小石塊數。

比方說,給定一個包含 N = 9 個整數的數組 H:

H[0] = 8 H[1] = 8 H[2] = 5 H[3] = 7 H[4] = 9 H[5] = 8 H[6] = 7 H[7] = 4 H[8] = 8

最終要的形狀會是不規則形,現在主要就是要計算有哪些是可以用更大的長方形去包含(把多個石塊用一個長方形合併起來)

對於給定的例子,以下是從左到右處理數組時的石塊堆疊狀態:

第 1 米處:添加一個高度為 8 的新石塊,堆疊中有 1 個石塊(堆疊中的石塊數為 1)。

第 2 米處:與前面的高度相同,不需要添加新的石塊,堆疊中有 1 個石塊(堆疊中的石塊數為 1)。

第 3 米處:當前高度比前面低,需要添加一個高度為 5 的新石塊,堆疊中有 2 個石塊(堆疊中的石塊數為 2)。

第 4 米處:當前高度比前面高,需要添加一個高度為 2 的新石塊,堆疊中有 3 個石塊(堆疊中的石塊數為 3)。

第 5 米處:當前高度比前面高,需要添加一個高度為 4 的新石塊,堆疊中有 4 個石塊(堆疊中的石塊數為 4)。

第 6 米處:當前高度比前面低,需要添加一個高度為 3 的新石塊,堆疊中有 5 個石塊(堆疊中的石塊數為 5)。

….以此類推

解題紀錄

function solution(H) {
    var stack = []
    var total = 0
    for(var i = 0;i<H.length;i++){
        if(stack.length == 0){
            stack.push(H[i])
            total++
        }else if(i > 0 && H[i-1] > H[i]){
            var height = H[i-1]
            while(stack.length > 0){
                height = height - stack.pop()
                if(height < H[i]) {
                    total++
                    stack.push(H[i]-height)
                    break
                }else if(height == H[i]){
                    break
                }
            }
        }else if(i > 0 && H[i-1] < H[i]){
            stack.push(H[i]-H[i-1])
            total++
        }else if(i ==  0 && H[i-1] < H[i]){
            stack.push(H[i])
            total++
        }
        //console.log(i,stack, total)
    }
    return total
}

https://app.codility.com/demo/results/training5QUJPS-FR6/

Posted on

Stacks and Queues – Fish解題紀錄

題目內容

題目頁面: https://app.codility.com/programmers/lessons/7-stacks_and_queues/fish/

題意分析

又是一個有故事的題目,最討厭了,不要管魚的故事的話,大概就是有一個循序數列會從0~N-1這樣子,例如[1,2,3,4,5],但是不會照著順序排列,而是會打散著的排列,如[4,3,2,1,5],然後有另一個陣列B,會指定該數字是往上還是往下,如[0,1,0,0,0],接著往下的若是遇到往上的,就比大小,刪掉較小的數字。

然後回傳最後剩下的數字的數量

解題紀錄

這是我第一次的解題紀錄

function solution(A, B) {
    var point = 0
    while(point < B.length){
        var currnet_direction = B[point]
        if(currnet_direction == 0){//往上
            while(point > 0 && A[point-1] < A[point]){
                //吃掉目標
                A.splice(point,1)
                B.splice(point,1)
            }
            //換目標
            point++
        }else{//往下
            while(point < B.length-1 && A[point+1] < A[point]){
                //吃掉目標
                A.splice(point+1,1)
                B.splice(point+1,1)
            }
            //換目標
            point++
        }
    }
    return A.length
}

只拿了12分,慘不忍睹,應該有思考邏輯上的錯誤。

仔細想一下這一題,我覺得應該會是2N左右的複雜度,就是往上遍歷一次、往下遍歷一次。往下遍歷時,選擇方向為下的,且之後的數字的方向為上的,把該吃掉的吃掉。接著再從下往上一次,選擇方向為上的,且之前的數字的方向為下的,把該吃掉的吃掉,應該就會試剩下的了。

下面為嘗試的實作程式碼

function solution(A, B) {
    var alive_A = []
    var alive_B = []
    // 往下
    while(A.length > 0){
        var target = A.shift()
        var target_direction = B.shift()
        while(target_direction == 1 && B[0] == 0 && target > A[0]){
            A.shift()
            B.shift()
        }
        alive_A.push(target)
        alive_B.push(target_direction)
    }
    A = alive_A
    B = alive_B
    alive_A = []
    alive_B = []
    //往上
    while(A.length > 0){
        var target = A.pop()
        var target_direction = B.pop()
        while(target_direction == 0 && B[B.length-1] == 1 && target > A[A.length-1]){
            A.pop()
            B.pop()
        }
        alive_A.push(target)
        alive_B.push(target_direction)
    }
    return alive_A.length
}

25%,慘不忍睹+1。

我發現問題是他們往上或往下可能不會只有兩次,而是會不停地變換方向,所以應該會需要把這樣的程式碼抽出來,然後使用迴圈或遞迴的去呼叫。但是比較慘的是,下面的效能測試其實是超時的,若是再透過遞迴或者迴圈,整個效能應該會更差。

觀察之後,因為我是整個陣列去掃,而事實上,他們往上或往下的範圍不會是整個陣列,而會是遇到與自己方向不同的範圍。所以我覺得應該不會是完整的掃過兩次迴圈,而是會有兩層的迴圈,然後根據現在的方向,掃到以自己方向為準最多可吃掉的位置做停止,在構想上應該比較類似我第一次的做法。

function solution(A, B) {
    var point = 0
    var finish = 0
    while(A.length > 0){
        if(point >= A.length ){
            point = A.length-1
        }
        //console.log("main", A, B, point)
        if(point == 0 && B[point] == 0){
            finish ++
            A.shift()
            B.shift()
        }else if(point == A.length-1 && B[A.length-1] == 1){
            finish ++
            A.pop()
            B.pop()
        }else{
            var target_direction = B[point] == 0 ? -1:1
            while(A[point] > A[point+target_direction] && B[point] != B[point+target_direction]){
                A.splice(point+target_direction,1)
                B.splice(point+target_direction,1)
            }
            point = point+target_direction
        }
    }
    return finish
}

邏輯正確了,但是效能不佳…要來優化了!

上面的作法會耗時間是因為下面的原因

  1. 使用了 while 迴圈,導致較長的運行時間。while 迴圈對於每條魚的比較都需要遍歷數組中的某些元素。相比之下,前面的實現使用了 for 迴圈,因此在處理每條魚時,它只需要對數組中的一個元素進行操作。
  2. 這個實現使用了多次數組操作,例如 splice()、shift() 和 pop()。這些操作可能會導致重新分配和複製整個數組,導致更長的運行時間。若只使用了一個堆疊紀錄往上的魚,原本的全部都是往下的,操作次數會少得多。

為了解決這個問題,我們可以使用一個堆疊,它用於記錄下游游動的魚,這些魚還沒有被吃掉。從頭到尾遍歷所有魚,並將所有向上游動的魚推入堆疊。如果遇到向下游動的魚,則將其與堆疊中的魚進行比較。如果堆疊中的魚較小,則將其彈出,並繼續與新的堆疊頂部進行比較,直到它遇到較大的魚,或者堆疊為空。

在這個算法中,堆疊中的魚保證向下游動,因此它們是可以被吃掉的魚。當向上游動的魚遇到堆疊頂部的魚時,它們的大小也被比較。如果它們相等,它們都可以保持存活,因為它們不會相互吃掉。如果向上游動的魚比堆疊頂部的魚大,則堆疊中的魚會被吃掉,否則向上游動的魚會被堆疊頂部的魚吃掉。在此過程中,我們不斷更新堆疊的內容,以便在下一輪比較中使用。

最後,堆疊中剩下的所有魚都可以保持存活,因為它們沒有遇到向下游動的魚,或者在它們前面的向下游動的魚都比它們大。

function solution(A, B) {
    var alive = 0
    var downstream = []
    for (var i = 0; i < A.length; i++) {
        if (B[i] == 1) {
            downstream.push(A[i])
        } else {
            //開始吃掉之前的往下的魚直到自己被吃掉
            while (downstream.length > 0 && downstream[downstream.length - 1] < A[i]) {
                downstream.pop()
            }
            if(downstream.length == 0){
                //過關
                alive++
            }
        }
    }
    return alive + downstream.length
}

https://app.codility.com/demo/results/trainingHMNQVG-XRN/

Posted on

Stacks and Queues – Brackets解題紀錄

題目內容

題目頁面: https://app.codility.com/programmers/lessons/7-stacks_and_queues/brackets/

解題紀錄

感覺很簡單的題目,先隨便寫一個答案

function solution(S) {
    var data = S.split("")
    var pair = {'[':']','{':'}','(':')'}
    var queue = []
    for (var i = 0; i < data.length; i++) {
        var start = data[i].match(/[\{\(\[]/)
        if(start != null){
            queue.push(pair[start.input])
        }else {
            var end = queue.pop()
            if(end != data[i]){
                return 0
            }
        }
    }
    return 1
}

這種簡單的題目真的就是陷阱多,這應該是也要考慮到})]為開頭的狀況,要過濾掉這種CASE

function solution(S) {
    //新增檢查邏輯
    if(S.length % 2 == 1 || S.match(/^[\}\)\]]/) != null){
        return 0
    }
    var data = S.split("")
    var pair = {'[':']','{':'}','(':')'}
    var queue = []
    for (var i = 0; i < data.length; i++) {
        var start = data[i].match(/[\{\(\[]/)
        if(start != null){
            queue.push(pair[start.input])
        }else {
            var end = queue.pop()
            if(end != data[i]){
                return 0
            }
        }
    }
    //一定要全部都有成對
    if(queue.length > 0){
        return 0
    }
    return 1
}

這種考細心度的我最吃虧了= =但是還是過了(https://app.codility.com/c/run/training2C9S74-MHH/)

Posted on

OpenCV魔術棒填充顏色

函數介紹

cv2.floodFill() 函數可以用來對圖像進行泛洪填充。泛洪填充是指將圖像中指定的像素點及其相連的像素點填充成指定的顏色。它通常用於圖像的背景去除、圖像分割等應用中。常用的場景如下:

  1. 圖像分割:可以使用泛洪填充來將圖像分割成不同的區域,例如可以從圖像中自動分離出前景和背景。
  2. 圖像去噪:可以使用泛洪填充來去除圖像中的噪聲,例如在二值化圖像中可以填充噪點附近的像素,使其與周圍的像素保持一致。
  3. 圖像修復:可以使用泛洪填充來修復圖像中的缺陷,例如在圖像中填充缺陷周圍的像素,使其與周圍的像素保持一致。
  4. 圖像標記:可以使用泛洪填充來對圖像進行標記,例如對圖像中的區域進行標記,或者在圖像中添加文字等。

總之,floodFill是一種非常實用的圖像處理技術,可以在很多場合下使用,並且可以通過調整填充的參數來達到不同的效果。

參數介紹

cv2.floodFill() 函數的常用參數如下:

cv2.floodFill(image, mask, seedPoint, newVal[, rect[, loDiff[, upDiff[, flags]]]]) -> retval, image, mask, rect
  • image:要填充的圖像,必須為8位、單通道或三通道影像。如果是三通道影像,則只有當 flags 參數中包含 cv2.FLOODFILL_FIXED_RANGE 時,填充才會基於每個像素的三通道值。
  • mask:用於指定填充區域的填充標記,必須為單通道、8位或32位浮點數影像,大小應比 image 多2個像素。如果填充標記中對應位置的值為0,則該像素將不會被填充。如果該參數為 None,則會自動創建一個和 image 大小相同的標記。
  • seedPoint:種子點的位置,是一個二元數組 (x, y)
  • newVal:填充的新值,可以是一個標量或一個三元數組 (B, G, R)
  • rect:可選的輸出參數,用於返回填充區域的最小矩形。
  • loDiff:可選的最小差值,如果當前像素和種子點之間的差值小於 loDiff,則這個像素將被填充。默認值為0。
  • upDiff:可選的最大差值,如果當前像素和種子點之間的差值大於 upDiff,則這個像素不會被填充。默認值為0。
  • flags:可選的填充標誌,可以是以下幾種取值之一或者它們的組合:
    • cv2.FLOODFILL_FIXED_RANGE:基於每個像素的三通道值來填充,默認基於灰度值。
      • cv2.FLOODFILL_MASK_ONLY:僅修改填充標記,不修改圖像。
        • cv2.FLOODFILL_MULTISCALE:使用多個尺度進行填充。
          • cv2.FLOODFILL_POINT:表示 seedPoint 參數為像素的坐標,而不是像素值。

使用範例

import cv2
import numpy as np

# 讀入圖像,轉為灰度
img = cv2.imread('image.jpg')
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

# 找到種子點
seed_point = (100, 100)

# 設置填充顏色和填充標記
fill_color = (0, 0, 255)
fill_mask = np.zeros((gray.shape[0]+2, gray.shape[1]+2), dtype=np.uint8)

# 泛洪填充
cv2.floodFill(img, fill_mask, seed_point, fill_color)

# 顯示圖像
cv2.imshow('image', img)
cv2.waitKey(0)
cv2.destroyAllWindows()

Posted on

OpenCV裡面形狀擬合的幾種方法

取得輪廓的矩形邊界框

cv2.boundingRect() 函數可以用來計算一個輪廓的矩形邊界框(bounding box),即最小矩形框,這個矩形框可以完全包圍輪廓的所有點。這個函數的返回值是一個元組 (x,y,w,h),其中 (x,y) 是矩形框左上角的座標,wh 是矩形框的寬度和高度。

下面是一個使用 cv2.boundingRect() 函數找到最小矩形框的範例程式碼:

import cv2

# 讀入圖像,轉為灰度
img = cv2.imread('image.jpg')
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

# 二值化,尋找輪廓
_, thresh = cv2.threshold(gray, 0, 255, cv2.THRESH_BINARY + cv2.THRESH_OTSU)
contours, _ = cv2.findContours(thresh, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_NONE)

# 畫出輪廓
cv2.drawContours(img, contours, -1, (0, 255, 0), 2)

# 尋找最小矩形框
x, y, w, h = cv2.boundingRect(contours[0])

# 畫出矩形框
cv2.rectangle(img, (x, y), (x+w, y+h), (0, 0, 255), 2)

# 顯示圖像
cv2.imshow('image', img)
cv2.waitKey(0)
cv2.destroyAllWindows()

最小擬合矩形

cv2.minAreaRect() 可計算最小擬合矩形,這個函數會將給定的輪廓點集擬合成一個矩形,這個矩形具有最小面積,可以包圍住所有的輪廓點。

下面是一個使用 cv2.minAreaRect() 函數找到最小擬合矩形的範例程式碼:

import cv2

# 讀入圖像,轉為灰度
img = cv2.imread('image.jpg')
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

# 二值化,尋找輪廓
_, thresh = cv2.threshold(gray, 0, 255, cv2.THRESH_BINARY + cv2.THRESH_OTSU)
contours, _ = cv2.findContours(thresh, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_NONE)

# 畫出輪廓
cv2.drawContours(img, contours, -1, (0, 255, 0), 2)

# 尋找最小擬合矩形
rect = cv2.minAreaRect(contours[0])
box = cv2.boxPoints(rect)
box = np.int0(box)

# 畫出矩形
cv2.drawContours(img, [box], 0, (0, 0, 255), 2)

# 顯示圖像
cv2.imshow('image', img)
cv2.waitKey(0)
cv2.destroyAllWindows()

取得最小包圍橢圓

若需要找到一個能夠包圍所有點的橢圓,可以使用 cv2.minEnclosingEllipse() 函數。這個函數會將給定的點集包圍在一個最小面積橢圓內。

下面是使用 cv2.minEnclosingEllipse() 函數找到最小包圍橢圓的範例程式碼:

import cv2

# 讀入圖像,轉為灰度
img = cv2.imread('image.jpg')
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

# 二值化,尋找輪廓
_, thresh = cv2.threshold(gray, 0, 255, cv2.THRESH_BINARY + cv2.THRESH_OTSU)
contours, _ = cv2.findContours(thresh, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_NONE)

# 畫出輪廓
cv2.drawContours(img, contours, -1, (0, 255, 0), 2)

# 尋找最小包圍橢圓
ellipse = cv2.fitEllipse(contours[0])
cv2.ellipse(img, ellipse, (0, 0, 255), 2)

# 尋找最小面積包圍橢圓
ellipse = cv2.minEnclosingEllipse(contours[0])
cv2.ellipse(img, (int(ellipse[0][0]), int(ellipse[0][1])),
            (int(ellipse[1][0] / 2), int(ellipse[1][1] / 2)),
            ellipse[2], 0, 360, (255, 0, 0), 2)

# 顯示圖像
cv2.imshow('image', img)
cv2.waitKey(0)
cv2.destroyAllWindows()

最佳擬合橢圓

cv2.fitEllipse() 函數找到的是能夠最好擬合給定點集的橢圓,並不一定能夠包圍住所有點。

這個函數會將輸入的輪廓點集擬合成一個橢圓,返回橢圓的中心座標、軸長、旋轉角度等相關信息。

下面是一個簡單的範例程式碼,展示如何使用 cv2.fitEllipse() 找到最小包圍橢圓:

import cv2

# 讀入圖像,轉為灰度
img = cv2.imread('image.jpg')
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

# 二值化,尋找輪廓
_, thresh = cv2.threshold(gray, 0, 255, cv2.THRESH_BINARY + cv2.THRESH_OTSU)
contours, _ = cv2.findContours(thresh, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_NONE)

# 畫出輪廓
cv2.drawContours(img, contours, -1, (0, 255, 0), 2)

# 尋找最小包圍橢圓
ellipse = cv2.fitEllipse(contours[0])
cv2.ellipse(img, ellipse, (0, 0, 255), 2)

# 顯示圖像
cv2.imshow('image', img)
cv2.waitKey(0)
cv2.destroyAllWindows()

最小包圍圓

要找到一個能夠最小外接圓包圍給定的點集,可以使用 cv2.minEnclosingCircle() 函數。這個函數會將給定的點集包圍在一個最小面積圓內。

下面是一個使用 cv2.minEnclosingCircle() 函數找到最小外接圓的範例程式碼:

import cv2
import numpy as np

# 讀入圖像,轉為灰度
img = cv2.imread('image.jpg')
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

# 二值化,尋找輪廓
_, thresh = cv2.threshold(gray, 0, 255, cv2.THRESH_BINARY + cv2.THRESH_OTSU)
contours, _ = cv2.findContours(thresh, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_NONE)

# 畫出輪廓
cv2.drawContours(img, contours, -1, (0, 255, 0), 2)

# 尋找最小外接圓
(x, y), radius = cv2.minEnclosingCircle(contours[0])
center = (int(x), int(y))
radius = int(radius)

# 畫出圓形
cv2.circle(img, center, radius, (0, 0, 255), 2)

# 顯示圖像
cv2.imshow('image', img)
cv2.waitKey(0)
cv2.destroyAllWindows()

最適擬合直線

要找到一個能夠最好擬合給定點集的直線,可以使用 cv2.fitLine() 函數。這個函數會將給定的點集擬合成一條直線,返回的是一個向量 (vx,vy,x0,y0),其中 (vx,vy) 是直線的方向向量,(x0,y0) 是直線上的一點。

下面是一個使用 cv2.fitLine() 函數找到最適擬和直線的範例程式碼:

import cv2
import numpy as np

# 讀入圖像,轉為灰度
img = cv2.imread('image.jpg')
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

# 二值化,尋找輪廓
_, thresh = cv2.threshold(gray, 0, 255, cv2.THRESH_BINARY + cv2.THRESH_OTSU)
contours, _ = cv2.findContours(thresh, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_NONE)

# 畫出輪廓
cv2.drawContours(img, contours, -1, (0, 255, 0), 2)

# 尋找最適擬和直線
rows, cols = img.shape[:2]
[vx, vy, x, y] = cv2.fitLine(contours[0], cv2.DIST_L2, 0, 0.01, 0.01)
lefty = int((-x*vy/vx) + y)
righty = int(((cols-x)*vy/vx)+y)

# 畫出直線
cv2.line(img, (cols-1, righty), (0, lefty), (0, 0, 255), 2)

# 顯示圖像
cv2.imshow('image', img)
cv2.waitKey(0)
cv2.destroyAllWindows()