fancycarp
fancycarp
全部文章
分类
题解(44)
归档
标签
去牛客网
登录
/
注册
fancycarp的博客
全部文章
(共44篇)
NC102 #在二叉树中找到两个节点的最近公共祖先#
用DFS如果root->val等于o1或者o2,就返回o1或者o2。如果左右子树一个返回o1一个返回o2,那就返回当前节点的val,因为这就是要找的节点。如果左右子树中有某一个返回了不是-1也不是o1或o2,那就说明那底下有要找的节点,直接返回他返回的值。如果都不是就返回-1。 class S...
DFS
递归
2021-05-09
1
412
NC40 #两个链表生成相加链表#
先反转链表,然后逐个加和并计算进位,最后再反转回来。 class Solution { public: ListNode* reverse(ListNode* head) { ListNode *pre = nullptr, *cur = head, *next = ...
链表
2021-05-09
0
372
NC66 #两个链表的第一个公共结点#
两个指针分别把两个链表a,b各走一遍,因为len(a + b) = len(b + a),所以相遇的时候就是第一个公共节点了。 class Solution { public: ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode...
链表
双指针
2021-05-08
0
355
NC127 #最长公共子串#
经典的动态规划题目。dp[i][j]表示以字符串str1 i位置结尾,以字符串str2 j位置结尾的公共字串的长度。状态转移方程:dp[i][j] = dp[i -1][j - 1] + 1, str1[i] == str2[j]dp[i][j] = 0, str1[i] != str2[j] cl...
动态规划
2021-05-08
0
394
NC14 #二叉树的之字形层序遍历#
同样是用队列维护,但是多用了一个栈用来反转。 class Solution { public: vector<vector<int> > zigzagLevelOrder(TreeNode* root) { vector<vector<in...
栈
队列
2021-05-08
1
381
题解 | #大数加法#
维护一个进位和一个当前位,从后往前迭代就行。注意补0. class Solution { public: string solve(string s, string t) { int slen = s.size(), tlen = t.size(); stac...
字符串
2021-05-08
0
352
NC53 #删除链表的倒数第n个节点#
先便利一遍查数,然后再走一遍删节点。 class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { int count = 0; ListNode *pHead = h...
链表
双指针
2021-05-08
0
485
题解 | #链表中环的入口节点#
用快慢指针,分别从两指针相遇位置和头指针位置出发两个相同速度的指针,相遇的位置就是环开始的位置。 class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode *fast = head, *...
双指针
2021-05-06
0
322
题解 | #括号序列#
用一个栈维护。 class Solution { public: bool isValid(string s) { stack<int> stk; int len = s.size(); for(int i = 0; i < ...
栈
2021-05-06
0
362
题解 | #合并两个有序的数组#
从后往前看,依次添加到A数组的末尾。 class Solution { public: void merge(int A[], int m, int B[], int n) { int i = m - 1, j = n - 1, index = m + n - 1; ...
归并
2021-05-06
0
300
首页
上一页
1
2
3
4
5
下一页
末页