Posted on

為影片產生會議紀錄及重點擷取

將影片轉為MP3

先照這篇的方式安裝FFMPEG,接著就可以使用ffmpeg將影片轉成mp3檔案

ffmpeg -i input.mp4 -vn -acodec libmp3lame output.mp3

在上述命令中,input.mp4是輸入的MP4文件路徑,output.mp3是輸出的MP3文件路徑。

從語音檔案使用AI提取文字

這個功能在WORD就有了,若是沒有WORD,GOOGLE文件也有相似的聽寫功能,以下為我使用Office內建聽寫功能的示範

先使用轉錄功能

接著選擇輸入語言為台灣國語,並上傳剛剛擷取出來的mp3檔案

選擇完檔案會開始上傳MP3並且擷取音檔內的文字,這也是為什麼一開始我會希望將mp4轉成mp3,因為含影像的檔案較大,純音檔較小,上傳較小的檔案這邊所花費的時間會少一點

當節錄文字完成後,選擇將文字加到檔案內,就會出現如下的語音謄錄文字

讓文字更易懂

使用工具: ChatGPT

一直到這邊所產生的文字,都很不容易讓人理解,因為所擷取出的文字很容易會有錯別字,例如: 【視障小孩】可能會被聽寫成【師丈小孩】,根本意義完全不同,讓人難以理解。

但是ChatGPT對於理解這樣的錯別字,比對上下文去猜出正確辭意的能力頗強,所以可以使用ChatGPT請他幫忙整理內容

例如上面的文字GTP所整理出的內容如下

接著再重複使用上面產生的內容,請GPT產生摘要、標題,我們只需要作內容審核、確認、修正即可,可以大幅節省人力唷!

另外,對CHATGPT所下的指令也會影響到產出,例如上面我使用【順成文章】的指令,所以最後面CHATGPT就自己唬爛了一些不相關的內容(甚麼不僅僅是個人問題之類的老師根本沒有講)。這時候就可以改使用【順過讓文字更好讀】這樣的指令,就比較不會產生不相關的內容。

建議可以多嘗試幾種不同的指令,直接針對他所整理過的不滿意的方向請她重新整理,直到CHATGPT給出較滿意的產出後,再自行做驗證/整理

Posted on

使用OBS做會議錄影

使用OBS把線上會議錄起來

若是線上會議,推薦使用OBS可以很方便的對所有類型的會議做錄影。

這邊是OBS的下載位置: https://obsproject.com/

OBS可以擷取視窗螢幕,只要是可以在桌面上執行的軟體,都可以從【+】 ->【 Window Capture】去獲取該程式的畫面並放置於OBS畫面上。使用這個方式錄影的優點是,我們可以在錄影的時候同時使用其他的軟體,並且不會被錄到除了你所選擇的應用程式以外的電腦上的操作,OBS只會持續的錄該程式的畫面。

例如下面這樣子就只會錄到所選擇的Chrome的視窗,我們在電腦上回Line訊息、開別的Chrome瀏覽網頁,都不會被錄進去

這樣的方式在Window上直接就會可以錄到畫面+聲音,但是若你的電腦是Mac,則需要另外做額外的設定,才能夠讓OBS取得電腦內部的聲音。這邊為教學文章: https://www.casper.tw/life/2021/06/13/mac-reacord-by-soundflower/

開始錄影

在上面設定完之後,按下右下的【開始錄製】並在會議結束時按下【結束錄製】,就可以在本機>影片找到錄好的影片,檔名會是錄影的時間

安裝FFMPEG

接著則要做影片的剪裁+合成,以下是一些簡單的影片操作指令

首先,下載別人已經Build好的ffmpeg: https://www.gyan.dev/ffmpeg/builds/packages/ffmpeg-5.1.2-full_build.7z

接著,把ffmpeg.exe丟到系統的路徑裡面,如C:\Windows\System32,或者將ffmpeg的路徑加到環境變數的Path裡面,讓系統能夠找的到ffmpeg的位置。

驗證方式: 開啟命令提示字元,輸入ffmpeg,如果能出現以下畫面,代表設定成功

做一些簡單的影片操作

擷取影片片段

ffmpeg -i input.mp4 -ss 00:12 -to 00:15:30 -c:v copy -c:a copy output.mp4

在上述命令中,input.mp4是輸入的視頻文件路徑,output.mp4是輸出的視頻文件路徑。 00:12表示起始時間,00:15:30表示結束時間。

刪除影片片段

ffmpeg -i input.mp4 -filter_complex "[0:v]trim=0:4,setpts=PTS-STARTPTS[v1]; [0:v]trim=8,setpts=PTS-STARTPTS[v2]; [v1][v2]concat=n=2:v=1:a=0" -c:v libx264 -preset veryfast -crf 18 output.mp4

在上述命令中,input.mp4是輸入的視頻文件路徑,output.mp4是輸出的視頻文件路徑。 0:4表示要刪除的起始時間範圍,8表示要刪除的結束時間。

合併多個影片檔案

  • 創建一個文本文件,例如input.txt,其中包含要合併的視頻文件的列表。每行包含一個視頻文件的路徑,例如:
file 'video1.mp4'
file 'video2.mp4'
file 'video3.mp4'
  • 將文件內所寫的影片使用ffmpeg合併為一個影片
ffmpeg -f concat -safe 0 -i input.txt -c copy output.mp4

為影片加上浮水印

ffmpeg -i input.mp4 -i watermark.png -filter_complex "overlay=W-w-10:H-h-10" -c:a copy output.mp4

在上述命令中,input.mp4是輸入的視頻文件路徑,watermark.png是水印圖片文件的路徑,output.mp4是輸出的帶有水印的視頻文件路徑。

-filter_complex “overlay=W-w-10:H-h-10″:使用filter_complex選項應用複雜的過濾器。 overlay過濾器用於將水印圖像疊加在視頻上。 W-w-10表示水印圖像的水平位置,H-h-10表示水印圖像的垂直位置。在這個示例中,水印位於視頻的右下角,並與邊緣保持10像素的間距。

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/)