# 題目2 (只有一個新題)

## Minimaze Array Cost
<details>
<summary>好像對6個左右側資</summary>

#include <bits/stdc++.h>

using namespace std;

string ltrim(const string &);
string rtrim(const string &);


/*
 * Complete the 'getMinimumCost' function below.
 *
 * The function is expected to return a LONG_INTEGER.
 * The function accepts INTEGER_ARRAY arr as parameter.
 */

long count(vector<int> arr,int min,int ins,int v){
    long sum=0;
    for(int i=0;i<arr.size()-1;i++){
        if(i==ins){
            sum+=(arr[i]-v)*(arr[i]-v);
            sum+=(v-arr[i+1])*(v-arr[i+1]);
                
            
            continue;
        }
    
        sum+=(arr[i]-arr[i+1])*(arr[i]-arr[i+1]);
    }
    return sum;
}

long getMinimumCost(vector<int> arr) {
    long sum=0;
    for(int i=0;i<arr.size()-1;i++){
        sum+=(arr[i]-arr[i+1])*(arr[i]-arr[i+1]);
    }
    long min=sum;
    for(int i=0;i<arr.size()-1;i++){
        for(int v=0;v<10000;v++){
            long nv=count(arr,min,i,v);
            if(nv<min)
                min=nv;
        }
    }
    return min;
}

>[name=Solved by 冠伍]
</details>

## 2.Count of distinct integers
<details>
<summary>測驗全對</summary>

> 原本寫的超時了(ㄌㄌㄎ跟我說不會超時qq
> 我把肇廷的queue改陣列

#include <bits/stdc++.h>

using namespace std;

string ltrim(const string &);
string rtrim(const string &);


/*
 * Complete the 'countDistinctIntegers' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts INTEGER n as parameter.
 */

int countDistinctIntegers(int n) {
    int board[1000]={},j=1;
    board[j]=n;
    
    unordered_set<int> list;
    list.insert(n);
    while(j!=0){
        int k=board[j];
        j--;
        for(int i=1;i<=k;i++){
            if(k%i==1){
                if(!list.count(k-i)){
                    j++;
                    board[j]=(k-i);
                    
                    list.insert(k-i);
                }
            }
        }
    }
    
    return list.size();
}

</details>

## 3.Valid BST Permutations
<details>
<summary>測驗全對</summary>

#include <bits/stdc++.h>

using namespace std;

string ltrim(const string &);
string rtrim(const string &);



/*
 * Complete the 'numBST' function below.
 *
 * The function is expected to return an INTEGER_ARRAY.
 * The function accepts INTEGER_ARRAY nodeValues as parameter.
 */
 long long int b[100000]={0};
long long int bst(int n){
    if(n==1)return 1;
    if(n==2)return 2;
    if(n>=3){
        long long int sum=0;
        for(int i=1;i<=n;i++){
            int rc=n-i,lc=i-1;
            if(lc==0){
                if(b[rc]==0)sum+=bst(rc);
                else sum+=b[rc];
            }
            else if(rc==0){
                 if(b[lc]==0)sum+=bst(lc);
                 else sum+=b[lc];
            }   
            else{
                if(b[rc]==0)sum+=bst(rc)*bst(lc);
                else if(b[lc]==0&&b[rc]!=0)sum+=bst(lc)*b[rc];
                else if(b[rc]==0&&b[lc]!=0)sum+=bst(rc)*b[lc];
                else sum+=b[lc]*b[rc];
            }
        }
        b[n]=sum%100000007;
        return b[n];
    }
    return 0;
}
vector<int> numBST(vector<int> nodeValues) {
        b[1]=1;
        b[2]=2;
        for(int i=0;i<nodeValues.size();i++){
            if(b[nodeValues[i]]!=0)nodeValues[i]=b[nodeValues[i]];
            else nodeValues[i]=bst(nodeValues[i]);
        }
        return nodeValues;
}

這樣寫應該也可:

 long long int T[1000]={};
        T[0] = 1;
        T[1] = 1;
        for(int i=2; i <= n; i++){
            for(int j=0; j <i; j++){
                T[i] += T[j]*T[i-j-1];
            }
	    T[i]%=100000007;
        }

</details>