【笔经】【大疆】

选择题忘光了

编程题

1.喝咖啡能提高改bug的效率。n表示bug数，a表示改bug效率的提升倍数，x表示咖啡的杯数。一杯咖啡只能在一个小时内有效，求最短能用多少时间改bug。

输入：

n=8

a=2

x=2

输出：240

输入：

n=4

a=3

x=3

333

100

输出：175

先做的第三题，最后没时间了，A了45

2.输入n和t，n是食物的种类，t是总价钱。接着是n行，每行三个数，分别是价钱，满意度，数量，问满意度最大是多少？

背包？又见背包？怎么每次笔试都有背包？A了11。

3.一个字符串方块，再给一个字符串数组，求字符串里面的字符串是否在方块里面，可以上下左右搜寻，跟贪吃蛇似的。

AC，dfs来做，要求按照字典序返回。

import java.lang.reflect.Array;
import java.util.*;

public class Main{
    public static void sortDic(String[] arr){
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if(arr[i].compareTo(arr[j]) > 0){
                    swap(arr, i, j);
                }
            }
        }
    }
    public static void swap(String[] arr, int i, int j){
        String t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        char[][] map = new char[n][255];
        int count = 0;
        for (int i = 0; i < n; i++) {
            String str = in.next();
            char[] ch = str.toCharArray();
            for (int j = 0; j < ch.length; j++) {
                map[i][j] = ch[j];
            }
        }
        int m = in.nextInt();
        String[] s = new String[m];
        for (int i = 0; i < m; i++) {
            s[i] = in.next();
        }
        sortDic(s);
        for (int i = 0; i < m; i++) {
            if(judge(map,s[i])){
                System.out.println(s[i]);
            }
        }
    }
    public static boolean judge(char[][] map, String str){
        char[] w = str.toCharArray();
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                if(dfs(map,w,i,j,0)) return true;
            }
        }
        return false;
    }
    public static  boolean dfs(char[][] map,char[] ch, int i, int j, int pos){
        if(pos == ch.length - 1) return true;
        if(i < 0|| i >= map.length || j < 0 || j >= map[0].length||map[i][j] != ch[pos]) return false;
        char tmp = map[i][j];
        map[i][j] = '0';
        boolean res = dfs(map, ch ,i+1 , j,pos+1) ||
                      dfs(map, ch ,i-1 , j,pos+1) ||
                      dfs(map, ch , i , j+1,pos+1) ||
                      dfs(map, ch , i , j-1,pos+1);
        map[i][j] = tmp;
        return res;
    }

}
/*
5
uvwxy
g
gobi
aos
tds
2
good
dos
 */

#笔试题目##大疆#