A 组队队名(模拟，略过)
链接：https://ac.nowcoder.com/acm/contest/8440/A
每个队伍一行，按“队名 队员一姓名 队员二姓名 队员三姓名”的格式输出，要求每个队中的队员按照排名从大到小排列。
B 两点距离
链接：https://ac.nowcoder.com/acm/contest/8440/B
已知现在有n个点，以1-n标号，不同两点之间的距离为两点标号的最大公约数，求点x到点y的所需移动的最短距离。
解析：
解题关键在于两点间最短距离不一定是两点标号的最大公约数，图的思想可以借助另一个点，再到达目标点
- 若两点相同，距离为0
- 若两点最大公约数为1，则距离为1
- 其他情况，对于两点来说，一定存在另一个点，到该两点的距离都为1，例如标号为1的点，所以其他情况为2
求最大公约数，建议用循环更节省时间(也可直接用库函数__gcd(int a,int b):
while(a%b!=0){
c=a%b;
a=b;
b=c;
}
return b;
C 轮到谁了(斐波那契数列)
链接：https://ac.nowcoder.com/acm/contest/8440/C
假设有一对兔子，长两个月它们就算长大成年了。然后以后每个月都会生出1对兔子，生下来的兔子也都是长两个月就算成年，然后每个月也都会生出1对兔子了。这里假设兔子不会死，每次都是只生1对兔子。 第一个月只有一对刚出生的小兔子（标号为0）。每对出生的兔子按照按照出生顺序0到m-1循环标号，前n个月内出生的最后一对兔子的标号就是需要做作业的人的学号。你能找出谜底吗？
解析：
通过题意能看出此题为斐波那切数列，若看不出来，把数据列出来，也能看出，每一项都等于前两项相加和再加一，加一原因在于标号从0开始。
#include<stdio.h>
int f[1005];
int main(){
int n,m,t;
scanf("%d",&t);
while(t--){
scanf("%d %d",&n,&m);
for(int i=2;i<n;i++){
f[i]=(f[i-1]+f[i-2]+1)%m;
}
printf("%d\n",f[n-1]);
}
}
F 最长回文串(判断一串字符是否能构成回文串)
链接：https://ac.nowcoder.com/acm/contest/8440/F
回文串是反转后与自身完全相同的字符串
比如："ABA","ACMMCA","A"。
给出一系列长度相同的字符串，请按序进行如下操作构造出最长的回文串:
1.舍弃一些字符串 2.重新排列剩余的每个**字符串内字符的顺序，重新排列后的结果可以与原字符串相同** 3.重新排列剩余字符串的顺序 4.将剩余字符串按序首尾连接组成回文串
解析：
根据题目要求可知，输入多个子串，可以打乱子串内部顺序，然后将子串重新排序构成回文串，求最后组成的回文长度。问题转换成，到底哪些子串可以参与组成回文串，解题思路：
- 回文串应首尾对应，所以出现次数大于2的子串都可取偶数个参与组成最后的回文串
- 满足以上条件，已取偶数个子串组成回文串，此时该回文串不一定是最长回文串，若还存在一个本身是回文串的子串可放在中间与上述偶数个回文串组成最长回文串。
- 所以需判断该子串是否能按照题意本身构造出回文串：用sort排序，若长度为偶数，则该子串字符应两两相等，若为奇数，则可用map记录，出现奇数次的字符个数应小于2，满足上述条件的奇偶子串可构成回文串。
- 综上，记录所有出现次数大于等于2的子串的最大偶数次，求出长度和，同时，若该子串出现次数为奇数次，并且他满足构成回文串条件，则同时记录他的长度，最后退出，将偶数次个数的子串长度+该回文子串长度即可求出结果
#include<bits/stdc++.h>
using namespace std;
bool Jhw(string s,int m){
int z[1000]={0};
int flag=0;
if(m==1){
return true;
}
if(m%2){
for(auto temp:s){
z[temp]++;
}
for(auto temp:s){
if(z[temp]%2){
flag++;
if(flag>1){
return false;
}
}
}
return true;
}else{
for(int i=0;i<s.size()-1;i=i+2){
if(s[i]!=s[i+1]){
return false;
}
}
return true;
}
}
int main(){
int n,m;
cin>>n>>m;
int maxlen=0;
unordered_map<string,int> p;
while(n--){
string s;
cin>>s;
sort(s.begin(),s.end());
p[s]++;
}
int flag=0;
for(auto temp:p){
if(temp.second>=2){
maxlen=temp.second/2*2*m+maxlen;
//出现次数大于2的，除以2再乘2，得到的便是他最大偶数次
}else if(flag==0&&temp.second%2){
if(Jhw(temp.first,m)){
flag=1;
}
}
}
if(flag){
cout<<maxlen+m;
}
else{
cout<<maxlen;
}
return 0;
}
G 线性筛查素数
链接：https://ac.nowcoder.com/acm/contest/8440/G
众所周知，每个人都有自己的幸运数字，而管管的幸运数字是除了1和它自身外，不能被其他自然数整除的数，管管现在有T次询问，每次询问会给定一个数字N，你需要告诉他N是不是他的幸运数字，如果不是，需要你告诉他离N最近的幸运数字L与N差的绝对值 即|L-N|。
解析
（虽然此题暴力可以过）但优化后应标记出范围内所有素数，避免每次都需要重新判断该数是不是素数，埃氏筛以倍数的形式排除掉合数，但会多次重复判断合数，但埃氏筛的原理可以保证，在找到下一个满足条件的该数时，比他小的除1外的所有数字都不是他的因数，所以他是质数，在埃氏筛原理的基础上，使用线性筛，让每个合数都被他最小质因数和当前判断数字排除，就可以达到不会重复判断一个数的目的例如12应该是被i×prime[j]（6×2）排除掉而不是(4*3)，
if(i%prime[j]==0) break;
当i能整除prime[j]时，就不会继续排除i×prime[j+1],因为质数数组是递增的，如果继续计算i×prime[j+1]那么表示，i×prime[j+1]这个数是被prime[j+1]这个质因数排查掉的，但是i能整除prime[j]，所以代表此时i可以转化成prime[j]×某个数，那么i×prime[j+1]就可以表示成prime[j]×某个数×prime[j+1]，由此可见，这个合数的最小质因数应该是prime[j]而并非prime[j+1],所以后续肯定会有一个大于i的值和prime[j]相乘等于这个数，把这个数排查掉，所以把这个数留给后面的i去排查，才能满足每个合数都被他最小质因数排查掉，才能达到去重的目的。PS：不得不感慨一句，能想出这个算法的人真的是天才。
线性筛素数时间复杂度为O(n),数据量越大，线性筛优势越明显。
#include<bits/stdc++.h>
using namespace std;
int s[10008];
int prime[10008];
void Searchzs(){
int index=0;
for(int i=2;i<=10008;i++){
if(s[i]==0){
index++;
prime[index]=i;
}
for(int j=1;j<=index&&prime[j]*i<10008;j++){
s[i*prime[j]]=1;
if(i%prime[j]==0) //线性筛的精髓
{
break;
}
}
}
}
int main(){
int t;
scanf("%d",&t);
Searchzs();
int jia=0;
int jian=0;
while(t--){
int n;
scanf("%d",&n);
if(s[n]==0){
printf("YES\n");
}else{
for(int i=0;;i++){
if(s[n-i]==0){
jian=i;
break;
}
}
for(int i=0;;i++){
if(s[n+i]==0){
jia=i;
break;
}
}
printf("%d\n",min(jia,jian));
}
}
return 0;
}
I 模拟签到题
略
J 给定坐标，判断该点是否在三角形内部
链接：https://ac.nowcoder.com/acm/contest/8440/J
在鸽者文明使用二项箔降维打击之后，整个宇宙都平面化了，不仅维度降低了，在二维世界中引力模式也产生了改变，只有特定的星球围成的三角形区域内才会产生引力，一个区域如果被上述三角形区域奇数次覆盖（1，3，5...）则有引力存在，而如果一块区域内被不同的三角区域覆盖偶数次（0，2，4...）则他们之间的引力作用就被抵消了（相当于没有引力）,为了更好的适应二维世界，鸽者文明知名学者-鸽伽尊，提出了伟大的鸽者文明的三体问题，给出n个已知的能产生引力的星球组坐标（一组坐标包含3个星球，一个星球坐标计为（xi，yi）），然后有q组询问，每次询问一个位置（xqi，yqi），这个点是否存在引力（被抵消等同没有引力），如果有引力则输出"Yes"(没有引号)，不然输出"No"(没有引号)
第一行跟着2个整数n,q (0<n,q≤1000)(0\lt n,q\le 1000)(0<n,q≤1000)，分别代表已知的能产生引力的星球组数，以及询问数，之后跟着3n行，每一行包含两个整数 xi,yi(0≤xi,yi≤1e5)x_i,y_i(0\le x_i,y_i\le 1e5)xi,yi(0≤xi,yi≤1e5) ，代表一个星球的坐标，第k+1，第k+2，第k+3星球组成的三角形内(包括边界)存在引力（k=0，3，6...）题目保证每一组的三个星球不会在同一直线上且组内不会有星球重叠（保证构成三角形）。之后跟着q行询问，每次询问给出2个整数xqi,yqi(0≤xqi,yqi≤1e5)x{qi},y{qi}(0\le x{qi},y{qi}\le 1e5)xqi,yqi(0≤xqi,yqi≤1e5),表示询问的地点的坐标，每次询问给出对应的答案，题目保证询问的点不会刚好在三角区域的顶点或边上。
输出q行，每一行仅有"Yes"或"No"，代表第k次询问的结果
解析：
当该点落在三角形内部时，满足：该点与另外两点共可构成三个小三角形，三个小三角形面积和等于此大三角形。
已知三角形三点坐标求面积，向量叉乘/2，ab*ac/2，注意必须是b点横纵坐标减去a点横纵坐标求出向量ab，ac同理，然后两个向量，|x1y2-x2y1|/2求出三角形面积。
#include <bits/stdc++.h>
using namespace std;
struct node{
int x,y;
};
node a[10010][3];
double area(node A,node B,node C){
double x1 = B.x - A.x;
double x2 = C.x - A.x;
double y1 = B.y - A.y;
double y2 = C.y - A.y;
return abs(x1*y2-x2*y1)/2.0;
}
int main()
{
int n,q;
cin>>n>>q;
for(int i=0;i<n;i++){
for(int j=0;j<3;j++){
cin>>a[i][j].x>>a[i][j].y;
}
}
while(q--){
node t;
cin>>t.x>>t.y;
int ans = 0;
for(int i=0;i<n;i++){
double area1 = area(a[i][0],a[i][1],a[i][2]);
double area2 = area(a[i][0],a[i][1],t)+area(a[i][0],a[i][2],t)+area(a[i][1],a[i][2],t);
if(area1==area2)
ans++;
}
if(ans%2==0)
cout<<"No"<<endl;
else
cout<<"Yes"<<endl;
}
return 0;
}
练习整理2
C 传染病统计(模拟)
链接：https://ac.nowcoder.com/acm/contest/22352/C
阿强来到大街上，街上有 N 个人，编号为 1 ∼N 。简单起见，我们把每个人都看成一条线上的一个点。对每个合法的 i，第 i 个人的位置是 xix_ixi。
这些人当中恰好有一个感染了 COVID-19，但我们不知道是哪一个。当一个被感染的人和一个未被感染的人之间的距离不超过 2 时，病毒会从前者传播到后者。如果我们等待足够长的时间，会有一些人（这些人由第一个感染者确定）被感染；这些人的数量被称作最终被感染的人数。
阿强希望求出最终被感染的人数的最小和最大可能的值，也就是最好和最坏情况下这个数的值。
解析：
模拟题，先排序，判断相邻两个距离是否小于等于二，分段计算传染链长度，同时维护最大值，注意判断时机，传染链断开或数组遍历结束
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
int s[n];
for(int i=0;i<n;i++){
scanf("%d",&s[i]);
}
sort(s,s+n);
int countmax=1;
int countmin=n;
int result=1;
int l=0;
int r=1;
while(r<n){
if(s[r]-s[l]<=2){
result++;
}
else{
l=r-1;
countmax=max(countmax,result);
countmin=min(countmin,result);
result=1;
}
r++;
l++;
}
countmax=max(countmax,result);
countmin=min(countmin,result);
printf("%d %d\n",countmin,countmax);
}
return 0;
}
D 阿强与网格(模拟)
链接：https://ac.nowcoder.com/acm/contest/22352/D
阿强在一个N行M列的网格中。 阿强可以用两种方式移动： 向下、向左、向上或向右移动，每次移动的代价为X。换句话说，如果您位于网格的单元格（i，j），则可以转到任意单元格（i+1，j），（i，j−1） ，（i−1，j）或（i，j+1），代价为X。
沿对角线向左下、向右下、向左上、向右上移动成本为Y。换句话说，如果你在网格的单元格（i，j）上，你可以去任意一个单元格（i+1，j−1） ，（i+1，j+1），（i−1，j−1） 或(i−1，j+1），代价为Y。
请你找到从阿强从左上角（1,1）到右下角（N，M）的最小成本。
阿强不能移出网格。
解析：
模拟题，斜着走一次等于两条边，判断对角线的代价和两条边的代价，若斜边代价低，同时需要继续判断，斜边能否直接到达终点，若不能，到达一侧边界，可继续选择走对角线还是边，两条对角线等于两条边，最后预留一条边到达终点，纯模拟题。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int t;
scanf("%d",&t);
while(t--){
ll result=0;
ll n,m,x,y;
scanf("%lld%lld%lld%lld",&n,&m,&x,&y);
if(n==1||m==1) {
result=abs(n-m)*x;
printf("%lld\n",result);
continue;
}
if(y<(2*x)){
result=(min(n,m)-1)*y;
if(x<=y){
result=result+abs(n-m)*x;
}else{
int temp=abs(n-m)%2;
result=result+(abs(n-m)-temp)*y+temp*x;
}
}else{
result=(m+n-2)*x;
}
printf("%lld\n",result);
}
return 0;
}
E 生活大爆炸(排列组合,数学)
链接：https://ac.nowcoder.com/acm/contest/22352/E
有n个男孩和m个女孩参加戏剧俱乐部。要制作一部戏剧《生活大爆炸》，他们需要选择一组由t个演员组成的剧组，其中包括不少于4名男孩和不少于1名女孩。有多少种方法可以组成一个小组？当然，只有剧团组成不同的变体才被认为是不同的。
解析：
遍历男孩可能的人数，求出所有排列组合情况，涉及排列组合公式
用动态规划思想也能推出，但较为困难。应该算是数学题...
#include<bits/stdc++.h>
using namespace std;
long long int C[60][60];
void jiecheng(){
for(int i=0;i<=35;i++){
for(int j=0;j<=i;j++){
if(j==0){
C[i][j]=1;
}
else{
C[i][j]=C[i-1][j]+C[i-1][j-1];
}
}
}
}
int main(){
int n,m,t;
cin>>n>>m>>t;
long long int result=0;
jiecheng();
for(int i=4;i<=min(n,t-1);i++){
result+=C[n][i]*C[m][t-i];
}
cout<<result;
return 0;
}
F Capslock 大小写误触，翻转(模拟)
解析：
纯模拟，根据题意判断，然后大写变小写，小写变大写
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
cin>>s;
int flag=1;
for(int i=1;i<s.size();i++){
if(s[i]>='a'&&s[i]<='z'){
flag=0;
}
}
if(!flag) cout<<s;
else{
if(s[0]>='a'&&s[0]<='z'){
s[0]=s[0]-32;
}else if(s[0]>='A'&&s[0]<='Z'){
s[0]=s[0]+32;
}
for(int i=1;i<s.size();i++){
s[i]+=32;
}
cout<<s;
}
return 0;
}
G 字节类型(大数模拟)
解析：
大数比较判断，题目要求输入整数，直接用无符号长整形判断即可通过
建议用python语言
n = eval(input())
if n>=-128 and n<=127:
print("byte",end='')
elif n>=-32768 and n<=32767:
print("short",end='')
elif n>= -2147483648 and n<=2147483647:
print("int",end='')
elif n>= -9223372036854775808 and n<=9223372036854775807:
print("long",end='')
else:
print("BigInteger",end='')
同时介绍一个__int128，128位整数，约39位数，但无输入方法，且有些编译器不支持，需自行判断，同时需要用代码进行赋值
#include<bits/stdc++.h>
using namespace std;
string a;
__int128 x=0;
int main()
{
cin>>a;
int len=a.size();
if(len>=20){
printf("BigInteger\n");
return 0;
}
for(int i=0;i<len;i++){
x=x*10+a[i]-'0';
}
if(x>9223372036854775807)printf("BigInteger\n");
else if(x>147483647)printf("long\n");
else if(x>32767)printf("int\n");
else if(x>127)printf("short\n");
else printf("byte\n");
return 0;
}
I 完美主义(区间问题) 线段树
链接：https://ac.nowcoder.com/acm/contest/22352/I 来源：牛客网
阿强采摘了一些苹果，并把他们分堆排成了一行，从左往右编号为第 1 … 𝑛 堆，其中第𝑖堆苹果有aia_iai个。
完美主义者阿珍看到这些苹果，觉得他们摆放的非常杂乱。她要求阿强进行如下的操作。
对某堆苹果进行调整：阿强将会将第𝑖堆苹果调整成bib_ibi个；
对阿珍询问做出答复：其中每次询问表示为[𝑙, 𝑟]，表示询问第𝑙堆到第𝑟堆之间的苹果数量是否满足al≤al+1≤⋯≤ar−1≤ara_l \leq a{l+1} \leq \dots \leq a{r-1} \leq a_ral≤al+1≤⋯≤ar−1≤ar，如果满足则称为完美。
解析：
给一些数字，组成一个序列，有两个操作，
- 给序列的第i个数加上X
- 给定区间，查询改区间（最大值，最小值，是否满足条件）
询问区间最值或判断是否满足条件，正常思维，遍历区间得到答案。查询复杂度O(N),Q次查询则为O(QN),修改复杂度为O(1)。
线段树是一颗二叉树，能解决线段一维问题
将每部分区间二分，查询的时间复杂度为log级别
- 用数组下标表示树的关系，即可省略节点中左孩子右孩子的表示
- 一般节点内容为：1. 左右区间 2.判定值(最大值，最小值，布尔值)
该节点区间最大值为，左右孩子的最大值
当有数据发生变化，应同时维护该节点以及父节点以此类推向上，直到根节点或检测到不需改变时停止
例:第一层会查询试图查询[1, 7], 发现区间不存在，然后根据mid位置拆分[1, 4]和[5, 7] 第二层会查询[1, 4],[5, 7], 发现[1, 4]已经存在，返回即可，[5, 7]仍旧需要继续拆分 第三层会查询[5, 6],[7, 7], 发现[5, 6]已经存在，返回即可，[7, 7]仍旧需要继续拆分 第四层会查询[7, 7]
#include<bits/stdc++.h>
using namespace std;
const int N=300015;
int a[N];
struct node{
int l,r;
int v;
}tr[4*N];
void update(int id){
tr[id].l=tr[id<<1].l;
tr[id].r=tr[id<<1|1].r;
if(tr[id<<1].r<=tr[id<<1|1].l&&tr[id<<1].v==1&&tr[id<<1|1].v==1){
tr[id].v=1;
}else{
tr[id].v=0;
}
}
void build(int id,int l,int r){
if(l==r){
tr[id].v=1;
tr[id].l=tr[id].r=a[l];
}
else{
int mid=(l+r)>>1;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
update(id);
}
}
void change(int id,int l,int r,int x,int y){
a[x]=y;
if(l==r){
tr[id].l=tr[id].r=y;
}
else{
int mid=(l+r)>>1;
if(x<=mid){
change(id<<1,l,mid,x,y);
}else{
change(id<<1|1,mid+1,r,x,y);
}
update(id);
}
}
int query(int id,int l,int r,int ql,int qr){
if(qr<l||ql>r){
return 0;
}
if(l>=ql&&r<=qr){
return tr[id].v;
}else{
int mid=(l+r)>>1;
if(qr<=mid){
return query(id<<1,l,mid,ql,qr);
}else if(ql>mid){
return query(id<<1|1,mid+1,r,ql,qr);
}else{
return query(id<<1,l,mid,ql,qr)&&query(id<<1|1,mid+1,r,ql,qr)&&a[mid]<=a[mid+1];
}
}
}
int main(){
int n,q;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
build(1,1,n);
while(q--){
int op,i,bi;
scanf("%d%d%d",&op,&i,&bi);
if(op==1){
change(1,1,n,i,bi);
}else{
if(query(1,1,n,i,bi)){
printf("Yes\n");
}else{
printf("No\n");
}
}
}
return 0;
}
差分数组
上述答案，叶子结点直接存数组元素，还可以存差分数组元素，比较差分数组是否出现负数，即可判断该区间是否满足递增条件
差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减，区间元素同时增加或减少相同的数的情况才能用
把原数组中后一个元素减前一个元素的差构成新的数组(区间元素同时增大或减小，作差不变)
1、将区间【1，4】的数值全部加上3
2、将区间【3，5】的数值全部减去5
例题：
特点：
- 线段树，查询，更新时间复杂度均为log级别，但更新后要维护线段树，算法复杂，同时空间复杂度较大，因为需要维护二叉树
- 差分数组，查询仍为O(N),但修改时间复杂度为O(1)，只需修改区间首和区间尾下一个。
L 神奇的回答(签到题)
略
BFS DFS模板
DFS
#include<bits/stdc++.h>
using namespace std;
int dx[8]={0,0,1,-1,1,1,-1,-1};
int dy[8]={1,-1,0,0,1,-1,1,-1};
int v[1000][1000];
int a[1000][1000];
int n,m,result=0;
void dfs(int tx,int ty){
int x,y;
if(tx==1&&ty==m){
result++;
return ;
}
for(int i=0;i<8;i++){
x=tx+dx[i];
y=ty+dy[i];
if(x>=1&&x<=n&&y>=1&&y<=m&&v[x][y]==0&&a[x][y]==0){
v[x][y]=1;
dfs(x,y);
v[x][y]=0;
}
}
return ;
}
int main(){
cin>>n;
m=n;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
a[1][1]=1;
dfs(1,1);
cout<<result;
return 0;
}
BFS
#include<bits/stdc++.h>
using namespace std;
int a[3000][3000];
int n,m,v[3000][3000];//标志数组
int way[3000][3000][2];
//移动
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
//横纵坐标队列
int qx[100005],qy[100005];
//根据题意设置结果变量
int result=0;
void bfs(int x,int y){
int fx=0,rx=0,fy=0,ry=0;
qx[rx++]=1,qy[ry++]=1;
v[1][1]=0;
while(fx!=rx){
x=qx[fx++],y=qy[fy++];
for(int i=0;i<4;i++){
int newx=x+dx[i],newy=y+dy[i];
//判断条件三要素:1.合法性2.可访问3.未标记
if(newx>=1&&newx<=n&&newy>=1&&newy<=m&&a[newx][newy]==0&&v[newx][newy]==0){
if(newx==n&&newy==m){
result++;
return ;
}
v[newx][newy]=v[x][y]+1;
qx[rx++]=newx,qy[ry++]=newy ;
way[newx][newy][0]=x;
way[newx][newy][1]=y;
}
}
}
}
void printWay(int x,int y){
if(x==0&&y==0){
return ;
}
printWay(way[x][y][0],way[x][y][1]);
cout<<x<<' '<<y<<endl;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
}
}
bfs(1,1);
if(result==0){
cout<<"no";
}
else{
cout<<"yes";
}
return 0;
}
无重复字符最长子串(滑动窗口)
int lengthOfLongestSubstring(string s){
unordered_map<char,int> map;
int size=s.size();
int left=0,right=0,result=0,len=0;
while(right<size){
char temp=s[right];
if(map.find(temp)!=map.end()&&map[temp] >=left){
left=map[temp]+1;
len=right-left;
}
map[temp]=right;
right++;
len++;
result=max(result,len);
}
return result;
}
最长回文子串
string longestPalindrome(string s) {
int dp[1001][1001]={0};
int length=s.size();
int maxlen=1;
if(length<=1){
return s;
}
for(int i=0;i<length;i++){
dp[i][i]=1;
}
int begin=0;
for(int l=2;l<=length;l++){
for(int i=0;i<length;i++){
int j=i+l-1;
if(j>=length){
break;
}
if(s[i]!=s[j]){
dp[i][j]=0;
}else{
if(j-i<=2){
dp[i][j]=1;
}
else{
dp[i][j]=dp[i+1][j-1];
}
}
if(dp[i][j]&&j-i+1>maxlen){
begin=i;
maxlen=j-i+1;
}
}
}
return s.substr(begin,maxlen);
}
两个正序数组中位数
int getKthElement(const vector<int>& nums1, const vector<int>& nums2, int k) {
/* 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
* 这里的 "/" 表示整除
* nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
* nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
* 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
* 这样 pivot 本身最大也只能是第 k-1 小的元素
* 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组
* 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组
* 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数
*/
int m = nums1.size();
int n = nums2.size();
int index1 = 0, index2 = 0;
while (true) {
// 边界情况
if (index1 == m) {
return nums2[index2 + k - 1];
}
if (index2 == n) {
return nums1[index1 + k - 1];
}
if (k == 1) {
return min(nums1[index1], nums2[index2]);
}
// 正常情况
int newIndex1 = min(index1 + k / 2 - 1, m - 1);
int newIndex2 = min(index2 + k / 2 - 1, n - 1);
int pivot1 = nums1[newIndex1];
int pivot2 = nums2[newIndex2];
if (pivot1 <= pivot2) {
k -= newIndex1 - index1 + 1;
index1 = newIndex1 + 1;
}
else {
k -= newIndex2 - index2 + 1;
index2 = newIndex2 + 1;
}
}
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int totalLength = nums1.size() + nums2.size();
if (totalLength % 2 == 1) {
return getKthElement(nums1, nums2, (totalLength + 1) / 2);
}
else {
return (getKthElement(nums1, nums2, totalLength / 2) + getKthElement(nums1, nums2, totalLength / 2 + 1)) / 2.0;
}
}
Comments NOTHING