Find all the numbers that can make a 直角 triangle

Q:  
给定一个数组，求所有可以组成勾股三角形的组合。
 首先，我们应该用hashSet.  这样，复杂度就是O(n^2)。

但如果题目是正整数， 例如， 1到100000.  根据链接
以任意一个大于1的奇数2n+1(n＞=1)为边可以构成勾股数，
其三边分别是2n+1、2n2+2n、2n2+2n+1。
弄出这么一个规律性的结论，问题得以大大简化。


A:



Mistakes:

151. Reverse Words in a String ---M

Given an input string, reverse the string word by word.

 

Example 1:

Input: "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: "  hello world!  "
Output: "world! hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

 

Note:

• A word is defined as a sequence of non-space characters.
• Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
• You need to reduce multiple spaces between two words to a single space in the reversed string.

 

Follow up:

For C programmers, try to solve it in-place in O(1) extra space.

A:
思路很简单，就是用tokenizer之后

class Solution {
public:
    string reverseWords(string s) {
        istringstream iss(s);
        vector<string> res( ( istream_iterator<string>(iss)), istream_iterator<string>() );
        string sRes="";
        for(int i = res.size()-1; i>=0;i--)
            sRes += " "+res[i];
        if(sRes.length() >0)
            sRes = sRes.substr(1);
        return sRes;
    }
};

2：天平称球 等智力测验

2：天平称球
假设有12个球、1架天平，现知道只有一个球和其他球重量不同，请问，怎样才能称3次就找到那个球？如果是13个球呢？（注意：此题并未说明那个球相比其他球是轻是重，所以需要仔细考虑。）

4：小猴子搬香蕉
一只小猴子身边有100根香蕉，它要走50米才能到家，每次它最多搬50根香蕉（多了就被压死了），它每走1米就要吃掉1根香蕉，请问它最多能把多少根香蕉搬到家里？



10：偷情的丈夫
村子里有100对 夫妻，其中每个丈夫都瞒着自己的妻子偷情。村里的每个妻子都能立即发现除自己丈夫之外的其他男人是否在偷情，唯独不知道她自己的丈夫到底有没有偷情。村里 的规矩不容忍通奸。任何一个妻子，一旦能证明自己的男人偷情，就必须当天把他杀死。村里的女人全都严格照此规矩办事。一天，女头领出来宣布，村里至少有一 个丈夫偷情。请问接下来会发生什么事？


11：形成三角形的概率
将一根木条折成3段之后，形成1个三角形的概率有多大？



19：如果你是教练
一场篮球赛还剩6秒，你们队差对手4分，似乎没可能追得上，但现在有一个暂停，如果你是教练，你会怎样指导球员？


20：字母排序
s-m-t-w-t-f-？

把一个数组， in-place，把其交叉

题目：给定整数数组，元素为a1 a2 a3 .. an b1 b2 b3 .. bn元素个数为 2n
要求：请生成如下数组，a1 b1, a2 b2, a3 b3, .. an bn. 
条件：时间复杂度为O(N),空间复杂度为O(1).
来源：http://blog.csdn.net/yuan8080/article/details/5705559
//***************************************************************************************
思路：
1、首先证明当 n=2^k 时，存在时间复杂度为O(N),空间复杂度为O(1)的算法。
2、其次证明对任意n，存在时间复杂度为O(N),空间复杂度为O(1)的算法。
证明：
1、当 n=2^k 时，存在时间复杂度为O(N),空间复杂度为O(1)的算法。
首先，从新编号，从“a1 a2 a3 .. an b1 b2 b3 .. bn” 到“0, 1, ... ，2^k-1， 2^k，... ，2^(k+1)-1”。
设某元素原来的下标为i，变换后的下标为j，则有：j=(2*i)%(2*n-1)。 例如：1-->2 (a2-->a3)， 2-->4 (a3-->a5)。
然后，从1，3，...， n-1依次执行变换。例如n=8，则有：
1-->2-->4-->8-->1
3-->6-->12-->9-->3
5-->10-->5
7-->14-->13-->11-->7
设从i(i=2*k+1)开始变换的一组下标的集合为Si，则可以证明，Si∩Sj=空集，且 ∪Si=全集。
所以，该变换的时间复杂度为O(N),空间复杂度为O(1)的算法。
2、对任意n，存在时间复杂度为O(N),空间复杂度为O(1)的算法。
对任意n，有n=∑ck*x^k，其中ck=0或1。
因此，可以采用对任意ck=1的情况：
首先，做整体移位，两个2^k连续块放在一起(采用翻转法[1]，时间复杂度为O(N),空间复杂度为O(1))；
其次，对两个2^k连续块采用上面的算法；
然后，对剩余部分再采取前两步的方法，直到k=1。
例如n=11，则有:
第一次：
0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21
变为 0,1,2,3,4,5,6,7,11,12,13,14,15,16,17,18,  8,9,10,19,20,21
然后 0,11,1,12,2,13,3,14,4,15,5,16,6,17,7,18,  8,9,10,19,20,21
第二次：
0,1,2,3,4,5,6,7,11,12,13,14,15,16,17,18,  8,9,10,19,20,21
变为 0,1,2,3,4,5,6,7,11,12,13,14,15,16,17,18,  8,9,19,20,  10,21
然后 0,11,1,12,2,13,3,14,4,15,5,16,6,17,7,18,  8,19,9,20,  10,21
证明对任意n该方法的时间复杂度为O(N)，有两种证明方法：
1、采用master theorem[2]，可直接证明。
2、到n=2^k-1时，该算法的时间复杂度最大。因此，只需证明此时的时间复杂度为O(N)。
利用等比数列，可以证明此结论。
算法与证明描述结束。
[1] 编程之美。问题2.17。
[2] 算法导论。定理4.1

implement Reader / Writer Lock

用数组实现 3种 hashTable

Djiastra , KMP , BFS, DFS , Dag 代码