2024 年 5 月 一 二 三 四 五 六 日 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 -
近期评论
没有评论可显示。
leetcode100-动态规划
70.爬楼梯
dp[i] = dp[i - 1] + dp[i - 2]- 滚动数字优化空间
- 初始值
dp[0] = 1 dp[1] = 1 dp[2] = 2 - 相比于斐波那契数列 初始值
dp[0] = 1 dp[1] = 1 dp[2] = 1
class Solution {
public:
int climbStairs(int n) {
int a = 1, b = 1, sum = 0;
for (int i = 0; i < n - 1; ++i) {
sum = a + b;
a = b;
b = sum;
}
return b;
}
};智能指针
智能指针
shared_ptr
作用
- 防止内存泄漏 析构时候自动释放
内存模型
包含两部分个指针，一个指向对象，一个指向控制块，控制块中包含reference count 引用计数 和 weak count 弱计数及其他数据
winDbg调试
静态分析 dump
- mini dump 文件较小 只包含概要内容
- 全量dump 文件较大 接近进程的虚拟内存大小
动态调试
- 附加进程
生成dump
- 通过SetUnhandledExceptionFilter注册异常处理回调函数，通过MiniDumpWriteDump生成dump文件
链表-合并链表
递归实现
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
if (!pHead1 || !pHead2)
return pHead1 ? pHead1 : pHead2;
if (pHead1->val < pHead2->val) {
pHead1->next = Merge(pHead1->next, pHead2);
return pHead1;
}
else {
pHead2->next = Merge(pHead1, pHead2->next);
return pHead2;
}
return nullptr;
}
};链表-两链表第一个公共结点
while退出时 如果有交点 则是交点位置 若无交点 则都为nullptr
走过的总长度是head1 + head2
class Solution {
public:
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
if (!pHead1 || !pHead2)
return nullptr;
ListNode *h1 = pHead1;
ListNode *h2 = pHead2;
while (h1 != h2) {
h1 = h1 ? h1->next : pHead2;
h2 = h2 ? h2->next : pHead1;
}
return h1;
}
};链表-链表倒数k个结点
k大于链表长度时 输出空
快慢指针
class Solution {
public:
ListNode* FindKthToTail(ListNode* pHead, int k) {
if (!pHead)
return pHead;
ListNode *fast = pHead;
ListNode *slow = pHead;
while (k--) {
fast = fast->next;
if (!fast && k)
return fast;
}
while(fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
};链表-反转链表
数据类型定义
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};全部反转
递归实现
链表-链表环
是否有环
迭代
class Solution {
public:
bool hasCycle(ListNode *head) {
if (!head || !head->next)
return false;
struct ListNode *fast = head;
struct ListNode *slow = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
return true;
}
return false;
}
};
while (fast) {
slow = slow->next;
fast = fast->next;
if (fast)
fast = fast->next;
else
return false;
if (slow == fast)
return true;
}