双指针

反转链表 原题链接：https://leetcode.cn/problems/reverse-linked-list/ 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 链表中节点的数目范围是 [0, 5000] -5000 <= Node.val <= 5000 1.利用外部空间主要思路：利用外部空间+STL算法 先申请一个动态扩容的数组或者容器，然后不断遍历链表，将链表中的元素添加到这个容器中。 再利用容器自身的 API，反转整个容器，这样就达到反转的效果了。 最后同时遍历容器和链表，将链表中的值改为容器中的值。 12345678910111213141516class Solution {public: int divide(int dividend, int divisor) { int flag = 0; int count = 0; if (dividend < 0 && divisor > 0 || dividend > 0 && divisor < 0) flag = 1; dividend = abs(dividend); divisor = abs(divisor); while (dividend - divisor >= 0) { dividend -= divisor; count++; } if (flag) count = -count; return count; }}; 2.双指针迭代3.优化的双指针4.递归

回文链表 原题链接：https://leetcode.cn/problems/aMhZSa/ 给定一个链表的 头节点 head ，请判断其是否为回文链表。 如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。 1.试解栈123456789101112131415161718192021class Solution {public: bool isPalindrome(ListNode* head) { if (head->next == nullptr) return true; //1.stk push stack<ListNode*> stk; ListNode* p = head; while (p) { stk.push(p); p = p->next; } //2.traverse linklist p = head; while (p) { if (stk.top()->val != p->val) return false; stk.pop(); p = p->next; } return true; }}; 2.数组+双指针1 3.递归1 4.快慢指针1

两个链表的第一个重合节点 原题链接：https://leetcode.cn/problems/3u1WK4/ 给定两个单链表的头节点 headA 和 headB ，请找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。 图示两个链表在节点 c1 开始相交： 题目数据 保证 整个链式结构中不存在环。 函数返回结果后，链表必须 保持其原始结构 。 1.哈希表主要思路： 遍历listA将其中的结点全部标记存入unset中（哈希表） 遍历listB直到其中出现相同的next域的值 直接返回其值即为结果 若遍历listB都完都没有出现符合要求的结果则返回nullptr 1234567891011121314151617181920//注：将unordered_set放到成员方法内部可以提高时间效率class Solution {public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { unordered_set<ListNode*> unset; //1.initialize unset ListNode* tmp = headA; while (tmp) { unset.insert(tmp); tmp = tmp->next; } //2.find the first node tmp = headB; while (tmp) { if (unset.count(tmp)) return tmp; tmp = tmp->next; } return nullptr; }}; 时间：48ms 内存：16.24mb 时间复杂度：$O(N)$ 空间复杂度：$O(N)$ 2.双指针主要思路： 首先判断链表是否为空，如果其中有一个链表为空则两个链表一定不相交返回nullptr 当链表都不为空时 创建两个指 ...

链表中环的入口节点 原题链接：https://leetcode.cn/problems/c32eOV/ 给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 注意 pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。 说明：不允许修改给定的链表。 1.哈希表思路： 利用哈希表建立一个标记数组 用于标记已经出现的next指针域 while循环遍历链表 直到出现重复的next指针域 表示链表环开始出现 返回此时的链表结点指针 即为环入口结点 unordered_map1234567891011121314class Solution {public: unordered_map<ListNode*, int> mark; ListNode *detectCycle(ListNode *head) { if (head == nullptr) return nullptr; ListNode* p = head; while (p) { if (mark[p]) return p; mark[p] = 1; p = p->next; } return nullptr; }}; 时间：12ms 内存：9.8mb unordered_set12345678910111213public: unordered_set<ListNode*> mark; ListNode *detectCycle(ListNode *head) { if (head == nullptr) return nullptr; ListNode* p = head; while (p) { if (mark. ...

不含重复字符的最长子字符串 原题链接：https://leetcode.cn/problems/wtcaE1/ 给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度。 1.静态滑动窗口11

