Author: Claire Chang

Posted on by

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 by

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

取得輪廓的矩形邊界框

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

下面是一個使用 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()
Posted on by

Sorting – NumberOfDiscIntersections解題紀錄

題目內容

題目頁面:  https://app.codility.com/programmers/lessons/6-sorting/number_of_disc_intersections/

解題思考

這個是在算N個圓是否有交集，例如以題目來說，A[0] = 1 A[1] = 5 A[2] = 2 A[3] = 1 A[4] = 4 A[5] = 0單純以範圍來看，會是這樣的範圍陣列[ -1, 1 ], [ -4, 6 ], [ 0, 4 ], [ 2, 4 ], [ 0, 8 ], [ 5, 5 ]，要尋找在這些範圍內取出兩者是有交集的

先用C6取2算出兩兩相配的最多次數，然後找出沒有交集的圈圈，就會是(0,3),(0,5),(2,5),(3,5)沒有交集，我們使用C6取2減掉沒有交集的4個，就會是有交集的數字11

解題紀錄

先用暴力法把沒有交集的找出來

function solution(A) {
    var count = A.length*(A.length-1)/2;
    for(var i=0;i<A.length;i++){
        for(var j = i+1;j<A.length;j++){
            if(i+A[i] < j-A[j]){
                count--;
            }
        }
    }
    return count
}

好，至少答案是正確的，先來想想優化方式

嘗試換個寫法，儲存所有結束的點(照順序排序)，然後後面的用開始的點去比較之前的結束的點，看看會不會比前面結束的點更大，若更大代表沒有交集，這樣子做會可以在計算時透過排序去節省時間。

function solution(A) {
    var range = []
    var no_intersect = 0
    for(var i=0;i<A.length;i++){
        var count = binarySearch(range, i-A[i])
        no_intersect += count
        //console.log(range,count, i-A[i])
        range.splice(binarySearch(range, i+A[i]), 0, i+A[i])
    }
    return A.length*(A.length-1)/2 - no_intersect
}
//在一個已排序的陣列裡，取得newValue應插入的index
function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return left
}

應該有邊界性的邏輯錯誤QQ但效能是有一個有通過了，來找找邊界性錯誤的位置…

哈..發現問題了

The function should return −1 if the number of intersecting pairs exceeds 10,000,000

所以就是用第一次的寫法，然後若數字超過直接就返回錯誤。但是因為這樣要知道現在的次數，所以要改一下加總的方式

function solution(A) {
    var count = 0//A.length*(A.length-1)/2;
    for(var i = A.length-1;i >=0;i--){
        for(var j = i-1;j>=0;j--){
            if(i-A[i]<=j+A[j]){
        //console.log(i,j)
                count++
                if(count > 10000000) return -1
            }
        }
    }
    return count
}

原來即便是跑到10000000就return也是超過標準…

經過思考之後，我覺得還是去尋找我第二個做法邏輯錯誤的部分好了…

我覺得應該是我在實作二分搜尋法上面的問題，因為對這個題目而言，應該要尋找”第一個”<=目標值的index，但是因為現在使用的二分搜尋法的邏輯，很可能所選到的不會是第一個，這樣就會造成些微的錯誤，所以會需要在遇到第一個arr[mid] === target的時候，往前搜尋確認現在的mid是第一個大於等於目標值的index

function solution(A) {
    var range = []
    var total = A.length*(A.length-1)/2
    var no_intersect = 0
    for(var i=0;i<A.length;i++){
        var count = binarySearch(range, i-A[i])
        no_intersect += count
        //console.log(range,count, i-A[i])
        range.splice(binarySearch(range, i+A[i]), 0, i+A[i])
        
    }
    var intersecting = total - no_intersect
    return intersecting > 10000000 ? -1: intersecting
}
//在一個已排序的陣列裡，取得newValue應插入的index
function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) {
            //在這邊確認拿到的是"第一個"大於等於目標值的數字
            while(mid > 0 && arr[mid-1] === target){
                mid--
            }
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return left
}

