wordpress站群代,西安网站制作资源,天元建设集团有限公司青岛分公司张德平不干了,蜘蛛网是个什么网站文章目录 #x1f37a; 二分法#x1f37b; 旋转数组#x1f942; 33. 搜索旋转排序数组 [旋转数组] [目标值] (二分法) #x1f37b; 元素边界#x1f942; 34. 在排序数组中查找元素的第一个和最后一个位置 [有序数组] [元素边界] (二分法)#x1f942; 81. … 文章目录 二分法 旋转数组 33. 搜索旋转排序数组 [旋转数组] [目标值] (二分法) 元素边界 34. 在排序数组中查找元素的第一个和最后一个位置 [有序数组] [元素边界] (二分法) 81. 搜索旋转排序数组Ⅱ [旋转数组] [有重] [目标值] (二分法) 153. 寻找旋转排序数组中的最小值 [旋转数组] [最小值] (二分法) 双指针 元素合并 21. 合并两个有序链表 [有序链表] [合并] (双指针) (归并) 元素交换 LCR 139. 训练计划 I [数组] [元素交换] (双指针) 元素相交 142. 环形链表II [链表] [环] (双指针) 160. 相交链表 [链表] [相交] (双指针) 面积 11. 盛最多水的容器 [数组] [面积] (双指针) 42. 接雨水 [数组] [面积] (双指针) 其他 31. 下一个排列 [数组] [排列] (双指针) (推导) 三指针 链表反转 25. K 个一组翻转链表 [链表] [分组反转] (三指针) 92. 反转链表II [链表] [反转] (三指针) 206. 反转链表 [链表] [反转] (三指针) 快速排序 215. 数组中的第K个最大元素 [数组] [第K大元素] (三指针) (快速排序) 912. 排序数组 [数组] [排序] (三指针) (快速排序) 滑动窗口 子串 3. 无重复字符的最长子串 [字符串] [子串] (滑动窗口) 区间和 1423. 可获得的最大点数 [数组] [区间外最大值] [区间内最小值] (定长滑动窗口) 二分法 旋转数组 33. 搜索旋转排序数组 [旋转数组] [目标值] (二分法)
class Solution {
public:int search(vectorint nums, int target) {int n nums.size();int left 0, right n - 1;// 二分法while (left right) {int mid left (right - left) / 2;// 先判断找到目标了没if (nums[mid] target) return mid;// 再继续左右两边找, nums[mid] nums[0] 说明 mid 在右边if (nums[mid] nums[0]) {// 此时 target 处于右右边if (nums[mid] target target nums[n - 1]) {left mid 1; // 右右} else {right mid - 1; // 右左}} else {if (nums[0] target target nums[mid]) {right mid - 1; // 左左} else {left mid 1; // 左右}}}return -1;}
};元素边界 34. 在排序数组中查找元素的第一个和最后一个位置 [有序数组] [元素边界] (二分法)
// [有序数组] [查找元素边界] (二分法)
class Solution {
public:vectorint searchRange(vectorint nums, int target) {int left find_l(nums, target);int right find_r(nums,target);return {left, right};}// 二分法查找左边界 [left, right]int find_l(vectorint nums, int target) {int n nums.size();int left 0, right n - 1;while (left right) {// [left, mid - 1] [mid] [mid 1, right]int mid left (right - left) / 2;if (nums[mid] target) {right mid - 1;} else {left mid 1;}}// left 3, right 3 - 1 2if (0 left left n nums[left] target) {return left;}return -1;}// 二分法查找右边界 [left, right]int find_r(vectorint nums, int target) {int n nums.size();int left 0, right n - 1;while (left right) {// [left, mid - 1] [mid] [mid 1, right]int mid left (right - left) / 2;if (nums[mid] target) {right mid - 1;} else {left mid 1;}}// right 4, left 4 1 5if (0 right right n nums[right] target) {return right;}return -1;}
};81. 搜索旋转排序数组Ⅱ [旋转数组] [有重] [目标值] (二分法)
class Solution {
public:bool search(vectorint nums, int target) {int n nums.size();int left 0, right n - 1;// 二分法while (left right) {// 判断是否存在int mid left (right - left) / 2;if (nums[mid] target) return true;// 去除重复元素if (nums[mid] nums[left]) {left;continue;}if (nums[mid] nums[right]) {right--;continue;}// 防止卡住, 区分不出左右if (nums[mid] nums[0]) { // 右// 再判断 target 在右边的左边还是右边 [left, mid-1][mid][mid1, right]if (nums[mid] target target nums[n - 1]) {left mid 1; // 右右} else {right mid - 1; // 右左}} else { // 左// 再判断 target 在左边的左边还是右边 [left, mid-1][mid][mid1, right]if (nums[0] target target nums[mid]) {right mid - 1; // 左左} else {left mid 1; // 左右}}}return false;}
};153. 寻找旋转排序数组中的最小值 [旋转数组] [最小值] (二分法)
class Solution {
public:int findMin(vectorint nums) {int left 0, right nums.size() - 1;// 二分法 [0, n-1]while (left right) {int mid left (right - left) / 2;if (nums[mid] nums[right]) {right mid;} else if (nums[mid] nums[right]) {left mid 1;} else {right--;}}return nums[left];}
};双指针 元素合并 21. 合并两个有序链表 [有序链表] [合并] (双指针) (归并)
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {// 虚拟头节点, 当前节点指向虚拟头节点ListNode* dummy new ListNode(-1), * cur dummy;// 双指针ListNode* p1 list1, * p2 list2;while (p1 ! nullptr p2 ! nullptr) {if (p1-val p2-val) {cur-next p1;p1 p1-next;} else {cur-next p2;p2 p2-next;}cur cur-next;}// 剩下的直接拼上if (p1 ! nullptr) cur-next p1;if (p2 ! nullptr) cur-next p2;return dummy-next;}
};元素交换 LCR 139. 训练计划 I [数组] [元素交换] (双指针)
class Solution {
public:vectorint trainingPlan(vectorint actions) {int n actions.size();if (n 1) return actions;// 定义双指针一个指向头一个指向尾int left 0, right n - 1; while (left right) {// 依次移动找到数时暂停while (left right actions[left] % 2 1) {left;}while (left right actions[right] % 2 0) {right--;}std::swap(actions[left], actions[right]);}return actions;}
};元素相交 142. 环形链表II [链表] [环] (双指针)
// [链表] [环] (双指针)
class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* dummy new ListNode(-1);dummy-next head;ListNode* fast dummy, * slow dummy;// 满指针走一步, 快指针走两步, 判断有无环while (fast-next fast-next-next) {slow slow-next;fast fast-next-next;// 如果相遇, 则让满指针从头开始走, 两者同步移动if (fast slow) {fast dummy;while (fast ! slow) {slow slow-next;fast fast-next;}return fast;}}return nullptr; }
};160. 相交链表 [链表] [相交] (双指针)
// [链表] [相交] (双指针)
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {// 双指针ListNode *p1 headA, *p2 headB;// A 走到 nullptr 后接着走 B, B 走到 nullptr 后接着走 A// 当 p1 p2 的地方就是相交的地方while (p1 ! p2) {if (p1 nullptr) p1 headB;else p1 p1-next;if (p2 nullptr) p2 headA;else p2 p2-next;}return p1;}
};面积 11. 盛最多水的容器 [数组] [面积] (双指针)
class Solution {
public:int maxArea(vectorint height) {// 双指针int left 0, right height.size() - 1;// 最大面积, 当前面积int res 0, cur 0;// 缩小区域while (left right) {cur min(height[left], height[right]) * (right - left);res max(res, cur);// 哪一边比较短, 移动哪一边if (height[left] height[right]) {left;} else {right--;}}return res;}
};42. 接雨水 [数组] [面积] (双指针)
class Solution {
public:int trap(vectorint height) {// 左边边界, 右边边界, 最边上存不了水int left 0, right height.size() - 1;// 左边最大值, 右边最大值int left_max height[left], right_max height[right];// 当前装水量, 总装水量int cur 0, res 0;while (left right) {left_max max(left_max, height[left]);right_max max(right_max, height[right]);if (left_max right_max) {// 左指针的leftMax比右指针的rightMax矮// 说明左指针的右边至少有一个板子 左指针左边所有板子// 那么可以计算左指针当前列的水量左边最大高度-当前列高度res left_max - height[left];left;} else {res right_max - height[right];right--;}}return res;}
};其他 31. 下一个排列 [数组] [排列] (双指针) (推导)
class Solution {
private:int flag 0; // 设置一个标志位, 代表找到当前排列了
public:void nextPermutation(vectorint nums) {int n nums.size();// 从后往前找, 找到第一个 nums[i] nums[j] 的地方int i n - 2, j n - 1;while (i 0 nums[i] nums[i 1]) {i--;}// 此时不是最后一个排列if (i 0) {// 找到一个比 nums[i] 大的第一个元素while (j i nums[j] nums[i]) {j--;}// 交换两者swap(nums[i], nums[j]);// 再将剩余部分逆转, 把降序变为升序reverse(nums.begin() i 1, nums.end());} else {// 如果是最后一个排列reverse(nums.begin(), nums.end());}return;}
};三指针 链表反转 25. K 个一组翻转链表 [链表] [分组反转] (三指针)
class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {// 虚拟头节点ListNode* dummy new ListNode(-1); dummy-next head;// 前置节点和后置节点ListNode* pre dummy, * end dummy;// 每次翻转 K 个节点while (end-next ! nullptr) {for (int i 0; i k end ! nullptr; i) {end end-next;}if (end nullptr) break;// [pre] [start] [2] [end] | [next] [5]ListNode* start pre-next, * next end-next;end-next nullptr;// [pre] [end] [2] [start] | [next] [5]pre-next reverse(start);// [pre] [end] [2] [start] [next] [5]start-next next;pre start;end start;}return dummy-next;}// 翻转链表ListNode* reverse(ListNode* head) {// [pre] | [cur] [next]ListNode* pre nullptr;ListNode* cur head;while (cur ! nullptr) {ListNode* next cur-next;// [pre] [cur] | [next]cur-next pre;// [N] [pre] | [cur]pre cur;cur next;}// 此时 cur 为空, pre 为最后一个非空节点return pre;}
};92. 反转链表II [链表] [反转] (三指针)
class Solution {
public:ListNode* reverseBetween(ListNode* head, int left, int right) {ListNode* dummy new ListNode(-1);dummy-next head;// 四个指针分别指向 pre start end next// [1] [pre] [start] [4] [5] [end] [next]ListNode* pre dummy, * end dummy;for (int i 0; i left - 1; i) pre pre-next;cout pre-val;for (int j 0; j right; j) end end-next;ListNode* start pre-next, * next end-next;// [1] [pre] [start] [4] [5] [end] | [next]end-next nullptr;// [1] [pre] [end] [5] [4] [start] | [next]pre-next reverse(start);// [1] [pre] [end] [5] [4] [start] [next]start-next next;return dummy-next;}// 翻转链表ListNode* reverse(ListNode* head) {// [pre] | [cur] [next]ListNode* pre nullptr;ListNode* cur head;while (cur ! nullptr) {ListNode* next cur-next;// [pre] [cur] | [next]cur-next pre;// [N] [pre] | [cur]pre cur;cur next;}// 此时 cur 为空, pre 为最后一个非空节点return pre;}
};206. 反转链表 [链表] [反转] (三指针)
class Solution {
public:ListNode* reverseList(ListNode* head) {return reverse(head);}// 翻转链表ListNode* reverse(ListNode* head) {// [pre] | [cur] [next]ListNode* pre nullptr;ListNode* cur head;while (cur ! nullptr) {ListNode* next cur-next;// [pre] [cur] | [next]cur-next pre;// [N] [pre] | [cur]pre cur;cur next;}// 此时 cur 为空, pre 为最后一个非空节点return pre;}
};快速排序 215. 数组中的第K个最大元素 [数组] [第K大元素] (三指针) (快速排序)
class Solution {
private:int target; // 目标索引, 第 n-k 小int res; // 目标值
public:int findKthLargest(vectorint nums, int k) {// 快速排序, 每次可以确定好一个元素的位置, 当索引为 k 时, 代表找到int n nums.size();// 第 k 大就是第 n - k 小target n - k;// 开始快排quickSort(nums, 0, n - 1);return res;}// 快排 [left, right]void quickSort(vectorint nums, int left, int right) {if (left right) return;// 只剩一个元素if (left right left target) {res nums[target];return;}// 先获取一个哨兵, 将数组分为小于它的部分和大于它的部分vectorint edge part(nums, left, right);// 如果 target 在左右边界之间, 则找到if (edge[0] target target edge[1]) {res nums[target];return;}// 继续递归quickSort(nums, left, edge[0] - 1);quickSort(nums, edge[1] 1, right);}// 分隔, 三指针, 这里返回相同元素的左右边界是为了去重vectorint part(vectorint nums, int left, int right) {int pivot_idx rand() % (right - left 1) left;int pivot nums[pivot_idx];// [pivot] [1] [2] [3] [4]// L/LP CP RP swap(nums[pivot_idx], nums[left]);// 设置三个指针, 分别指向小于 pivot 的元素, 当前元素, 大于 pivot 的元素int curp left 1, leftp left, rightp right 1;// 还没走到尽头, rightp 始终是指向大于 pivot 元素的while (curp rightp) {if (nums[curp] pivot) { // 小于哨兵leftp;swap(nums[curp], nums[leftp]);curp;} else if (nums[curp] pivot) { // 大于哨兵rightp--;swap(nums[curp], nums[rightp]);} else { // 相等, 什么也不做curp;}}// 最后 leftp 指向的内容肯定是最后一个小于 pivot 的, 它与 pivot 交换swap(nums[left], nums[leftp]);// 返回等于 pivot 的左边界和右边界 [小于] [pivot] [大于]return {leftp, rightp - 1};}
};912. 排序数组 [数组] [排序] (三指针) (快速排序)
class Solution {
public:vectorint sortArray(vectorint nums) {int n nums.size();quickSort(nums, 0, n - 1);return nums;}// 快排 [left, right]void quickSort(vectorint nums, int left, int right) {// 只剩一个元素, 就不用排了if (left right) return;// 先获取一个哨兵, 将数组分为小于它的部分和大于它的部分vectorint edge part(nums, left, right);// 继续递归quickSort(nums, left, edge[0] - 1);quickSort(nums, edge[1] 1, right);}// 分隔, 三指针, 这里返回相同元素的左右边界是为了去重vectorint part(vectorint nums, int left, int right) {int pivot_idx rand() % (right - left 1) left;int pivot nums[pivot_idx];// [pivot] [1] [2] [3] [4]// L/LP CP RP swap(nums[pivot_idx], nums[left]);// 设置三个指针, 分别指向小于 pivot 的元素, 当前元素, 大于 pivot 的元素int curp left 1, leftp left, rightp right 1;// 还没走到尽头, rightp 始终是指向大于 pivot 元素的while (curp rightp) {if (nums[curp] pivot) { // 小于哨兵leftp;swap(nums[curp], nums[leftp]);curp;} else if (nums[curp] pivot) { // 大于哨兵rightp--;swap(nums[curp], nums[rightp]);} else { // 相等, 什么也不做curp;}}// 最后 leftp 指向的内容肯定是最后一个小于 pivot 的, 它与 pivot 交换swap(nums[left], nums[leftp]);// 返回等于 pivot 的左边界和右边界 [小于] [pivot] [大于]return {leftp, rightp - 1};}
};滑动窗口 子串 3. 无重复字符的最长子串 [字符串] [子串] (滑动窗口)
class Solution {
private:unordered_mapchar, int umap; // 滑动窗口int res 0; // 存放结果
public:int lengthOfLongestSubstring(string s) {int n s.size();int left 0, right 0; // 窗口边界while (right n) {char cur_r s[right]; // 取当前字符串umap[cur_r]; // 更新窗口内容// 判断是否该缩小窗口while (umap[cur_r] 1) {char cur_l s[left];umap[cur_l]--;}// 此时已经没有重复元素出现 [left, right)res max(res, right - left);}return res;}
};区间和 1423. 可获得的最大点数 [数组] [区间外最大值] [区间内最小值] (定长滑动窗口)
// [数组] [区间外最大值] [区间内最小值] (定长滑动窗口)
class Solution {
public:int maxScore(vectorint cardPoints, int k) {int n cardPoints.size();int windowSize n - k;// [0, n-k] 的区间和int sum accumulate(cardPoints.begin(), cardPoints.begin() windowSize, 0);int min_val sum; // 窗口的最小值// 移动for (int i 0; i n - windowSize; i) {int left i, right i windowSize;sum cardPoints[right] - cardPoints[left];min_val min(min_val, sum);}return accumulate(cardPoints.begin(), cardPoints.end(), 0) - min_val;}
};
