首頁面試題目

# 印星星

印星星
#include <iostream>
using namespace std;
void printUpperTriangle(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            cout << "* ";
        }
        cout << endl;
    }
}
void printLowerTriangle(int n) {
    for (int i = n; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            cout << "* ";
        }
        cout << endl;
    }
}
int main() {
    int n;
    cout << "請輸入行數: ";
    cin >> n;
    cout << "上三角形：" << endl;
    printUpperTriangle(n);
    cout << "下三角形：" << endl;
    printLowerTriangle(n);
    return 0;
}
# 用遞迴寫階乘


用遞迴寫階乘
#include <iostream>
using namespace std;
// 定義遞迴函式計算階乘
int factorial(int n) {
    // Base case: 當 n 為 0 或 1 時，階乘為 1
    if (n == 0 || n == 1) {
        return 1;
    }
    // 遞迴呼叫：將問題分解為較小的子問題
    // 階乘 n 可以表示為 n 乘上 (n-1) 的階乘
    return n * factorial(n - 1);
}
int main() {
    int num;
    cout << "請輸入一個正整數: ";
    cin >> num;
    // 呼叫遞迴函式計算階乘
    int result = factorial(num);
    cout << num << " 的階乘是: " << result << endl;
    return 0;
}
# 找出陣列中第二大的數字


找出陣列中第二大的數字 
#include <iostream>
using namespace std;
int findSecondLargest(int arr[], int size) {
    int largest = INT_MIN;  // 初始化最大值為 int 類型的最小值
    int secondLargest = INT_MIN;  // 初始化第二大值為 int 類型的最小值
    // 遍歷數組，更新最大值和第二大值
    for (int i = 0; i < size; i++) {
        if (arr[i] > largest) {
            secondLargest = largest;
            largest = arr[i];
        } else if (arr[i] > secondLargest && arr[i] != largest) {
            secondLargest = arr[i];
        }
    }
    return secondLargest;
}
int main() {
    int arr[] = {5, 2, 9, 1, 7, 4};  // 範例數組
    int size = sizeof(arr) / sizeof(arr[0]);  // 計算數組大小
    // 調用函數找到第二大的數
    int secondLargest = findSecondLargest(arr, size);
    cout << "第二大的數字是: " << secondLargest << endl;
    return 0;
}
# 給定一數字，找出因數


給定一數字，找出因數
#include <iostream>
#include <vector>
using namespace std;
// 找出給定數字的因數
vector<int> findFactors(int num) {
    vector<int> factors;
    // 從 1 開始遍歷到 num 的平方根
    for (int i = 1; i * i <= num; i++) {
        if (num % i == 0) {
            factors.push_back(i); // 將因數 i 加入 factors
            if (i != num / i) {
                factors.push_back(num / i); // 將因數 num/i 加入 factors
            }
        }
    }
    return factors;
}
int main() {
    int num;
    cout << "請輸入一個正整數：";
    cin >> num;
    vector<int> factors = findFactors(num);
    cout << num << " 的因數有：";
    for (int factor : factors) {
        cout << factor << " ";
    }
    cout << endl;
    return 0;
}
# 判斷質數


判斷質數
#include <iostream>
#include <cmath>
using namespace std;
// 判斷一個數字是否為質數
bool isPrime(int number) {
    // 負數和小於等於 1 的數字不是質數
    if (number <= 1) {
        return false;
    }
    // 使用平方根的方法進行質數判斷
    // 如果一個數字 n 是合數（非質數）
    // 那麼它必定可以分解為兩個因數 a 和 b
    // 其中 a 和 b 都不大於 sqrt (n)
    int sqrtNumber = sqrt(number);
    for (int i = 2; i <= sqrtNumber; i++) {
        if (number % i == 0) {
            return false;
        }
    }
    // 如果沒有找到能整除 number 的數字，則 number 是質數
    return true;
}
// 測試程式碼
int main() {
    int number;
    cout << "請輸入一個數字：";
    cin >> number;
    // 呼叫 isPrime 函式判斷是否為質數
    bool result = isPrime(number);
    // 根據結果輸出訊息
    if (result) {
        cout << number << " 是質數" << endl;
    } else {
        cout << number << " 不是質數" << endl;
    }
    return 0;
}
# 判斷子字串


判斷子字串  
#include <iostream>
#include <string>
using namespace std;
// 判斷一個字串是否為另一個字串的子字串
bool isSubstring(const string& str, const string& substring) {
    // 如果子字串長度大於原始字串，則直接返回 false
    if (substring.length() > str.length()) {
        return false;
    }
    // 遍歷原始字串，逐個比較字元
    for (size_t i = 0; i <= str.length() - substring.length(); i++) {
        bool isMatch = true;
        // 檢查子字串是否匹配
        for (size_t j = 0; j < substring.length(); j++) {
            if (str[i + j] != substring[j]) {
                isMatch = false;
                break;
            }
        }
        // 如果子字串匹配，則返回 true
        if (isMatch) {
            return true;
        }
    }
    // 沒有找到匹配的子字串，返回 false
    return false;
}
// 測試程式碼
int main() {
    string str, substring;
    cout << "請輸入一個字串：";
    getline(cin, str);
    cout << "請輸入一個子字串：";
    getline(cin, substring);
    // 呼叫 isSubstring 函式判斷是否為子字串
    bool result = isSubstring(str, substring);
    // 根據結果輸出訊息
    if (result) {
        cout << substring <<  " 是 "  << str <<  "的子字串" << endl;
    } else {
        cout << substring << " 不是 " << str <<" 的子字串 " << endl;
    }
    return 0;
}
    

  • 使用迴圈逐個比較字元的方式來實現。
    • 



    

  1. 

    檢查子字串的長度是否大於原始字串的長度，如果是，則直接返回 false，因為子字串不可能是原始字串的子字串。
    

    2. 

  2. 

    使用兩個嵌套的迴圈。外層迴圈遍歷原始字串，內層迴圈檢查從當前位置開始的子字串是否匹配。如果在內層迴圈中找到了不匹配的字元，則設置  isMatch  為 false，並且跳出內層迴圈。
    

    3. 



