Xaiver_97-CSDN博客

原创 LeetCode 718. 最长重复子数组/最长公共子串(C++)

唯一的不同就在于，最长子序列允许序列并非连续的，而最长子数组（子串）要求序列是连续的。而“12”和“32”子串在dp数组中保存的值就为1，因此它们最后一位相等，然后再往前找，发现不相等，于是最长就为1。我们可以看到，经过这样的滑动窗口之后，数组1的每个数都和数组2的每一个数对齐进行了一次匹配比较，因此只需要记录下匹配过程中的最大子串就完成了整个过程。在暴力解法中，我们开始计算公共子串的长度的步骤总是等到两个数组的当前元素相等的时候才开始，但是两个元素相等的位置我们根本不知道在哪，所以任何地方都有可能，即。

2022-09-27 22:26:42 694 1

原创 LeetCode 1143. 最长公共子序列(C++)

若我们用二维表格的代替dp数组，我们会发现，点(i, j)可能会依赖于其上边(i-1, j)，左边(i, j-1)，以及左上方(i-1, j-1)的值，因此我们需要从头开始迭代来计算出表格中的每一个数值，最后取右下角的数值即为最终的结果。在上面的代码中，我们开辟的数组行和列都比实际的长度要多一位，这是因为我们比较两个字符串第一位dp[0][0]的时候也需要利用上一个状态，而上一个状态有可能是dp[-1][-1], dp[-1][0], dp[0][-1]。，这个不需要证明，显然可以得出这样的结论。

2022-09-20 19:51:34 498

原创 LeetCode 2085. 统计出现过一次的公共字符串(C++)

对于word1中的每一个字符串，判断其在word1中是否只出现了一次，而且也在word2中也恰好出现一次，若满足条件，计数器加1。这种方法不需要额外的空间，但是耗时很高。我们可以遍历两个数组，以哈希表来存储其中出现的元素，若出现一次则为true，若出现多余一次则为false。最后再遍历一遍哈希表即可。遍历、哈希表、STL方法。

2022-09-19 17:09:07 402

原创 C++实现四舍五入的几种方法

要得到四舍五入小数点后的结果，我们可以将小数转换为整数来处理，然后再转换为小数。例如我们需要将1.2345这个数保留小数点后两位四舍五入，我们可以先将其乘以100转换为123.45，然后套用整数的方法来进行四舍五入，再将其除以100转换为小数。fixed(std::fixed)表示用于setpricision的有效数字针对的是小数点后的有效数字。若只需要得到四舍五入的输出，那我们可以利用printf来进行输出，选择保留小数点后0位，即可达到四舍五入的目的。

2022-09-19 14:40:09 41144 1

原创 LeetCode 23. 合并K个升序链表(C++)

对于数组中每个链表我们在头部都放置一个指针，将最小的元素放进结果链表中。一种简单的思路就是每次进行两两合并，比如以第一个链表最为最终链表，那么把剩下的链表都合并到第一个链表上来。还需要判断一下数组中没有链表和只有一个链表的情况。这种方法的缺点就是要扫描第一个链表很多遍，会产生重复的对比，因此时间复杂度比较高，但是不需要额外的空间，因此空间复杂度较低。我们可以采用归并的算法使得链表两两合并，这样能够使得合并步骤的时间复杂度由k降为logk级别，因此下面采用归并的方法合并。

2022-09-16 21:14:01 225

原创 LeetCode 46. 全排列(C++)

因此回溯要求的就是我们可以回到上一步的状态，看看是否有其他的选择，如果有的话就输出下一种选择。因此我们可以用一张表来记录哪些元素当前是已经选择了的，在回退的时候修改这张表就可以了。这道题要输出所有的数的全排列，首先我们可以想到的是依次选数，假设数组的大小为3，那么第一个位置就有3种选择，三种选择下面对应的第二个位置又分别有两种选择，第三个位置没有选择。用队列记录下每一层的所有情况，并在下层遍历的时候，根据上层的每一项分别添加上每一种可能加入队列，直到所有数都被选择进队列。广度优先遍历、回溯、树形结构。

2022-09-16 13:22:47 469

原创 LeetCode 103. 二叉树的锯齿形层序遍历(C++)

实现锯齿形遍历，首先发现这道题要求是层序遍历，和层序遍历不相同的地方就在于它每隔一行就会由“从右向左”变为“从左向右”，依次在这两个状态之间转换。那么很容易想到的就是使用标志位来判断到底应该是哪个状态，同时由于从右向左和从左向右对节点顺序有要求，那么使用双端队列或者双栈就成了很容易想到的解法。二叉树层序遍历、双端队列。

