1. 区间异或算法：st+rmq算法思路

根据题意，需要多次查询某区间的最大/最小值，那么我们可以考虑预处理st表，然后通过rmq快速查询某个区间的最大最小值

预处理(以区间最大值为例)：

设$F[i][j]$表示数列A从第i个数起连续$2^j$个数$([i,i+2^j−1])$中的最大值。递推边界是$F[i][0] = A[i]$，即数列A在区间$[i,i]$里的最大值。在递推时，我们把子区间的长度成倍增加，即长度为$2^j$的子区间最大值是左右两半长度为$2^j$的子区间的最大值中较大的一个。即$Fi=max(Fi,Fi+2^j−1)$区间最小值同理

查询：

假如我们需要查询的区间为$[i, j]$，那么我们需要找到覆盖这个闭区间（左边界取i,右边界取j）。可以重复，比如查询5，6，7，8，9，我们可以查询5678和6789.因为这个区间的长度为$j-i+1$，所以我们可以取$k=log_2{(j−i+1)}$，则有$F[i,j]=max(F[i,k],F[j−2^k+1,k])$复杂度分析时间复杂度为$O(n*logn)$

+ $n$为数组的长度，rmq查询时间复杂度为$O(1)$空间复杂度为$O(n)$

+ $n$为数组的长度题解

C++

// This solution is powered by @lintcode.comclass Solution {public:    /**     * @param num: Array of num     * @param ask: Interval pairs     * @return: return the sum of xor     */    void st(int n) {        int k = (int)(log(n) / log(2.0));        for (int j = 1; j <= k; j++) {            for (int i = 0; i + (1 << j) - 1 < n; i++) {                intervalMax[i][j] = max(intervalMax[i][j - 1], intervalMax[i + (1 << (j - 1))][j - 1]);                intervalMin[i][j] = min(intervalMin[i][j - 1], intervalMin[i + (1 << (j - 1))][j - 1]);            }        }    }    int rmq(int l,int r,int flag){        int k = (int)(log(r - l + 1.0) / log(2.0));        if(flag)            return max(intervalMax[l][k], intervalMax[r - (1 << k) + 1][k]);        else            return min(intervalMin[l][k], intervalMin[r - (1 << k) + 1][k]);    }    int sumInterval(int l1,int r1,int l2,int r2) {        return rmq(l1,r1,1) + rmq(l2,r2,0);    }    int Intervalxor(vector<int> &num, vector<vector<int>> &ask) {        int n = num.size();        intervalMin.resize(n + 1);        intervalMax.resize(n + 1);        for (int i  = 0; i <= n; ++i) {            intervalMin[i].resize(30);            intervalMax[i].resize(30);        }        for(int i = 0; i < n; i++) {            intervalMin[i][0] = num[i];            intervalMax[i][0] = num[i];        }        st(n);        int ans = 0;        for (int i = 0;i < ask.size(); i++) {            int l1,r1,l2,r2;            l1 = ask[i][0] - 1;            r1 = ask[i][1] - 1;            l2 = ask[i][2] - 1;            r2 = ask[i][3] - 1;            ans ^= sumInterval(l1,r1,l2,r2);        }        return ans;    }private:    vector<vector<int> >intervalMax;    vector<vector<int> >intervalMin;};

Python

