面试题-消失的数字
class Solution
{
public:
void reverse(vector<int>& nums, int start, int end)
{
while (start < end)
{
swap(nums[start], nums[end]);
start += 1;
end -= 1;
}
}
void rotate(vector<int>& nums, int k)
{
// 防止被套圈
k %= nums.size();
// 先整体逆置
reverse(nums, 0, nums.size() - 1);
// 1. 将逆置到前面的逆置正常顺序
reverse(nums, 0, k - 1);
// 2. 将后面的也转换正常
reverse(nums, k, nums.size() - 1);
}
};
- 初始化:
- int N = nums.size();：获取输入数组 nums 的大小，这表示从0到N-1的连续整数中应该有多少个数字。
- int x = 0;：初始化一个变量 x，用于存储异或运算的结果。
- 第一个for循环:
- 遍历数组 nums 中的每一个元素，并与 x 进行异或运算。
- 因为异或运算的性质是：任何数与0异或都等于它本身；任何数与自身异或都等于0。所以，当遍历完数组后，x 中存储的是从0到N-1的所有整数与数组 nums 中实际存在的整数的异或结果。
- 第二个for循环:
- 这个循环从0开始，到N（包括N）结束，与 x 进行异或运算。
- 理想情况下，如果数组 nums 是完整的，即包含从0到N-1的所有整数，那么在这个循环结束后，x 的值应该是0（因为所有数字都异或了自己，结果为0）。
- 但是，由于数组 nums 中缺失了一个数字，所以在这个循环结束后，x 的值将是缺失的那个数字（因为缺失的那个数字只被异或了一次，而其他数字都被异或了两次，结果为0）。
- 返回结果:
- 最后，函数返回 x，即缺失的那个数字。
注意：第二个for循环中的 j 是从0遍历到 N（包括N），但实际上，当 j 等于 N 时，它并不与任何数组中的元素异或（因为数组索引是从0到N-1），但这并不影响结果，因为 N 与任何其他数字异或都会得到非零值（除非该数字也是 N，但这种情况不可能发生，因为数组中不可能有 N 这个元素）。
轮转数组
class Solution
{
public:
void reverse(vector<int>& nums, int start, int end)
{
while (start < end)
{
swap(nums[start], nums[end]);
start += 1;
end -= 1;
}
}
void rotate(vector<int>& nums, int k)
{
// 防止被套圈
k %= nums.size();
// 先整体逆置
reverse(nums, 0, nums.size() - 1);
// 1. 将逆置到前面的逆置正常顺序
reverse(nums, 0, k - 1);
// 2. 将后面的也转换正常
reverse(nums, k, nums.size() - 1);
}
};
- reverse 函数是一个辅助函数，用于反转数组 nums 中从索引 start 到 end（不包括 end）的部分。这个函数使用了双指针法，从两端开始交换元素，直到两个指针相遇或交叉。
- rotate 函数是主要的旋转函数。首先，它对 k 取模数组的长度 nums.size()，以确保 k 不会超出数组的范围。这是因为如果 k 大于数组的长度，那么实际上只需要旋转 k % nums.size() 次即可。
- 接下来，rotate 函数执行三次反转操作：
- 第一次反转：对整个数组 nums 进行反转。这样，原本在末尾的 k 个元素现在就被移动到了数组的开头，但顺序是反的。
- 第二次反转：对数组的前 k 个元素（索引从 0 到 k-1）进行反转。这样，原本在数组开头的 k 个元素（但顺序是反的）现在就被转回了正常顺序。
- 第三次反转：对数组从索引 k 到末尾的部分进行反转。这样，剩余的元素也被转回了正常顺序。
经过这三次反转操作后，数组就被成功地旋转了 k 个位置。
这种方法的关键在于理解如何通过反转操作来重新排列数组中的元素。它避免了使用额外的空间，并且时间复杂度为 O(n)，其中 n 是数组的长度。
回文链表
class PalindromeList
{
public:
bool chkPalindrome(ListNode* A)
{
// 如果链表为空或者只有一个节点，那么它一定是回文的
if (A == nullptr || A->next == nullptr)
return true;
// 快慢指针找出中间节点，slow 指针指向链表中间位置（如果链表长度是奇数，则指向中间节点；如果是偶数，则指向中间两个节点的第一个）
ListNode* slow = A;
ListNode* fast = A;
while (fast != nullptr && fast->next != nullptr)
{
fast = fast->next->next;
slow = slow->next;
}
// 反转后半部分链表，prev 指针指向反转后的链表头部
ListNode* prev = nullptr;
ListNode* curr = slow;
while (curr != nullptr)
{
ListNode* temp = curr->next;
curr->next = prev;
prev = curr;
curr = temp;
}
// 检查回文，p1 指针指向链表头部，p2 指针指向反转后的链表头部
ListNode* p1 = A;
ListNode* p2 = prev;
while (p1 != nullptr && p2 != nullptr)
{
// 如果节点值不相等，则链表不是回文的
if (p1->val != p2->val)
{
return false;
}
p1 = p1->next;
p2 = p2->next;
}
// 链表是回文的
return true;
}
};
找中间节点
// 快慢指针找出中间节点，slow 指针指向链表中间位置（如果链表长度是奇数，则指向中间节点；如果是偶数，则指向中间两个节点的第一个）
ListNode* slow = A;
ListNode* fast = A;
while (fast != nullptr && fast->next != nullptr)
{
fast = fast->next->next;
slow = slow->next;
}
定义了两个指针 slow 和 fast，初始时它们都指向链表的头部。在循环中，fast 指针每次向前移动两步，而 slow 指针每次向前移动一步。当 fast 指针到达链表的末尾时，slow 指针就会指向链表的中间位置。
- 该步骤用来分割链表，以便后续操作
反转后半链表
// 反转后半部分链表，prev 指针指向反转后的链表头部
ListNode* prev = nullptr;
ListNode* curr = slow;
while (curr != nullptr)
{
ListNode* temp = curr->next;
curr->next = prev;
prev = curr;
curr = temp;
}
就是将后半部分的链表每个节点
next指向前一个节点，这样就形成了反转链表，链表头是翻转前的最后一个节点。
值得注意：前半部分的最后一个节点的next还是指向翻转前的后半部分第一个节点（也就是后半部分反转后的最后一个节点），所以在后续进行判断两个链表是否相同的时候直接向后进行判断就可以。
检查两个链表
// 检查回文，p1 指针指向链表头部，p2 指针指向反转后的链表头部
ListNode* p1 = A;
ListNode* p2 = prev;
while (p1 != nullptr && p2 != nullptr)
{
// 如果节点值不相等，则链表不是回文的
if (p1->val != p2->val)
{
return false;
}
p1 = p1->next;
p2 = p2->next;
}
// 链表是回文的
return true;
}
使用一个循环来比较两个指针所指向的节点值。如果发现任何一个节点值不相等，就意味着链表不是回文的，我们直接返回 false。如果循环完成后都没有发现不相等的节点值，那么链表就是回文的，我们返回 true。
相交链表
class Solution
{
public:
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB)
{
if (headA == nullptr || headB == nullptr)
{
return nullptr;
}
ListNode* pA = headA, * pB = headB;
// 如果有交点，那么在第一次相同的时候就会返回pa
while (pA != pB)
{
pA = pA == nullptr ? headB : pA->next;
pB = pB == nullptr ? headA : pB->next;
}
// 换道思想，如果两个链表长度不同，可以理解为补长度，
// 然后重新回到另一个链表的头的那个长度和和另一个指针指向剩余的长度相同，然后就可以达到一个相同的交点
return pA;
}
};
对于以下代码可能理解的时候存在一些误区，所以我作出以下思路整理：
while (pA != pB)
{
pA = pA == nullptr ? headB : pA->next;
pB = pB == nullptr ? headA : pB->next;
}
// 换道思想，如果两个链表长度不同，可以理解为补长度，
// 然后重新回到另一个链表的头的那个长度和和另一个指针指向剩余的长度相同，然后就可以达到一个相同的交点
return pA;
- 假设链表 A 和链表 B 的长度不同，我们让指针从另一个链表的头部重新开始遍历，实际上就是将短链表的指针向前移动了长度差的距离，以此来“补齐长度”。
- 当两个指针再次开始从头部出发时，它们之间的距离就会相等，这时它们就像在同一起跑线上开始了新的竞赛。
- 当两个指针在两个链表中遍历时，它们会同时移动相同的步数。这样，当它们到达交点时，它们就会处于相同的位置，即使两个链表的长度不同。