2022-09-15 23:26:28 812

原创 LeetCode 257. 二叉树的所有路径(C++)

使用先序遍历，使用字符串记录下已经经历过的节点，若找到叶子节点，则把叶子结点经过的路径加入结果中。若并非叶子节点，则加入“->”，接着遍历左右孩子。想要找到二叉树的所有路径，也就是找到所有的子节点，那么必然会涉及到二叉树的遍历。因此我们可以采用深度优先的方法（先、中、后序遍历），也可以采用广度优先的方法（层序遍历）。广度优先的方法则需要维护两个队列，一个队列用于层序遍历，另一个队列用于存储根节点到第一个队列中每个节点的路径，因此广度优先写起来比较麻烦，这也就暂时不写这个方法了。

2022-09-15 22:07:04 333

原创 LeetCode 236. 二叉树的最近公共祖先(C++)

其核心思想就是，对于某个节点（假设为curNode）来说，假设我找到了一个左孩子或者右孩子是p或者q，那么我就不需要继续往下递归找我的子树了，我只需要往上返回这个节点（假设为findNode）即可，让上层节点（curNode的父节点）判断它的右子树情况，若上层节点的右子树没找到p或者q，说明剩下一个一定在findNode的子树里面。由于我们判断的是左子树或右子树是否包含p或q，因此在第一种情况并非一定要祖先的左右节点正好是p,q，而是祖先的左子树中包含p，右子树中包含q即可。这样我们就可以使用这个方法了。

2022-09-14 15:36:53 639

原创 LeetCode 5. 最长回文子串(C++)

一个字符串是否是回文串，可以分解为更小规模的问题，比如一个字符串str = "abba" 是否为回文串，首先我可以判断str[0] == str[3]，也就是最左边和最右边做判断。例如字符串总长为4，若我们的从第二行看（i=1），其子串只可能为str[1][2], str[1][3], str[1][4]，即只需要3个空间来记录。对于每个字符，都可能是单中心或者双中心，因此在遍历的时候我们需要考虑单中心（回文子串长度为奇）和双中心（回文子串长度为偶数）两种情况，取两种情况的最大者作为我们最终的结果。

2022-09-13 14:56:04 4267 1

原创利用union判断CPU大小端以及大小端转换(C++)

0x12345678。这个数的低位，指的就是右边，比如78就是低位。而高位指的就是左边，比如12就是高位。常见的处理器如X86、ARM等一般用的都是小端，其中某些处理器可以设置大小端。我们知道存放一个数的内存地址一般是连续的，那么就有两种情况，我们可以利用union来查看自己的机器是大端还是小端存储。，这样整个数在内存中看起来就是顺序排列的。，高位的字节放在内存高地址。这样整个数在内存中看起来就像是逆序排列的。，低位的字节放在内存高地址。

2022-09-11 23:27:52 690

原创 LeetCode 200. 岛屿数量(C++)

思路：我们从题目中可以得知，孤立的岛屿旁边全是海，假设岛屿范围内每一个‘1’是岛屿的一部分，那么我们从岛屿的任意一部分登岛，走遍岛屿的每一块土地，就能确定岛屿的大小和范围。为了找遍所有的岛屿，我们还需要把走过的土地都标记为0，防止从同一岛屿的另一部分登岛。记录岛屿的数量加1，再继续找还没有'1'的部分，走遍下一个岛屿。比如下面的例子，不同颜色的'1'表示不同岛屿的一部分。对于这道题来说，广度优先遍历值得注意的地方在于，要先把当前出队的元素上下左右置0（若有岛屿部分），然后再把那些置过0的元素入队。

2022-09-11 19:37:20 1633

原创 LeetCode 33. 搜索旋转排序数组(C++)

其实还有第三种情况，就是反转的位置正好在mid，这种情况和第一种情况的处理方式其实是一样的。我们可以发现，在所有可能的情况里，mid位置的元素和right位置的元素只有两种可能性，分别是mid位置元素 > right位置元素， mid位置元素 < right位置元素，由于题目保证了数组中没有相同元素，因此第一次二分查找不可能出现等于的情况。1、当mid位置元素 > right位置元素时（说明原数组的头在mid位置右边），mid元素及其左边是严格升序的，这意味着唯一可能出现失序的情况在mid右边。