# This solution is powered by @lintcode.comimport mathclass Solution:    """    @param num: Array of num    @param ask: Interval pairs    @return: return the sum of xor    """    def st(self,n):        k = (int)(math.log(n) / math.log(2.0)) + 1        for j in range(1,k):            i = 0            while i + (1 << j) - 1 < n:                self.interval_max[i][j] = max(self.interval_max[i][j - 1], self.interval_max[i + (1 << (j - 1))][j - 1]);                self.interval_min[i][j] = min(self.interval_min[i][j - 1], self.interval_min[i + (1 << (j - 1))][j - 1]);                i += 1    def rmq(self,l,r,flag):        k = (int)(math.log(r - l + 1.0) / math.log(2.0))        if flag:            return max(self.interval_max[l][k], self.interval_max[r - (1 << k) + 1][k]);        else:            return min(self.interval_min[l][k], self.interval_min[r - (1 << k) + 1][k]);    def sum_interval(self,l1,r1,l2,r2):        return self.rmq(l1,r1,1) + self.rmq(l2,r2,0)    def Intervalxor(self, num, ask):        n = len(num);        self.interval_min = [[0 for _ in range(30)] for _ in range(n + 1)]        self.interval_max = [[0 for _ in range(30)] for _ in range(n + 1)]        for i in range(n):            self.interval_min[i][0] = num[i]            self.interval_max[i][0] = num[i]        self.st(n)        ans = 0        for interval in ask:            l1 = interval[0] - 1            r1 = interval[1] - 1            l2 = interval[2] - 1            r2 = interval[3] - 1            ans ^= self.sum_interval(l1,r1,l2,r2)        return ans;

Java题解详见：九章solution

2. 五字回文算法：模拟算法思路

根据题意，只要从头到尾判断长度为5的子串是否是五字回文

仔细观察给定数据，只有如abcba这种前三个不同的回文串才是符合题意的

那么每取一个长度为5的串就判断一下这个串是否符合条件五字回文的条件即可

复杂度分析时间复杂度为$O(n)$

+ $n$为字符串的长度空间复杂度为$O(1)$

+ 常量级额外空间题解

C++

// This solution is powered by @lintcode.comclass Solution {public:    bool isPalindrome(string s) {        if (s[0] != s[4] || s[1] != s[3]) {            return false;        }        if (s[0] == s[1] || s[1] == s[2] || s[0] == s[2]) {            return false;        }        return true;    }    int Fivecharacterpalindrome(string &s) {        int len = s.size();        if (len < 5) {            return 0;        }        int ans = 0;        for (int i = 0;i < len - 4;i++) {            if (isPalindrome(s.substr(i,5))) {                ans++;            }        }        return ans;    }};

Python

# This solution is powered by @lintcode.comclass Solution:    def is_palindrome(self,s):        if s[0] != s[4] or s[1] != s[3]:            return False        if s[0] == s[1] or s[1] == s[2] or s[0] == s[2]:            return False        return True;    def Fivecharacterpalindrome(self, s):        Len = len(s)        if Len < 5:            return 0        ans = 0;        for i in range(Len - 4):            if self.is_palindrome(s[i:i + 5]):                ans += 1        return ans

Java题解详见：九章solution

3. 三角魔法算法：几何算法思路

根据题意，只要给定点在给定的三个点构成的三角形中，那么就输出Yes

一个点在三角形内时，他与三个顶点可以构成三个三角形，这三个三角形的面积和等于原三角形的面积，同理如果点在三角形边上时也可以这样计算

同时记得特判三个点不构成三角形的情况，比如三点共线的情况。

复杂度分析时间复杂度为$O(1)$空间复杂度为$O(1)$题解

C++

// This solution is powered by @lintcode.comclass Solution {public:    typedef long long ll;    double triangleArea(int x1,int y1,int x2,int y2,int x3,int y3){        return abs((double)x1 * y2 + (double)y1 * x3 + (double)x2 * y3 -             (double)y2 * x3 - (double)y3 * x1 - (double)y1 * x2) / 2.0;     }    string castMagic(vector<vector<int>> &triangle, vector<int> &point) {        int x1 = triangle[0][0], y1 = triangle[0][1];        int x2 = triangle[1][0], y2 = triangle[1][1];        int x3 = triangle[2][0], y3 = triangle[2][1];        int p1 = point[0],p2 = point[1];        double sumArea = triangleArea(x1,y1,x2,y2,x3,y3);        if (sumArea == 0) {            return "No";        }        double area1 = triangleArea(x1,y1,x2,y2,p1,p2);        double area2 = triangleArea(x1,y1,x3,y3,p1,p2);        double area3 = triangleArea(x2,y2,x3,y3,p1,p2);        if(area1 + area2 + area3 == sumArea) {            return "Yes";        }        return "No";    }};

