Leetcode编程练习

news/2024/10/19 9:42:10/

面试题-消失的数字

. - 力扣（LeetCode）

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);}
};
  1. 初始化:
    • int N = nums.size();：获取输入数组 nums 的大小，这表示从0到N-1的连续整数中应该有多少个数字。
    • int x = 0;：初始化一个变量 x，用于存储异或运算的结果。
  2. 第一个for循环:
    • 遍历数组 nums 中的每一个元素，并与 x 进行异或运算。
    • 因为异或运算的性质是：任何数与0异或都等于它本身；任何数与自身异或都等于0。所以，当遍历完数组后，x 中存储的是从0到N-1的所有整数与数组 nums 中实际存在的整数的异或结果。
  3. 第二个for循环:
    • 这个循环从0开始，到N（包括N）结束，与 x 进行异或运算。
    • 理想情况下，如果数组 nums 是完整的，即包含从0到N-1的所有整数，那么在这个循环结束后，x 的值应该是0（因为所有数字都异或了自己，结果为0）。
    • 但是，由于数组 nums 中缺失了一个数字，所以在这个循环结束后，x 的值将是缺失的那个数字（因为缺失的那个数字只被异或了一次，而其他数字都被异或了两次，结果为0）。
  4. 返回结果:
    • 最后，函数返回 x，即缺失的那个数字。

注意：第二个for循环中的 j 是从0遍历到 N（包括N），但实际上，当 j 等于 N 时，它并不与任何数组中的元素异或（因为数组索引是从0到N-1），但这并不影响结果，因为 N 与任何其他数字异或都会得到非零值（除非该数字也是 N，但这种情况不可能发生，因为数组中不可能有 N 这个元素）。

轮转数组

. - 力扣（LeetCode）

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);}
};
  1. reverse 函数是一个辅助函数，用于反转数组 nums 中从索引 start 到 end（不包括 end）的部分。这个函数使用了双指针法，从两端开始交换元素，直到两个指针相遇或交叉。
  2. rotate 函数是主要的旋转函数。首先，它对 k 取模数组的长度 nums.size()，以确保 k 不会超出数组的范围。这是因为如果 k 大于数组的长度，那么实际上只需要旋转 k % nums.size() 次即可。
  3. 接下来，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;// 如果有交点，那么在第一次相同的时候就会返回pawhile (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;

image.png

  1. 假设链表 A 和链表 B 的长度不同，我们让指针从另一个链表的头部重新开始遍历，实际上就是将短链表的指针向前移动了长度差的距离，以此来“补齐长度”。
  2. 当两个指针再次开始从头部出发时，它们之间的距离就会相等，这时它们就像在同一起跑线上开始了新的竞赛。
  3. 当两个指针在两个链表中遍历时，它们会同时移动相同的步数。这样，当它们到达交点时，它们就会处于相同的位置，即使两个链表的长度不同。

http://www.ppmy.cn/news/1455296.html

相关文章

我独自升级：崛起怎么下载 我独自升级游戏下载教程分享

我独自升级：崛起怎么下载 我独自升级游戏下载教程分享

定于5月8日全球揭幕的《我独自升级崛起》——一款扣人心弦的动作RPG巨制&#xff0c;灵感采撷于同名动画及网络漫画的热潮&#xff0c;誓将引领满怀热忱的玩家步入一场交织着深邃探索和宏大规模的奇妙冒险。该游戏立足于一个独树一帜的网络武侠宇宙&#xff0c;细腻刻画了一个凡…
阅读更多...
SV-1031 32路网络消防报警矩阵

SV-1031 32路网络消防报警矩阵

SV-1031 32路网络消防报警矩阵 18123651365 一、描述 SV-1031是深圳锐科达电子有限公司的一款机架式网络消防报警矩阵&#xff0c;具有10/100M以太网接口&#xff0c;并提供32路消防报警通道输入端子&#xff0c;可以直接连接烟感输出或报警设备开关量输出。当SV-1031的消防报…
阅读更多...
MMC设备

MMC设备

MMC&#xff08;MultiMediaCard&#xff09;是一种闪存卡标准&#xff0c;用于作为便携式设备上的存储媒介&#xff0c;例如数码相机、智能手机、平板电脑、个人数字助理&#xff08;PDA&#xff09;以及其他便携式设备。MMC卡最初是由SanDisk和Siemens AG开发的&#xff0c;并…
阅读更多...
GateWay检查接口耗时

GateWay检查接口耗时

添加gateway依赖 <dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-starter-gateway</artifactId> </dependency>创建一个LogTimeGateWayFilterFactory类&#xff0c;可以不是这个名字但是后面必须是x…
阅读更多...
PHP基础【介绍，注释，更改编码，赋值，数据类型】

PHP基础【介绍，注释，更改编码，赋值，数据类型】

源码 <?php //单行注释 /* 多行注释 *///通过header()函数发送http头的请求信息用来指定页面的字符集编码 header("Content-type:text/html;Charsetutf-8"); //告诉浏览器&#xff0c;当前页面的内容类型是HTML&#xff0c;并且页面内容使用的是UTF-8编码。//ph…
阅读更多...
最原理的一集——Mathtype公式编号设置（Mathtype7.8+Word）

最原理的一集——Mathtype公式编号设置（Mathtype7.8+Word）

版本 Mathtype7.8Office2019 Word 读完本文你将会 随心所欲&#xff0c;想怎么给公式编号就怎么给公式编号&#xff0c;想从(X.1)开始&#xff0c;就从(X.1)开始大概了解Mathtype公式设置原理给作者点赞 如果你想自己跟着文章做的话 请不要在自己的论文里边直接操作&#…
阅读更多...
《大数据最全面试题-Offer直通车》目录

《大数据最全面试题-Offer直通车》目录

大数据时代已经到来&#xff0c;数据科学家、大数据工程师、数据分析师等岗位成为了热门职业。如果你正准备面试&#xff0c;想要脱颖而出&#xff0c;那么《大数据最全面试题-Offer直通车》是你的不二选择。 本书汇集了多篇超过1万字的精华内容&#xff0c;包括程序员入职新公…
阅读更多...
git stash 工作中常用命令记录

git stash 工作中常用命令记录

save 可省略, 则使用最近一次的提交记录的描述来存储 git stash save “暂存内容描述” 查看暂存列表 git stash list 获取/使用 但不删除 本次暂存内容 git stash apply 默认第一个使用其他则追加 stash{number} 即可, 例如,使用第三个(从0开始) git stash apply stash{2} 获取…
阅读更多...
最新文章

Copyright @ 2022~2023