编程之美答案

㈠ 学习数据结构，有哪些值得推荐的好书

在微信高校专业集里面粘贴
入门
1.《啊哈！算法》
2.《算法设计与分析基础》
3.《算法引论：一种创造性方法》
4.原书名：Introction to Algorithms
中文名：算法导论
5.数据结构与算法分析：C语言描述（原书第2版）
进阶
1.原书名：The Design and Analysis of Computer Algorithms
中文名：算法设计与分析
作者：Aho，Hopcroft，Ullman
2.原书名：Algorithms Design Techniques and Analysis
中文名：算法设计技巧与分析
作者：M.H.Alsuwaiyel
3.中文名：算法与数据结构
作者：傅清祥 王晓东
程序设计竞赛
1.原书名：Introction to Algorithms
中文名：算法导论
作者：Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest,Clifford Stein
2.原书名：Introction to The Design & Analysis of Algorithms
中文名：算法设计与分析基础
作者：Anany Levitin
4.算法竞赛 | 信息学奥赛一本通
5.算法竞赛 | 算法竞赛进阶指南

㈡ 终于知道怎么判断字符串相似度了

一直不理解，为什么要计算两个字符串的相似度呢。什么叫做两个字符串的相似度。经常看别人的博客，碰到比较牛的人，然后就翻了翻，终于找到了比较全面的答案和为什么要计算字符串相似度的解释。因为搜索引擎要把通过爬虫抓取的页面给记录下来，那么除了通过记录url是否被访问过之外，还可以这样，比较两个页面的相似度，因为不同的url中可能记录着相同的内容，这样，就不必再次记录到搜索引擎的存储空间中去了。还有，大家毕业的时候都写过论文吧，我们论文的查重系统相信也会采用计算两个字符串相似度这个概念。
以下叙述摘自编程之美一书：
许多程序会大量使用字符串。对于不同的字符串，我们希望能够有办法判断其相似程序。我们定义一套操作方法来把两个不相同的字符串变得相同，具体的操作方法为：
1.修改一个字符（如把“a”替换为“b”）;
2.增加一个字符（如把“abdd”变为“aebdd”）;
3.删除一个字符（如把“travelling”变为“traveling”）;
比如，对于“abcdefg”和“abcdef”两个字符串来说，我们认为可以通过增加/减少一个“g”的方式来达到目的。上面的两种方案，都仅需要一 次 。把这个操作所需要的次数定义为两个字符串的距离，而相似度等于“距离+1”的倒数。也就是说，“abcdefg”和“abcdef”的距离为1，相似度 为1/2=0.5。
给定任意两个字符串，你是否能写出一个算法来计算它们的相似度呢？
原文的分析与解法
不难看出，两个字符串的距离肯定不超过它们的长度之和（我们可以通过删除操作把两个串都转化为空串）。虽然这个结论对结果没有帮助，但至少可以知道，任意两个字符串的距离都是有限的。我们还是就住集中考虑如何才能把这个问题转化成规模较小的同样的子问题。如果有两个串A=xabcdae和B=xfdfa，它们的第一个字符是 相同的，只要计算A[2,...,7]=abcdae和B[2,...,5]=fdfa的距离就可以了。但是如果两个串的第一个字符不相同，那么可以进行 如下的操作（lenA和lenB分别是A串和B串的长度）。
1.删除A串的第一个字符，然后计算A[2,...,lenA]和B[1,...,lenB]的距离。
2.删除B串的第一个字符，然后计算A[1,...,lenA]和B[2,...,lenB]的距离。
3.修改A串的第一个字符为B串的第一个字符，然后计算A[2,...,lenA]和B[2,...,lenB]的距离。
4.修改B串的第一个字符为A串的第一个字符，然后计算A[2,...,lenA]和B[2,...,lenB]的距离。
5.增加B串的第一个字符到A串的第一个字符之前，然后计算A[1,...,lenA]和B[2,...,lenB]的距离。
6.增加A串的第一个字符到B串的第一个字符之前，然后计算A[2,...,lenA]和B[1,...,lenB]的距离。
在这个题目中，我们并不在乎两个字符串变得相等之后的字符串是怎样的。所以，可以将上面的6个操作合并为：
1.一步操作之后，再将A[2,...,lenA]和B[1,...,lenB]变成相字符串。
2.一步操作之后，再将A[2,...,lenA]和B[2,...,lenB]变成相字符串。
3.一步操作之后，再将A[1,...,lenA]和B[2,...,lenB]变成相字符串。

