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算法)
定理:假设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; }