模拟算法

2026-09-12

Coding

所谓的模拟算法类型的题目，没有特定的模板，没有特定的算法，你需要做的是找规律，或者单纯的根据题意模拟一段过程。关键是读题，明确输入输出以及各个变量之间的隐藏关系！

提莫攻击

思路是很直接的，读懂题目即可。时间复杂度为O（N），空间复杂度为O（1）

  class Solution {
    public:
        int findPoisonedDuration(vector<int>& timeSeries, int duration) {
            
            int totally_result=0;
            int time_last=timeSeries[0];
            for(int i=1;i<timeSeries.size();i++)
            {
                if(time_last+duration<=timeSeries[i])
                {//不用重置
                    totally_result+=duration;//记录冰冻的时间
                    time_last=timeSeries[i];//更新
                }
                else
                {//要重置
                    totally_result+=(timeSeries[i]-time_last);
                    time_last=timeSeries[i];//更新
                }
            }
            totally_result+=duration;//最后的结果
            return totally_result;
        }
    };

z字型变换

我的解法的时间和空间复杂度都为O（N）思路很简单。就是定义一个size为numRows的Vector.每一个元素为string，按照z变换的索引来把每个字符放到该在的vector元素上。最后输出依次叠加即可~

class Solution {
  public:
      string convert(string s, int numRows) {
  
          if(numRows<2)
              return s;
          
          //按行索引来存到vector中
          vector<string> result_group (numRows);//一共就numRows个元素（string也是vector的一种）
          int i=0;//代表索引。
          int flag=1;//控制索引的移动
  
          for(auto c:s)
          {
              result_group[i]+=c;//在对应行上加字符
              //到一侧（0或numRows-1）就要反向
              if(i==numRows-1 && flag==1)
                  flag=-1;
              if(i==0 && flag==-1)
                  flag=1;
              i+=flag;//flag的正负决定了是向上还是向下
          }
  
          string result;
          for(int i=0;i<numRows;i++)
              result+=result_group[i];
  
          return result;
          
      }
  };

外观数列

采用递归的解法：由于递归中带有for循环，时间复杂度为O（N²）,空间复杂度为递归的栈空间

class Solution {
  public:
      string countAndSay(int n) {
  
          if(n==1)
              return "1";
          
          string input_str=countAndSay(n-1);//每次输入的为上一个的结果
          int temp_num=1;//初始化为1
          char temp_char=input_str[0];
          string result;
          for(int i=1;i<input_str.size();i++)
          {
              if(input_str[i]==temp_char)//还是等于结果的
              {
                  temp_num++;
              }
              else
              {
                  result=result+to_string(temp_num)+temp_char;
                  //然后重置一下
                  temp_char=input_str[i];//新的字符
                  temp_num=1;//当前为1个
              }
          }
  
          //出来的结果再加一次
          result=result+to_string(temp_num)+temp_char;
  
          return result;
      }
  };

由于数量只有30个，还有一种解法是打表直接输出全部结果😂,时间复杂度为O(1)，空间复杂度为O(C×M)。其中 C 是 N 是上界，在本题中 C=30，M 为生成的字符串中的最大长度。

但类似这种可以拆分为子问题的解题思路最直接其实还是递归~

数青蛙

时间复杂度为O（N），空间复杂度为O（1）.用计数法最简单

class Solution {
  public:
      int minNumberOfFrogs(string croakOfFrogs) {
  
          // croak为一只青蛙完整的叫声
  
          //用计数器，分别计算每个字符发了多少
          int c=0, r=0, o=0, a=0,k=0;
          int num_frog=0;
  
          for(auto _str:croakOfFrogs)
          {
              if(_str=='c')
              {
                  if(k>0)
                      k--;//若前面有青蛙发过k，那么就是前面那只
                  else//前面没有k
                      num_frog++;//增加一只青蛙
                  c++;//发了声音，自加
              }
              else if (_str=='r')
              {
                  if(c>0)
                      c--;
                  else //若前面没有c，那么就是不符合要求
                      return -1;
                  r++;//发了r
              }
              else if (_str=='o')
              {
                  if(r>0)
                      r--;
                  else //若前面没有r，那么就是不符合要求
                      return -1;
                  o++;//发了o
              }
              else if (_str=='a')
              {
                  if(o>0)
                      o--;
                  else //若前面没有o，那么就是不符合要求
                      return -1;
                  a++;//发了a
              }
              else if (_str=='k')
              {
                  if(a>0)
                      a--;
                  else //若前面没有a，那么就是不符合要求
                      return -1;
                  k++;//发了k
              }
          }
          // 遍历完后。如果全部都为0，那么正好发完音
          if(c==0
              &&r==0
              &&o==0
              &&a==0
              &&k>=1) //最后的k应该是大于等于1（由于k可能是不受到c影响的）
              return num_frog;
          else
              return -1;
      }
  };

