8.26 雅虎面试

pupuchan1116 发表于 2016-8-31 12:18
楼主其实已经很详细了，把问题转化为coin change来做，就是一道最基本的一维DP题。有兴趣可以上网搜一下c ...

不对吧，这个题要看清要求啊，跟leetcode combination sum IV不一样的，
举个例子  coints = [1,2,3], target是100, 如果开一个一维数组f[100],那就是求f[100],
那f[100]要怎么得来呢，
假设f[100]的定义是sum为100的各种不同的组合的个数之和(注意这里不同的sequence只能算是一个)
那首先f[100]可以先表示为f[97]+3,即最后以3作为结尾的，那么计算f[98]+2的时候就出现问题了(表示最后一位以2结尾的),因为这个会跟之前里面的f[97]+3那个case会产生重复（比如[1,3,2]和[1,2,3]其实是算一种）
所以这里要真用DP做得用二维数组

aangel 发表于 2016-9-1 04:27
不对吧，这个题要看清要求啊，跟leetcode combination sum IV不一样的，
举个例子  coints = [1,2,3], t ...

你说的对，我的错，我没有仔细想顺着楼主的思路就理所当然以为是这样了了，其实确实要用二维dp。

请问full time 和intern 冷冻期分别是多少呀？

真的有人还在面试Yahoo 么？

楼主我主要想请问一下reverse string in place，这个in place我完全想不到办法做到啊，怎么都要用到O(n) space，看到leetcode discuss上的in-place方法实际上也不算是in-place啊
求指点迷津

小魏Stenica 发表于 2016-9-3 09:08
楼主我主要想请问一下reverse string in place，这个in place我完全想不到办法做到啊，怎么都要用到O(n) sp ...

如果用Java是怎麼都不可能in place的，因為java的String是immutable的。那個應該是針對C和C++的吧

pupuchan1116 发表于 2016-9-3 20:02
如果用Java是怎麼都不可能in place的，因為java的String是immutable的。那個應該是針對C和C++的吧

对，我是用的Java，打破脑袋都想不通为什么在说in-place，原来是c++, 我对c++一点都不熟悉
多谢解答！

小魏Stenica 发表于 2016-9-4 14:01
对，我是用的Java，打破脑袋都想不通为什么在说in-place，原来是c++, 我对c++一点都不熟悉
多 ...

就是char[] 做，就叫in-place 了你得跟考官说。java string 没有智能转char[]

cicean 发表于 2016-9-5 22:48
就是char[] 做，就叫in-place 了你得跟考官说。java string 没有智能转char[]

好的，谢谢！我明白了！

aangel 发表于 2016-9-1 04:27
不对吧，这个题要看清要求啊，跟leetcode combination sum IV不一样的，
举个例子  coints = [1,2,3], t ...

不用二维数组，楼主的一维数组DP思路是对的！
但是需要加两个语句：
1. 把输入数组排序
2. 在外循环中跳过重复的数。
这样你提到的重复case也不会发生。