2022-09-10 22:18:15 464

原创 LeetCode 429. n-叉树的层序遍历(C++)

和二叉树类似，n叉树层序遍历也是一层一层输出节点，返回值应该是一个二维数组。我们可以用一个队列来存储每一层的节点，输出节点的时候将其孩子加入队列。同时使用一个变量来记录每一层的节点数量，当出队的节点数量等于该层节点数，就完成了当前层的遍历。以此类推，直到队列为空就说明遍历完了整棵树。n-叉树和二叉树唯一不同的地方就在于其孩子并非左右孩子两个，而是需要把当前节点的所有孩子加入队列。

2022-09-09 22:47:26 968

原创 LeetCode 102. 二叉树的层序遍历(C++)

思路：二叉树的层序遍历要求是一层一层输出节点，返回值应该是一个二维数组。我们可以用一个队列来存储每一层的节点，输出节点的时候将其左孩子和右孩子加入队列，这样就可以完成层序遍历。

2022-09-09 22:19:17 402

原创 LeetCode 15. 三数之和(C++)

这道题一个比较麻烦的地方就是去重，比如数组[-2, -1, -1, 0, 3, 3]，我们固定-2，当左边指针指到-1的时候可以和最右边的3匹配使总和为0，此时将答案记录下来，将左边指针和右边指针同时向中间移动，但是会发现又碰到了-1和3，这样就会出现重复的三元组，不符合题目的要求。因此这道题需要对固定的第一个数进行去重，左指针和右指针的数也需要去重。由于当前数组是排序过后的，因此已经是有序的，所以右边的数一定比左边的大，因此我们固定的数必须要小于0，才有可能使得其和后面两个数加在一起等于0。

2022-09-09 21:59:00 207

原创 LeetCode 25. K个一组翻转链表(C++)

比如翻转后的子链需要连接到原链最后一个节点的next，但是如果是第一个翻转的子链就没有上一个节点，因此这里本来需要进行特殊的if判断，我们引入哨兵节点之后就可以统一化处理。还需要注意的地方就是，这道题如果最后剩余的元素不到k，那么最后就不进行翻转，因此我们需要先探路，探路后发现长度满足条件再进行翻转。尾插法则比上一种方法要更加简洁，其思想是找到待翻转部分的头和尾，将从头开始一个个把节点接在尾的后面，这样的好处就是翻转完之后当前部分和下一部分还是非常自然的接在一起的。

2022-09-08 20:31:14 255

原创常见的十种排序算法C++实现（附时空复杂度，稳定性分析）

每一轮排序使得当前无序的部分的最大值冒到当前无序数组的末尾，下一轮中无序部分的长度等于上一轮减一，原数组的末端不断的变成有序的部分。时间复杂度最坏和平均情况是O()，最好的情况是已经有序所以是O(n)，空间复杂度O(1)，且因为两个相同的元素是不会交换位置的，因此是一种稳定的排序。

2022-09-07 17:54:56 3121

原创 LeetCode 122. 买卖股票的最佳时机 II(C++)

思路：通过历史最小值来判断哪一天买入，然后通过当前节点往后看是否跌了来判断是否卖出，感觉也类似于贪心。但是买股票用贪心的方法本来就是收益最大化的手段啊。思路：某一天的利润等于max(前一天的利润，前一天的利润加上昨天买今天卖的利润)

2022-09-04 16:54:41 281

原创 LeetCode 14. 最长公共前缀(C++)

思路：既然要找公共子前缀，那么直接遍历整个数组，首先看一个字母是不是，是的话看两个字母是不，以此类推。要注意的是，公共子前缀的最长长度不超过数组中最短的字符串长度。因此可以先通过一轮遍历找出数组中最短的字符串。再进行正式的比较操作。思路：对于数组中每一个字符串，依次比较它们的第一位是否一样，是的话就继续检查第二位，直至检查到某个字符串末尾，时间复杂度是O(mn)，空间复杂度O(1)

2022-09-04 15:28:30 1466

原创 LeetCode 226. 翻转二叉树(C++)

翻转二叉树这道题目，根据力扣上的图示可以很好的理解，就是左子树和右子树交换位置，左子树的左子树和左子树的右子树交换位置，以此类推，因此这道题目应该是一道递归很好解的题目。

2022-09-03 22:48:40 182

原创 LeetCode 169. 多数元素(C++)

显然，因为目标值超过数组长度的一半，那么只需返回排序之后中间的结果即可。

