對輪廓的點做旋轉計算

使用角度的正弦和餘弦函數,將長方形的寬度和高度乘以正確的係數,以獲得旋轉後的角點座標。

下面為一個將一個長方形的四個點作45度旋轉的簡單範例:

import cv2
import numpy as np
import math

base_x = 100
base_y = 100
width = 100
height = 50
angle = 45

# 計算長方形中心點座標
center_x = base_x + (width // 2)
center_y = base_y + (height // 2)

# 將角度轉換為弧度
angle_rad = math.radians(angle)

# 計算長方形四個角的相對座標
cos_val = math.cos(angle_rad)
sin_val = math.sin(angle_rad)
x = width / 2
y = height / 2

# 計算四個角點座標
point1 = (int(center_x - x * cos_val + y * sin_val), int(center_y - x * sin_val - y * cos_val))
point2 = (int(center_x + x * cos_val + y * sin_val), int(center_y + x * sin_val - y * cos_val))
point3 = (int(center_x + x * cos_val - y * sin_val), int(center_y + x * sin_val + y * cos_val))
point4 = (int(center_x - x * cos_val - y * sin_val), int(center_y - x * sin_val + y * cos_val))

print("Point 1:", point1)
print("Point 2:", point2)
print("Point 3:", point3)
print("Point 4:", point4)

# 創建空白影像
image = np.zeros((500, 500, 3), dtype=np.uint8)

# 轉換座標為Numpy陣列
pts = np.array([point1, point2, point3, point4], dtype=np.int32)

# 繪製多邊形
cv2.polylines(image, [pts], True, (0, 255, 0), thickness=2)

# 顯示結果
cv2.imshow('Rectangle', image)
cv2.waitKey(0)
cv2.destroyAllWindows()

顯示結果如下

點到多邊形的最短距離

cv2.pointPolygonTest是OpenCV中的一個函數,用於計算點到多邊形的最短距離或點是否在多邊形內。

函數的語法如下:

_, intersection = cv2.pointPolygonTest(rect3, tuple(line1_midpoint), measureDist=False)
  • contour:多邊形的輪廓,可以是Numpy陣列或OpenCV的輪廓物件。
  • point:要計算距離的點,通常是一個(x, y)座標元組。
  • measureDist:指定是否計算點到多邊形的最短距離。如果為True,則返回距離值;如果為False,則返回一個整數值表示點的位置關係:正數表示點在多邊形內部、負數表示點在多邊形外部、0表示點在多邊形邊界上。

相關函數請參考: cv2.distanceTransform

另外要畫出多邊形可使用cv2.polylines,如以下範例

import cv2
import numpy as np

# 定義長方形的四個角點
rect1 = np.array([[100, 100], [300, 100], [300, 200], [100, 200]])

# 創建空白影像
image = np.zeros((500, 500, 3), dtype=np.uint8)

# 繪製長方形
cv2.polylines(image, [rect1], True, (0, 255, 0), thickness=2)

# 顯示結果
cv2.imshow('Image', image)
cv2.waitKey(0)
cv2.destroyAllWindows()

使用OpenCV將圖形轉正

旋轉圖片的方法

若是單純只是要把圖片做角度的旋轉,可以直接使用OpenCV 的 cv2.rotate() 函数。可按指定的方向旋轉圖像。如下:

import cv2

# 讀取圖像
image = cv2.imread('your_image.jpg')

# 將圖像旋轉90度
rotated_image = cv2.rotate(image, cv2.ROTATE_90_CLOCKWISE)

# 顯示旋轉後的圖像
cv2.imshow('Rotated Image', rotated_image)
cv2.waitKey(0)
cv2.destroyAllWindows()

翻轉圖片的方法

cv2.flip() 是 OpenCV 中用於圖像翻轉的函數。它可以在水平、垂直或兩個方向上翻轉圖像。該函數接受三個參數:輸入圖像、翻轉的模式和輸出圖像的可選參數。

dst = cv2.flip(src, flipCode[, dst])

flipCode:翻轉的模式。可以是以下值之一:

  • 0:水平翻轉(沿著垂直軸翻轉)。
  • 1:垂直翻轉(沿著水平軸翻轉)。
  • -1:同時在水平和垂直方向上翻轉。

cv2.flip() 函數和 cv2.rotate() 函數都可以用於實現圖像的旋轉和翻轉,但它們的效果是不同的。

cv2.flip() 函數可以在水平和垂直方向上翻轉圖像,包括水平翻轉、垂直翻轉和同時在水平和垂直方向上翻轉。例如,使用 cv2.flip(image, -1) 可以同時在水平和垂直方向上翻轉圖像。

cv2.rotate() 函數用於對圖像進行旋轉。通過指定旋轉的角度和旋轉中心點,可以實現不同角度的旋轉。例如,使用 cv2.rotate(image, cv2.ROTATE_180_CLOCKWISE) 可以將圖像順時針旋轉180度。

雖然cv2.flip(image, -1)cv2.rotate(image, cv2.ROTATE_180_CLOCKWISE) 可以實現類似的效果,將圖像翻轉或旋轉180度,但它們的內部操作是不同的。 cv2.flip() 是基於軸對稱翻轉實現的,而 cv2.rotate() 是基於旋轉變換實現的。

針對形狀做角度校正

在許多圖像偵測的狀況,我們仍然會需要針對物件去做旋轉,首先我們一定是先用cv2.findContours取得輪廓,然後取得該物件輪廓的角度。這邊很重要的,就是要取得物件輪廓的角度,要取得角度,首先就要先去做輪廓擬合(請參考: OpenCV裡面形狀擬合的幾種方法)。

這邊我大推使用橢圓去做輪廓擬合並且取得軸心的角度,為什麼呢? 雖然cv2.minAreaRect() 可計算最小擬合矩形,但是這個矩形會非常容易受到輪廓的些微影響而改變擬合的方式,例如以下圖為例,就有可能有黑框、紅色框兩種的最小擬合矩形(會視當下輪廓取得的細微變化而改變)。也因此所取得的角度會非常多變,後續的辨識也會更困難

但是使用最小擬合橢圓,對於像上面這種左右、上下為對稱,但是長寬不同的形狀來說,非常適合使用最小擬合橢圓cv2.fitEllipse(),使用範例如下

import cv2

image = cv2.imread('./333_2023-06-08_19-57-30.jpg')
canny = cv2.Canny(image , 50, 250)
cnts, hier = cv2.findContours(canny , cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)
# 執行最小橢圓擬合
ellipse = cv2.fitEllipse(cnts[0])
(center, axes, angle) = ellipse
cv2.ellipse(image, ellipse, (0, 255, 0), 2)
# 顯示結果
cv2.imshow('image', image)
cv2.waitKey(0)
cv2.destroyAllWindows()

上面可以看到(center, axes, angle) = ellipse這邊的angle就是所偵測到的輪廓的角度,接著可以用cv2.warpAffine方法將圖像轉正

def rotatedDice(image, cnt):
    # 取得最小擬合橢圓並對圖像做翻轉
    ellipse = cv2.fitEllipse(cnt)
    (center, axes, angle) = ellipse
    angle = angle + 90
    rotation_matrix = cv2.getRotationMatrix2D(tuple(center), angle, 1)
    image = cv2.warpAffine(image, rotation_matrix,(image.shape[1], image.shape[0]))
    # 計算裁切位置
    mark = np.zeros_like(image)
    cv2.drawContours(mark, [cnt], 0, (255, 255, 255), -1)
    mark = cv2.warpAffine(mark, rotation_matrix,(mark.shape[1], mark.shape[0]))
    mark = cv2.cvtColor(mark, cv2.COLOR_RGB2GRAY)
    cnts, hier = cv2.findContours(mark, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)
    x, y, w, h = cv2.boundingRect(cnts[0])
    matting_result = image[y:y+h,x:x+w,:]
    return matting_result

從上面,我們使用cv2.warpAffine來做圖片角度的校正,warpAffine裡面有要輸入一個旋轉的矩陣的參數,在上面的範例,我們使用cv2.getRotationMatrix2D,這個參數是單純做形狀旋轉,但是在真實的世界當中,大部分3D的角度轉換也會帶有著深度的轉換,如下圖

這時候就會需要使用cv2.getAffineTransform來取得這個旋轉矩陣

import cv2
import numpy as np

# 定義三個點的坐標
point1 = (106, 92)
point2 = (28, 91)
point3 = (154, 33)

# 定義旋轉角度
rotation_angle = -45

# 創建一個空白圖像
image = np.zeros((500, 500), dtype=np.uint8)

# 在圖像上繪製三角形
cv2.drawContours(image, [np.array([point1, point2, point3])], 0, (255), thickness=2)

# 計算旋轉中心
center = np.mean([point1, point2, point3], axis=0)

# 構建旋轉矩陣
rotation_matrix = cv2.getRotationMatrix2D(tuple(center), rotation_angle, 1)

# 對整個圖像進行旋轉
rotated_image = cv2.warpAffine(image, rotation_matrix, (image.shape[1], image.shape[0]))

# 顯示旋轉後的圖像
cv2.imshow("Rotated Image", rotated_image)
cv2.waitKey(0)
cv2.destroyAllWindows()

限制ffmpeg初始連接的時間

ffmpeg中的analyzeduration和probesize

在FFmpeg中,-analyzeduration和-probesize是用於設置媒體分析的參數。

-analyzeduration參數用於指定分析媒體文件的持續時間。當你在FFmpeg中打開一個媒體文件時,它需要一些時間來分析文件的內容,以確定其格式、編解碼器和其他相關的信息。這個參數設置了分析的時間長度。較長的-analyzeduration值可能會導致更準確的分析結果,但同時也會增加打開文件的時間。預設值為5,000,000微秒(5秒)。

-probesize參數用於指定分析媒體文件時讀取的數據大小。當FFmpeg分析媒體文件時,它會從文件中讀取一些數據並進行分析。這個參數設置了從媒體文件中讀取的數據大小。較大的-probesize值可能會導致更準確的分析結果,但同時也會增加分析的時間和記憶體使用量。預設值為50,000字節。

前置metadata

播放器在網絡點播場景下去請求MP4 視頻數據,需要先獲取到文件的metadata,解析出該文件的編碼、幀率等信息後才能開始邊下邊播。如果MP4 的metadata 數據塊被編碼在文件尾部,這種情況會導致播放器只有下載完整個文件後才能成功解析並播放這個視頻。對於這種視頻,我們最好能夠在服務端將其重新編碼,將metadata 數據塊轉移到靠近文件頭部的位置,保證播放器在線請求時能較快播放。比如FFmpeg 的下列命令就可以支持這個操作:

ffmpeg -i bad.mp4 -movflags faststart good.mp4

控制讀取的數據量大小

在外部可以通過設置 probesize 和 analyzeduration 兩個參數來控制該函數讀取的數據量大小和分析時長為比較小的值來降低 avformat_find_stream_info 的耗時,從而優化播放器首屏秒開。但是,需要注意的是這兩個參數設置過小時,可能會造成預讀數據不足,無法解析出碼流信息,從而導致播放失敗、無音頻或無視頻的情況。所以,在服務端對視頻格式進行標準化轉碼,從而確定視頻格式,進而再去推算 avformat_find_stream_info 分析碼流信息所兼容的最小的 probesize 和analyzeduration,就能在保證播放成功率的情況下最大限度地區優化首屏秒開。

probesize 和 analyzeduration太短的可能影響


如果將-probesize和-analyzeduration設置得太短,可能會導致以下問題:

  • 不準確的媒體分析:probesize和analyzeduration參數用於指定媒體分析的數據大小和時間長度。如果這兩個值設置得太短,FFmpeg可能無法讀取足夠的數據或分析足夠長的時間,從而導致分析結果的不準確性。這可能會影響到媒體文件的正確解碼、格式識別和相關信息的獲取。
  • 遺漏關鍵信息:媒體文件中的關鍵信息通常在文件的早期部分或特定位置。如果probesize和analyzeduration設置得太短,FFmpeg可能無法讀取到這些關鍵信息,進而影響解碼、播放或處理過程的正確性和完整性。
  • 性能問題:probesize和analyzeduration參數的值也會影響處理媒體文件所需的時間和資源。如果值設置得太短,FFmpeg可能需要更頻繁地從媒體文件中讀取數據或進行分析,增加了I/O操作和CPU負載,進而導致性能下降。

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 的公鑰伺服器中下載指定的公鑰,並且更新系統的軟體庫。完成後,您可以再次嘗試安裝所需的軟體,看看問題是否已經解決了。

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,則可以刪除這個符號連結即可。

在K8S內ksoftirqd耗費大量CPU

問題描述

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

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

形成原因

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

IRQ是甚麼

IRQ 是中斷請求的簡寫,是一種處理設備 I/O 操作的機制。當設備有 I/O 操作時,它會觸發一個中斷請求,通知操作系統或應用程序需要處理這個 I/O 操作。在網絡通信中,每個數據包都會觸發一次 IRQ 請求,因此當流量高峰期間,大量的 IRQ 請求可能會導致節點的 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 的負載。為了解決這個問題,可以考慮使用負載均衡器(ingress)等技術,將流量轉發到多個節點上,以降低單個節點的負載。

解決方法

由於我們所架設的伺服器為串流伺服器,原本在一般的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

最大子序列和問題

概念解釋

最大子序列和問題(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/

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
}

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/