通过以上1和6,2和5，3和4的结合操作，最后两个字符串每个对应的字符会相同，但是这三种操作产生的最终的两个字符串是不一样的。我们不知道通过上述的三种结合那种使用的操作次数是最少的。所以我们要比较操作次数来求得最小值。

㈢ 有什么适合大一计算机专业学生免费的刷题网站

既然大一的同学选择计算机专业，当然少不了刷题啦！但是有很多刷题网站是免费的，同学们想知道吗？下面由我来讲讲吧。

1.力扣

这个网站收录了很多知名互联网公司出的算法题目，相信大一同学很熟悉了，很多同学都在这里刷题，增强对计算机基础知识掌握。它支持多种编程语言，如：java、Ptthon、Ruby等。最常做的是算法题，目前有一千多道的题目。有专门的图文和视频讲解，方便同学们茶楼补缺。也可以在个人界面查看进展，看自己的学习情况。如果出来工作笔试中，面试官会从这里抽题。刷题过程中全部会了，那么工作没有什么大问题。

以上我列举了三个计算机免费刷题的网站，同学们看到我写的推荐后，来收藏夹吃灰~希望同学们有时间使用这三个网站学习计算机相关知识，提高计算机专业能力，祝你们学有所成！

㈣ 计算机面试主考官一般都会问到什么问题

《编程之美——微软技术面试心得》里面有60多道面试题目，很多IT公司的算法或者程序设计题目都跟它类似，而且里面每个题目都给出了好几种解法，还有扩展问题。
不知道符不符合你的要求。

㈤ 求高手用c++解决二十四点的问题，具体如下

