《LeetCode 顺序刷题》81 - 90

81、[中等] 搜索旋转排序数组 Ⅱ数组二分查找class Solution { public: bool search(vectorint nums, int target) { int n nums.size(); if (n 0) { return false; } if (n 1) { return nums[0] target; } 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; } };82、[中等] 删除排序链表中重复元素 Ⅱ链表class Solution { public: ListNode* deleteDuplicates(ListNode* head) { if (head nullptr) { return nullptr; } ListNode newhead; newhead.next head; ListNode* cur newhead; while (cur-next cur-next-next) { if (cur-next-val cur-next-next-val) { int x cur-next-val; while (cur-next cur-next-val x) { cur-next cur-next-next; } } else { cur cur-next; } } return newhead.next; } };83、[简单] 删除排序链表中的重复元素链表class Solution { public: ListNode* deleteDuplicates(ListNode* head) { if (head nullptr) { return head; } ListNode* cur head; while (cur-next) { ListNode* next cur-next; if (cur-val next-val) { cur-next next-next; delete next; } else { cur cur-next; } } return head; } };84、[困难] 柱状图中最大的矩形栈数组单调栈class Solution { public: int largestRectangleArea(vectorint heights) { int n heights.size(); vectorint left(n), right(n); stackint s; for (int i 0; i n; i) { while (!s.empty() heights[s.top()] heights[i]) { s.pop(); } left[i] s.empty() ? -1 : s.top(); s.push(i); } s stackint(); for (int i n - 1; i 0; --i) { while (!s.empty() heights[s.top()] heights[i]) { s.pop(); } right[i] s.empty() ? n : s.top(); s.push(i); } int ret 0; for (int i 0; i n; i) { ret max(ret, (right[i] - left[i] - 1) * heights[i]); } return ret; } };单调栈常数优化class Solution { public: int largestRectangleArea(vectorint heights) { int n heights.size(); vectorint left(n), right(n, n); stackint s; for (int i 0; i n; i) { while (!s.empty() heights[s.top()] heights[i]) { right[s.top()] i; s.pop(); } left[i] s.empty() ? -1 : s.top(); s.push(i); } int ret 0; for (int i 0; i n; i) { ret max(ret, (right[i] - left[i] - 1) * heights[i]); } return ret; } };86、[中等] 分隔链表链表class Solution { public: ListNode* partition(ListNode* head, int x) { ListNode shead, *cur1 shead; ListNode lhead, *cur2 lhead; ListNode* cur head; while (cur) { if (cur-val x) { cur1-next cur; cur1 cur1-next; } else { cur2-next cur; cur2 cur2-next; } cur cur-next; } cur1-next lhead.next; cur2-next nullptr; return shead.next; } };88、[简单] 合并两个有序数组排序数组双指针逆向双指针class Solution { public: void merge(vectorint nums1, int m, vectorint nums2, int n) { int end1 m - 1, end2 n - 1; int end m n - 1; while (end1 0 end2 0) { if (nums1[end1] nums2[end2]) { nums1[end--] nums1[end1--]; } else { nums1[end--] nums2[end2--]; } } while (end2 0) { nums1[end--] nums2[end2--]; } } };直接合并后排序class Solution { public: void merge(vectorint nums1, int m, vectorint nums2, int n) { for (int i 0; i n; i) { nums1[m i] nums2[i]; } sort(nums1.begin(), nums1.end()); } };90、[中等] 子集 Ⅱ迭代法实现子集枚举class Solution { private: vectorint path; vectorvectorint ret; public: vectorvectorint subsetsWithDup(vectorint nums) { sort(nums.begin(), nums.end()); int n nums.size(); for (int mask 0; mask (1 n); mask) { path.clear(); bool flag true; for (int i 0; i n; i) { if (mask (1 i)) { if (i 0 (mask (i - 1) 1) 0 nums[i] nums[i - 1]) { flag false; break; } path.push_back(nums[i]); } } if (flag) { ret.push_back(path); } } return ret; } };递归实现子集枚举class Solution { private: vectorint path; vectorvectorint ret; void dfs(bool choosePre, int cur, vectorint nums) { if (cur nums.size()) { ret.push_back(path); return; } dfs(false, cur 1, nums); if (!choosePre cur 0 nums[cur - 1] nums[cur]) { return; } path.push_back(nums[cur]); dfs(true, cur 1, nums); path.pop_back(); } public: vectorvectorint subsetsWithDup(vectorint nums) { sort(nums.begin(), nums.end()); dfs(false, 0, nums); return ret; } };