2023 年「資訊科技產業專案設計」作業 1

貢獻者: 失去倪-RBIN
模擬面試錄影(漢)
模擬面試錄影(漢)
模擬面試錄影(英)

9. Palindrome Number

題目描述

給一個整數x，如果x是回文則回傳true，否的話回傳false。

程式碼解說

x小於0或者除了0以外個位數為0的x不可能為palindrome直接回傳false，最後要注意當x是奇數個位數時要去跟比較值(check)除以10做比較。

bool isPalindrome(int x){
    if(x<0 || x!=0 && x%10 ==0 ) return false;
    int check=0;
    while(x>check){
        check = check*10 + x%10;
        x/=10;
    }
    return (x==check || x==check/10);
}

Time: O(n)

Space: O(1)

針對 interviewer 的檢討:

針對 interviewee 的檢討:

11. Container With Most Water

題目敘述

給定一個長度為 n 的整數數組。繪製 n 條垂直線，第 i 條線的兩個端點為 (i, 0) 和 (i, height[i])。

求與 x 軸一起形成容器的兩條線，使得該容器包含最多的水

程式碼解說

方法一 Brute force

用兩個for迴圈去一次一次更新最大contain的值，但如果題目是給一個很大的array可能會超出設定的時間。

int maxArea(int* height, int heightSize){
    int max = height[0], hgt = 0, temp = 0, result = 0;
    if(heightSize == 1){
        return height[0];
    }
    else{   
        for(int i = 0; i < heightSize - 1; i++){
            for(int j = 1; j < heightSize; j++){
                if(height[i] < height[j]){
                    hgt = height[i];
                }
                else{
                    hgt = height[j];
                }
                temp = (j - i) * hgt;
                if(temp > result){
                    result = temp;
                }
            }
        }
    }
    return result;
}

Time: O(n^2)

從兩側端點找

i從起點，j從最尾端開始找，如果a[i] < a[j]就i + 1，否則就 j –，然後去做最大值更新，這樣只需要找n次就好

int maxArea(int* arr, int N){
    int max = 0,test,i=0,j=N-1;
    while(j>i){
        test = arr[i];
        if(test>arr[j]) test = arr[j];
        test = (j - i) * test;
        if(max < test) max = test;
        if(arr[i] < arr[j]) i++ ;
        else j--;
    }
    return max;
}

Time: O(n)

7. Reverse Integer

程式碼解說

確認res大於INT_MAX/10

int reverse(int x){
    int j = 1, res = 0;
    for(int i = 0; i < j; i++){
        if(res > INT_MAX / 10 || res < INT_MIN / 10){
            return 0;
        }
        res *= 10;
        res += x % 10;
        x /= 10;
        if(x != 0){
            j++;
        }

    }
    return res;
}