去哪儿秋招 java 笔试算法题

1.k-bingo

，给定k,l,r,找出[l,r]区间中满足以下条件之一的数 :

• x%k==0
• x,k转为字符串，k是x的子串

模拟 :

java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class t1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in) ;
        int k = sc.nextInt() , l = sc.nextInt() , r = sc.nextInt();
        String ks = String.valueOf(k) ;
        int p = ks.length() ;
        List<Integer> ls = new ArrayList<>() ;
        for(int i=l;i<=r;i++){
            if(i%k==0) {
                ls.add(i);
                continue ;
            }
            boolean tag = false ;
            String xs = String.valueOf(i) ;
            for (int j = 0; j <= xs.length() - p; j++) {
                if (xs.substring(j, j + p).equals(ks)) {
                    tag = true;
                    break;
                }
            }
            if(tag) ls.add(i) ;
        }
        for(int x : ls){
            System.out.print(x);
        }
    }
}

c++

#include<bits/stdc++.h>
using namespace std ;
int main(){
	int k , l , r ;
	cin >> k >> l >> r ;
	string ks = to_string(k) ;
	int p = ks.size() ;
	vector<int> ans ;
	for(int i=l;i<=r;i++){
		if(i%k==0) {
			ans.push_back(i) ;
			continue ;
		}
		bool tag = false ;
		int x = i ;
		string xs = to_string(x) ;
		for(int j=0;j<xs.size()-p+1;j++){
			if(xs.substr(j,p)==ks){
				tag = true ;
				break ;
			}
		}
		if(tag) ans.push_back(i) ;
	}
	for(int x : ans) cout << x << " " ;
}

2.固定词与移位

给你一个长为n的字符串，q次操作 :

• op=1 , idx : 将idx位置的字符固定
• op=2 ,将除了固定字符的其它字符全部向后移动一位(遇到固定字符需要移到下一位)，最后一位的下一位是第一位;

求处q次操作之后的字符串 :

tets case :

/*
6 4
abcdef
1 2
1 4
2
2
 */

用一个hash表记录固定的下标，op=2时，模拟移动即可 ;

java :

import java.util.HashSet;
import java.util.Scanner;

public class t2 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in) ;
        int n = sc.nextInt() , q = sc.nextInt() ;
        String str = sc.next() ;
        char[] s = str.toCharArray() , s1 = str.toCharArray() ;
        HashSet<Integer> st = new HashSet<>() ;
        for(int k=0;k<q;k++){
            int op = sc.nextInt() ;
            if(op==1){
                int idx =sc.nextInt() - 1 ;
                st.add(idx) ;
            }else{
                for(int i=0;i<n;i++){
                    if(!st.contains(i)){
                        // 进行移动
                        boolean tag = false ;
                        for(int j=i+1;j<n;j++){
                            if(!st.contains(j)){
                                s1[j] = s[i] ;
                                tag = true ;
                                break ;
                            }
                        }
                        if(!tag){
                            for(int j=0;j<n;j++){
                                if(!st.contains(j)){
                                    s1[j] = s[i] ;
                                    break ;
                                }
                            }
                        }
                    }
                }
                for(int i=0;i<n;i++) s[i] = s1[i] ;
            }
        }
        for(char c : s){
            System.out.print(c);
        }
    }
}

c++ :

#include<bits/stdc++.h>
using namespace std ;
int main(){
	int n , q ; cin >> n >> q ;
	string s ; cin >> s ;
	string s1 = s ;
	set<int> st ;
	while(q--){
		int op ; cin >> op ;
		if(op==1){
			int x ; cin >> x ;
			st.insert(x-1) ;
		}else{
			for(int i=0;i<n;i++){
				if(!st.count(i)){
					// 需要移动
					bool tag = false ;
					for(int j=i+1;j<n;j++){
						if(!st.count(j)){
							tag = true ;
							s1[j] = s[i] ;
							break ;
						}
					}
					if(!tag){
						for(int j=0;j<n;j++){
							if(!st.count(j)){
								s1[j] = s[i] ;
								break ;
							}
						}
					} 
				}
			}
			for(int i=0;i<n;i++) s[i] = s1[i] ;
		}
	}
	for(int i=0;i<n;i++) cout << s[i] ;
	return 0 ;
}

3.坐车

// n个点，m表示最大值
// a[i][j] 表示(i,j)之间的距离  ，为-1表示两点之间不相邻
// 求对于每一个点，从该点出发经过x点之后回到原点(x->[1,m])的最小花费是什么? 

不会，暴力拿了0.2;

#include<bits/stdc++.h>
using namespace std ;


const int N = 210 ;
int a[N][N] ;
#define int long long
const int INF = 1e18 ;

// n个点，m表示最大值
// a[i][j] 表示(i,j)之间的距离  ，为-1表示两点之间不相邻
// 求对于每一个点，从该点出发经过x点之后回到原点(x->[1,m])的最小花费是什么? 

int dp[N][N] ;

int ans = INF , p = -1 ;

vector<int> e[N] ;

void dfs(int sum , int i ,int k){
	if(i==p&&k==0){
		ans = min(ans,sum) ;
		return ;
	}
	if(k<0) return ;
	for(int j : e[i]){
		dfs(sum+a[i][j],j,k-1) ;
	}
	
}

signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) ;
	int n , m ; cin >> n >> m ;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin >> a[i][j] ;
			if(a[i][j]!=-1) e[i].push_back(j) ;
		}
	}
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){// 经过j分钟 
			if(j==1) {
				dp[i][j] = -1 ;
				continue ;
			}
			ans = INF ;
			p = i ;
			dfs(0,i,j) ;// sum , 当前下标 , 还剩次数 
			if(ans!=INF) dp[i][j] = ans ;
			else dp[i][j] = -1 ;
		} 
	}
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)
			cout << dp[i][j] << " " ;
		cout << endl ;
	}
}

期望面试!!!