Polaris-hzn8

有序顺序表合并 将两个有序表合并为一个新的有序顺序表，并由函数返回结果顺序表。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263//[顺序表合并]将两个（有序）顺序表 合并为一个 新的（有序）顺序表，并由函数返回结果顺序表#include "preset.h"//顺序表合并（利用三个int类型指针i\j\k）bool merge(SqList a, SqList b, SqList &c) { if (c.length < a.length + b.length) return false; int i = 0, j = 0, k = 0; //逐个比较 将较小的插入顺序表c中 while (i < a.length && j < b.length) { if (a.elem[i] <= b.elem[j]) { c.elem[k] = a.elem[i]; i++; k++; } else { c.elem[k] = b.elem[j]; j++; k++; } } //剩余元素直接插入结果 while (i < a.length) { c.elem[k] = a.elem[i]; k++; i++; } while (j < b.length) { c.elem[k] = b.elem[j]; k++; j++; } //修改顺序表c的长度 c.length = a.length + b.length; return true;}//顺序表合并（利用三个int*类型指针pa\pb\pc）bool mergeList(SqList La, SqList Lb, SqList &Lc) &# ...

顺序表子表逆置 已知在一维数组A[m+n]中依次存放两个线性表(a1,a2,a3…,am)和(b1,b2,b3…bn)，编写函数将数组中两个顺序表的位置互换。 顺序表 内部块序 更改 已知一个一维数组A[m+n]中依次存放着 两个线性表(a1,a2,a3…am)和(b1,b2,b3…bn) 编写一个函数将数组中两个顺序表的位置互换，即将(b1,b2,b3…bn)放在(a1,a2,a3…am)的前面 123456789101112131415161718192021222324252627282930313233#include "preset.h"//顺序表逆置void listReverse(SqList &sql, int left, int right) { //int p = 0; //int q = sql.length - 1; while (left < right) { int temp = sql.elem[left]; sql.elem[left] = sql.elem[right]; sql.elem[right] = temp; left++; right--; }}//逆置前n个元素、逆置后m个元素void test(SqList &sql, int n, int m) { cout << "Reverse all: " << endl; listReverse(sql, 0, sql.length - 1); print(sql); cout << "Reverse the first " << n << " elements:" << endl; listReverse(sql, 0, n - 1); print(sql); cout << "Reverse the last " << m << " elements:&quo ...

顺序表综合操作 线性表(a1,a2,a3…an)中的元素递增有序且按顺序存储与计算机内， 要求设计一个算法完成用最少时间在表中查找数值为x的元素，若找到则将其与后继元素位置相互交换，若找不到则将其插入表中并使表中元素仍然递增有序 1.二分查找递归12345678910111213141516171819202122232425#include "preset.h"//有序顺序表查找（二分查找）递归写法int binSearch(SqList sql, int target, int low, int high) { if (low > high) return -1; int mid = (low + high) / 2; cout << "low : " << low << " high : " << high << " mid : " << mid << endl; if (target == sql.elem[mid]) { return mid; } else if (target < sql.elem[mid]) { high = mid - 1; binSearch(sql, target, low, high); } else { low = mid + 1; binSearch(sql, target, low, high); }}int main() { SqList sql = {{1, 3, 5, 7, 8, 10, 11}, 7}; cout << "current List:" << endl; print(sql); int target; cin >> target; cout << binSearch(sql, target, 0 ...

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