2022-09-03 21:52:38 255

原创 LeetCode 234. 回文链表(C++)

这种方法需要一个额外的节点用来保存链表头结点，并且在递归到达最里层的时候往后走，这样就可以实现头指针向后，尾指针向前对比。解法1的问题在于要开辟额外数组，递归虽然不用开辟额外空间，但是需要占用系统栈的空间，而且效率可能还更差。

2022-09-03 19:25:04 301

原创 LeetCode 112. 路径总和(C++)

这道题思路比较简单，但是要注意的是，一定要找到叶子结点才能判断是否满足，因此一定要遍历完所有的叶子结点，那么很容易想到的就是DFS，因此可以采用递归的方法。

2022-09-02 17:39:02 196

原创 LeetCode 543. 二叉树的直径 (C++)

这道题我觉得官方题解有点难懂，反而是我自己的思路更好想明白这个问题。根据题目定义，某个根节点二叉树的直径实际上就是其左子树的深度加上右子树深度之和，因此求深度的问题很容易想到使用DFS递归。但是呢，问题在于二叉树的最大直径并非是一定经过根节点的，因此所有节点都有机会得到最大的直径，所以我们可以设置一个全局的最大直径并不断对其进行更新。

2022-09-02 15:28:50 205

原创 LeetCode 101. 对称二叉树 (C++)

树对称，则说明从根往下走，根的左孩子的情况和根的右孩子情况相同（即要空都是空，不空的话值一定相等），根左孩子的左孩子情况与根右孩子的右孩子情况相同。思路：很容易想到的是树的层次遍历，因此需要队列。可以用一个队列存左子树的情况，一个队列存右子树的情况，然后比较即可。但是想一想，也可以不需要两个队列，一个队列就能搞定，只要依次序交叉存左孩子和右孩子的情况即可。那么在比较的时候，一次弹出两个元素就可以了。

2022-09-01 23:30:11 194

原创 LeetCode 110.平衡二叉树 (C++)

平衡二叉树，指的就是每个节点的左右子树高度相差不超过1的树思路：首先需要知道左子树和右子树的高度，那么可以定义一个depth函数求高度，要求高度那么很显然是递归函数，从上向下找到最高的再返回上来。总的判断二叉树平衡又需要满足三个条件：1、当前节点是平衡的2、当前节点的左子树是平衡的3、当前节点的右子树是平衡的因此判断是否平衡的函数也是一个递归函数。这种解法容易想到，但是有一个问题在于很多操作都重复求了同一个节点的高度，因此这种方法的时间复杂度较高。

2022-09-01 21:02:02 357

原创 LeetCode 145.二叉树的后序遍历 (C++)

二叉树后序遍历的Morris方法可以说是最难的，主要思想还是把左子树的最右节点指向根节点。然后回来的时候把指针给取消。但是不同的地方就在于打印的时候要么是只打印左孩子单个叶子节点，要么就是打印根节点及其右孩子叶子节点，因此每次打印的时候需要使用reverse来反转一下，而且最后树的总的根节点需要单独打印，所以最后会对root进行单独的打印操作。二叉树的后序遍历就是，左 -> 右 -> 根，这样的次序。解法1：递归，这个模板是前中后通用的。解法2：迭代（手动建栈模拟系统操作）解法3：Morris遍历。

2022-09-01 17:44:23 213

原创 LeetCode 155.最小栈 (C++)

解法1：可以使用multiset来对元素进行保存，因为multiset总是有序的，因此可以快速得到栈中最小的元素。具体思路：栈中不存真实的val数值，而是val与最小值之间的差值。而且只要栈中元素为负（差值为负），就说明当前的真实值就是当前的最小值。这种方法不需要额外的辅助集合或者辅助栈，只需要维护一个全局最小值即可，但是根据题目的限制，存差值的话如果栈为int型会溢出，因此必须要为long long型。解法2：辅助栈，主栈和辅助栈共同进退，唯一不同的就是辅助栈保存的是每一次操作后，当前栈中的最小值。...

2022-08-31 23:43:21 165

原创 LeetCode 144.二叉树的前序遍历 (C++)

思想还是向左遍历之前，让当前节点左子树的最右节点指向自己，这样回溯的时候就能找到。二叉树的前序遍历就是，根 -> 左 -> 右，这样的次序。解法1：递归，这个模板是前中后通用的。解法2：迭代（手动建栈模拟系统操作）解法3：Morris遍历。...

2022-08-31 21:32:56 246