24点算法分析
很久没有研究程序了，惭愧中。。。这个夏天大致地翻了一下微软亚洲研究院出的《编程之美》，很喜欢这本书的风格，里面很多题目都很有意思。书中主要突出的是一个“巧”字，最关键的，就是从变化中寻找不变的规律。 这次说的问题其实也很简单，给四个数，写一个程序输出算24点的结果，如果没有就输出“No Answer”。但是如果用我们自己算24点的思维来写程序是不行的，因为那属于一种“凑”的方法，有碰巧和经验的成分。计算机能做的，就是通过一种固定的方式来找寻结果。如果没有一般性的所谓“固定”方式，那么只有通过遍历和穷举来解决问题。这样的方法下诞生了很多所谓的NP难问题，如果原始数据规模比较大就要花很长的时间来得到结果。
24点这个问题最直接的方法就是，列举四个数所有的排列组合，加上各种运算符以及括号，所有的情况经过处理之后可以得到一个包含所有计算结果和计算式的列表，从其中寻找24的影踪就可以了。如果不计计算结果重复的情况，最终的结果有7680种，数据量还是有点大，因此这个算法需要进一步的优化。例如，考虑到加法和乘法的交换律，如果遇到相应的情况只计算一种，对于另一种直接返回。这样的剪枝处理可以减少不少的运算。
不过我用的是书中的另一种思路，采用了划分的思想。具体的算法是：
如果A是一个数组，定义f(A)为数组中的所有数经过四则运算所能得到的结果的集合。对于A中元素个数大于1的情况，可以将A分拆成两个集合，定义运算 Fork(A,B)为f(A)和f(B)中各取一个元素的四则运算得到的所有的结果的集合。这样，如果列举出集合A所有的拆分情况，那么所有Fork结果的并集就是f(A)的结果。
对于24点的情况，因为数组A有4个数，因此将其用各种方法拆分即可得到最终的f(A)，然后查询其中是否存在元素24即可得到有解或者无解的判断。
需要说明的有几点：
1.这个问题表面上需要采用递归的算法，即如果只有一个元素那么直接返回，否则将问题转化为多个f的计算，而每个f的计算又要经过转化，层层递归，直至只有一个元素的情况。但是，不要忘了递归的方法一般都是针对回溯次数不确定的问题。例如汉诺塔问题，只有一个盘子的情况和64个盘子的情况，回溯次数截然不同，千差万别；但是对于24点，因为只有4个数，实际上分拆的可能性是固定的，就那么有限种情况。递归算法的思路是从树的根部往下遍历，而且一般不知道树的大小和规模。而对于24点问题，这棵树的大小固定，完全可以从树的叶子着手，从叶子向根步进，从而得到最终的结果。
2.分拆有一定的技巧，最合适的方法是通过位运算。比如一种分拆方法是{a1,a2},{a3,a4},那么写做1100和0011。这种方法的好处在于，比如要判断1000是不是1100的一个子集，只需要将两者做与运算，最后的结果如果还等于1100则表明确实是子集，同时分拆的另一个结果便是两者的差。这样至多只需要比较 10多次就可以列举出每个集合所有的分拆情况，比较巧妙的方法。同时，位运算的速度也很快，不会对计算的时间有较大的影响。
3.这个方法的缺点在于，最终得到的只是一个无解或者有解的判断，并没有输出表达式。
所以我对这个算法进行了一定的改进，使之能输出表达式。
首先要考虑的，也是最重要的，是这个程序的数据结构。最终的目的自然是为了达到最少的时间复杂度。由于上述方法中f函数返回的是“集合”，因此不存在重复的元素。这样的情况下，哈希表自然是首选的数据结构。
为了记录表达式，需要引入另一套数据结构。每一个计算的结果都必须和一个表达式对应。这样，当最终查询到一个计算结果为24的时候，只需查找相应的表达式就可以得到结果。
这里就产生了冲突。哈希表的特点是存放是乱序的，也就是说，如果只采用一个哈希表存放计算结果，用一个vector存放表达式，那么无法产生对应关系。
因此，有两种方案：
第一种方案比较节省存储空间，将计算结果和表达式分别存在两个vector中，由于两者都是有序的集合类，因此可以在插入数据的时候令各自的下标对应，这样就可以方便地得到对应关系。但是，这样做的后果是，在插入新数据的时候需要在vector中查找是否已经存在这个计算结果，如果已有则不必插入。 vector的查找是穷举式的，效率比较低，尤其是当vector比较大的时候将很大程度上影响计算的效率。但如果不进行查找，势必会计算很多没有意义的重复结果，这样就失去了这个算法的意义了。
第二种方案在第一种方案的基础上将计算结果多存一份哈希表数据。这样做增加了存储空间，但是在时间上的优势是显而易见的。在插入的时候，通过查找哈希表来决定是否已经存在这个结果，由于哈希表的查找效率很高，因此这一步不会对这个程序造成时间上的瓶颈。如果不存在，那么同时在哈希表和两个vector中同时插入数据即可。计算结果和表达式的对应关系依然存在，同时查找的效率也大大提高，整个程序的时间复杂度大大降低。这是典型的空间换时间的方法。
写算法我首选的语言还是c++，但是很惭愧c++的HashTable我不会用，因此用java写了一个版本，还算比较成功，能输出最终的结果。在写程序前我写了一个小程序来测试java的HashSet和ArrayList的查找效率，结果很令人惊讶。在10000次查询中，HashSet所用时间为0ms，而ArrayList则用了1300多ms，看来这个效率完全不是一个数量级上的。因此我采用了上述的第二种方案，最终的效果还不错。
曾经有人问过我5，5，5，1怎么算24点，当时想了很久都没想出来。现在用这个程序可以很轻松地算出5*(5-1/5)=24。看来这个程序可以输出一些大家想不到的结果，很强大把。类似的例子还有很多，比如3，3，7，7等等。总之呢，优化了的穷举法（我这个程序实际上还是一种变相的穷举）是一种很不错的解决问题的思路，值得采用！
过几天就开学了。也许每年的开学前才有时间去研究下这种问题，等到开学之后就基本没什么时间了。嗯，好好工作把，也愿今年能开个好题，明年好好做毕设。Good luck。

PS:昨天经同学提醒才发现有更好的解决方法。主要是因为好久没用，把java的HashMap给忘了。这个数据结构用在这里正合适，也就是说不用两个HashSet加两个ArrayList解决了，直接存在一个HashMap里面就可以。
具体的做法是：把计算结果存在map的key中，而表达式存在map的value中，问题彻底解决。map中key的查找效率是很高的，同时插入也很快；当找到一个计算结果为24的时候直接根据这个key去寻找相应的value即可得到完美的答案，同时HashMap也保证了每个计算结果只保留一个表达式，避免了重复。
我做了一下性能测试，总的来这个改进后的版本效率比以前的版本略有提高，但是最关键的是大大减少了空间的存储，因此也算是对程序进行的大优化把我想。这两天看这个帖子似乎看的人比较多哈，也愿我的想法能给大家一些启发。