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
}
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
}
//這會有錯誤的結果
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
}
陷阱在這: 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
}
function solution(X, A) {
// Implement your solution here
var filled = new Array(X).fill(false);
var current_filled = 0;
for (let index = 0; index < A.length; index++) {
//console.log(filled)
if(!filled[A[index]-1]){
filled[A[index]-1] = true
current_filled ++;
if(current_filled == X){
return index
}
}
}
return -1
}
function solution(A) {
// Implement your solution here
var total_a = 0;
var total_b = A.reduce((partialSum, a) => partialSum + a, 0);
var min = Infinity;
for(var i=0;i<A.length-1;i++){
total_a = total_a+A[i];
total_b = total_b-A[i];
//console.log(total_a, total_b,Math.abs(total_a-total_b), i)
if(Math.abs(total_a-total_b) < min){
min = Math.abs(total_a-total_b)
}
}
return min
}
