DSA

Hash 【C++ 哈希表查找口诀】 想知道有没有 key？ → 用 count: if (map.count(key)) 想查并用它的 value？ → 用 find: if (map.find(key) != map.end()) 口诀： count 大于 0，就说明有 find 不等于 end，就说明找到了 两数之和 vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> hashtable; for (int i = 0; i < nums.size(); i++){ auto it = hashtable.find(target - nums[i]);//判断是否存在 if (it != hashtable.end()){ return {i, it->second}; } hashtable[nums[i]] = i;// 添加元素, 这里的添加顺序不可提前,因为我想做的是先查找,如果先添加会影响这一次查找 } return {}; }

二分查找 在有序数组中确定num的存在 二分查找的两种写法 // 左闭右开 //更适合找边界、插入位置等复杂问题 int searchInsert(vector<int>& nums, int target) { int left = 0; int right = nums.size();// !! while (left < right) {// !! int mid = left + ((right - left) >> 1);// >>运算的优先级低于+ if (nums[mid] == target) return mid; else if (nums[mid] < target) left = mid + 1;// !! else right = mid;// !! } return left; } // 闭区间 //更适合标准查找、简单理解 int searchInsert(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1;// !! while (left <= right) {// !! int mid = left + ((right - left) >> 1); if (nums[mid] == target) return mid; else if (nums[mid] < target) left = mid + 1;// !! else right = mid - 1;// !! } return left; } 在有序数组中找到>=num的最左位置 int findLeft(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1;// !! int ans = -1; while (left <= right) {// !! int mid = left + ((right - left) >> 1); if (nums[mid] >= target) ans = mid; right = mid - 1; else left = mid + 1;// !! } return ans; } 在有序数组中找到<=num的最右位置 int findRight(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1;// !! int ans = -1; while (left <= right) {// !! int mid = left + ((right - left) >> 1); if (nums[mid] <= target) ans = mid; left = mid + 1; else right = mid - 1;// !! } return ans; }

双指针 快慢指针 删除有序数组中的重复项 一个有序数组nums，原地删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度 int removeDuplicates(vector<int>& nums) { int n = nums.size(); if (n <= 2) { return n; } int slow = 2; for (int fast = 2; fast < n; ++fast){ if (nums[fast] != nums[slow-2]){// fast 是读指针，不是写指针。我们无法知道前面已经写了多少个相同的值。只有 slow 才能记录我们已经保留了多少个相同的值。 nums[slow++] = nums[fast]; } } return slow; } 移除元素 在数组中,原地移除所有数值等于val的元素 ...

基数与序数的规律 ​ 对于一个数据, 要先判断是基数还是序数, 如果要计数,还要考虑是否包括边界 基数: 绝对的,有一个基底数, 日常生活中基底是1; 编程中一般是0; 常见的基数概念有 数量, 个数, 体积, 面积, 时间段, 年龄(周岁), 分数 序数: 相对的, 表示先后顺序, 常见的概念: 位次, 时间点 端点的开闭规律: 全开 ​ 基本的转换规律: 基数 = 序数 - based + 1 ...

堆的核心算法解析 核心要点 这个精简版堆只保留了最核心的两个算法： 节点索引计算公式（堆的基础） 父节点索引 = (当前索引 - 1) / 2 左子节点索引 = 当前索引 * 2 + 1 右子节点索引 = 当前索引 * 2 + 2 核心算法1: 上浮调整 (heapifyUp) 用途: 插入新元素后维护堆性质 原理: 新元素从末尾开始，与父节点比较，如果优先级更高就向上交换 ...

链表 删除特定节点 ListNode* removeElements(ListNode* head, int val) { ListNode dummy(0, head); ListNode* cur = &dummy; while (cur->next) {// if (cur->next->val == val) { ListNode* tmp = cur->next; cur->next = cur->next->next;//比条件可以多一个next delete tmp; } else cur = cur->next; } return dummy.next; } 两两交换相邻节点 ​ 在改变单链表时,优先改变上游的指针 ListNode* swapPairs(ListNode* head) { if (!head || !head->next) return head; ListNode dummy(0, head); ListNode* cur = &dummy; while (cur->next && cur->next->next) { ListNode* p1 = cur->next; ListNode* p2 = cur->next->next; cur->next = p2;//先改头->p2 cur-->p1-->p2-->other p1->next = p2->next;//在改p1->other p2->next = p1;//最后在p2->p1; cur = p1; } return dummy.next; } 合并有序链表 struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} }; class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { // 创建一个哑节点作为新链表的起点 ListNode dummy(0); ListNode* curr = &dummy; // 当前指针用于构建新链表 // 同时遍历两个链表 while (l1 && l2) { if (l1->val <= l2->val) { curr->next = l1; l1 = l1->next; } else { curr->next = l2; l2 = l2->next; } curr = curr->next; // 移动当前指针 } // 将剩余部分直接连接到新链表末尾 curr->next = (l1 != nullptr) ? l1 : l2; // 返回合并后的头节点 return dummy.next; } }; 环形链表 struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} }; class Solution { public: bool hasCycle(ListNode *head) { // 边界情况：空链表或只有一个节点且无环 if (head == nullptr || head->next == nullptr) { return false; } // 初始化快慢指针 ListNode *slow = head; ListNode *fast = head; // 快指针及其下一个节点都非空时继续循环 while (fast != nullptr && fast->next != nullptr) { slow = slow->next; // 慢指针每次走一步 fast = fast->next->next; // 快指针每次走两步 if (slow == fast) { // 快慢指针相遇，说明存在环 return true; } } // 遍历结束未相遇，说明没有环 return false; } }; 在有序链表中删除相同元素 ​ 在链表的循环中, 判断条件一般是所有指针中最前面的指针 ...