owned this note   changed 2 years ago  
Published Linked with GitHub

Leetcode刷題學習筆記–Recursive

153. Find Minimum in Rotated Sorted Array

在有旋轉過的遞增排序的array中，找出最小值。
如果沒有旋轉的array，則

nums.front() < nums[mid] 且 >nums[mid] < nums.back();
所以rotated過的array，如果
nums.front() > nums[mid] 則最小值在前半array裡面
nums[mid] > nums.back() 則最小值在後半array裡面

題目提示時間複雜度為O(logN)，很明顯就是binary search。














int findMin(vector<int>& nums) {
    auto n = nums.size();
    if(n == 1) return nums[0];
    if(n == 2) return min(nums[0], nums[1]);
    int mid = n / 2;
    vector<int> subvec;
    if(nums[mid] > nums.back())
        subvec = vector<int>(nums.begin() + mid, nums.end());
    else
        subvec = vector<int>(nums.begin(), nums.begin() + mid + 1);
        
    return findMin(subvec);
}

雖然說這樣的解法看起來比較漂亮，但是執行效果不好，因為每次都會產生一個新的vector。可以用只傳index來改善。

這邊使用了vector的range constructor，Constructs a container with as many elements as the range [first,last)，其中range包括了開頭，但不包括結尾。這是因為為了配合end()指向nullptr。

beginend

另外begin()和end()回傳回來是iterator，必須使用"*"才可以取值，例如:

cout << *(nums.begin() + 3) << endl;

22. Generate Parentheses(Medium)

給你一個n,生成n個左括號和n個右括號，所有的可能組合。這些組合必須符合well-formed parentheses。

解題思路

  1. 如果n = 1，只有一個左括號和一個右括號。"("和")"。
  2. 離開條件當然是左括號比右括號還多。

程式解釋

  1. 使用left和right來表示左括號和右括號的剩餘量。
  2. left > right，表示left比較多，則不可能生成合理的表示式。














void helper(int left, int right, string cur, vector<string>& res) {
    if(left > right) return;
    else if(left == 0 && right == 0)
        res.push_back(cur);
    else {
        if(left > 0) helper(left - 1, right, cur + "(", res);
        if(right > 0) helper(left, right - 1, cur + ")", res);
    }
}
vector<string> generateParenthesis(int n) {
    vector<string> res;
    helper(n, n, "", res);    
    return res;
}
tags: leetcode 刷題
Select a repo