删除链表的倒数第 n 个结点 原题链接：https://leetcode.cn/problems/SLwz0R/ 给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 1.计算链表长度一种最容易想到的方法：（无虚拟头结点） 首先从头节点开始对链表进行一次遍历，得到链表的长度length 然后从头节点开始对链表进行一次遍历，当遍历到第L−n+1个节点时，其下一个就是需要删除的节点 1234567891011121314151617181920212223242526272829303132333435363738class Solution {public: int getLength(ListNode *head) { int length = 0; while (head) { head = head->next; length++; } return length; } ListNode* removeNthFromEnd(ListNode *head, int n) { if (head == nullptr) return nullptr; int listSize = getLength(head); if (n < 1 || n > listSize) return nullptr;// 1 <= n <= len ListNode* deleteNode; if (n == listSize) { //delete the firstNode deleteNode = head; head = head->next; } else { ListNode* p = head; int ind = listSize - n - 1; while (ind--) p = p->n ...

字符串中的变位词 原题链接：https://leetcode.cn/problems/MPnaiL/ 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。第一个字符串的排列之一是第二个字符串的 子串 。 1.静态滑动窗口1由于知道目标字符串的长度，故可以通过暴力枚举的方式（一个静态的滑动窗口）来枚举出所有的情况， 并对枚举的每种情况进行字母数量的统计，利用哈希表实现字母数量的统计， 123456789101112131415class Solution {public: bool checkInclusion(string pattern, string text) { for (int i = 0, j = i + pattern.length(); j <= text.length(); ++i, ++j) { int flag = 0; vector<int> cnt(26); for (int k = 0; k < pattern.length(); ++k) cnt[pattern[k] - 'a']++;//查找目标的字母数量统计 for (int k = i; k < j; ++k) cnt[text[k] - 'a']--;//遍历的字符串的字母数量统计 for (int i = 0; i < 26; ++i) if (cnt[i] != 0) flag = 1;//判断字母数量是否相同 if (flag) continue; return true; } return false; }}; 勉强能过，时间复杂度与空间复杂度都很高。 2.静态滑动窗口2对每次的字母数量判断操作进行修改，对边界值进行加入与减出操作，思路没有问题的，先做记录在此。 1234567891011121314151617181920212223class Solution {public ...

字符串中的所有变位词 原题链接：https://leetcode.cn/problems/VabMRr/ 给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。 变位词 指字母相同，但排列不同的字符串。 1.静态滑动窗口11

和为k的子数组 原题链接：https://leetcode.cn/problems/QTMn0o/ 给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数， 1.静态滑动窗口1遍历滑动窗口大小，每次for循环滑动窗口大小值固定，每次对滑动窗口中的内容进行求和，尝试更新答案，时间超时： 1234567891011121314class Solution {public: int subarraySum(vector<int>& nums, int k) { int ans = 0; for (int len = 1; len < nums.size(); ++len) { for (int i = 0, j = i + len; j <= nums.size(); ++i, ++j) { int sum = 0; for (int n = i; n < j; ++n) sum += nums[n]; if (sum == k) ans++; } } return ans; }}; 所有用例成功输出结果，但由于时间复杂度太高，导致程序超时， 2.静态滑动窗口2遍历滑动窗口大小，每次for循环滑动窗口大小值固定， 维护一个sum值 进行加入与减出，每次窗口移动加入与减出边界值，尝试更新答案： 1234567891011121314151617class Solution {public: int subarraySum(vector<int>& nums, int k) { int ans = 0; for (int len = 1; len <= nums.size(); ++len) { int sum = 0; for (int i = 0; i < len; ++i) sum += n ...

和大于等于target的最短子数组 原题链接：https://leetcode.cn/problems/2VG8Kg/ 给定一个含有 n 个正整数的数组和一个正整数 target ， 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。 如果不存在符合条件的子数组，返回 0 。 1.静态滑动窗口1遍历滑动窗口大小，每次for循环滑动窗口大小值固定，每次对滑动窗口中的内容进行求和，尝试更新答案，时间超时： 1234567891011121314151617181920class Solution {public: int minSubArrayLen(int target, vector<int>& nums) { int flag = 0; int ans = nums.size(); //遍历滑动窗口的大小 for (int len = 1; len <= nums.size(); ++len) { for (int i = 0, j = i + len; j <= nums.size(); ++i, ++j) { int sum = 0; for (int k = i; k < j; ++k) sum += nums[k]; if (sum >= target && len <= ans) { ans = len; flag = 1; } } } if (!flag) return 0; return ans; }}; 2.静态滑动窗口2遍历滑动窗口大小，每次for循环滑动窗口大小值固定， 维护一个sum值 进行加入与减出，每次窗口移动加入与减出 ...