摘要: 称球问题经常是面试中的常客，这里我用做了一个称球的程序，主要的方法就是递归和扫描，贴出来请大家指正。
阅读全文
摘要: 这是一个美国IT企业的面试题，原题大意是从一个文件中读取出可连通的城市对，给出两个城市，判断是否可连通，如果可连通就输出yes，不可连通就输出no，否则给出命令行帮助。
其实判断连接状态不用遍历图，用蔓延法即可，具体做法就是从起始城市开始，依次改变其周边连通城市的连通状态，再从周边开始向周边连通城市蔓延，如果能蔓延到结束城市的周边可连通城市，则说明两个城市是完全可连通的。这种做法和多米诺骨牌效应很像。我姑且称之为蔓延法。
阅读全文
摘要: 回溯法有“通用的解题法“之称。用它可以系统的搜索一个问题的所有解或任一解。会所法是一个既带有系统性又带有跳跃性的搜索算法，他在包含问题的所有解的解空间树中，按照深度有限的策略，从根节点出发搜索解空间树，算法搜索至解空间树的任一节点时，总是先判断该节点是否肯定不包含问题的解。如果肯定不包含，则跳过对该节点为根的子树的系统搜索，逐层向其祖先节点回溯，否则进入该子树，继续按照深度优先的策略进行搜索。回溯法在用来求问题的任一接时，只要搜索到问题的一个解就可以结束。
这种深度优先的解的算法称为回溯法，它适合于解一些组合数较大的问题。
用回溯法解n皇后问题时，可以用一棵完全n叉树来表示其解空间。剪去不满足行列和斜线攻击的子树后，剩下的就是问题的解答。
阅读全文
摘要: 求两字符串的公共子串，如abc123与123456的公共字串为123，基本想法是在长的字符串前面加上长度等于短字符串的空格前缀，然后拿短字符串与新字符串挨个匹配，匹配上的置上匹配字符，否则置上空格，这样的新串就包含了匹配字串和空格，再劈分放入set即可，重复的元素会被set略过去。
阅读全文