# Binary Search Tree


二元搜尋樹
#include <iostream>
using namespace std;
// 定義二元搜尋樹的節點結構
struct Node {
    int data;
    Node* left;
    Node* right;
    // 節點的建構函式
    Node(int value) {
        data = value;
        left = nullptr;
        right = nullptr;
    }
};
// 搜尋操作
bool search(Node* root, int value) {
    // 若樹為空則返回 false
    if (root == nullptr) {
        return false;
    }
    // 若找到了目標值，則返回 true
    if (root->data == value) {
        return true;
    }
    // 若目標值比根節點的值小，則在左子樹中搜尋
    if (value < root->data) {
        return search(root->left, value);
    }
    // 若目標值比根節點的值大，則在右子樹中搜尋
    return search(root->right, value);
}
// 插入操作
Node* insert(Node* root, int value) {
    // 若樹為空，則創建一個新節點並返回
    if (root == nullptr) {
        return new Node(value);
    }
    // 若目標值比根節點的值小，則插入左子樹中
    if (value < root->data) {
        root->left = insert(root->left, value);
    }
    // 若目標值比根節點的值大，則插入右子樹中
    else if (value > root->data) {
        root->right = insert(root->right, value);
    }
    // 若目標值等於根節點的值，不插入，直接返回根節點
    // 返回根節點
    return root;
}
// 刪除操作
Node* remove(Node* root, int value) {
    // 若樹為空，則返回空指針
    if (root == nullptr) {
        return root;
    }
    // 若目標值比根節點的值小，則在左子樹中刪除
    if (value < root->data) {
        root->left = remove(root->left, value);
    }
    // 若目標值比根節點的值大，則在右子樹中刪除
    else if (value > root->data) {
        root->right = remove(root->right, value);
    }
    // 若找到了目標值
    else {
        // 情況 1：沒有子節點或只有一個子節點
        if (root->left == nullptr) {
            Node* temp = root->right;
            delete root;
            return temp;
        }
        else if (root->right == nullptr) {
            Node* temp = root->left;
            delete root;
            return temp;
        }
        // 情況 2：有兩個子節點
        // 找到右子樹中的最小值節點
        Node* minNode = root->right;
        while (minNode->left != nullptr) {
            minNode = minNode->left;
        }
        // 複製最小值到目標節點
        root->data = minNode->data;
        // 在右子樹中刪除最小值節點
        root->right = remove(root->right, minNode->data);
    }
    // 返回修改後的根節點
    return root;
}
// 測試程式碼
int main() {
    // 建立一個二元搜尋樹
    Node* root = nullptr;
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 70);
    root = insert(root, 60);
    root = insert(root, 80);
    // 搜尋值 40
    if (search(root, 40)) {
        cout << "搜尋到值 40" << endl;
    } else {
        cout << "未找到值 40" << endl;
    }
    // 刪除值 30
    root = remove(root, 30);
    // 搜尋值 30
    if (search(root, 30)) {
        cout << "搜尋到值 30" << endl;
    } else {
        cout << "未找到值 30" << endl;
    }
    return 0;
}
我們使用  struct  定義了二元搜尋樹的節點結構，每個節點包含一個整數數據、左子樹指針和右子樹指針。


    

  • 

    search  函式實現了搜尋操作。它遞迴地在二元搜尋樹中搜尋目標值。如果樹為空則返回  false ，如果找到了目標值則返回  true ，否則根據目標值與根節點數據的比較結果遞迴地在左子樹或右子樹中搜尋。
    

    • 

  • 

    insert  函式實現了插入操作。它遞迴地在二元搜尋樹中找到合適的位置插入新節點。如果樹為空則創建一個新節點，否則根據目標值與根節點數據的比較結果遞迴地在左子樹或右子樹中插入。如果目標值等於根節點的值，則不進行插入操作（忽略重複值）。
    

    • 

  • 

    remove  函式實現了刪除操作。它遞迴地在二元搜尋樹中找到目標值所在的節點，並根據不同情況進行刪除。若目標節點沒有子節點或只有一個子節點，則直接刪除該節點並返回相應的子節點。若目標節點有兩個子節點，則找到右子樹中的最小值節點，將最小值複製到目標節點，然後在右子樹中刪除最小值節點。
    

    • 



在  main  函式中，插入了一些節點，然後使用  search  函式搜尋值 40，並根據結果輸出相應的訊息。

接著，我們刪除值 30 的節點，再次使用  search  函式搜尋值 30，並根據結果輸出相應的訊息。