汽水瓶

#include <iostream>
using namespace std;

int main() {
    int n;//一开始汽水瓶的数目
    while (cin >> n) { // 注意 while 处理多个 case
        int result=0;//一共喝到汽水的数目
        
        if (n<2)
            continue;
        //当最终的汽水瓶的数目大于等于2就可以向老板借一个
        while(n>=2)
        {
            if(n==2)
                n=n+1;//向老板借一个
            int get_new=n/3;//整除了3就是可以获得多少瓶新的汽水
            int remain=n%3;//换完后剩余的汽水
            result+=get_new;
            n=remain+get_new;//剩余的汽水+新拿到的喝完的
        }

        std::cout<<result<<std::endl;
    }
}

下面解法写法上更简单，但是不好理解，建议用上面直观的一步一步分析～

#include <iostream>
using namespace std;

int main() {
    int input_vale;
    while (cin >> input_vale) {
        if (input_vale == 0)
            continue;
        // 每有两个瓶子，借1个，就有3个。可以喝一瓶，然后换掉。最终位0个瓶子。
        //故此，可以被2整除，就是可以喝多少个
        cout << input_vale/2 << endl;
    }
}

杨辉三角的变形

采用数学归纳法

#include <iostream>
using namespace std;

int main() {
    //数学归纳法：
    // 1。-1
    // 2。-1
    // 3。 2
    // 4。 3
    // 5。 2
    // 6。 4
    // 下面会重复2、3、2、4

    int n;
    cin>>n;

    if(n<=2)
        std::cout<<-1;
    else if(n%2==1)
        std::cout<<2;
    else if(n%4==0)
        std::cout<<3;
    else 
        std::cout<<4;
}

完全数计算

直接按照题目要求实现数学过程

#include <iostream>
  using namespace std;
  
  int main() {
      int num;
      cin>>num;
  
      int count_result=0;
  
      for(int i=1;i<=num;i++)
      {
          //每个进行判断
          int sum=0;
          for(int j=1;j<=i/2;j++)//注意：除了自身，那么最大应该只到一半
          {
              if(i%j==0)//能整除
                  sum+=j;//和
          }
          if(sum==i)//因子只和相等
              count_result++;
      }
      std::cout<<count_result;
  }

质数/素数

质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数

质数因子

#include <cmath>
#include <iostream>
using namespace std;

int main() {

    long intput_value;
    cin >> intput_value;
    // 质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数

    //注意从2开始，1不能算。
    // 注意：一个数的质因数不会超过它的算术平方根
    for (long i = 2; i <= sqrt(intput_value); i++) { ////从小到大的质因子，质因子不会超过它的开方

        //能整除掉，就是当前是质因子
        while (intput_value % i == 0) { //那么需要将其全部除完再继续下一步
            std::cout << i << " ";
            intput_value = intput_value / i; //去掉当前的质数因子后的值
        }
    }
    //结束后，如果最后一个值还是大于1，那么它也是质数因子
    if (intput_value > 1)
        std::cout << intput_value << std::endl;
}

素数伴侣

此题较难，在做的时候也是根据答案一步一步做的，首先设计了判断是否素数的判据（给出两种写法）。其次这里用递归获取最长的素数伴侣，又涉及到选择与否，更像是回溯算法，稍微有点复杂了～

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

//如果一个数是素数，只有1和本身可以被整除
// bool isprime(const int value) {
//     for(int i=2;i<=sqrt(value);i++)
//     {
//         if(value%i==0)
//             return false;
//     }
//     return true;
// }

