青叶摩卡

分类

/ 注册

TA的专栏 0篇文章 0人订阅

面试高频榜单思路

0篇文章 0人学习

面试高频榜单思路梳理

0篇文章 0人学习

面试高频榜单思路梳理

0篇文章 0人学习

全部文章（共136篇）

题解 | #合并两个排序的链表#

链表问题为了解题方便，一般都会建立伪头节点dummyhead。其他部分按照归并排序一样比较并尾部插入就行了。如果有一个指针指向nullptr，那么另一个指针所指链表剩下的数一定都要大于当前尾部的数，直接尾部插入即可。/* struct ListNode { int val; struct Lis...

2022-12-04

0 232

题解 | #反转链表#

递归：函数返回的是反转后的头节点，即固定为原链表中最后一个节点，所以当前函数的返回值应该与递归函数的返回值是一样的。反转之后应该由原链表中pHead->next指向的节点指向pHead，同时考虑pHead是反转后尾部的情况，应该把pHead->next置为nullptr。class So...

2022-12-03

0 286

题解 | #链表中倒数第k个结点#

快慢指针可以做到一次遍历，需要返回倒数第k个节点，我们可以看做当快指针now指向链表末尾的nullptr时，慢指针bef正好指向倒数第k个节点，所以需要一开始先让快指针now移动k个节点。为了方便处理，设置一个dummyhead作为伪头节点，bef和now都从dummyhead出发。因为样例中存在k...

2022-12-03

0 234

题解 | #调整数组顺序使奇数位于偶数前面#

本来以为需要时间复杂度O(n)，空间复杂度O(1)的解法，实在没想出来去看了官方题解，结果还是需要n方的时间复杂度。。。class Solution { public: void reOrderArray(vector<int> &array) { int...

2022-12-03

0 282

题解 | #数值的整数次方#

由于要求空间复杂度为常数，所以需要使用快速幂。以base^19为例，19对应的二进制数为10011，base^19可以分解成base^16 * base^2 * base^1，16、2、1都是2的整数次幂，可以通过base *= base快速得到。class Solution { public: ...

2022-12-03

0 300

题解 | #二进制中1的个数#

可以每次右移一位遍历统计，也可以用n & (n - 1) 快速将最低位的1消去，统计消去所有1所需的次数，即为1的个数。原理：设n的最低位1为第i位，那么n肯定是这样的形式...10...0（i - 1个0），那么n - 1的形式为...01...1（i - 1个1），可以看出n与n - 1...

2022-12-03

0 313

题解 | #矩形覆盖#

2 * i的矩形可以由2 * (i - 1)的矩形竖放一块2 * 1的矩形得到，也可以由2 * (i - 2)的矩形横放两块2 * 1的矩形得到（不能计算竖放两块2 * 1的矩形，因为竖放一块时就是2 * (i - 1)的矩形，已经计算在上一种情况中了），所以写出递推式为dp[i] = dp[i -...

2022-12-03

0 289

题解 | #跳台阶扩展问题#

第一步先写出递推式dp[n] = dp[n - 1] + dp[n - 2] + ... + dp[1]，然后观察，由于dp[n - 1] = dp[n - 2] + ... + dp[1]，化简后得到dp[n] = 2 * dp[n - 1]。class Solution { public: ...

2022-12-03

0 233

题解 | #跳台阶#

与斐波那契数一样，只是提前了一位而已。class Solution { public: int jumpFloor(int number) { if (number == 1) return 1; if (number == 2) return 2; ...

2022-12-03

0 194

题解 | #斐波那契数列#

递推式为dp[i] = dp[i - 1] + dp[i - 2]，可以递归（重复计算占用大量时间空间，可能超时），也可以建立dp数组，但是观察递推式可以发现当前值只与前两次的值有关，所以可以将dp数组缩减为三个变量。class Solution { public: int Fibonacc...

2022-12-03

0 205