查看全部 130 个回答
I see it time and again in Google interviews or new-grad hires: The way data structures and algorithms—among the most important subjects in a proper computer science curriculum—are learnt is often insufficient. That's not to say students read the wrong books (see my recommendation below) or professors teach the wrong material, but how students ultimately come to understand the subject is lacking.
The key to a solid foundation in data structures and algorithms is not an exhaustive survey of every conceivable data structure and its subforms, with memorization of each's Big-O value and amortized cost. Such knowledge is great and impressive if you've got it, but you will rarely need it. For better or worse, your career will likely never require you to implement a red-black tree node removal algorithm. But you ought be able—with complete ease!—to identify when a binary search tree is a useful solution to a problem, because you will often need that skill.
So stop trying to memorize everything. Instead, start with the basics and learn to do two things:
Visualize the data structure. Intuitively understand what the data structurelooks like, what it feels like to use it, and how it is structured both in the abstract and physically in your computer's memory. This is the single most important thing you can do, and it is useful from the simplest queues and stacks up through the most complicated self-balancing tree. Draw it, visualize it in your head, whatever you need to do: Understand the structure intuitively.
Learn when and how to use different data structures and their algorithms in your own code. This is harder as a student, as the problem assignments you'll work through just won't impart this knowledge. That's fine. Realize you won't master data structures until you are working on a real-world problem and discover that a hash is the solution to your performance woes. But even as a student you should focus on learning not the minutia details but the practicalities: When do you want a hash? When do you want a tree? When is a min-heap the right solution?所以,不要试图记住所有的东西.而是从基础开始,做两件事:
第一件事. 把数据结构图形化,视觉化.(突然想起来我高中竞赛老师说的一句话:数形结合千般好,一旦不做万事休啊! 就是要画图! )在直觉上感受一个数据结构是什么样子的.使用它是什么感觉,抽象上和具体实现上是什么样子的.这就是最重要的事情.并且无论是对于简单的队列,栈还是天杀的平衡树都很重要而且有效.把数据结构画出来,在你的脑袋瓜里面就能想象出来,总之,你需要做的就是,直观的去了解这些数据结构.
第二件事.学习什么时候用什么样的数据结构和算法.对于学生来说这很难,而且你要做作业的时候老师也没告诉你们这该怎么办.╮(￣▽￣")╭ 不过没关系. 你要认识到当你真正处理到现实问题的时候或许你才能掌握某些数据结构,比如哈希表.但是即使是个学生,你也应该知道数据结构的实用性:什么时候你需要个哈希表,什么时候你需要个树,什么时候你需要个堆? 而不是一开始就陷入到追求细节中去.
One of the questions I ask in Google engineering interviews has a binary search tree as a potential solution (among others). Good candidates can arrive at the binary search tree as the right path in a few minutes, and then take 10-15 minutes working through the rest of the problem and the other roadblocks I toss out. But occasionally I get a candidate who intuitively understands trees and can visualize the problem I'm presenting. They might stumble on the exact algorithmic complexity of some operation, but they can respond to roadblocks without pause because they can visualize the tree. They get it.
As for a book, there is but one: Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, otherwise known as CLRS.
If you want another text, perhaps one with more examples in a specific language, I recommend Robert Sedgewick's Algorithms in C++