// 一个数的质因数不会超过它的算术平方根

// 对于判断是否素数，下面写法更好
bool isprime(const int value) {
    for (int i = 2; i * i <= value; i++) {
        if (value % i == 0) //如果被整除了
            return false;
    }
    return true;
}

bool find(int odd, vector<int>& evens, vector<bool>& evens_used,
          vector <int>& match_evens) {
    //遍历所有的偶数
    for (int i = 0; i < evens.size(); i++) {
        //如果当前偶数没有被用过，且它跟奇数之和是素数
        if (!evens_used[i] && isprime(odd + evens[i])) 
        {
            evens_used[i] = true; //标记以及被用了
            //如果这个偶数，还没匹配到奇数，或者已经匹配了，但是还有其他奇数匹配的选择
            if (match_evens[i] == 0 ||
                find(match_evens[i], evens, evens_used, match_evens)) 
            {
                match_evens[i] = odd;//匹配到的基数
                return true;
            }

        }
    }
    return false;
}

int main() {
    int num_int;
    cin >> num_int;//输入的数的数目

    // 偶数+偶数=偶数，必不是素数，因此素数只能是奇数+偶数
    vector<int> int_group(num_int);
    vector<int> evens;//存偶数
    vector<int> odds;//存奇数
    for (int i = 0; i < num_int; i++) {
        cin >> int_group[i];
        //同时记录奇数与偶数
        if (int_group[i] % 2 == 0) //若能被2整除（为偶数）
            evens.push_back(int_group[i]);
        else
            odds.push_back(int_group[i]);
    }

    int count = 0;
    //缺少奇数或者偶数无法构成素数
    if (evens.size() == 0 || odds.size() == 0) {
        std::cout << count << std::endl;
        return 0;//跳出下面的
    }

    //统计每个偶数，匹配的是哪个奇数
    vector<int> match_evens(evens.size(), 0);

    //遍历所有的奇数
    for (int i = 0; i < odds.size(); i++) {
        vector<bool> evens_used(evens.size(), false); //每一轮都将偶数是否用过记为0

        //对每个基数进行匹配（进行递归）
        if (find(odds[i], evens, evens_used, match_evens)) //最优的匹配的偶数对
            count++;
    }
    std::cout << count << std::endl;

    
    return 0;
}

查找组成一个偶数最接近的两个素数

也可以用一个全局变量来记录全部最小值。但是这样的复杂度为O（N）而本方法的复杂度为O（N/2）。当然乘上还没算循环内的isprimary函数的复杂度为O（N）

#include <iostream>
using namespace std;

bool isprimary(int input_value)
{
    for(int i=2;i*i<=input_value;i++)
    {
        if(input_value%i==0)//可以被整除
            return false;
    }
    return true;//是素数
}

int main() {
    int input_value;
    cin>>input_value;
    for(int i=input_value/2;i>=2;i--)//也可以用一个全局变量来记录全部最小值。但是这样的复杂度为O（N）而本方法的复杂度为O（N/2）
    {
        int num1=i;
        int num2=input_value-i;

        if(isprimary(num1) && isprimary(num2))
        {
            // 输出组成指定偶数的两个素数差值最小的素数对。
            std::cout<<num1<<std::endl<<num2;
            break;
        }
    }

}

高效寻找素数

class Solution {
  public:
      bool isPrimes(int input_value)
      {
              
          //素数只能被自身和1整除
          for(int i=2;i*i<=input_value;i++)
          {
              if(input_value%i==0)//能被整除
                  return false;
          }
          return true;
      }
  
      int countPrimes(int n) {
          if(n<2)
              return 0;
          int result=0;
  
          vector<bool> isPrimegroup(n, true);//初始化全部为true
          for (int i = 2; i < n; i++) 
          {
              if (isPrimegroup[i]) //如果i是素数
              {
                  result++;
                  //那么全部的j=2*i;j=j+i都不是素数
                  for (int j = 2 * i; j < n; j += i) {
                      isPrimegroup[j] = false;
                  }
              }
          }
          
          // //这种做法是最基本的，但会超时
          // for(int i=2;i<n;i++)//从2开始
          // {
          //     if(isPrimes(i))//是数素就统计一下
          //         result++;
          // }
  
          return result;
      }
  };

