3Sum Closet

3Sum Closet 利用3Sum的算法，这里需要注意的是返回的结果不是差值，而是3数之和。

Jul 10 2016

3Sum

3Sum 这道题目可以先使用2Sum的方法，就是先对数组排序，再用两个指针分别从头和尾来遍历， 如果两数和为target，那么就保留该结果，并将tail往前挪，head往后挪一位； 如果和大于target，说明tail指向的数大了，需要往前挪一位； 如果和小于target，说明h

Jul 10 2016

Maximal Rectangle

Maximal Rectangle 这道题目需要用到之前Largest Rectangle in Histogram的做法。维护一个大小为v[0].size()的数组height，该height将记录第i列的从第j行到第0行是1的高度。每次按行来更新该height数组。 比如输入

Jul 10 2016

Super Pow

Super Pow 这道题目我一开始是用迭代b次，就是把vector b求和计算，然后result = (result*b)%1337，但是后来发现b太大了，根本不能求和，所以我们得换个思路来。 这里我们得知道两个数学知识： (a*b)%n = ((a%n)*(b%n)) %

Jul 10 2016

Subsets

Subsets 我的方法是使用递归回溯的方法，每次传入函数的参数有一个当前集合，和刚刚压入集合的数字的下标。在函数开始时先压入当前集合，接着从下标的下一个开始遍历，调用该递归函数即可。 需要注意空集是任何集合的子集。

Jul 10 2016

Largest Rectangle in Histogram

Largest Rectangle in Histogram 这道题目的解答可以这样来看，我们每次都只求一个波峰图的最大面积，比如3 4 5 6 7 2，那么波峰图就是3 4 5 6 7。我们可以用一个栈来维护这个波峰图。 栈记录的是波峰图的下标，这样我们就不需要额外的空间来储存

Jul 9 2016

Mybatis mapper的各种sql

Mybatis mapper的各种sql 参考资料： http://blog.csdn.net/luqin1988/article/details/7831927

Jul 6 2016

Largest Divisible Subset

Largest Divisible Subset 这道题目可以用动态规划来实现: dp[i]表示有序数组nums以nums[i]结尾的子数组中可分割最大子集和的大小是dp[i]。 那么dp[i+1] = max(dp[j]+1 如果nums[i+1] % nums[j] == 0

Jul 6 2016

Water and Jug Problem

Water and Jug Problem 这道题目需要可以抽象成z = ax + by,那么这里需要用到一个定理，就是贝祖定理：若x和y是整数，那么存在整数a和b，使得ax+by = gcd(a,b)。 那么整道题目只需要判断一下z是否是gcd(x,y)的倍数即可。当然不能超过

Jul 5 2016

Valid Perfect Square

Valid Perfect Square 我一开始用减半求平方根，超时了，之后就用牛顿迭代法求平方根就过了。 后来看了discuss，其实一个平方数16 = 1+3+5+7，即n^2 = 1+3+5+…+(2n-1) = (1+2n-1)*n/2 = n^2

Jul 5 2016

Count Numbers With Unique Digits

Count Numbers With Unique Digits 下面是数字位数与不同数位的数字个数的映射 1 10 2 9*9 3 998 4 998*7 也就是说numCnt(n) = 998…*(11-n) 最后再将之前的个位数加起来即可。

Jul 5 2016

radio点不中

radio点不中 radio按钮点不中，需要往旁边移一点才能点到，这是因为html写的是 1<input type="radio" id="type2_radio" name="evatype" value=&qu

Jul 5 2016

H-Index

H-Index 我一开始的做法是如果输入是[3,0,6,1,5],想办法构建一个 0 5 1 4 2 3 3 3 4 2 5 2 这样的映射，即记录指数与大于该指数个数的映射。然后再从后往前扫，如果key<=value，那么就返回key。这样的做法是O(n^2) 有O(N)

Jul 3 2016

Repeated DNA Sequences

Repeated DNA Sequences 我的做法就是从0到s.size()-10去获取所有长度为10的子串，根据这些子串来生成一个map，记录它们出现的次数。最后遍历这个map，如果次数大于1，那么就压入容器中。

Jul 3 2016

Bulls and Cows

Bulls and Cows 我的做法是先为secret的字符串构建一个数字与出现次数的映射map。 遍历guess字符串，如果guess[i]与secret[i]相同，那么bull的计数器+1，map[guess[i]-‘0’]–; 如果不想等且map[guess[i]-‘0’

Jul 3 2016