怎么做网站安全运维,网站这么推广,北京会所网站推广,wordpress会员可见目录
1.字母异位词分组
2.环形链表
3.环形链表2
4.二叉树的中序遍历
5.搜索插入位置 1.字母异位词分组
给你一个字符串数组#xff0c;请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 排序字符…目录
1.字母异位词分组
2.环形链表
3.环形链表2
4.二叉树的中序遍历
5.搜索插入位置 1.字母异位词分组
给你一个字符串数组请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 排序字符对于每个字符串我们将其字符排序得到一个唯一的 排序后的字母 作为该字符串的标识符key。 使用哈希表利用哈希表unordered_map来将排序后的字母作为键key将相同字母异位词的字符串作为值value。如果两个字符串排序后得到相同的结果它们属于同一组。 最终结果哈希表中存储了多个键值对其中每个键对应的值是一个字母异位词列表。
class Solution {
public:vectorvectorstring groupAnagrams(vectorstring strs) {unordered_mapstring, vectorstring anagrams;for (const string str : strs) {string sorted_str str;sort(sorted_str.begin(), sorted_str.end());anagrams[sorted_str].push_back(str);}vectorvectorstring result;for (auto pair : anagrams) {result.push_back(pair.second);}return result;}
};
unordered_mapstring, vectorstring anagrams;使用哈希表 anagrams 来存储字母异位词。键是排序后的字符串值是一个包含所有字母异位词的字符串数组。
遍历每个字符串
对每个字符串 str我们创建它的副本 sorted_str。 使用 sort() 函数对 sorted_str 进行排序。 将排序后的 sorted_str 作为哈希表的键原字符串 str 被添加到相应的值即字母异位词组中。 提取结果哈希表中的每个值都是一个字母异位词的组我们将所有这些组收集到 result 数组中并返回。 2.环形链表
给你一个链表的头节点 head 判断链表中是否有环。
如果链表中有某个节点可以通过连续跟踪 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:vectorint inorderTraversal(TreeNode* root) {vectorint result;stackTreeNode* 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;}
};
vectorint result; 用来存储中序遍历的结果。 stackTreeNode* 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(vectorint 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 将指向目标值应该插入的位置。