矩阵乘法

数组中的矩阵运算

#include <iostream>
using namespace std;

int main() {
    int x, y,z;
    cin>>x>>y>>z;

    int a[x][y], b[y][z], result[x][z];

    //传入数据到矩阵中
    for(int i=0;i<x;i++)
    {
        for(int j=0;j<y;j++)
        {
            cin>>a[i][j];
        }
    }
    
    //传入数据到矩阵中
    for(int j=0;j<y;j++)
    {
        for(int k=0;k<z;k++)
        {
            cin>>b[j][k];
        }
    }
    
    //模拟矩阵的计算过程
    for(int i=0;i<x;i++)
    {
        for(int k=0;k<z;k++)
        {
            int sum=0;
            for(int j=0;j<y;j++)
            {
                sum+=a[i][j]*b[j][k];
            }
            result[i][k]=sum;
        }
    }
    
    //从矩阵中输出结果
    for(int i=0;i<x;i++)
    {
        for(int k=0;k<z;k++)
        {
            std::cout<<result[i][k]<<" ";
        }
        std::cout<<endl;
    }

}
// 64 位输出请用 printf("%lld")

百钱买百鸡问题

#include <iostream>
using namespace std;

int main() {
    int n;
    while(cin>>n)//输入任何一个整数，即可运行程序。
    {
        int totally_n=100;
        int totally_money=100;
        int x,y,z;//5，3，1/3
        for(int x=0;5*x<=100;x++)
        {
            for(int y=0;3*y<=(100-5*x);y++)
            {
                z=100-x-y;
                if(z%3==0 && z/3==(100-5*x-3*y))//必然可以被3整除
                    std::cout<<x<<" "<<y<<" "<<z<<std::endl; 
            }
        }
        
    }
}

计算日期到天数转换

闰年是可以整除4但不能整除100

#include <iostream>
#include <map>
using namespace std;

map<int, int> moonth_days
{
    {1,31},
    {2,28},//2月先统一为28天
    {3,31},
    {4,30},
    {5,31},
    {6,30},
    {7,31},
    {8,31},
    {9,30},
    {10,31},
    {11,30},
    {12,31}
};

//或：int moonth[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int main() {
    int year, moonth,day;
    cin>>year>>moonth>>day;

    int result=day;

    for(int i=1;i<moonth;i++)
    {
        result+=moonth_days[i];
    }

    if(moonth>2)
    {
        //根据年份判断，2月是否29，若是就要加1
        if(year%4==0 && year%100!=0)//闰年是可以整除4但不能整除100？（公历年份是4的倍数，且不是100的倍数的）
            result+=1;
    }

    std::cout<<result;
}
// 64 位输出请用 printf("%lld")

尼科彻斯定理

数学归纳法

#include <iostream>
#include <cmath>
#include <string>
using namespace std;

int main() {
    int num;
    cin>>num;

    //由数学归纳法可得，为num的平方为中心点,num个奇数
    string result;
    int middle_index=pow(num,2);
    int start_index=middle_index-num;
    int end_index=middle_index+num;

    for(int i=start_index;i<=end_index;i++)
    {
        if(i%2!=0)//为基数
            result+=to_string(i)+'+';
    }

    std::cout<<result.substr(0,result.size()-1);//去掉最后一个+号
}

将真分数分解为埃及分数

最简单的解法～～～

#include <iostream>
#include <string>
using namespace std;

int main() {
    //由于子需要输出一个结果，那么最直接的其实就是所有的分子只和，分母不变！
    string input_str;
    while(cin>>input_str)
    {
        int index=input_str.find('/');

        string fenzi=input_str.substr(0,index);//不包含index
        string fenmu=input_str.substr(index+1,input_str.size()-index-1);
        int num=stoi(fenzi);
        string result;
        while(num--)
        {
            result+="1/"+fenmu+'+';
        }

        std::cout<<result.substr(0, result.size()-1)<<std::endl;
    }
}

等差数列

#include <iostream>
using namespace std;

