青叶摩卡

分类

/ 注册

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

面试高频榜单思路

0篇文章 0人学习

面试高频榜单思路梳理

0篇文章 0人学习

面试高频榜单思路梳理

0篇文章 0人学习

全部文章（共136篇）

题解 | #两个链表的第一个公共结点#

倒推：如果有公共节点，那么从公共节点到链表尾部长度一定相同，又因为两条链表长度和相同，所以两者相减也一定相同。因为没法从尾部出发倒着遍历，所以只能让两个指针分别跑完自己的链表后再从另一个链表开始跑了。最后如果相遇，相遇点就是公共节点（如果没有公共节点，那么由于长度和相同，最终也会相等，只不过都是nu...

2022-12-06

0 224

题解 | #数组中的逆序对#

求逆序对一般使用归并排序的思想。假设目前在递归过程中，左右两个子数组指针为l、r。由于归并排序是先排序左右子数组，所以此时左右子数组已经有序。当data[l] > data[r]时，根据左边子数组有序的性质，左子数组中下标在l之后的数也一定大于data[r]，从而l到左子数组末尾的数与data...

2022-12-05

0 252

题解 | #第一个只出现一次的字符#

因为有大写字母所以不能只申请26空间class Solution { public: int FirstNotRepeatingChar(string str) { vector<int> cnt(58, 0); for (auto &i:...

2022-12-05

0 186

题解 | #丑数#

使用三指针法，三指针分别指向2、3、5当前的另一个乘数，由于丑数的质因子只能是2、3、5，所以需要在遍历过程中记录所有的丑数，当作另一个乘数使用。class Solution { public: int GetUglyNumber_Solution(int index) { ...

2022-12-05

0 211

题解 | #把数组排成最小的数#

class Solution { public: string PrintMinNumber(vector<int> numbers) { vector<string> ns; for (auto &i: numbers) { ...

2022-12-05

0 177

题解 | #整数中1出现的次数

设当前数为abcde...（n位）。由于a是否为1限制了1的出现次数，因此分为最高位与后面的数字两个子问题，可以递归处理。a=1，则a处的1贡献了bcde...+1次（a0000...也算一次）。a>1，则最高位为1时可贡献1000...次。计算完最高位贡献的1后，递归计算去除最高位后的数字贡...

2022-12-05

0 231

题解 | #连续子数组的最大和#

本质上是动态规划，设以下标为i结尾的子数组最大和为dp[i]，转移方程为dp[i] = max(0, dp[i - 1]) + array[i]。（如果之前的子数组对和的贡献度为负，那么不如舍弃之前的子数组直接选择当前元素）然后再使用一个res变量记录dp[i]的最大值。由于dp[i]只与dp[i-...

2022-12-05

0 211

题解 | #最小的K个数#

基本思路：寻找最大/最小的k个数，用优先队列（堆）做。因为每次堆超出k个数时需要把堆顶，即最大的那个数pop，所以需要维护大顶堆。class Solution { public: vector<int> GetLeastNumbers_Solution(vector<int...

2022-12-05

0 268

题解 | #数组中出现次数超过一半的数字#

摩尔投票法，因为题目保证有解所以最后可以免去验证的步骤class Solution { public: int MoreThanHalfNum_Solution(vector<int> numbers) { int res, cnt = 0; fo...

2022-12-05

0 218

题解 | #字符串的排列#

回溯算法：加入去重操作class Solution { public: void dfs(vector<string>& res, vector<bool>& used, string& path, string& str) { ...

2022-12-05

0 264