完全参考了算法导论 第九章 《中位数和统计学》

概述：中位数问题／选择问题

　　数组的个数为奇数时，中位数惟一，个数为偶数时，中位数为中间两个，这里为了讨论的简单，下文提到的中位数就是值小的中位数。我们还假设数组中元素值都是不同的。所以问题可以变成如下描述：

数组（下标从1开始）元素各不相同，输出第i小的元素

　　很显然我们可以利用排序在O(n*logn)时间内解出，但实际上会有更加高效的算法。

题目大意

　　https://leetcode.com/problems/palindrome-linked-list/

　　判断单链表是否是回文，要求时间复杂度O(n)，空间复杂度:O(1)

题目分析

　　先求链表长度，然后从头开始就地逆置一半长度的链表，此时链表相当于一分为二了，然后再从中间往两端逐个比较元素值，注意需要判断长度奇偶性。当然更加好的方法是用快慢指针找到链表中点，链表后半段元素就地逆置，然后再比较两部分。

题目大意

　　https://leetcode.com/problems/shortest-palindrome/

　　在字符串之前加最少的字符使得新的字符串为回文串。

题目分析

　　本题要先求出最长回文前缀，利用了kmp算法中的辅助数组，关于kmp算法可以看我之前的博客，如果理解了lps数组的含义，那么就很好解本题了，原字符串s，原字符串的s的反转为s_rev，那么s+"#"+s_rev的lps数组的最后一项即是字符串s的最长的回文前缀得长度，再经过简单的处理就是答案了。

题目大意

　　https://leetcode.com/problems/concatenated-words/

　　给你一个单词的list，返回list中的满足这样条件的单词：该单词由list中其它至少两个更短的单词拼接组成。

题目分析

　　跟https://leetcode.com/problems/word-break-ii/有类似之处，本题需要借助trie树进行高效的搜索前缀。首先是要将list中的单词建立trie树。search方法返回组成的单词数量，注意如果返回-1，那么就说明该单词无法由list中的单词组成，search方法利用了动态规划，用map进行记忆。