Claire's Blog

題目內容 題目頁面: https://app.codility.com/programmers/lessons/7-stacks_and_queues/brackets/ 解題紀錄 感覺很簡單的題目，先隨便寫一個答案 這種簡單的題目真的就是陷阱多，這應該是也要考慮到})]為開頭的狀況，要過濾掉這種CASE 這種考細心度的我最吃虧了= =但是還是過了(https://app.codility.com/c/run/training2C9S74-MHH/)

題目內容 題目頁面:  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…

題目內容 題目頁面: https://app.codility.com/programmers/lessons/6-sorting/triangle/ 題意解析 除了任兩邊的長度必須大於第三邊之外，組成三角形的線段還有一些其他的限制： 如果以上任何一個條件不滿足，則無法組成三角形。 0 ≤ P < Q < R < N 解題過程 先寫一個一定會被打槍的暴力解，複雜度為O(N^3) 結果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]，以此類推，直到遍歷完整個陣列。 總之，當一個陣列已經排好序時，只需要檢查相鄰的三個元素是否能夠構成三角形，即可判斷是否存在三個元素能夠構成三角形。這比遍歷所有可能的三元組要更高效。 所以就是要知道這個定理就可以了

題目內容 題目頁面: 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陣列，找尋最大的前三個正數數字以及最小的前三個負數數字(當正值時使用)，以及最小的前三個正數數字以及最大的負數數字(當負值時使用)，然後統計正值的數量和負值的數量，以決定最後輸出的會是正值還是負值 100%!!!一次成功~感動(https://app.codility.com/demo/results/trainingR9PVFF-P78/)

題目內容 題目頁面: https://app.codility.com/programmers/lessons/6-sorting/distinct/ 題目解析 這一題之前其實出現過，但是因為這一題A的範圍是負一百萬到正一百萬，實在太大了，沒辦法直接用查表的方式儲存，所以會需要使用到二分搜尋法去建立這個不重複陣列 我的解題記錄 第一次的解法 對於這結果，我真是滿腹委屈，明明二分搜尋法就是O(logN)阿!到底是誰把他變成O(N^2)的…我覺得應該是原本遍歷陣列為N,又乘上搜尋的LogN，因此變得很耗時 經過了一陣思考後，我覺得我根本被這一個章節的篇名所騙了，我幹嘛要建立有序陣列呢?用物件不就好了嗎?甚麼二分搜尋法根本自討苦吃!! 結果根本沒在鳥甚麼Sorting不Sorting的反而過關，100%PASS!(https://app.codility.com/demo/results/trainingTR8QQS-TDU/)

題目內容 題目頁面: 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)，但是先這樣試看看 解題思路 第一次的嘗試 我就知道….60%，timeout errors。複雜度還是太高，現在的解法是很直接的思考平均算法，先嘗試思考看看”平均”有沒有其他可能的算法 本來想嘗試必定包含最小值得所有可能，但是發現有邏輯錯誤，因為一個最小值不代表平均起來就一定最小，因為若該最小值的左右兩邊比較大，旁邊有兩個比較小的值，平均值會比包含最小值的還要小。所以即便是最小的值也不一定在最小平均之內。 萬般無助之下，詢問了ChatGPT，沒想到他都比我聰明(哭)，好吧這就來改寫!! 以下為改寫後的程式碼 好，100%!謝謝ChatGPT大神!!!

題目內容 題目頁面: 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…

題目內容 題目頁面: 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，但是為了求正確性，我們還是先從簡單的方法寫起，再來慢慢改善效能，不要一下想太難的方法。先把暴力破解法寫出來 但是有了上次的經驗，我根本不想送出這個答案被打槍。所以先來想改善方法，首先，我想找到比A大，最小能夠被整除的數字，和比B小最大能夠被整除的數字然後相減後直接除以K 結果!!甚麼!!!中等程度這麼快解決!!太棒了!!!https://app.codility.com/demo/results/trainingCYGC6K-3H8/