商湯科技2021秋招筆試験プログラミング問題

1、文字列の中で“Good”を構成することができる個数を探し出していくつあって、文字の列の中の相対的な位置を変えることができません

#include 
using namespace std;
int a[100001]; 
int main(){
     
    string s;
    int i,min,sum,j,k,flag;
    getline(cin,s);
    for(i=0;i<100001;i++)    a[i]=0;
    sum=0;
   // flag=0;
    for(i=0;i<s.size();i++){
     
        if(s[i]=='G'){
     
            flag=0;
            for(j=i+1;j<s.size();j++){
     
                if(s[j]=='o'&&flag==0&&a[j]==0){
     
                    a[j]=1;
                    flag=1;
                    continue;
                }
                else if(s[j]=='o'&&flag==1&&a[j]==0){
     
                    a[j]=1;
                    for(k=j+1;k<s.size();k++){
     
                        if(s[k]=='d'&&a[k]==0){
     
                            a[k]=1;
                            sum++;
                            break;
                        }
                    }
                    break;
                }
            }
        }
        }
    cout<<sum<<endl;  
}

2、一つの行列をあげて、位置ごとに上下左右に移動することができて、移動の過程の中で、数字の昇順の最長の数が何であるかを聞きます.

#include 
using namespace std;
void dfs(int x,int y,int num,int sum);
int Max,m,n;
int a[40002][40002];
int main(){
      
    int i,j;
    cin>>n>>m;
    for(i=0;i<n;i++){
     
     for(j=0;j<m;j++){
     
      cin>>a[i][j];
  }
 }
   Max=0;
   for(i=0;i<n;i++){
     
    for(j=0;j<m;j++){
     
     dfs(i,j,-100000,0);
  }
 }
 cout<<Max<<endl;
}
void dfs(int x,int y,int num,int sum){
     
 if(x<0||x>=n||y<0||y>=m) return;
 if(a[x][y]>num){
     
  sum++;
 }
 else{
     
  if(sum>Max) Max=sum;
  return;
 }
 dfs(x-1,y,a[x][y],sum);
 dfs(x+1,y,a[x][y],sum);
 dfs(x,y-1,a[x][y],sum);
 dfs(x,y+1,a[x][y],sum);
}

3、一連の区間を与えて、少なくともいくつかの区間を取り除いてこれらの区間を交差させないようにすることを聞く

int eraseOverlapIntervals(int** intervals, int intervalsRowLen, int* intervalsColLen ) {
     
    // write code here
    int m,tmp,n,x,i,j;
    m=intervalsRowLen;
    for(i=0;i<m;i++){
     
        for(j=i+1;j<m;j++){
     
            if(intervals[i][0]>intervals[j][0]){
     
                tmp=intervals[i][0];
                intervals[i][0]=intervals[j][0];
                intervals[j][0]=tmp;
                 tmp=intervals[i][1];
                intervals[i][1]=intervals[j][1];
                intervals[j][1]=tmp;
            }
            if(intervals[i][0]==intervals[j][0]&&intervals[i][1]>intervals[j][1]){
     
                tmp=intervals[i][1];
                intervals[i][1]=intervals[j][1];
                intervals[j][1]=tmp;
            }
        }
    }
    n=0;
    x=0;
   for(i=1;i<m;i++){
     
       if(intervals[i][0]<intervals[x][1]){
     
            n++;
       }
       else    x=i;
   }
    return n;
}