天天看点
返回

天池×九章算法｜超级码力在线编程大赛 第2场题解

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)$

        + 常量级额外空间

// 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;
    }
};           
# 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 ans

3. 三角魔法

算法：几何

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

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

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

  • 时间复杂度为$O(1)$ 

// 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";
    }
};           
# 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"

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}$的值即可

    • $n$为金字塔的层数，查询时间复杂度为$O(1)$
    • $n$为金字塔的层数 

// 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;
    }
};           
# 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;

更多高频算法题，可在

LintCode

进行在线评测

机器学习/深度学习 人工智能 算法 java c++ Python java后台人工智能算法 java后台大数据人工智能算法 python人工智能机器人 Python深度学习 python深度学习学习
上一篇: 构建微信公众号管理系统构建微信公众号管理系统
下一篇: Class1

继续阅读