其他算法题

末蓝、 2021-09-18 12:54 321阅读 0赞

**绳子可以覆盖的最多点数**  
数轴上从左到右有n各点a\[0\], a\[1\], ……,a\[n -1\]，给定一根长度为L的绳子，求绳子最多能覆盖其中的几个点  
题解：对于数轴上的点，我们考虑一根长度为L的绳子如何尽可能的覆盖到多的点。那么最直观的解法就是如果我们把长度为L的绳子放在这个数轴上，每次向右移动一格，统计在内的点数。那么存在的一个问题就是如何移动？我们先假定绳子已经在覆盖到最够多的点，此时再往前一步就超过绳子长度。这时候我们就该考虑向右平移绳子，平移方法就是我们的绳子尾部收缩一格，然后考虑是否能够继续往前一步，如果不能的话继续收缩。  
使用两个指针，一个front，一个rear，每次front到rear距离比L小，统计覆盖的点数。保存覆盖点数的最大值，然后front++；比L大，rear++，每个数最多遍历2遍，复杂度O(N)。

#include <iostream>
    
    using namespace std;
    int main(void)
    {
        int arr[] = {-3, 1, 3, 9, 11, 13, 14, 25};
        int front = 0, rear = 0;
        int max_n = 0;
        const int l = 15;
        int n = sizeof(arr) / sizeof(arr[0]);
        while(front < n)
        {
            if(arr[front] - arr[rear] <= l)
            {
                max_n = max_n > (front - rear) ? max_n : front - rear;
                front++;
            }
            else
                rear++;     }
        cout<<"长度为："<<l<<"的绳子最多覆盖轴上的点数为："<<max_n+1<<endl;
        return 0;
    }

**子序列的个数**  
[试题][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2MjM0NjEz_size_16_color_FFFFFF_t_70]  
对于不重复序列，那么每个数可以出现或者不出现，也就是2^n-1（除掉全空情况）。对于重复序列，例如上图第二个红框，会出现下列情况：  
如果8439存在一个数那不会重复，如果8439全不出现，那么会有以下情况：  
第一个6出现，第二个6出现；  
第一个6出现，第二个6不出现；  
第一个6不出现，第二个6出现；  
第一个6不出现，第二个6不出现；  
以上第二种情况会导致出现相同子序列问题。

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    const int mod=1e9+7;
    int mat[100005];
    int dp[100005];
    int have[100005];
    int main()
    {
    	int n;
    	memset(dp,0,sizeof(dp));
    	memset(have,0,sizeof(have));
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++) {
    		scanf("%d",&mat[i]);
    	}
    	dp[0]=1;//初始化，空串 
    	for(int i=1;i<=n;i++) {
    		dp[i]=dp[i-1]*2%mod;//不能加mod后在%mod,会超int 
    		if(have[mat[i]]) {
    			dp[i]=(dp[i]-dp[have[mat[i]]-1]+mod)%mod;
    		}
    		have[mat[i]]=i;//每次只记录前一次出现的位置就行 
    	}
    	printf("%d\n",dp[n]-1);//空串计算两次，减一
    	return 0;
    }

**博弈论之取石子游戏的学习**  
[博弈论之取石子游戏的学习][Link 2]

**蚂蚁爬杆**  
[蚂蚁爬杆][Link 3]

#include <iostream>
    using namespace std;
    
    void CalcTime(double PoleLen,double *xPos,int AntNum,double speed,double &tMin,double &tMax)
    {
        tMax=tMin=0;
        for(int i=0;i<AntNum;++i)
        {
            double curMax=0;
            double curMin=0;
            if (xPos[i]>(PoleLen/2))
            {
                curMax=xPos[i];
            }
            else
            {
                curMax=(PoleLen-xPos[i]);
            }
            curMin = PoleLen - curMax;
            if (tMax < curMax)
            {
                tMax = curMax;
            }
            if (tMin < curMin)  //注意这里是小于因为是所有蚂蚁最短时间，取最短中最大的
            {
                tMin = curMin;
            }
        }
        tMax/=speed;
        tMin/=speed;
    }
    
    void main()
    {
        double poleLength=27;
        double ants[5]={3,7,11,17,23};
        double speed=1;
        double timeMax,timeMin;
    
        CalcTime(poleLength,ants,5,speed,timeMin,timeMax);
        cout<<"MaxTime:"<<timeMax<<endl;
        cout<<"MinTime"<<timeMin<<endl;
    }

[Link 1]: https://blog.csdn.net/bbhhtt/article/details/81875092
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2MjM0NjEz_size_16_color_FFFFFF_t_70]: /images/20210520/8eb218212c6045d78095f1e57b89533b.png
[Link 2]: https://blog.csdn.net/qq_33765907/article/details/51174524
[Link 3]: https://www.cnblogs.com/Linkabox/archive/2013/10/09/3359828.html