100%過關!!(https://app.codility.com/demo/results/training7T4RZ2-QP8/)

Posted on by

Sorting – Triangle解題紀錄

題目內容

題目頁面: https://app.codility.com/programmers/lessons/6-sorting/triangle/

題意解析


除了任兩邊的長度必須大於第三邊之外，組成三角形的線段還有一些其他的限制：

  1. 三條邊的長度必須為正數。
  2. 任兩邊的長度之差必須小於第三邊的長度，也就是說，最長的邊的長度必須小於其他兩邊的長度之和。
  3. 任何一邊的長度都不能超過其他兩邊長度之和的兩倍。

如果以上任何一個條件不滿足，則無法組成三角形。

0 ≤ P < Q < R < N

解題過程

先寫一個一定會被打槍的暴力解，複雜度為O(N^3)

function solution(A) {
    for (let i = 0; i < A.length; i++) {
        if (A[i] > 0) {
            for (let j = i + 1; j < A.length; j++) {
                if (A[j] > 0) {
                    for (let k = j + 1; k < A.length; k++) {
                        if (A[k] > 0) {
                            if (A[i] + A[j] > A[k] &&
                                A[j] + A[k] > A[i] &&
                                A[k] + A[i] > A[j]) {
                                return 1;
                            }
                        }
                    }
                }
            }
        }
        return 0;
    }
}

結果0%，，沒一個過的了，不是答案錯誤就是runtime error

直覺猜測，這一定和三角形的定義有關，查了一下谷歌大神，找到這段

當一個陣列已經排好序時，如果能夠構成三角形，那麼任意三個相鄰的元素都能構成三角形。

假設排序後的陣列為arr，元素個數為n。我們使用一個for循環遍歷arr中的元素arr[i]。由於arr已經排好序，因此arr[i]一定是arr[i]、arr[i+1]和arr[i+2]中最小的一個，arr[i+1]是中間的一個，arr[i+2]是最大的一個。如果這三個元素能夠構成三角形，那麼其他任意三個相鄰的元素也能構成三角形。

如果arr[i]+arr[i+1]>arr[i+2]，那麼一定存在一組三個相鄰的元素可以構成三角形。因此，在檢查完arr[i]、arr[i+1]和arr[i+2]之後，我們可以繼續檢查arr[i+1]、arr[i+2]和arr[i+3]，arr[i+2]、arr[i+3]和arr[i+4]，以此類推，直到遍歷完整個陣列。

總之，當一個陣列已經排好序時，只需要檢查相鄰的三個元素是否能夠構成三角形，即可判斷是否存在三個元素能夠構成三角形。這比遍歷所有可能的三元組要更高效。

所以就是要知道這個定理就可以了

function solution(A) {
    A.sort((a, b) => a - b);

    for (let i = 0; i < A.length - 2; i++) {
        if (A[i] + A[i + 1] > A[i + 2]) {
            return 1;
        }
    }

    return 0;
}
Posted on by

Sorting – MaxProductOfThree解題紀錄

題目內容

題目頁面: https://app.codility.com/programmers/lessons/6-sorting/max_product_of_three/

題目理解

總之就是取得陣列A裡面，由N個數字所挑選隨意三個相乘的最大值，這些數字可能是-1000~1000，然後陣列長度最少3個最多10萬個

解題紀錄

首先我想到，形成最大值的三個值，當該值為正數時，只有可能由3個正數或2個負數*1個正數組成。當該值為負數時，則有可能由3個負數或2個正數*1個負數組成。所以，現在所需的就是先遍歷整個陣列，然後確認正數和負數的數量。當有可能有正數乘積時，則以正數乘積為優先，否則則需要考慮負數的乘積。

因此，我決定先遍歷A陣列，找尋最大的前三個正數數字以及最小的前三個負數數字(當正值時使用)，以及最小的前三個正數數字以及最大的負數數字(當負值時使用)，然後統計正值的數量和負值的數量，以決定最後輸出的會是正值還是負值

function solution(A) {
    // Implement your solution here
    var max_positive = new triplet(true)
    var min_positive = new triplet(false)
    var positive_count = 0
    var max_negative = new triplet(true)
    var min_negative = new triplet(false)
    var negative_count = 0
    var has_zero = false
    for (var i = 0; i < A.length; i++) {
        if (A[i] == 0) has_zero = true
        else if (A[i] > 0) {
            max_positive.compareMax(A[i])
            min_positive.compareMin(A[i])
            positive_count++
        } else {
            max_negative.compareMax(A[i])
            min_negative.compareMin(A[i])
            negative_count++
        }
    }
    if (positive_count >= 3 || (negative_count >= 2 && positive_count > 0)) {
        var pos_3 = 0
        var pos_2_neg_1 = 0
        if (positive_count >= 3) {
            pos_3 = max_positive.max * max_positive.middle * max_positive.min
        }
        if (negative_count >= 2 && positive_count > 0) {
            pos_2_neg_1 = min_negative.middle * min_negative.min * max_positive.max
        }
        return Math.max(pos_3, pos_2_neg_1)
    } else if (has_zero) {
        return 0
    } else {
        //確認該使用2個正數*1個負數還是3個負數
        var max_2_pos_1_neg = -Infinity
        var max_3_neg = -Infinity
        if (negative_count > 0 && positive_count >= 2) {
            max_2_pos_1_neg = min_positive.min * min_positive.middle * max_negative.max
        }
        if (negative_count >= 3) {
            max_3_neg = max_negative.max * max_negative.middle * max_negative.min
        }
        return Math.max(max_2_pos_1_neg, max_3_neg)
    }
}
class triplet {
    constructor(isMaxCompare) {
        var data = isMaxCompare ? -Infinity : Infinity
        this.max = data;
        this.middle = data;
        this.min = data;
    }
    getValue() {
        console.log(this.max, this.middle, this.min)
    }
    compareMax(value) {
        if (value > this.max) {
            this.min = this.middle
            this.middle = this.max
            this.max = value
        } else if (value > this.middle) {
            this.min = this.middle
            this.middle = value
        } else if (value > this.min) {
            this.min = value
        }
    }
    compareMin(value) {
        if (value < this.min) {
            this.max = this.middle
            this.middle = this.min
            this.min = value
        } else if (value < this.middle) {
            this.max = this.middle
            this.middle = value
        } else if (value < this.max) {
            this.max = value
        }
    }
}

100%!!!一次成功~感動(https://app.codility.com/demo/results/trainingR9PVFF-P78/)

Posted on by

Sorting – Distinct解題紀錄

題目內容

題目頁面: https://app.codility.com/programmers/lessons/6-sorting/distinct/

題目解析

這一題之前其實出現過，但是因為這一題A的範圍是負一百萬到正一百萬，實在太大了，沒辦法直接用查表的方式儲存，所以會需要使用到二分搜尋法去建立這個不重複陣列

我的解題記錄

第一次的解法

function solution(A) {
    var M = []
    for (var i = 0; i < A.length; i++) {
        var idx = binarySearch(M, A[i]);
        if(M[idx] != A[i]){
            M.splice(idx, 0, A[i])
        }
    }
    //console.log(M)
    return M.length
}

//在一個已排序的陣列裡，取得newValue應插入的index
function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return left
}

對於這結果，我真是滿腹委屈，明明二分搜尋法就是O(logN)阿!到底是誰把他變成O(N^2)的…我覺得應該是原本遍歷陣列為N,又乘上搜尋的LogN，因此變得很耗時

經過了一陣思考後，我覺得我根本被這一個章節的篇名所騙了，我幹嘛要建立有序陣列呢?用物件不就好了嗎?甚麼二分搜尋法根本自討苦吃!!

function solution(A) {
    var M = {}
    for (var i = 0; i < A.length; i++) {
        M[A[i]] = true;
    }
    //console.log(Object.keys(M))
    return Object.keys(M).length
}

結果根本沒在鳥甚麼Sorting不Sorting的反而過關，100%PASS!(https://app.codility.com/demo/results/trainingTR8QQS-TDU/)

Posted on by

Prefix Sums – MinAvgTwoSlice解題紀錄

題目內容

題目頁面: https://app.codility.com/programmers/lessons/5-prefix_sums/min_avg_two_slice/

題目理解

尋找 (P, Q)，其中0 ≤ P < Q < N，為陣列A的切片，N介於2~100000之間，並尋找最小平均切片的起始位置，要注意的是，陣列的內容為-10000~10000

感覺起來就是要先儲存從0~N的加總，然後再來尋找最小平均切片，但是思考起來這樣子複雜度應該也會有O(N**2)，但是先這樣試看看

解題思路

第一次的嘗試

function solution(A) {
    var sum = []
    var current_sum = 0
    sum.push(0)
    for(var i=0;i<A.length;i++){
        current_sum += A[i];
        sum.push(current_sum)
    }

    var min = Infinity;
    var min_start = -1
    for(var i = 0;i<A.length;i++){
        for(var j = i+1;j<A.length;j++){
            var avg = (sum[j+1]-sum[i])/(j+1-i);
            if(min > avg) {
                min = avg;
                min_start = i
            }
        }
    }
    return min_start
}

我就知道….60%，timeout errors。複雜度還是太高，現在的解法是很直接的思考平均算法，先嘗試思考看看”平均”有沒有其他可能的算法

本來想嘗試必定包含最小值得所有可能，但是發現有邏輯錯誤，因為一個最小值不代表平均起來就一定最小，因為若該最小值的左右兩邊比較大，旁邊有兩個比較小的值，平均值會比包含最小值的還要小。所以即便是最小的值也不一定在最小平均之內。

//這會有錯誤的結果
function solution(A) {
    var sum = []
    var current_sum = 0
    sum.push(0)
    var mustIncludeIndex = -1
    var mustIncludeValue = Infinity
    for(var i=0;i<A.length;i++){
        current_sum += A[i];
        sum.push(current_sum)
        if(mustIncludeValue > A[i]) {
            mustIncludeValue = A[i];
            mustIncludeIndex = i
        }
    }
    var min = Infinity;
    var min_start = -1
    for(var i = 0;i<mustIncludeIndex;i++){
        for(var j = i+1;j<A.length;j++){
            var avg = (sum[j+1]-sum[i])/(j+1-i);
            if(min > avg) {
                min = avg;
                min_start = i
            }
        }
    }
    return min_start
}

萬般無助之下，詢問了ChatGPT，沒想到他都比我聰明(哭)，好吧這就來改寫!!

以下為改寫後的程式碼

function solution(A) {
    var sum = []
    var current_sum = 0
    sum.push(0)
    for(var i=0;i<A.length;i++){
        current_sum += A[i];
        sum.push(current_sum)
    }

    var min = Infinity;
    var min_start = -1
    for(var i = 0;i<A.length;i++){
        var max_possible = Math.min(A.length, i+3)
        for(var j = i+1;j<max_possible;j++){
            var avg = (sum[j+1]-sum[i])/(j+1-i);
            if(min > avg) {
                min = avg;
                min_start = i
            }
        }
    }
    return min_start
}

好，100%!謝謝ChatGPT大神!!!

Posted on by

Prefix Sums – GenomicRangeQuery解題紀錄

題目內容

題目頁面: https://app.codility.com/programmers/lessons/5-prefix_sums/genomic_range_query/

題目理解

天啊~我最討厭有故事性的題目了如汽車或DNA，好長阿~~~讓我認真看他在說啥!

DNA和factor可表示為: {‘A’:1,’C’:2,’G’:3,’T’:4}，S = CAGCCTA，P=[2,5,0]，Q=[4,5,6]

然後要找第 K 個查詢（0 ≤ K < M），找到 P[K] 和 Q[K]（含）之間的 DNA 序列中包含的核苷酸的最小影響因子。也就是要計算出一個長度為M(M為P、Q的長度)的陣列，然後返回最小影響因子

例如M[0] = Math.min(S[2],S[3]) = Math.min(‘G’,’C’) = Math.min(2,3) =2

陷阱在這: each element of arrays P and Q is an integer within the range [0..N – 1]; => 所以不一定一樣長

解題思路

先用暴力法寫出一個可行解

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(S, P, Q) {
    // Implement your solution here
    factor = {'A':1,'C':2,'G':3,'T':4}
    var length_M = Math.min(P.length, Q.length)
    var M = []
    for( var i = 0 ; i < length_M; i++){
        var inclusive_S = S.slice(P[i], Q[i]+1).split("")
        var minimum = Infinity
        for(var j =0;j<inclusive_S.length;j++){
            //console.log(minimum,  factor[inclusive_S[j]])
            if(minimum > factor[inclusive_S[j]]){
                minimum = factor[inclusive_S[j]]
            }
        }
        M.push(minimum)
    }
    return M
}

因為邏輯有一點複雜，先把暴力解送出驗證一下正確性，之後再來優化

好的!!62%!!至少邏輯正確，那我們在想想要如何優化。讓我先觀察一下是死在那些效能測試上。分別是GGGGGG..??..GGGGGG..??..GGGGGG、large random string, length、all max ranges，首先先看到almost_all_same_letters，所以先把CAGC對應數字的部分做掉，如: S = CAGCCTA = [2,1,3,2,2,4,1]

下面為改善後的程式碼，可以減少重複將字串轉換為數字的部分。雖然沒有很樂觀，因為還是有先暫存中間值的可能性，先送看看有沒有改善，並評估一下效能瓶頸是否有改變。

function solution(S, P, Q) {
    // Implement your solution here
    factor = {'A':1,'C':2,'G':3,'T':4}
    var length_M = Math.min(P.length, Q.length)
    var S = S.split("").map(x => factor[x])
    var M = []
    for( var i = 0 ; i < length_M; i++){
        M.push(Math.min(...S.slice(P[i], Q[i]+1)))
    }
    return M
}

結果並沒有改善

— M = 0
minimum: Infinity
minimum: 3
minimum: 2
— M = 1
minimum: Infinity
— M = 2
minimum: Infinity
minimum: 2
minimum: 1
minimum: 1
minimum: 1
minimum: 1
minimum: 1

觀察一下現在的迴圈狀況，來找尋可改善的重複步驟，首先最明顯的，就是若遇到1應該可直接break，但我猜這影響不大。另外我發現，因為factor = {‘A’:1,’C’:2,’G’:3,’T’:4}是固定的，且最多就是4種，所以與其在那邊一個個轉換並且比較大小，還不如用4個if…else來從小尋找到最大的值。

function solution(S, P, Q) {
    // Implement your solution here
    //factor = {'A':1,'C':2,'G':3,'T':4}
    var length_M = Math.min(P.length, Q.length)
    var M = []
    for( var i = 0 ; i < length_M; i++){
        var inclusive_S = S.slice(P[i], Q[i]+1).split("")
        //console.log(inclusive_S)
        if(inclusive_S.indexOf('A') >= 0) M.push(1)
        else if(inclusive_S.indexOf('C') >= 0) M.push(2)
        else if(inclusive_S.indexOf('G') >= 0) M.push(3)
        else M.push(4)
    }
    return M
}

仍然沒有好轉

事已至此，感覺卡在一個切入觀點了，所以只好上網搜尋一下: http://myjavawar.blogspot.com/2018/10/genomicrangequery.html

原來要改變一下思考方向，要把原本的思維從”在一個已被切好的陣列中，搜尋某字元有沒有出現過”的思維，改成”計算從0到M以來某字元出現的次數”。接著若是陣列要從N開始，就直接把M-N，就會是從N~M之間某字元出現的次數”了

function solution(S, P, Q) {
    // Implement your solution here
    //factor = {'A':1,'C':2,'G':3,'T':4}
    var length_M = Math.min(P.length, Q.length)
    var M = []
    var showTimes = []
    var currentShowTime =  {'A':0,'C':0,'G':0,'T':0}
    for( var i = 0 ; i < S.length; i++){
        currentShowTime[S[i]]++
        showTimes.push({'A':currentShowTime['A'],'C':currentShowTime['C'],'G':currentShowTime['G'],'T':currentShowTime['T']})
    }
    for( var i = 0 ; i < length_M; i++){
        //var inclusive_S = S.slice(P[i], Q[i]+1).split("")
        //console.log(inclusive_S)
        if(showTimes[Q[i]]['A'] - showTimes[P[i]]['A'] > 0) M.push(1)
        else if(showTimes[Q[i]]['C'] - showTimes[P[i]]['C'] > 0) M.push(2)
        else if(showTimes[Q[i]]['G'] - showTimes[P[i]]['G'] > 0) M.push(3)
        else M.push(4)
    }
    return M
}

結果雖然效率過了，但是會有錯誤的結果，檢查了一下，這是因為當P[i]與Q[i]一樣大小時，就會出現錯誤，所以要加一個if用別的方法找答案

function solution(S, P, Q) {
    // Implement your solution here
    //factor = {'A':1,'C':2,'G':3,'T':4}
    var length_M = Math.min(P.length, Q.length)
    var M = []
    var showTimes = []
    var currentShowTime =  {'A':0,'C':0,'G':0,'T':0}
    for( var i = 0 ; i < S.length; i++){
        currentShowTime[S[i]]++
        showTimes.push({'A':currentShowTime['A'],'C':currentShowTime['C'],'G':currentShowTime['G'],'T':currentShowTime['T']})
    }
    //console.log(showTimes)
    for( var i = 0 ; i < length_M; i++){
        //var inclusive_S = S.slice(P[i], Q[i]+1).split("")
        //console.log(inclusive_S)
        if(P[i] == Q[i]){
            var factor = {'A':1,'C':2,'G':3,'T':4}
            M.push(factor[S[P[i]]])
        }else{
            if(showTimes[Q[i]]['A'] - showTimes[P[i]]['A'] > 0) M.push(1)
            else if(showTimes[Q[i]]['C'] - showTimes[P[i]]['C'] > 0) M.push(2)
            else if(showTimes[Q[i]]['G'] - showTimes[P[i]]['G'] > 0) M.push(3)
            else if(showTimes[Q[i]]['T'] - showTimes[P[i]]['T'] > 0) M.push(4)
        }
        
    }
    return M
}

結果還是有錯

仔細檢查了一下，錯誤的情況是solution(‘AC’, [0, 0, 1], [0, 1, 1])，發現P[i] 應該要減1，但這樣子P[i]==0時會出現問題，所以要給個預設值

function solution(S, P, Q) {
    // Implement your solution here
    //factor = {'A':1,'C':2,'G':3,'T':4}
    var length_M = Math.min(P.length, Q.length)
    var M = []
    var showTimes = []
    var currentShowTime =  {'A':0,'C':0,'G':0,'T':0}
    for( var i = 0 ; i < S.length; i++){
        currentShowTime[S[i]]++
        showTimes.push({'A':currentShowTime['A'],'C':currentShowTime['C'],'G':currentShowTime['G'],'T':currentShowTime['T']})
    }
    //console.log(showTimes)
    for( var i = 0 ; i < length_M; i++){
        var inclusive_S = S.slice(P[i], Q[i]+1).split("")
        //console.log(inclusive_S)
        if(P[i] == Q[i]){
            var factor = {'A':1,'C':2,'G':3,'T':4}
            M.push(factor[S[P[i]]])
        }else{
            var showTimesMax = showTimes[Q[i]]
            var showTimesMin = P[i] == 0 ? {'A':0,'C':0,'G':0,'T':0}:showTimes[P[i]-1]
            //console.log(showTimesMax, showTimesMin)
            if(showTimesMax['A'] - showTimesMin['A'] > 0) M.push(1)
            else if(showTimesMax['C'] - showTimesMin['C'] > 0) M.push(2)
            else if(showTimesMax['G'] - showTimesMin['G'] > 0) M.push(3)
            else M.push(4)
        }
    }
    return M
}

好了~終於100%了，真是個身心俱疲的一題阿! (https://app.codility.com/demo/results/trainingYXRWFN-H4J/)

Posted on by

Prefix Sums – CountDiv解題紀錄

題目內容

題目頁面: https://app.codility.com/programmers/lessons/5-prefix_sums/count_div/

解題思路

給定三個整數 A、B 和 K，返回 [A..B] 範圍內可被 K 整除的整數個數，且A 和 B 是 [ 0 .. 2,000,000,000 ]範圍內的整數； K 是 [ 1 .. 2,000,000,000 ]範圍內的整數。

嗯…看起來這是一題用效能卡死人的題目，因為最大值可到2,000,000,000，但是為了求正確性，我們還是先從簡單的方法寫起，再來慢慢改善效能，不要一下想太難的方法。先把暴力破解法寫出來

function solution(A, B, K) {
    // Implement your solution here
    var counter = 0;
    for(var i = A;i<=B;i++){
        if(i%K == 0) counter++
    }
    return counter
}

但是有了上次的經驗，我根本不想送出這個答案被打槍。所以先來想改善方法，首先，我想找到比A大，最小能夠被整除的數字，和比B小最大能夠被整除的數字然後相減後直接除以K

function solution(A, B, K) {
    var minimum_divisible = K*Math.ceil(A/K)
    var maximum_divisible = K*Math.floor(B/K)
    
    return (maximum_divisible - minimum_divisible)/K + 1
}

結果!!甚麼!!!中等程度這麼快解決!!太棒了!!!
https://app.codility.com/demo/results/trainingCYGC6K-3H8/

Posted on by

Prefix Sums（前綴和）概念

甚麼是Prefix Sums（前綴和）

當需要快速查詢數組中某一區間的元素和時，Prefix Sums可以幫助我們在O(1)的時間複雜度內進行查詢。

具體做法是先對數組進行預處理，計算出從第一個元素到當前位置的所有元素的和，然後通過兩個元素的前綴和之差來計算出任意區間的元素和。例如，要查詢數組中第i到第j個元素的和，只需要計算sums[j+1] – sums[i]即可。

Prefix Sums通常用於需要頻繁查詢數組中某一區間的元素和的情況，例如在數學、統計學、計算機科學和機器學習等領域中。Prefix Sums的計算可以在預處理的階段中完成，因此可以在之後的查詢中以O(1)的時間複雜度快速地回答各種區間求和問題。

例如，在計算機科學中，Prefix Sums通常用於解決數組中的區間查詢問題，例如求解區間最大子段和、區間平均值、區間中位數等。Prefix Sums還可以用於在數據壓縮、圖像處理和信號處理等領域中，進行離散化、濾波和卷積等操作。

計算出從第一個元素到當前位置的所有元素的和，是因為這樣可以在之後的區間求和操作中，通過兩個元素的前綴和之差來快速計算任意區間的元素和。例如，要查詢數組中第i到第j個元素的和，只需要計算sums[j+1] – sums[i]即可。這樣可以大大降低區間求和操作的時間複雜度，提高算法效率。

Prefix Sums使用時機


在許多需要進行區間求和操作的問題中，Prefix Sums都是一種常用的解決方案。因此，在識別哪些問題需要使用Prefix Sums時，可以考慮以下幾點：

  1. 問題是否需要進行區間求和操作：如果問題需要計算數組中某一區間的元素和，那麼Prefix Sums可能是一個合適的解決方案。
  2. 數據集的大小：Prefix Sums通常適用於數據集較小的情況下，因為在預處理階段中需要計算每個元素的前綴和，這可能需要額外的空間和時間。
  3. 數據是否可以修改：如果數據集可以修改，那麼在每次修改後，需要重新計算前綴和，這可能會影響算法的效率。因此，在這種情況下，需要仔細考慮使用Prefix Sums的適當性。
  4. 計算區間求和的頻率：如果需要頻繁地進行區間求和操作，那麼使用Prefix Sums可能比其他方法更有效。

綜合以上幾點，可以初步判斷哪些問題可能需要使用Prefix Sums。在實際應用中，還需要進一步評估和優化算法，以確保其效率和準確性。

使用Binary Indexed Tree來計算前綴和

BIT的基本思想是將原始數組轉換為一個二進制表示的數組，並在其中儲存一些特定位置的前綴和。BIT的建立和查詢操作都可以在O(n log n)的時間複雜度內完成，其中n是數組的長度。BIT的更新操作可以在O(log n)的時間複雜度內完成。

更多詳細介紹: https://yuihuang.com/binary-indexed-tree/

範例題目 – PassingCars

題目連結

https://app.codility.com/programmers/lessons/5-prefix_sums/passing_cars/

我的第一次解法(javascript) 

function solution(A) {
    // Implement your solution here
    var current_sum = 0
    for(var i=0;i<A.length;i++){
        if(A[i] == 0){
            for(var j = i;j<A.length;j++){
                if(A[j] == 1){
                    current_sum++
                }
            }
        }
    }
    return current_sum
}

成績如下，雖然答案是正確的，但是效率不夠，為O(N**2)，只拿到70%的分數

改善方向

我發現if(A[j] == 1)和if(A[i] == 0)這段其實重複跑了，其實可能在之前的檢查中早就會知道有那些是1哪些是0，重複遍歷是不必要的，因此我決定嘗試用另外的陣列來儲存index為1的index值(value_1_index)和index為0的index(value_0_index)

接下來因為 0 ≤ P < Q < N，所以我們會需要找value_1_index裡面的key值大於value_0_index的，所以會使用var j = value_1_index.findIndex(x=>x>value_0_index[i])來找尋。

function solution(A) {
    // Implement your solution here
    var current_sum = 0
    var value_1_index = [], value_0_index = []
    for(var i=0;i<A.length;i++){
        if(A[i] == 0) value_0_index.push(i)
        else value_1_index.push(i)
    }
    for(var i=0;i<value_0_index.length;i++){
        var j = value_1_index.findIndex(x=>x>value_0_index[i])
        if(j >= 0){
            while(j < value_1_index.length){
                j++
                current_sum++
            }
        }
    }
    return current_sum
}

結果也太哭了，居然沒省多少XD只多了一個勾勾

Detected time complexity:O(N ** 2)

接著我發現這句話!!

The function should return −1 if the number of pairs of passing cars exceeds 1,000,000,000.

因此我決定加上if(current_sum > 1000000000){ return -1 }的判斷在current_sum ++的後面，但結果仍然一樣，但是可以發現至少程式有跑完(不是顯示Killed)，只是速度達不到標準，尤其是large_random和large_alternate差異很大，我的程式跑了5.336秒，要求卻是0.304秒，差了10倍以上(汗顏)。仔細觀察了一下，我個人覺得在large_alternate的題目代表是0和1頻繁交替的狀況下，我的演算法的效能會很差。

因此我猜測這個效能瓶頸和var j = value_1_index.findIndex(x=>x>value_0_index[i])這個搜尋的動作有關，我決定改成當i和j用完就把用完的部分砍掉，以減少搜尋量。為此，我必須把for迴圈改成while，並且讓value_0_index與value_1_index都能隨著時間變小。

function solution(A) {
    // Implement your solution here
    var current_sum = 0
    var value_1_index = [], value_0_index = []
    for(var i=0;i<A.length;i++){
        if(A[i] == 0) value_0_index.push(i)
        else value_1_index.push(i)
    }
    while(value_0_index.length > 0){
        var j = value_1_index.findIndex(x=>x>value_0_index[0])
        if(j >= 0){
            value_1_index = value_1_index.slice(j,value_1_index.length)
            var pointer = 0
            while(pointer < value_1_index.length){
                pointer++
                current_sum++
                if(current_sum > 1000000000){
                    return -1
                }
            }
        }
        value_0_index.shift();
    }
    return current_sum
}

所以問題是出在value_1_index = value_1_index.slice(j,value_1_index.length)這邊太耗時，尤其是最後一項，可以看出是在當某個數字多的時候會更耗時。在這邊我嘗試把slice改成splice，並且在j>0時才去做

function solution(A) {
    // Implement your solution here
    var current_sum = 0
    var value_1_index = [], value_0_index = []
    for(var i=0;i<A.length;i++){
        if(A[i] == 0) value_0_index.push(i)
        else value_1_index.push(i)
    }
    while(value_0_index.length > 0){
        var j = value_1_index.findIndex(x=>x>value_0_index[0])
        if(j >= 0){
            if(j > 0){
                value_1_index.splice(0,j)
            }
            var pointer = 0
            while(pointer < value_1_index.length){
                pointer++
                current_sum++
                if(current_sum > 1000000000){
                    return -1
                }
            }
        }
        value_0_index.shift();
    }
    return current_sum
}

結果有改善，但仍需努力

接著我發現，等等…value_1_index好像不用刪啊!!先決定不要先搜尋好了，把條件設定成從最後一個value_1_index去找起，找到value_1_index裡的值小於value_0_index[0]時停止

function solution(A) {
    // Implement your solution here
    var current_sum = 0
    var value_1_index = [], value_0_index = []
    for(var i=0;i<A.length;i++){
        if(A[i] == 0) value_0_index.push(i)
        else value_1_index.push(i)
    }
    while(value_0_index.length > 0){
        var point = value_1_index.length-1
        while(value_1_index[point] > value_0_index[0]){
            current_sum++
            point--
        }
        value_0_index.shift();
    }
    return (current_sum > 1000000000) ? -1 : current_sum 
}

結果仍然超時，我發現似乎value_0_index也可以不用刪，改回使用for迴圈看看

function solution(A) {
    // Implement your solution here
    var current_sum = 0
    var value_1_index = [], value_0_index = []
    for(var i=0;i<A.length;i++){
        if(A[i] == 0) value_0_index.push(i)
        else value_1_index.push(i)
    }
    for(var i=0;i<value_0_index.length;i++){
        var pointer = value_1_index.length-1
        while(value_1_index[pointer] > value_0_index[i]){
            current_sum++
            pointer  --
        }
    }
    return (current_sum > 1000000000) ? -1 : current_sum 
}

繞了這麼久，我覺得最大的問題應該是在 (0, 1), (0, 3), (0, 4), (2, 3), (2, 4)中，  (2, 3), (2, 4)中的3,4其實是(0, 1), (0, 3), (0, 4)中的1,3,4的子集合，所以應該是要做暫存，把第一次的集合儲存起來，之後直接減掉A[0] = 0 A[1] = 1 A[2] = 0之中兩個0中間的1這個值然後加上去就可以了

function solution(A) {
    // Implement your solution here
    var current_sum = 0
    var value_1_index = [], value_0_index = []
    //紀錄兩個0中間經過的1
    var value_0_interval = []
    for(var i=0;i<A.length;i++){
        if(A[i] == 0) {
            value_0_index.push(i)
            value_0_interval[value_0_index.length-1] = 0
        }else {
            value_1_index.push(i)
            value_0_interval[value_0_index.length-1]++
        }
    }
    var current_value_1 = value_1_index.length
    for(var i=0;i<value_0_index.length;i++){
        current_sum = current_sum + current_value_1
        current_value_1 = current_value_1 - value_0_interval[i]
    }
    return (current_sum > 1000000000) ? -1 : current_sum 
}

好…90%，快過了，一開始就要除去第一個value_0_index之前的value_1_index

function solution(A) {
    // Implement your solution here
    var current_sum = 0
    var value_1_index = [], value_0_index = []
    //紀錄兩個0中間經過的1
    var value_0_interval = []
    for(var i=A.indexOf(0);i<A.length;i++){
        if(A[i] == 0) {
            value_0_index.push(i)
            value_0_interval[value_0_index.length-1] = 0
        }else {
            value_1_index.push(i)
            value_0_interval[value_0_index.length-1]++
        }
    }
    var current_value_1 = value_1_index.length
    for(var i=0;i<value_0_index.length;i++){
        current_sum = current_sum + current_value_1
        current_value_1 = current_value_1 - value_0_interval[i]
    }
    return (current_sum > 1000000000) ? -1 : current_sum 
}

終於100%了….https://app.codility.com/demo/results/trainingWK5QAP-PP8/

結論，一個easy程度的我玩這麼多次，真的很哭…但滿好玩的(有嗎?)