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.com
class 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.com
import math
class 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.com
class 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.com
class 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 ansJava题解详见：九章solution
3. 三角魔法
算法：几何
算法思路
根据题意，只要给定点在给定的三个点构成的三角形中，那么就输出Yes
一个点在三角形内时，他与三个顶点可以构成三个三角形，这三个三角形的面积和等于原三角形的面积，同理如果点在三角形边上时也可以这样计算
同时记得特判三个点不构成三角形的情况，比如三点共线的情况。
复杂度分析
- 时间复杂度为$O(1)$
- 空间复杂度为$O(1)$
题解
C++
// This solution is powered by @lintcode.com
class 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.com
class 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.com
class 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.com
MOD = 1000000007
class 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;Java题解详见：九章solution
更多高频算法题，可在 LintCode 进行在线评测