原创 LeetCode 69.x的平方根 (C++)

其中带有下标的x都是迭代法每一步的近似根，而分母的不带下标的x则为想要求根的数。这道题实际上就是让你在不用sqrt()的情况下求平方根。

2022-08-31 15:40:37 219

原创 LeetCode 94.二叉树的中序遍历 (C++)

因为中序遍历的话我们需要一直深入到左子树底，这样就找不到最初的根节点了，因此这里的想法就是将二叉树改造为线索二叉树。由于根节点左子树中的最右下的节点一定是根节点中序遍历的前驱结点，因此只需要每往下找一层左子树的时候，将根节点赋给前驱结点的right即可，这样就可以找到根节点了。但是要注意的是，二叉树的遍历理论上不会改变二叉树结构，所以要保证遍历完之后所有前驱节点的right重新指向空才行，否则leetcode就会报stack over flow的问题。解法2：迭代，用栈来模拟递归调用的过程。...

2022-08-30 20:18:40 411

原创 LeetCode 160.相交链表 (C++)

大致思路就是：当第一个节点走到第一条链尾的时候，将节点放在第二条链头，然后继续走；当第二个节点走到第二条链尾的时候，将节点放在第一条链头，然后继续走。每次这两个节点都只走一步，如果他们之间有重合的部分，那么必然会在第一个地方相遇。如果没有重合的部分，那么最后就会在nullptr处相遇。假设第一条链长度为a，第二条链长度为b，长度不包括重合部分。若重合部分链长为c；那么用着个方法，节点在相遇（或同指向nullptr的时候），第一条链最后走的总长度就是a+c+b，第二条链走的总长度就是b+c+a。...

2022-08-28 19:43:17 262

原创 LeetCode 88. 合并两个有序数组(C++)

由于第一种方法从需要从nums1的头开始一直遍历到尾，因此就需要一个额外的辅助数组。然而nums1的末尾都是0，我们如果从尾一直遍历到头就可以实现原地合并。因此原来是谁小谁进去，现在变为谁大谁进去。这种方法也没啥好讲的，就是把nums2的元素先填到nums1的真实元素的后面（即那些用0占位的地方），然后调用sort对nums1排序即可。以最终的nums1数组为核心，每一个位置进行判断，到底是用copy_nums1的值还是用nums2的值，直到结尾。解法2：追加然后排序。...

2022-08-28 17:21:02 242

原创 LeetCode 20. 有效的括号(C++)

2、可以用map来存括号对，碰到s里面的字符直接找，速度很快，但是要将右括号存为key，不然碰到右括号的时候没法找。3、注意循环结束以后，只有栈为空才是正确匹配情况，如果栈还有东西说明匹配失败。1、可以先判断字符串s是不是2的倍数，如果不是，直接返回false。解法：用栈匹配的方法来判断括号是否符合。...

2022-08-27 21:35:55 128

原创 LeetCode 141. 环形链表(C++)

若链表有环，则pos的值为链表中的位置下标（从0开始编号）。其中题目中每个节点的数字是迷惑作用，思路：用一个set来把碰到过的指针都存下来，如果在遍历的过程中发现set中有这个指针，那么说明有环，返回true。给你一个链表的头节点指针head ，判断链表中是否有环。这里快指针一次走2步，走3步，甚至走更多步都可以，慢指针一定要比快指针的步子小。思路：使用一块一慢两个指针，若链表有环，慢的指针迟早都会和快的指针相遇。下面的代码是快指针一次走2步，慢指针一次走1步。还可以写成快指针一次3步，慢指针一次2步。..

2022-08-27 21:00:33 287

原创 LeetCode 121. 买卖股票的最佳时机(C++)

因为要求股票收益的最大值，因此我可以新建一个数组用来存取每两天股票价格的差值，这样N天就可以构造一个大小为N-1的数组，这个数组里面存放着每两天股票涨了多少或者跌了多少。要求股票收益最大的时候，那么只需要在每天的价格往前看，假设自己在当天以前的最低点购买，利益是多少，如果当前点的收益比全局收益更大则更新全局收益。同时保存当前以前的全局最低点。这里动态规划的思路是，下一个状态只与前一个状态有关。如果当前值减掉历史最小值大于前一个状态，当前状态就设为当前值减掉历史最小值，否则当前状态就等于前一个状态。...

2022-08-27 18:04:07 446

空空如也

PAT 1075 PAT Judge最后一个测试点死活都不过去（C语言）