Ivy嘟嘟

【题目描述】 Write an algorithm which computes the number of trailing zeros in n factorial. 设计一个算法，计算出n阶乘中尾部零的个数。 【题目链接】 http://www.lintcode.com/en/problem/trailing-zeros/ 【题目解析】 传统解法是首先求出n!，然后计算末尾0的个数。（重复÷10，直到余数非0）该解法在输入的数字稍大时就会导致阶乘得数溢出，不足取。 O（logn）解法：一个更聪明的解法是考虑n!的质数因子。后缀0总是由质因子2和质因子5相乘得来的。如果我们可以计数2和5的个数，问题就解决了。考虑下面的例子： n = 5: 5!的质因子中 (2 * 2 * 2 * 3 * 5)包含一个5和三个2。因而后缀0的个数是1。 n = 11: 11!的质因子中(2^8 * 3^4 * 5^2 * 7)包含两个5和三个2。于是后缀0的个数就是2。 我们很容易观察到质因子中2的个数总是大于等于5的个数。因此只要计数5的个数就可以了。那么怎样计算n!的质因子中所有5的个数呢？一个简单的方法是计算floor(n/5)。例如，7!有一个5，10!有两个5。除此之外，还有一件事情要考虑。诸如25，125之类的数字有不止一个5。例如，如果我们考虑28!，我们得到一个额外的5，并且0的总数变成了6。处理这个问题也很简单，首先对n÷5，移除所有的单个5，然后÷25，移除额外的5，以此类推。 【参考答案】 http://www.jiuzhang.com/solutions/trailing-zeros/

【题目描述】 Write a function that add two numbers A and B. You should not use + or any arithmetic operators. Notice:There is no need to read data from standard input stream. Both parameters are given in function aplusb, you job is to calculate the sum and return it. 给出两个整数a和b, 求他们的和, 但不能使用 + 等数学运算符。 注意：你不需要从输入流读入数据，只需要根据aplusb的两个参数a和b，计算他们的和并返回就行。 【题目链接】 http://www.lintcode.com/en/problem/a-b-problem/ 【题目解析】 直接+没什么好说的，关键在于不用+的操作：考验Bit Operation, 可以用按位^异或两个操作数对应位以及carry，只是carry是1还是0需要分情况讨论。求更优的解法。 位运算实现整数加法本质就是用二进制进行运算。其主要用了两个基本表达式：x^y //执行加法，不考虑进位。(x&y)<<1 //进位操作 令x=x^y ；y=(x&y)<<1 进行迭代，每迭代一次进位操作右面就多一位0，最多需要“加数二进制位长度”次迭代就没有进位了，此时x^y的值就是结果。 【参考答案】 http://www.jiuzhang.com/solutions/a-b-problem/

【题目描述】 There are a row of  n  houses, each house can be painted with one of the  k  colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color. The cost of painting each house with a certain color is represented by a  n  x  k  cost matrix. For example,  costs[0][0]  is the cost of painting house  0  with color  0 ;  costs[1][2]  is the cost of painting house  1  with color  2 , and so on... Find the minimum cost to paint all houses.  Notice All costs are positive integers. Example Given  n  = 3,  k  = 3,  costs  =  [[14,2,11],[11,14,5],[14,3,10]]  return  10 house 0 is color 2, house 1 is color 3, house 2 is color 2,  2 + 5 + 3 = 10 这里有 n 个房子在一列直线上，现在我们需要给房屋染色，分别有红色蓝色和绿色。每个房屋染不同的颜色费用也不同，你需要设计一种染色方案使得相邻的房屋颜色不同，并且费用最小。 费用通过...

【题目描述】 Factory is a design pattern in common usage. Please implement a  ToyFactory  which can generate proper toy based on the given type. 工厂模式是一种常见的设计模式。请实现一个玩具工厂  ToyFactory  用来产生不同的玩具类。可以假设只有猫和狗两种玩具。 样例 ToyFactory tf = ToyFactory(); Toy toy = tf.getToy('Dog'); toy.talk(); >> Wow toy = tf.getToy('Cat'); toy.talk(); >> Meow 【题目链接】 http://www.lintcode.com/en/problem/toy-factory/ 【题目解析】 和shape factory一样，重载函数。 【参考答案】 http://www.jiuzhang.com/solutions/toy-factory/

【题目描述】 Given a digit string excluded  01 , return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below. Notice Although the above answer is in lexicographical order, your answer could be in any order you want. Example + Given "23" Return ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"] 给一个不包含 01 的数字字符串，每个数字代表一个字母，请返回其所有可能的字母组合。 下图的手机按键图，就表示了每个数字可以代表的字母。 注意事项 以上的答案是按照编撰顺序进行输出的，不过，在做本题时，你也可以任意选择你喜欢的输出顺序 【题目链接】 http://www.lintcode.com/en/problem/letter-combinations-of-a-phone-number/?rand=true 【题目解析】 这个问题我们可以采用递归的思路来进行解决，首先看第1个数字，我们可以通过对应的表来知道第1个数字对应的字母可能有哪些，那么此时只需要知道剩下的l-1(l是数字串长度)可能代表的字符串有哪些，然后将第1个数字对应的字母与这些字符串两两拼接起来，便可以得到所有可能的解。 【参考答案】 http://www.jiuzhang.com/solutions/letter-combinations-of-a-phone-number/

【题目描述】 Given a binary tree, find all paths that sum of the nodes in the path equals to a given number  target . A valid path is from root node to any of the leaf nodes. 给定一个二叉树，找出所有路径中各节点相加总和等于给定  目标值  的路径。 一个有效的路径，指的是从根节点到叶节点的路径。 【题目链接】 http://www.lintcode.com/en/problem/binary-tree-path-sum/ 【题目解析】 对于root来说，最大路径有两种情况 不通过root, 在左右两边的子树里 通过root, 如果左child, 和右child通过他们的最大path > 0,就可以连到root上 然后比较三个 左边子树里的最大path 右边子树里的最大path 通过root的最大path 注意,child return给上面的可以连的值应该是通过自己的path sum,而不一定是最大的， return 俩个值，maxSum, single recursive, helper function 【参考答案】 http://www.jiuzhang.com/solutions/binary-tree-path-sum/

[题目描述] Singleton  is a most widely used design pattern. If a class has and only has one instance at every moment, we call this design as singleton. For example, for class Mouse (not a animal mouse), we should design it in singleton. You job is to implement a  getInstance  method for given class, return the same instance of this class every time you call this method. 单例  是最为最常见的设计模式之一。对于任何时刻，如果某个类只存在且最多存在一个具体的实例，那么我们称这种设计模式为单例。例如，对于 class Mouse (不是动物的mouse哦)，我们应将其设计为 singleton 模式。 你的任务是设计一个  getInstance  方法，对于给定的类，每次调用  getInstance  时，都可得到同一个实例。 [题目链接] http://www.lintcode.com/en/problem/singleton/ [题目解析] 单例模式，要考虑并发情况。 为了防止多个线程创建多个实例，要在new之前加一个锁，即synchronized。同时为了防止多个线程在判断实例为null之后先后进入synchronized依然创建多个实例，可以在synchronized之后double check一下实例是否为null。 [参考答案] http://www.jiuzhang.com/solution/singleton/