Python

# This solution is powered by @lintcode.comclass Solution:    def triangleArea(self,x1,y1,x2,y2,x3,y3):        return abs(x1 * y2 + y1 * x3 + x2 * y3 - y2 * x3 - y3 * x1 - y1 * x2) / 2.0    def castMagic(self, triangle, point):        x1,y1 = triangle[0][0], triangle[0][1]        x2,y2 = triangle[1][0], triangle[1][1]        x3,y3 = triangle[2][0], triangle[2][1]        p1,p2 = point[0], point[1];        sumArea = self.triangleArea(x1,y1,x2,y2,x3,y3)        if sumArea == 0:            return "No"        area1 = self.triangleArea(x1,y1,x2,y2,p1,p2)        area2 = self.triangleArea(x1,y1,x3,y3,p1,p2)        area3 = self.triangleArea(x2,y2,x3,y3,p1,p2)        if area1 + area2 + area3 == sumArea:            return "Yes"        return "No"

Java题解详见：九章solution

4. 小栖的金字塔算法：超级卡特兰数（大施罗德数）算法思路

假设从$[1,1]$按照题目思路到$[n,n]$,手推前几项，可以发现他符合施罗德数

施罗德数的递推公式为$F_n = F_{n-1} + \sum_{k=0}^{n-1}{F_{k}*F_{n-1-k}}\$，显然直接按照这个公式暴力递推会超时，所以我们引入超级卡特兰数，施罗德数恰好是他的的2倍关系($(F[1])$除外)

超级卡特兰数的递推公式：$F_n * (n+1) = (6*n-3)*F_{n-1}-(n-2)*F_{n-2}$,利用这个公式，就可以$O(n)$的时间内推出第n项超级卡特兰数

根据题意很容易发现,由于题目的限制，无论$[k,k]$在哪儿，到达$[n,n]$的路径都是一个小金字塔，那么我们只要现预处理$F_n$序列，然后直接计算$F_{n-k}$的值即可

复杂度分析时间复杂度为$O(n)$$n$为金字塔的层数，查询时间复杂度为$O(1)$空间复杂度为$O(n)$$n$为金字塔的层数题解

C++

// This solution is powered by @lintcode.comclass Solution {public:    typedef long long ll;    ll mod = 1e9 + 7;    ll inverse(ll x,ll y){        ll sum = 1;        while(y > 0){            if(y%2==1){                sum = sum * x % mod;            }            y /= 2;            x = x * x % mod;        }        return sum % mod;    }    int pyramid(int n, vector<int> &k) {        vector<ll> catalan(n + 1);        catalan[0] = 1;        catalan[1] = 1;        for(int i = 2; i <= n; i++){            catalan[i] = ((6 * i - 3) * catalan[i - 1] % mod - (i - 2) * catalan[i - 2] % mod + mod) % mod * inverse(i + 1,mod - 2) % mod;            cout<<catalan[i]<<endl;        }        ll ans = 0;        for(auto m:k){            if(n - m == 0){                ans += 1;                ans %= mod;                continue;            }            ans += catalan[n - m] * 2;            ans %= mod;        }        return ans;    }};

Python

# This solution is powered by @lintcode.comMOD = 1000000007class Solution:    def inverse(self,x,y):        sum = 1        while y > 0:            if y % 2 == 1:                sum = sum * x % MOD            y //= 2            x = x * x % MOD        return sum % MOD    def pyramid(self, n, k):        catalan = [1] * (n + 1)        for i in range(2,n + 1):            catalan[i] = ((6 * i - 3) * catalan[i - 1] % MOD - (i - 2) * catalan[i - 2] % MOD + MOD) % MOD * self.inverse(i + 1,MOD - 2) % MOD;        ans = 0        for m in k:            if n - m == 0:                ans += 1;                ans %= MOD;                continue;            ans += catalan[n - m] * 2;            ans %= MOD;        return ans;