int main() {
    int n;
    cin>>n;
    int a1=2;
    int d=3;//公差为3
    int sum=0;
    // sum=n*a1+n*(n-1)*d/2;//等差数列求和公式

    sum=a1;
    n=n-1;//第一个放入
    while(n--)
    {
        a1+=3;//每次加3;
        sum+=a1;
    }

    std::cout<<sum;
}

求解立方根

关键点在于要考虑负号以及小数的情况。且浮点数left<=right会无限运行，需要给个小范围的阈值

#include <iomanip>
#include <iostream>
#include <cmath>
using namespace std;

int main() {
   double value;
   cin>>value;

   //二分法

   //由于是开立方根，所以存在为负号的情况
   //同时需要考虑小数的情况    
   double left=min(-1.0, value);
   double right=max(1.0, value);
   double middle;//就是结果
//    while(left<=right)//由于是浮点数，为此永远都很接近不会相等
    while(abs(right-left)>0.01)//因此给0.01。毕竟小数点保留1位而已（注意是相减大于某个小数）
   {
        middle=(left+right)/2.0;
        double result=pow(middle,3);
        if(result<value)
        {
            left=middle;
        }
        else if(result>value)
        {
            right=middle;
        }
        else//相等
            break;
   }
   std::cout<<fixed<<setprecision(1)<<middle;
}

求最小公倍数

a*b一定是a、b的公倍数，但不一定是最小的

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin>>a>>b;

    // // 方法1:暴力匹配
    for(int i=max(a,b); ;i++)//从较大者开始
    {
        int beishu=i;
        if(beishu%a==0 && beishu%b==0)
        {
            std::cout<<beishu;
            return 0;
        }
    }

    // //方法2:最小公倍数一定是较大者的整数倍
    // //a*b一定是a、b的公倍数，但不一定是最小的
    // for(int i=1;i<=min(a,b);i++)
    // {
    //     int beishu=i*max(a,b);//较大者的整数倍。最大也是到min(a,b)*max(a,b)
    //     if(beishu%a==0 && beishu%b==0)
    //     {
    //         std::cout<<beishu;
    //         return 0;
    //     }
    // }

}

Nim游戏

class Solution {
  public:
      bool canWinNim(int n) {
          //数序归纳法：
          // 我先手，一次可以拿1～3。要保证对手拿前有4块石头，这样无论它拿多少，最后都是我拿的。
  
          //必然为4的倍数.若可以整除4那么就我赢，否则对手赢
          if(n%4==0)//整除了4，我先拿则必然输
              return false;
          return true;
          // return (n%4!=0);
      }
  };

石头游戏

class Solution {
  public:
      bool stoneGame(vector<int>& piles) {
          //解法1:先蒙一个true，毕竟题目给的案例都是true，可能一蒙就对了，或者至少一半。
  
          //首先：石头的堆的数量为偶数，所以你们两人拿走的堆数一定是相同的。石头的总数为奇数，也就是你们最后不可能拥有相同多的石头，一定有胜负之分。
          // 先手的必胜（毕竟题目说了，发挥最佳水平，提前算好就可以了！）
          return true;
      }
  };

灯泡开关

没有很理解这个过程，单纯做一个记录吧。可参考Link

class Solution {
  public:
      int bulbSwitch(int n) {
          // 数学归纳法：
          // 将所有的灯泡从左到右依次编号为 1,2,⋯,n，
          // 对于第 k 个灯泡，它被切换的次数恰好就是 k 的约数个数。如果 k 有偶数个约数，那么最终第 k 个灯泡的状态为暗；如果 k 有奇数个约数，那么最终第 k 个灯泡的状态为亮。
  
          return (int) sqrt(n);
  
      }
  };

2的幂

class Solution {
  public:
      bool isPowerOfTwo(int n) {
  
          //能被2整除,且余数也可以继续被2整除
          while(n>2)
          {
              if(n%2!=0)
                  return false;
              n=n/2;
          }
  
          //整除后剩余的数是2或者原本就是1，那也是
          if(n<=2 && n>0)
              return true;
  
          // （整除后必然小于等于2啦～）其他都是false
          return false;
      }
  };

Kwan Wai-Pang