剑指offerII

回文链表 原题链接：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

二维子矩阵的和 原题链接：https://leetcode.cn/problems/O4NDxx/ 给定一个二维矩阵 matrix，以下类型的多个请求： 计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。 实现 NumMatrix 类： NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化 int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角 (row2, col2) 的子矩阵的元素总和。 1.二维前缀和1234567891011121314151617181920class NumMatrix {public: vector<vector<int>> prefix; NumMatrix(vector<vector<int>>& matrix) { /* 初始化前缀和数组 */ if (matrix.size() == 0) return; int m = matrix.size(); int n = matrix[0].size(); prefix.assign(m + 1, vector<int>(n + 1, 0)); //prefix.resize(m + 1, vector<int>(n + 1)); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) prefix[i + 1][j + 1] = prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j] + matrix[i][j]; } int sumRegion(int x1, int y1, int x2, int y2) { /* 利用前缀和数组进行面积和su ...

左右两边子数组和相等 原题链接：https://leetcode.cn/problems/tvdfij/solutions/ 给你一个整数数组 nums ，请计算数组的中心下标。 数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。 如果中心下标位于最左端，那么左侧数之和视为0，因为在下标左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。 如果数组有多个中心下标，应该返回最靠近左边的那一个。如果数组不存在中心下标返回-1 1.前缀和12345678910111213141516171819202122class Solution {public: int pivotIndex(vector<int>& nums) { int ans = INT32_MAX; int len = nums.size(); //1.初始化前缀和数组 int *prefix = new int[len + 10](); for (int i = 1; i <= len; ++i) prefix[i] = prefix[i - 1] + nums[i - 1]; //2.开始计算首先处理首位两种特殊情况 if (prefix[len] - prefix[1] == 0) return 0; if (prefix[len - 1] == 0) ans = min(ans , len - 1); //3.处理一般情况 for (int i = 1; i < len - 1; ++i) { if (prefix[i] == prefix[len] - prefix[i + 1]) ans = min(ans, i); } return ans == INT32_MAX ? -1 : ans; }}; 时间复杂度：$O(n)$ 空间复杂度：$O(n)$ 2.前缀和优化利用一些简单的数学知识知识，可以对前缀和的思路进行进一步的优 ...

0和1个数相同的子数组 原题链接：https://leetcode.cn/problems/A1NYOS/ 给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。 1.暴力枚举123456789101112131415class Solution {public: int findMaxLength(vector<int>& nums) { int ans = 0; for (int j = 0; j < nums.size(); ++j) { int sum = 0; for (int i = j; i >= 0; --i) { if (nums[i] == 1) sum++; else sum--; if (sum == 0) ans = max(ans, j - i + 1); } } return ans; }}; 程序超时，看来这题对时间复杂度的要求很高，需要牺牲空间复杂度换时间复杂度降低。 2.前缀和+哈希 在预处理前缀和时，将 nums[i] 为 0 的值当做 −1 处理 从而将问题转化为：如何求得最长一段区间和为 0 的子数组，使用哈希表来记录某个前缀和出现的最小下标是多少。 12345678910111213141516171819202122class Solution {public: int findMaxLength(vector<int>& nums) { int ans = 0; int len = nums.size(); //1.前缀和数组初始化 int *prefix = new int[len + 10](); for (int i = 1; i <= nums.size(); ++i) prefix[i] = pref ...