-
Notifications
You must be signed in to change notification settings - Fork 27
Home
Welcome to the leetcode-csharp wiki!
借用李开复老师的一篇阐述算法的文章，解释算法的重要性。
leetcode是面试算法真题，囊括了常用算法思想和经典题目，是算法入门和提升算法实力的天堂。 做leetcode的题目有一个多月了，通过做题认识到了算法的魅力，很多题目也都总结在了csdn上，这几天我又总结到了github上，接下来，每天拿出一点时间，至少每天做一道题。算法的力量，李开复聊算法的重要性
算法的力量 算法是计算机科学领域最重要的基石之一，但却受到了国内一些程序员的冷落。许多学生看到一些公司在招聘时要求的编程语言五花八门就产生了一种误解，认为学计算机就是学各种编程语言，或者认为，学习最新的语言、技术、标准就是最好的铺路方法。其实大家都被这些公司误导了。编程语言虽然该学，但是学习计算机算法和理论更重要，因为计算机算法和理论更重要，因为计算机语言和开发平台日新月异，但万变不离其宗的是那些算法和理论，例如数据结构、算法、编译原理、计算机体系结构、关系型数据库原理等等。在“开复学生网”上，有位同学生动地把这些基础课程比拟为“内功”，把新的语言、技术、标准比拟为“外功”。整天赶时髦的人最后只懂得招式，没有功力，是不可能成为高手的。
算法与我 当我在1980年转入计算机科学系时，还没有多少人的专业方向是计算机科学。有许多其他系的人嘲笑我们说：“知道为什么只有你们系要加一个‘科学’，而没有‘物理科学系’或‘化学科学系’吗？因为人家是真的科学，不需要画蛇添足，而你们自己心虚，生怕不‘科学’，才这样欲盖弥彰。”其实，这点他们彻底弄错了。真正学懂计算机的人（不只是“编程匠”）都对数学有相当的造诣，既能用科学家的严谨思维来求证，也能用工程师的务实手段来解决问题——而这种思维和手段的最佳演绎就是“算法”。
记得我读博时写的Othello对弈软件获得了世界冠军。当时，得第二名的人认为我是靠侥幸才打赢他，不服气地问我的程序平均每秒能搜索多少步棋，当他发现我的软件在搜索效率上比他快60多倍时，才彻底服输。为什么在同样的机器上，我可以多做60倍的工作呢？这是因为我用了一个最新的算法，能够把一个指数函数转换成四个近似的表，只要用常数时间就可得到近似的答案。在这个例子中，是否用对算法才是能否赢得世界冠军的关键。
还记得1988年贝尔实验室副总裁亲自来访问我的学校，目的就是为了想了解为什么他们的语音识别系统比我开发的慢几十倍，而且，在扩大至大词汇系统后，速度差异更有几百倍之多。他们虽然买了几台超级计算机，勉强让系统跑了起来，但这么贵的计算资源让他们的产品部门很反感，因为“昂贵”的技术是没有应用前景的。在与他们探讨的过程中，我惊讶地发现一个O(nm)的动态规划(dynamic programming)居然被他们做成了O(nn*m)。更惊讶的是，他们还为此发表了不少文章，甚至为自己的算法起了一个很特别的名字，并将算法提名到一个科学会议里，希望能得到大奖。当时，贝尔实验室的研究员当然绝顶聪明，但他们全都是学数学、物理或电机出身，从未学过计算机科学或算法，才犯了这么基本的错误。我想那些人以后再也不会嘲笑学计算机科学的人了吧！
网络时代的算法 有人也许会说：“今天计算机这么快，算法还重要吗？”其实永远不会有太快的计算机，因为我们总会想出新的应用。虽然在摩尔定律的作用下，计算机的计算能力每年都在飞快增长，价格也在不断下降。可我们不要忘记，需要处理的信息量更是呈指数级的增长。现在每人每天都会创造出大量数据（照片，视频，语音，文本等等）。日益先进的纪录和存储手段使我们每个人的信息量都在爆炸式的增长。互联网的信息流量和日志容量也在飞快增长。在科学研究方面，随着研究手段的进步，数据量更是达到了前所未有的程度。无论是三维图形、海量数据处理、机器学习、语音识别，都需要极大的计算量。在网络时代，越来越多的挑战需要靠卓越的算法来解决。 再举另一个网络时代的例子。在互联网和手机搜索，如果要找附近的咖啡店，那么搜索引擎该怎么处理这个请求呢？最简单的办法就是把整个城市的咖啡馆都找出来，然后计算出它们的所在位置与你之间的距离，再进行排序，然后返回最近的结果。但该如何计算距离呢？图论里有不少算法可以解决这个问题。
这么做也许是最直观的，但绝对不是最迅速的。如果一个城市只有为数不多的咖啡馆，那么这么做应该没什么问题，反正计算量不大。但如果一个城市里有很多咖啡馆，又有很多用户都需要类似的搜索，那么服务器所承受的压力就大多了。在这种情况下，我们该怎样优化算法呢？ 首先，我们可以把整个城市的咖啡馆做一次“预处理”。比如，把一个城市分成若干个“格子(grid)”，然后根据用户所在的位置把他放到某一个格子里，只对格子里的咖啡馆进行距离排序。 问题又来了，如果格子大小一样，那么绝大多数结果都可能出现在市中心的一个格子里，而郊区的格子里只有极少的结果。在这种情况下，我们应该把市中心多分出几个格子。更进一步，格子应该是一个“树结构”，最顶层是一个大格——整个城市，然后逐层下降，格子越来越小，这样有利于用户进行精确搜索——如果在最底层的格子里搜索结果不多，用户可以逐级上升，放大搜索范围。 上述算法对咖啡馆的例子很实用，但是它具有通用性吗？答案是否定的。把咖啡馆抽象一下，它是一个“点”，如果要搜索一个“面”该怎么办呢？比如，用户想去一个水库玩，而一个水库有好几个入口，那么哪一个离用户最近呢？这个时候，上述“树结构”就要改成“r-tree”，因为树中间的每一个节点都是一个范围，一个有边界的范围（参考:http://www.cs.umd.edu/~hjs/rtrees/index.html）。 通过这个小例子，我们看到，应用程序的要求千变万化，很多时候需要把一个复杂的问题分解成若干简单的小问题，然后再选用合适的算法和数据结构。
并行算法：Google的核心优势 上面的例子在Google里就要算是小case了！每天Google的网站要处理十亿个以上的搜索，GMail要储存几千万用户的2G邮箱，Google Earth要让数十万用户同时在整个地球上遨游，并将合适的图片经过互联网提交给每个用户。如果没有好的算法，这些应用都无法成为现实。 在这些的应用中，哪怕是最基本的问题都会给传统的计算带来很大的挑战。例如，每天都有十亿以上的用户访问Google的网站，使用Google的服务，也产生很多很多的日志(Log)。因为Log每份每秒都在飞速增加，我们必须有聪明的办法来进行处理。我曾经在面试中问过关于如何对Log进行一些分析处理的问题，有很多面试者的回答虽然在逻辑上正确，但是实际应用中是几乎不可行的。按照它们的算法，即便用上几万台机器，我们的处理速度都根不上数据产生的速度。 那么Google是如何解决这些问题的？ 首先，在网络时代，就算有最好的算法，也要能在并行计算的环境下执行。在Google的数据中心，我们使用的是超大的并行计算机。但传统的并行算法运行时，效率会在增加机器数量后迅速降低，也就是说，十台机器如果有五倍的效果，增加到一千台时也许就只有几十倍的效果。这种事半功倍的代价是没有哪家公司可以负担得起的。而且，在许多并行算法中，只要一个结点犯错误，所有计算都会前功尽弃。
那么Google是如何开发出既有效率又能容错的并行计算的呢？ Google最资深的计算机科学家Jeff Dean认识到，Google所需的绝大部分数据处理都可以归结为一个简单的并行算法：Map and Reduce（http://labs.google.com/papers/mapreduce.html）。这个算法能够在很多种计算中达到相当高的效率，而且是可扩展的（也就是说，一千台机器就算不能达到一千倍的效果，至少也可以达到几百倍的效果）。Map and Reduce的另外一大特色是它可以利用大批廉价的机器组成功能强大的server farm。最后，它的容错性能异常出色，就算一个server farm宕掉一半，整个fram依然能够运行。正是因为这个天才的认识，才有了Map and Reduce算法。借助该算法，Google几乎能无限地增加计算量，与日新月异的互联网应用一同成长。
算法并不局限于计算机和网络 举一个计算机领域外的例子：在高能物理研究方面，很多实验每秒钟都能几个TB的数据量。但因为处理能力和存储能力的不足，科学家不得不把绝大部分未经处理的数据丢弃掉。可大家要知道，新元素的信息很有可能就藏在我们来不及处理的数据里面。同样的，在其他任何领域里，算法可以改变人类的生活。例如人类基因的研究，就可能因为算法而发明新的医疗方式。在国家安全领域，有效的算法可能避免下一个911的发生。在气象方面，算法可以更好地预测未来天灾的发生，以拯救生命。
github的链接地址：leetcode-csharp 欢迎感兴趣的朋友加入进来，也欢迎star，或pull request。
Array标签的题目主要运用数组结构，算法思想涉及二分查找，dynamic programming，贪心算法等。LeetCode中的tag为Array的，easy部分的所有题目，如下表格所示：
LeetCode中的tag为HashTable的，easy部分的所有题目，如下表格所示：
| 题目编号 | 标题 |
|---|---|
| 136 | Single number |
| 1 | Two Sum |
| 447 | Number of Boomerangs |
| 463 | Island Perimeter |
| 409 | Longest Palindrome |
| 438 | Find All Anagrams in a String |
| 389 | Find the Difference |
| 350 | Intersection of Two Arrays II |
| 349 | Intersection of Two Arrays |
| 500 | Keyboard Row |
| 217 | Contains Duplicate |
| 204 | Count Primes |
| 202 | Happy Number |
| 219 | Contains Duplicate II |
| 242 | Valid Anagram |
| 290 | Word Pattern |
| 205 | Isomorphic Strings |
| 36 | Valid Sudoku |
LeetCode中的tag为HashTable的，easy部分的所有题目，如下表格所示：
LeetCode中的tag为Math的，easy部分的所有题目，如下表格所示：
| 题目编号 | 标题 |
|---|---|
| 231 | Power of Two |
| 268 | Missing Number |
| 507 | Perfect Number |
| 9 | Palindrome Number |
| 453 | Minimum Moves to Equal Array Elements |
| 13 | Roman to Integer |
| 441 | Arranging Coins |
| 415 | Add Strings |
| 400 | Nth Digit |
| 367 | Valid Perfect Square |
| 66 | Plus One |
| 7 | Reverse Integer |
| 204 | Count Primes |
| 202 | Happy Number |
| 172 | Factorial Trailing Zeroes |
| 171 | Excel Sheet Column Number |
| 168 | Excel Sheet Column Title |
| 258 | Add Digits |
| 263 | Ugly Number |
| 69 | Sqrt(x) |
| 67 | Add Binary |
| 246 | Strobogrammatic Number |
| 326 | Power of Three |
LeetCode中的tag为Two Pointers的，easy部分的所有题目，如下表格所示：
| 题目编号 | 标题 |
|---|
345 |[Reverse Vowels of a String](http://blog.csdn.net/daigualu/article/details/69257693)
125 |Valid Palindrome 283| Move Zeroes 88 |Merge Sorted Array 234| Palindrome Linked List 349 |Intersection of Two Arrays 167 |Two Sum II - Input array is sorted 350| Intersection of Two Arrays II 344| Reverse String 28| Implement strStr() 27 |Remove Element 26| Remove Duplicates from Sorted Array 141| Linked List Cycle 532| K-diff Pairs in an Array
题目编号|题目|通过率|难以程度| ---------|------------|---------| 58| Length of Last Word| 31.5%| Easy 20 |Valid Parentheses |32.8% |Easy 520 |Detect Capital| 52.5%| Easy 459 |Repeated Substring Pattern| 38.4%| Easy 434 |Number of Segments in a String |37.0% |Easy 408 |Valid Word Abbreviation | 27.5% |Easy 13 |Roman to Integer |44.6%| Easy 14 |Longest Common Prefix |31.0% |Easy 383 |Ransom Note |46.5% |Easy 521 |Longest Uncommon Subsequence I |46.1% |Easy 345 |Reverse Vowels of a String| 37.9% |Easy 28 |Implement strStr() |27.5% |Easy 344 |Reverse String| 58.2%| Easy 293 |Flip Game |54.8% |Easy 38 |Count and Say |33.4% |Easy 157 |Read N Characters Given Read4 | 29.2%| Easy 541 |Reverse String II |44.1% |Easy 125 |Valid Palindrome |25.8% |Easy 67 |Add Binary |31.3% |Easy
编号|题目|接受度|难易程度| :----:|:-----:|-------:|:---------:| 367 |[Valid Perfect Square](http://blog.csdn.net/daigualu/article/details/69787644)| 37.8%| Easy 270| Closest Binary Search Tree Value| 38.8%| Easy 167 |[Two Sum II - Input array is sorted](http://blog.csdn.net/daigualu/article/details/69787679) |47.4%| Easy 441 |[Arranging Coins](http://blog.csdn.net/daigualu/article/details/69788500)| 36.0%| Easy 35| [Search Insert Position](http://blog.csdn.net/daigualu/article/details/66995617)| 39.3%| Easy 374 |Guess Number Higher or Lower |34.4%| Easy 69 |Sqrt(x) |27.4%| Easy| 278| [First Bad Version](http://blog.csdn.net/daigualu/article/details/69802371) |24.8% |Easy 475| Heaters |29.7%| Easy 350 |[Intersection of Two Arrays II](http://blog.csdn.net/daigualu/article/details/69666351) |44.1%| Easy 349| [Intersection of Two Arrays](http://blog.csdn.net/daigualu/article/details/69666198)| 46.5%| Easy 编号|题目|通过率|程度| :---:|:----:|:-----:|:---:| 53| [Maximum Subarray](http://blog.csdn.net/daigualu/article/details/69936974)| 39.2%| Easy| 169| [Majority Element](http://blog.csdn.net/daigualu/article/details/69937729)| 45.6%| Easy| 303| [Range Sum Query - Immutable](http://blog.csdn.net/daigualu/article/details/69938986)| 27.8%| Easy| 276 |Paint Fence | 34.1%| Easy| 523 |[Continuous Subarray Sum](http://blog.csdn.net/daigualu/article/details/69941770)| 21.6%| Easy| 256| Paint House | 45.9%| Easy| 198| [House Robber](http://blog.csdn.net/daigualu/article/details/69946684)| 38.1%| Easy| 121| Best Time to Buy and Sell Stock|40.1% |Easy| 70| Climbing Stairs |39.2%| Easy| 编号|题目|接受度|难易程度| :----:|:-----:|-------:|:---------:| 225|[Implement Stack using Queues](http://blog.csdn.net/daigualu/article/details/70183272)| 32.0%| Easy 496| [Next Greater Element I](http://blog.csdn.net/daigualu/article/details/70185529) |57.5% |Easy 155| [Min Stack](http://blog.csdn.net/daigualu/article/details/70185814)| 27.4%| Easy 232| [Implement Queue using Stacks](http://blog.csdn.net/daigualu/article/details/70186010)| 35.8%| Easy 20| [Valid Parentheses](http://blog.csdn.net/daigualu/article/details/69569622)| 32.9%| Easy 编号| 题目| 通过率|程度 ---|:------:|--------| 107| [Binary Tree Level Order Traversal II](http://blog.csdn.net/daigualu/article/details/70254459)| 39.0%| Easy 257 |[Binary Tree Paths](http://blog.csdn.net/daigualu/article/details/70340125)| 36.8%| Easy 501 |[Find Mode in Binary Search Tree](http://blog.csdn.net/daigualu/article/details/70341143)| 38.4%| Easy 437 |[Path Sum III](http://blog.csdn.net/daigualu/article/details/70342773)| 39.3% |Easy 404 |[Sum of Left Leaves](http://blog.csdn.net/daigualu/article/details/70482270)| 46.5%| Easy 112 |[Path Sum](http://blog.csdn.net/daigualu/article/details/70482285)| 33.5% |Easy 110 |[Balanced Binary Tree](http://blog.csdn.net/daigualu/article/details/70482667)| 36.8% |Easy 108 |[Convert Sorted Array to Binary Search Tree](http://blog.csdn.net/daigualu/article/details/70485834)| 41.3%| Easy 543 |[Diameter of Binary Tree](http://blog.csdn.net/daigualu/article/details/70491447)| 42.3%| Easy 226 |[Invert Binary Tree](http://blog.csdn.net/daigualu/article/details/70536685)| 50.8%| Easy 235 |[Lowest Common Ancestor of a Binary Search Tree](http://blog.csdn.net/daigualu/article/details/70539096)| 38.5%| Easy 104 |[Maximum Depth of Binary Tree](http://blog.csdn.net/daigualu/article/details/70541420)| 51.7%| Easy 111| [Minimum Depth of Binary Tree](http://blog.csdn.net/daigualu/article/details/70543969)| 32.7% |Easy 101 |[Symmetric Tree](http://blog.csdn.net/daigualu/article/details/70544774)| 37.9%| Easy 100| [Same Tree](http://blog.csdn.net/daigualu/article/details/70254478)| 45.8%| Easy http://blog.csdn.net/daigualu/article/details/66486175 希望看过的朋友给我一个鼓励，希望感兴趣的朋友，一同努力，加油！ github的链接地址：[leetcode-csharp](https://github.com/jackzhenguo/leetcode-csharp) 欢迎感兴趣的朋友加入进来，也欢迎star，或pull request。LeetCode Array HashTable Stack Heap Tree Graph ...
I love LeetCode.