Letbook Cookbook題單——數組5

81. 搜尋旋轉排序數組 II

難度中等

已知存在一個按非降序排列的整數數組

nums

，數組中的值不必互不相同。

在傳遞給函數之前，

nums

在預先未知的某個下标

k

（

0 <= k < nums.length

）上進行了 旋轉 ，使數組變為

[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]

（下标 從 0 開始 計數）。例如，

[0,1,2,4,4,4,5,6,6,7]

在下标

5

處經旋轉後可能變為

[4,5,6,6,7,0,1,2,4,4]

。

給你 旋轉後 的數組

nums

和一個整數

target

，請你編寫一個函數來判斷給定的目标值是否存在于數組中。如果

nums

中存在這個目标值

target

，則傳回

true

，否則傳回

false

。

你必須盡可能減少整個操作步驟。

示例 1：

輸入：nums = [2,5,6,0,0,1,2], target = 0
輸出：true
           

示例 2：

輸入：nums = [2,5,6,0,0,1,2], target = 3
輸出：false
           

提示：

• 1 <= nums.length <= 5000

• -104 <= nums[i] <= 104

• 題目資料保證

  nums

  在預先未知的某個下标上進行了旋轉

• -104 <= target <= 104

進階：

• 這是 搜尋旋轉排序數組 的延伸題目，本題中的

  nums

  可能包含重複元素。
• 這會影響到程式的時間複雜度嗎？會有怎樣的影響，為什麼？

暴力

樸實無華不枯燥

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        for(int i:nums)
        if(i==target)
        return true;
        return false;
    }
};
           

二分

這題是個擴充題，不同點在于加了一個存在相同元素，邊界一下子變複雜了，剛開始沒相出，看了官方解釋後發現自己還是想複雜了，不過在資料範圍較小的情況下下面這個方法和暴力也差不多

對于a[l]==a[mid]=a[r]的情況，我們無法判斷哪邊是有序的，是以我們可以将目前二分區間的左邊界加一，右邊界減一，然後在新區間上繼續二分查找。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = (int)nums.size();
        if (!n) {
            return false;
        }
        if (n == 1) {
            return nums[0] == target ? true : false;
        }
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) return true;
             if (nums[l] == nums[mid] && nums[mid] == nums[r]) {
                ++l;
                --r;
            } 
            else if (nums[l] <= nums[mid]) {
                if (nums[l] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return false;
    }
};
           

84. 柱狀圖中最大的矩形

難度困難

給定 n 個非負整數，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰，且寬度為 1 。

求在該柱狀圖中，能夠勾勒出來的矩形的最大面積。

示例 1:

輸入：heights = [2,1,5,6,2,3]
輸出：10
解釋：最大的矩形為圖中紅色區域，面積為 10
           

示例 2：

輸入： heights = [2,4]
輸出： 4
           

提示：

• 1 <= heights.length <=105

• 0 <= heights[i] <= 104

單調棧

單調棧，當時看過三葉姐一個對于這類題的題解，講得很好，這題雖然寫得有點坎坷，但還是寫出來了，不過沒有用最優的一個棧一個循環來寫

class Solution {
public:
    int largestRectangleArea(vector<int>& h) {
        stack<int>st;
        vector<int>a(h.size()), b(h.size());
        int ans = 0;
        for (int i = 0; i < h.size(); i++)
        {
            a[i] = i-1;
            while (!st.empty() && h[i] <= h[st.top()])
            {
                st.pop();
                if (st.empty())
                    a[i] = -1;
                else
                    a[i] = st.top();
            }
            st.push(i);
        }
        stack<int>st1;
        for (int i = h.size() - 1; i >= 0; i--)
        {
            b[i] = i+1;
            while (!st1.empty() && h[i] <= h[st1.top()])
            {
               st1.pop();
               if (st1.empty())
                   b[i] = h.size();
               else
                   b[i] = st1.top();
            }
            st1.push(i);
        }
        for (int i = 0; i < h.size(); i++)
            ans = max(ans, h[i] * (i - a[i]) + h[i] * (b[i] - i) - h[i]);
        return ans;
    }
};
           

90. 子集 II

難度中等

給你一個整數數組

nums

，其中可能包含重複元素，請你傳回該數組所有可能的子集（幂集）。

解集 不能 包含重複的子集。傳回的解集中，子集可以按 任意順序 排列。

示例 1：

輸入：nums = [1,2,2]
輸出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
           

示例 2：

輸入：nums = [0]
輸出：[[],[0]]
           

提示：

• 1 <= nums.length <= 10

• -10 <= nums[i] <= 10

挺标準的一個二進制枚舉，注意下判重就行，和以前那些題目判重一樣，nums[i]和nums[i+1]相等，對nums[i+1]後面的枚舉沒必要了

當然回溯枚舉也可以

二進制枚舉

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int>>ans;
        int n=1<<nums.size();
        for(int i=0;i<n;i++)
        {
            vector<int>x;
             bool flag=true;
            for(int j=1;j<nums.size();j++)
            {
                if((i>>j&1)&&!(i>>(j-1)&1)&&nums[j-1]==nums[j])
                {
                    flag=false;
                    break;
                }
            }
               if(flag)
               {
                for(int j=0;j<nums.size();j++)
                {
                    if(i>>j&1)
                    x.push_back(nums[j]);
                }
                ans.push_back(x);
               }
        }
        return ans;
    }
};