- 在线时间
- 3 小时
- 最后登录
- 2015-5-5
- 注册时间
- 2015-4-8
- 听众数
- 10
- 收听数
- 0
- 能力
- 0 分
- 体力
- 92 点
- 威望
- 0 点
- 阅读权限
- 20
- 积分
- 43
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 26
- 主题
- 14
- 精华
- 0
- 分享
- 0
- 好友
- 7
升级   40% TA的每日心情 | 慵懒 2015-5-5 09:46 |
|---|
签到天数: 10 天 [LV.3]偶尔看看II
- 自我介绍
- 撒
 |
LeetCode 对基础数据结构和基础算法是很好的训练和考查。7 @) z& W6 n* s# r
/ c. |8 T+ ?% a! ^
(1)涉及的重要数据结构:
. V3 z1 r7 b5 u) L. S数组(一维,多维),链表,栈,队列,二叉树,无向图,散列,。。。
* u+ X7 e' v3 n) x, G% \* s
- w' o; m$ j3 n" `- b+ Q" q(2)涉及的重要算法技术:
4 m9 J% H( S7 }/ f贪心,动态规划,分治(递归),回溯(剪枝),搜索(广搜,深搜),。。。1 ]# K% A8 _, k; A, `* J
1 z# Y! T7 n0 |! l* g* K4 L
刷题后的一些体会(以下说法不绝对):7 N/ S6 V. G/ _8 c2 {; |* D
9 p& {1 N; h+ ]6 }! | }1,一般来说,贪心的时间复杂度在O(n),空间复杂度是O(1) 或 O(n) 。
) q6 [2 F R( S4 Q$ b2,动规需要记录表(标记数组),时间复杂度经常是O(n^2),空间复杂度也通常是O(n^2) 。
$ ^1 z- A+ b. I" @2 T3,回溯很常见,重点是确定何时找到一个解、何时退出、越界时如何处理;通常需要一个线性结构来保存前面的状态,以便回溯时使用。$ C! j% H9 v4 }) T, k# i( M
4,如果贪心、动规等方法都行不通,通常就考虑搜索来解决。2 c/ J3 B" ?( T! B
5,线性时间复杂度一般通过贪心方法实现;有时候,需要借助HASH结构(如unordered_map)。
/ b' ~1 n1 K/ s# J6,利用好栈(stack)!很多问题通过栈能够在O(n) 时间内解决。1 L9 f+ B7 i X! r7 w
7,深度优先搜索一般是递归的,数据过大时,递归深度太大出现问题;广度优先搜索一般借助队列,一般不需要递归。
) G- _5 x: R* t& M2 G3 P4 C+ k( ?1 M8,初始化数组时,memset(address, value, n_bytes) (包含在cstring.h) 是针对“字节”赋值!所以除非是单字节元素,或者初值为0或者-1,否则不要用memset 初始化;使用vector 比较方便。
: ]1 [! I& y+ q' \8 M9,必要时,使用unordered_map, unordered_set 等C++ 容器。
1 [& O) ~5 w% R/ N" H10,必要时,利用类变量简化传参。( t; C: N9 @+ X4 L7 k
11,动规的关键是找到转移方程;因此动规的子问题具有“累积”性质。
; K" R2 ?# y2 }5 Y; w5 e" o12,贪心不同于动规,贪心的子问题不是“累积性“,而是具有“决定性”。
$ ?1 _. P u6 c: B: Z7 g13,写代码最重要的是思路清楚、可理解性,而不是纠结变量少、代码短等无关紧要的问题。
' _- s( i1 K f7 w6 _4 ?14,由于单链表只能从前向后遍历,因此操作时经常需要保存所关心结点的前趋结点。
# N' W1 M) b$ Y; U& ]$ g! U' q15,处理链表要时刻注意检查空指针NULL。; Q) [8 o% w( }0 C# R W7 K
16,数组检索、定位快;链表插入、删除快(不需要移动数据)。! Z& N$ v, _5 q, N" E0 U7 c0 U
17,vector, string 的性质都倾向于数组;List 的性质倾向于链表。6 u) W$ Z8 j' M$ U) u
18,二叉树问题的基础是遍历方法:前序/中序/后续,递归与非递归都很重要。$ O& z) _# M2 p/ j
19,关于二叉树的问题,有些是自顶向下的;也有些是自底向上的,如检查平衡二叉树。通常这两类问题都可以通过递归、非递归两种方法解决。
' B: I+ c; H' M! W2 V3 {20,二叉树非递归遍历:前序遍历最简单,当前结点没有左儿子时,栈顶就是下一个结点;中序遍历需要先将当前结点(顶点)入栈,当前结点没有左儿子时,访问栈顶,并且栈内结点的头一个非空右儿子是下一个结点;后序遍历最后访问根结点,所以,顶点不仅要入栈,而且要记录是否访问了它的右儿子,只有访问了顶点的右儿子之后才能访问它自己。0 t) P! X3 k! g; p
21,许多问题需要应用二叉树遍历方法,有些问题需要在结点入栈的同时保存当前状态(如求最长路径)。
2 Q6 j, } c# J( b' U3 N; h22,二叉树Level 遍历的本质是广度优先搜索,需要利用队列。" B& i, Y9 L* V; V( S6 L
23,关于”图“,LeetCode 只有一道遍历题目,需要到其他地方补充一下。
# z7 x/ H; C, r4 t, P24,有些方法虽然AC 了,但并不一定是最优美的。4 B& H6 S5 u+ h- A5 ]0 N+ `
4 r5 s' ?. v/ V& }% k4 y(未完待续)( L1 m# ?3 L+ Q0 n1 y7 t$ ?; Z2 ]
|
zan
|