騰迅2017秋招筆試験プログラミング

一、符号化の符号化範囲がa~yの25文字で、1ビットから4ビットの符号化であると仮定し、この符号化を辞書順に並べ替えると、a,aaa,aaaaa,aaab,aaac,...,b,baa,baaa,baab,baac,...,yyyw,yyyyx,yyyyyyのうちaのIndexは0,aaaのIndexは1,aaaのIndexは2となる配列を形成する.関数を記述する、入力は任意の符号化であり、この符号化に対応するIndexを出力する.入力説明:符号化対象の文字列を入力し、文字列の長さは100以下である.出力記述:この符号化されたindex入力baca出力16331を出力する

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        /*  str , 
         *  hijk
         *  1 ， a、b、... h，8 ( )。 res=(ch[0]-'a') + 1
         *  2 ， a、aa~ay、b、ba~by、... 、h、ha~hi， len1， 25*7+9 。 res+=25*(ch[0]-'a')+(ch[1]-'a')+1
         *  3 ， aaa~aay、aba~aby、... 、aya~ayy、... 、haa~hay、... 、hia~hij。 25*25*7+25*8+10 
         *  res+=25*25*(ch[0]-'a')+25*(ch[1]-'a')+ch[2]-'a'+1
         *  res+=25*25*25(ch[0]-'a')+25*25(ch[1]-'a')+25*(ch[2]-'a')+ch[3]-'a'（ hijk）
         *  
         */
        while(sc.hasNext()) {
            String str = sc.next();
            char []ch = str.toCharArray();
            int len = ch.length;
            int res = 0;
            int cur = 0;
            for(int i = 0; i < 4; i++) {
                cur *= 25;
                if(i < len) {
                    cur += (ch[i] - 'a');
                }
                res += cur;
                if(i + 1< len) {
                    res += 1;
                }
            }
            System.out.println(res);
        }
        sc.close();
    }
}

二、ゲームにはいろいろなタスクがあり、そのうち1つのタスクプレイヤーは1回しかできない.このようなタスクは全部で1024個あり、タスクIDの範囲[1024].32個のunsigned intタイプで1024個のタスクが完了したかどうかを記録してください.初期状態はすべて未完了です.2つのパラメータを入力し、いずれもタスクIDであり、最初のIDを設定する必要があるタスクはすでに完了している.2番目のIDのタスクが完了しているかどうかを確認します.2番目のIDのタスクが出力1を完了した場合、出力0が完了していない場合、パラメータを出力します.第1または第2のIDが［1024］の範囲外である場合、出力−1.入力説明:入力は1行を含み、2つの整数は人物IDを表す.出力説明:出力完了入力1024 1024出力1

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int []bit = new int[32];// 0~1023
        while(sc.hasNext()) {
            int num1 = sc.nextInt();
            int num2 = sc.nextInt();
            if(num1>1023 || num1<0 || num2>1023 || num2<0) {
                System.out.println(-1);
            }else {
                bit[num1/32] = 1 << num1 % 32;
                if ((bit[num2/32] & 1 << num2 % 32) != 0) {
                    System.out.print(1);
                }else { 
                    System.out.print(0);
                }
            }
        }
        sc.close();
    }
}

三、正の整数を与え、プログラミングプログラムはどれだけの質量数の和が入力したこの正の整数に等しいかを計算し、結果を出力する.入力値は1000未満です.例えば、入力が10の場合、プログラムは結果を2に出力すべきである.入力記述:入力は整数nを含み、(3≦n<1000)出力記述:出力対数入力10出力2

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        List prime = new ArrayList<>();
        prime.add(2);
        for(int i = 3; i < 1000; i++) {
            if(isPrime(i)) {
                prime.add(i);
            }
        }
        int len = prime.size();
        while(sc.hasNext()) {
            int n = sc.nextInt();
            int res = 0;
            int i = 0, j = len - 1;
            while(i <= j) {
                int sum = prime.get(i) + prime.get(j);
                if(sum == n) {
                    res++;
                    j--;
                    i++;
                }else if(sum < n){
                    i++;
                }else {
                    j--;
                }
            }
            System.out.println(res);
        }
        sc.close();
    }

    private static boolean isPrime(int n) {
        for(int i = 2; i <= Math.sqrt(n); i++) {
            if(n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

四、geohash符号化:geohashは2次元の緯度を文字列に変換するのによく用いられ、2つのステップに分けられる:第1ステップは緯度のバイナリ符号化であり、第2ステップはbase 32トランスコードである.この問題は緯度のバイナリ符号化を考察する:アルゴリズムは緯度[-90,90]に対して二分法によって無限に近似する(所望の精度に依存して、本題の精度は6である).なお,本題では二分法近似の過程で下向きに整列するだけで二分を行い,二分中間値に対して右区間に属する.アルゴリズムの例は以下の通りである:緯度80に対してバイナリ符号化過程を行う:1)区間[-90,90]は[-90,0),[0,90]に二分され、左右区間となり、80が右区間と決定され、1と表記される.2)前ステップの右区間[0,90]に対して[0,45],[45,90]に二分し,[45,90]を行い,80が右区間であることを決定し,1と表記する.3)[45,90]に対して[45,67],[67,90]の2分割を行い、80を右区間とし、1としてマークすることができる.4)[67,90]に対して[67,78],[78,90]の2分割を行い、80を右区間とし、1としてマークすることができる.5)[78,90]に対して二分[78,84),[84,90]を行い、80を左区間とし、0と表記することができる.6)［78,84］に対して二分［78,81),［81,84)を行い、80を左区間とし、0としてマークすることができる.入力記述:入力は整数nを含み、(−90≦n≦90)出力記述:出力バイナリ符号化例1入力80出力111100

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()) {
            int n = sc.nextInt();
            StringBuffer sb = new StringBuffer();
            int l = -90, r = 90;
            // ， 
            for(int i = 0; i < 6; i++) {
                int mid = (l+r) / 2;
                if(n < mid) {
                    sb.append(0);
                    r = mid;
                }else {
                    sb.append(1);
                    l = mid;
                }
            }
            System.out.println(sb.toString());
        }
        sc.close();
    }
}