目录
1.字母异位词分组
2.环形链表
3.环形链表2
4.二叉树的中序遍历
5.搜索插入位置
1.字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
排序字符：对于每个字符串，我们将其字符排序，得到一个唯一的 "排序后的字母" 作为该字符串的标识符（key）。
使用哈希表：利用哈希表（unordered_map）来将排序后的字母作为键（key），将相同字母异位词的字符串作为值（value）。如果两个字符串排序后得到相同的结果，它们属于同一组。
最终结果：哈希表中存储了多个键值对，其中每个键对应的值是一个字母异位词列表。
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> anagrams;
for (const string& str : strs) {
string sorted_str = str;
sort(sorted_str.begin(), sorted_str.end());
anagrams[sorted_str].push_back(str);
}
vector<vector<string>> result;
for (auto& pair : anagrams) {
result.push_back(pair.second);
}
return result;
}
};unordered_map<string, vector<string>> anagrams;：使用哈希表 anagrams 来存储字母异位词。键是排序后的字符串，值是一个包含所有字母异位词的字符串数组。
遍历每个字符串：
对每个字符串 str，我们创建它的副本 sorted_str。
使用 sort() 函数对 sorted_str 进行排序。
将排序后的 sorted_str 作为哈希表的键，原字符串 str 被添加到相应的值（即字母异位词组）中。
提取结果：哈希表中的每个值都是一个字母异位词的组，我们将所有这些组收集到 result 数组中并返回。
2.环形链表
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ，则返回 true 。 否则，返回 false 。
初始化：
两个指针 slow 和 fast，都指向链表头部。
slow 每次走一步，fast 每次走两步。
循环遍历：
如果链表没有环，fast 指针最终会到达链表的末尾（即 fast 或 fast->next 为 NULL）。
如果链表有环，fast 指针和 slow 指针一定会相遇，因为 fast 走得比 slow 快，两者最终会在环内某个节点相遇。
判定条件：
如果在某个时刻 slow == fast，说明链表中存在环，返回 true。
如果 fast 指针走到链表末尾，即 fast 或 fast->next 为 NULL，说明链表没有环，返回 false。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if (!head || !head->next) return false; // 空链表或只有一个节点没有环
ListNode *slow = head; // 慢指针
ListNode *fast = head; // 快指针
while (fast && fast->next) {
slow = slow->next; // 慢指针走一步
fast = fast->next->next; // 快指针走两步
if (slow == fast) {
return true; // 快慢指针相遇，说明链表中有环
}
}
return false; // 快指针走到链表末尾，说明无环
}
};3.环形链表2
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。
初始化：
设置两个指针 slow 和 fast，都指向链表的头部。
环的检测：
slow 每次移动一步，fast 每次移动两步。
如果链表存在环，slow 和 fast 会在环中相遇。
如果链表没有环，fast 会在没有环的链表中走到 NULL，循环结束。
寻找环的入口：
当 slow 和 fast 相遇时，说明链表中有环。
将 slow 指针保持在相遇点，并将 entry 指针指向链表的头部。
然后，两个指针都以相同的速度（每次一步）移动，直到它们相遇。相遇点就是环的入口节点。
返回值：如果链表有环，返回环的入口节点；如果链表没有环，返回 NULL。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if (!head || !head->next) return NULL; // 空链表或者只有一个节点没有环
ListNode *slow = head; // 慢指针
ListNode *fast = head; // 快指针
// 检测链表是否有环
while (fast && fast->next) {
slow = slow->next; // 慢指针走一步
fast = fast->next->next; // 快指针走两步
if (slow == fast) {
// 当快慢指针相遇，说明有环
ListNode *entry = head; // 入口指针从头开始
while (entry != slow) {
entry = entry->next;
slow = slow->next;
}
return entry; // 返回环的入口节点
}
}
return NULL; // 没有环
}
};4.二叉树的中序遍历
给定一个二叉树的根节点root ，返回 它的 中序 遍历 。
如下为代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> stk;
TreeNode* curr = root;
while (curr != nullptr || !stk.empty()) {
while (curr != nullptr) {
stk.push(curr);
curr = curr->left;
}
curr = stk.top();
stk.pop();
result.push_back(curr->val);
curr = curr->right;
}
return result;
}
};vector<int> result; 用来存储中序遍历的结果。
stack<TreeNode*> stk; 用来模拟递归过程中访问的栈。
TreeNode* curr = root; 将 curr 初始化为二叉树的根节点，用来遍历树。
while (curr != nullptr || !stk.empty())：这个循环会一直进行，直到遍历完所有节点。条件判断包括两部分：
curr != nullptr：表示当前节点还存在。
!stk.empty()：表示栈不为空，说明还有节点待访问。
while (curr != nullptr)：这个内层循环将沿着左子树访问，直到当前节点为空。
在每一步，当前节点 curr 会被压入栈中 (stk.push(curr);)，然后将 curr 移动到左子节点 (curr = curr->left;)。
当左子树遍历完毕后，栈顶的节点就是当前最左的节点。
curr = stk.top(); 从栈中取出栈顶节点，即当前最左的节点。
stk.pop(); 弹出栈顶节点，因为这个节点已经被访问过。
result.push_back(curr->val); 将当前节点的值添加到结果数组中。
curr = curr->right; 将 curr 移动到右子树节点，继续进行下一个循环。
5.搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
代码如下所示：
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
};int left = 0; 和 int right = nums.size() - 1;：初始化左右指针，分别指向数组的头部和尾部。
while (left <= right)：这个循环会持续进行，直到找到目标值或确定目标值的插入位置。
int mid = left + (right - left) / 2;：计算中间位置。使用 left + (right - left) / 2 来避免 left + right 可能出现的溢出问题。
if (nums[mid] == target)：如果 mid 位置的元素等于目标值，直接返回该索引。
else if (nums[mid] < target)：如果 mid 位置的元素小于目标值，目标值应该在 mid 右侧，更新 left = mid + 1。
else：如果 mid 位置的元素大于目标值，目标值应该在 mid 左侧，更新 right = mid - 1。
return left;：如果循环结束时没有找到目标值，left 将指向目标值应该插入的位置。
