字节笔试测开9.20

1.求字符串最短重复节

Input

ababab

Output

ab

暴力思路

错误分析，笔试时候由于不能本地调试，一直报错，事后分析原因，应该是python 两个整数相除会自动转化为浮点数。另外暴力法估计会超时。细节，最后不知道要不要加回车符，可以通过end控制，试一试

def solve(s):
    for i in range(1,int(n/2)+1): # 2. n/2
        if n%i == 0:
            mode = s[:i]
            if mode*(int(n/i)) == s: # 1. n/1
                return mode
    return s

s = input()
n = len(s)
if n==0:
    print(s, end = '')
else:
    print(solve(s), end = '')

KMP思路

比较好的解法是KMP解法，自己学习过KMP，一直以为是模板匹配的，就是在字符串a中找到字符串b第一次出现的位置。还是没有完全理解这个算法。还可以求最小重复节。（推荐一个比较好理解的KMP算法）

KMP可以用来求最小循环节

定理：假设S的长度为len，则S存在最小循环节，循环节的长度L = len-next[len]，子串为
S[0…len-next[len]-1]。

（1）如果len可以被len - next[len]整除，则表明字符串S可以完全由循环节循环组成，循环周期T=len/L。
（2）如果不能，说明还需要再添加几个字母才能补全。需要补的个数是循环个数
L-len%L=L-(len-L)%L=L-next[len]%L，L=len-next[len]。

KMP也可以匹配字符串

vector<int>  getNext(string p)
{
  vector<int> next;
  next.resize(p.size());

  next[0] = -1;
  int i = 0, j = -1;

  int pL = p.size();

  while (i < pL-1)
  {
    if (j == -1 || p[i] == p[j])
    {
      ++i;
      ++j;
      next[i] = j;

    } 
    else
    {
      j = next[j]; 
    }

  }
  return next;
}

int main(int argc, char const *argv[])
{
    /* code */

    string s;
    cin>>s;
    vector<int> next = getNext(s);

    cout<<"next "<<endl;
    for(auto& iter:next)
    {
      cout<<iter<<" ";
    }
    cout<<"min length "<<s.size()-1-next[s.size()-1]<<endl;
    return 0;
}

简单计算器
包含'+','-','*','^'四种运算的计算器，其中 ^ 代表幂运算
Input

1 2 + （-2^9~2^9）

Output

3

错误分析：笔试的时候，自己不知道脑袋咋了，直接把^当运算符了，其他三个可以，但是^在c++中定义为求异或。不过令人疑惑的是，一直是%0可还行，难道不是75%，哈哈。不过，此题坑点也不少。主要是要用快速幂和求负幂。我记得输入应该是整数，但是，求负幂的时候要用浮点类型，要不然直接取整了，真的是细节太多，看不清。

快速幂

快速幂一个版本可以理解为
把幂指数拆成二进制，这样的好处是可以用到增量的思想，减少了很多计算。
比如2^10, 把10拆成1010，意思就是2^8 * 2^2。

#include<bits/stdc++.h>
using namespace std;
constexpr const int MAXVAL = 505;
typedef long long ll;

// 八千三百万零二十
// 1 2 3 4 5 6 7 8
// 
#define MOD (1000000007)

double fastPower(ll a, ll b)
{
    ll ans = 1, base = a;

    bool minus = false;
    if(b<0) 
      {
        minus = true;
        b = -b;
      }

    while(b)
    {
      if (b&1) ans = (ans*base)%MOD;
      base = base*base%MOD;
      b >>= 1;
    }
    return minus? 1.0/static_cast<double>(ans):static_cast<double>(ans);
}



int main(int argc, char const *argv[])
{
  int n;
  cin>>n;


  while(n--)
  {
    ll a,b; char c;
    cin>>a>>b>>c;

    ll ans;
    switch (c)
    {
      case '+':
      {
        ans = (a%MOD+b%MOD)%MOD;
        cout<<ans<<endl;
        break;
      }
      case '-':
      {
        ans = (a%MOD-b%MOD)%MOD;
        cout<<ans<<endl;
        break;
      }
      case '*':
      {
        ans = (a%MOD*b%MOD)%MOD;
        cout<<ans<<endl;
        break;
      }
      case '^':
      {
        cout<<fastPower(a, b)<<endl;
        break;
      }
    }

  }
  return 0;
}