演算法作業 HW04

第一題

第二題

第三題

第四題

通過畫面

程式碼

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        if (numbers.size() < 2) return{};
        int l = 0;
        int r = numbers.size() - 1;
        while(l < r) {
            if (numbers[l] + numbers[r] == target) return{ l + 1,r + 1 };
            else if (numbers[l] + numbers[r] > target) r--;
            else if (numbers[l] + numbers[r] < target) l++;
        }
        return {};
    }
};

解題思路

如果字串中的元素小於兩個，即不能完成加法的運算，回傳null
之後如果兩個數字加起來即為所求，則回傳index值
如果不是所求，則用if條件式讓兩側靠中間收齊
最後如果沒有找到，回傳null

花費時間

約20分鐘

自己完成的比例

約五成，有參考老師貼的文章去理解思路，最後再自己寫Code

第五題

通過畫面

程式碼

class Solution {
public:
    bool isPalindrome(string s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            // 忽略非字母和數字的字符
            while (i < j && !isalnum(s[i])) i++;
            while (i < j && !isalnum(s[j])) j--;
            // 轉換為小寫字母進行比較
            if (tolower(s[i++]) != tolower(s[j--])) return false;
        }
        return true;
    }
};

解題思路

與上一題相似，主要就是增加一個條件，如果非英文以外的符號皆跳過
如果不是回文，則回傳false;如果是，則回傳true

花費時間

約10分鐘，前面一題已經熟悉一些

自己完成的比例

八成，只有一些函式是上網找的

第六題

通過畫面

程式碼

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != NULL && fast->next != NULL) {
            slow = slow->next;  // 慢指針每次走一步
            fast = fast->next->next;  // 快指針每次走兩步
            if (slow == fast) {  // 快慢指針相遇，表示有循環
                return true;
            }
        }
        return false;  // 快指針到達鏈表的最後，沒有循環
    }
};

解題思路

慢指針每次走一步，快指針每次走兩步。如果存在循環，快指針最終一定會追上慢指針，此時就可以判斷存在循環，返回true；如果快指針到達鏈的最後，則代表沒有循環，返回false。

花費時間

約二十分鐘

自己完成的比例

約七成，有稍微複習指標

第七題

這次的程式碼並不難，經過一下的學習就能吸收，但是觀念題那邊，第二題，我與同學有些疑惑，Worst case中是否可以存在空集合?