C++算法
环形链表、两个数组中的交集、随机链表的复制
环形链表检测使用快慢指针或哈希集合定位环入口。两个数组交集通过集合去重后遍历比较获取唯一元素，并扩展至对比算法求交差并集。随机链表深拷贝可采用节点穿插法或哈希映射记录原节点与新节点的对应关系，确保 random 指针正确指向新节点。
环形链表检测使用快慢指针或哈希集合定位环入口。两个数组交集通过集合去重后遍历比较获取唯一元素，并扩展至对比算法求交差并集。随机链表深拷贝可采用节点穿插法或哈希映射记录原节点与新节点的对应关系，确保 random 指针正确指向新节点。
给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。注意不允许修改链表。
此处使用 C++ STL 实现。利用 std::set 遍历链表，如果链表中的节点不在 set 中就插入（注意这里不是插入节点的值，而是节点的指针，因为节点的值可能有几个相等）；如果在就代表带环，并且该节点就是环入口点。
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
std::set<ListNode*> s;
ListNode* cur = head;
while(cur) {
auto it = s.find(cur);
if(it == s.end()) {
s.insert(cur);
} else {
return *it;
}
cur = cur->next;
}
return nullptr;
}
};
给定两个数组 nums1 和 nums2，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。
**示例 1：**输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2] **示例 2：**输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[9,4] 解释：[4,9] 也是可通过的
思路 1：一个数组的每个值到另一个数组中遍历，这种方法效率低且容易出错。
思路 2（正确思路）：先将两个数组去重（可用 STL 中的 set），再拿一个数组中的值分别到另一个数组中查找（使用 set::count），最后将遍历找到的插入到一个容器中返回即可。
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
// 去重
std::set<int> s1(nums1.begin(), nums1.end());
std::set<int> s2(nums2.begin(), nums2.end());
vector<int> v;
// 将一个数组中的值依次到另一个数组中查找
for(auto e : s1) {
if(s2.count(e)) {
v.push_back(e);
}
}
return v;
}
};
从上面来看这个是没有什么作用的，但是现实生活中不只是用来查找交集的，一般是要找交/差/并集，这时候就有著名的对比算法。
两个数组中找交/差/并集的整体思路：
【示例】使用对比算法找交集:
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
std::set<int> s1(nums1.begin(), nums1.end());
std::set<int> s2(nums2.begin(), nums2.end());
// 因为 set 遍历是有序的，有序值，依次比较
// 小的++，相等的就是交集
vector<int> ret;
auto it1 = s1.begin();
auto it2 = s2.begin();
while(it1 != s1.end() && it2 != s2.end()) {
if(*it1 < *it2) {
it1++;
} else if(*it1 > *it2) {
it2++;
} else {
ret.push_back(*it1);
it1++;
it2++;
}
}
return ret;
}
};
【对比算法在生活中的应用】 例如我们要更换手机，而之前的手机中有许多的照片是要的，此时怎么办呢？可以将云端照片和本地照片进行对比，判断是否要导入到云端中，而照片存在，但是照片可能存在更改，这时候可以比较照片最后的时间。所以这个对比算法在生活中还是有很多用处的。
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random，该指针可以指向链表中的任何节点或空节点。
构造这个链表的深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null。你的代码只接受原链表的头节点 head 作为传入参数。
/**
* Definition for a Node.
* struct Node {
* int val;
* struct Node *next;
* struct Node *random;
* };
*/
typedef struct Node Node;
// 构造一个简单 Node
Node* buyNode(int x) {
Node* newnode = (Node*)malloc(sizeof(Node));
newnode->val = x;
newnode->next = newnode->random = NULL;
return newnode;
}
// 在原链表的基础上拷贝节点 (即原链表的每个节点后面拷贝一个一样的节点)
void AddNode(Node* head) {
Node* pcur = head;
while(pcur) {
Node* newnode = buyNode(pcur->val);
Node* next = pcur->next;
newnode->next = next;
pcur->next = newnode;
pcur = next;
}
}
// 设置新节点的 random 利用关系式
// copy(新节点)->random = pcur(原链表节点)->random->next;
void setRandom(Node* head) {
Node* pcur = head;
while(pcur) {
Node* copy = pcur->next;
if(pcur->random) {
copy->random = pcur->random->next;
}
pcur = copy->next;
}
}
struct Node* copyRandomList(struct Node* head) {
if(head == NULL) {
return head;
}
// 1 在原链表基础上拷贝节点并插入到原链表的每个节点之后
AddNode(head);
// 2 设置新节点的 random
setRandom(head);
// 断开新旧链表
Node* pcur = head;
Node* copyHead, *copyTail;
copyHead = copyTail = pcur->next;
while(copyTail->next) {
pcur = copyTail->next;
copyTail->next = pcur->next;
copyTail = copyTail->next;
}
return copyHead;
}
由于出现一个很难处理的问题节点中的 random(随机) 节点怎么拷贝，如果通过节点中的值进行判断指向关系，显然这种方法是不行的。如果想走这种匹配关系，那只能暴力遍历，此时时间复杂度为 O(N^2)。这是因为原链表和拷贝出的链表直接的节点没关系才导致的，C 语言的处理方法是先拷贝在原链表中，这就导致原链表和拷贝出的链表之间的节点有了关系。那 C++ 怎么处理了，C++ 所有 STL 中的 map 由于储存 map(原链表节点，拷贝链表的节点)，这不就巧妙地将原链表和拷贝出的链表之间的节点联系起来了吗，可以通过原链表节点得到拷贝对应的节点。
【解决代码】
class Solution {
public:
Node* copyRandomList(Node* head) {
std::map<Node*, Node*> nodeMap;
Node* copyhead = nullptr, *copytail = nullptr;
Node* cur = head;
while(cur) {
if(copytail == nullptr) {
copyhead = copytail = new Node(cur->val);
} else {
copytail->next = new Node(cur->val);
copytail = copytail->next;
}
// 原节点和拷贝节点 map kv 存储
nodeMap[cur] = copytail;
cur = cur->next;
}
// 处理 random
cur = head;
Node* copy = copyhead;
while(cur) {
if(cur->random == nullptr) {
copy->random = nullptr;
} else {
copy->random = nodeMap[cur->random];
}
cur = cur->next;
copy = copy->next;
}
return copyhead;
}
};
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online