笔试复盘 | 网易8.21笔试全A经

（投网易是8月初看见师兄在群里发二维码随手投的....然后昨天才笔试。笔试比较简单，大概花了一小时完成3.8，又花了40min a掉剩下0.2。第一次全a，纪念一下嘿嘿嘿

第一题 一个数组的两数之和小于等于target的个数

（送分题，无脑暴力）

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int []nums = Arrays.stream(in.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int target = Integer.valueOf(in.nextLine());
        System.out.println(helper(nums,target));
    }
    private static int helper(int []nums,int target) {
        Arrays.sort(nums);
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                if(nums[i]+nums[j]<=target) res++;
                else break;
            }
        }
        return res;
    }
}

第二题 对字符串的变换

无脑模拟，送分题

class Main {
    public char findKthBit(int n,int k){
        String []arr = new String[n];
        arr[0] = "a";
        for (int i = 1; i < n; i++) {
            arr[i] = arr[i-1] + (char)('a'+i) + reverse(invert(arr[i-1]));
        }
        return arr[n-1].charAt(k-1);
    }
    private String reverse(String s){
        return new StringBuilder(s).reverse().toString();
    }
    private String invert(String s){
        char []ch = s.toCharArray();
        for (int i = 0; i < ch.length; i++) {
            ch[i] = (char)('z'+'a'-ch[i]);
        }
        return new String(ch);
    }
}

第三题 分发纸张，与leetcode分发糖果不同的是，这里的小朋友围成了一个圈

看有人说是两次遍历，然后判断下边界条件就可以了。但我的做法是先把所有小朋友按年龄排序，先给年龄小的小朋友发。个人觉得两次遍历+判断第一个小朋友和最后一个小朋友这种做法只是恰巧能过测试用例了，感觉思路不严谨。

高能来袭：下面的代码长得非常难看

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] ages = Arrays.stream(in.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        System.out.println(helper(ages));
    }
    static class Child{
        int index;
        int age;

        public Child(int index, int age) {
            this.index = index;
            this.age = age;
        }
    }
    private static int helper(int[] ages) {
        if(ages.length<2) return ages.length;
        List<Child> children = new ArrayList<>();
        for (int i = 0; i < ages.length; i++) {
            Child child = new Child(i,ages[i]);
            children.add(child);
        }
        children.sort((o1, o2) -> o1.age-o2.age);
        int []paper = new int[ages.length];
        for(Child ch:children){
            int index = ch.index;
            if(index==0){
                if(ages[index]>ages[1] && ages[index]>ages[ages.length-1]) {
                    paper[index] = Math.max(paper[1], paper[ages.length - 1]) + 1;
                }else if(ages[index]>ages[1]){
                    paper[index] = paper[1]+1;
                }else if(ages[index]>paper[ages.length-1]){
                    paper[index] = paper[ages.length-1]+1;
                }else {
                    paper[index] = 1;
                }
            } else if(index==ages.length-1){
                if(ages[index]>ages[0] && ages[index]>ages[ages.length-2]) {
                    paper[index] = Math.max(paper[0], paper[ages.length - 2]) + 1;
                }else if(ages[index]>ages[0]){
                    paper[index] = paper[0]+1;
                }else if(ages[index]>ages[ages.length-2]){
                    paper[index] = paper[ages.length-2]+1;
                }else {
                    paper[index] = 1;
                }
            }else {
                if(ages[index]>ages[index-1] && ages[index]>ages[index+1]) {
                    paper[index] = Math.max(paper[index-1],paper[index+1])+1;
                }else if(ages[index]>ages[index+1]){
                    paper[index] = paper[index+1]+1;
                }else if(ages[index]>ages[index-1]){
                    paper[index] = paper[index-1]+1;
                }else {
                    paper[index] = 1;
                }
            }
        }
        return Arrays.stream(paper).sum();
    }

第四题 bfs

这道题我使用dfs剪枝也只能过70%，使用bfs过了100%

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

public class Main {
    int []d = {-1,0,1,0,-1};
    public int minSailCost (int[][] input) {
        int m = input.length;
        int n = input[0].length;
        int [][]dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(dp[i],Integer.MAX_VALUE);
        }
        dp[0][0] = 0;
        Queue<int []> queue = new ArrayDeque<>();
        queue.add(new int[]{0,0});
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int []site = queue.poll();
                int x = site[0],y=site[1];
                for (int j = 0; j < 4; j++) {
                    int n_x = x+d[j];
                    int n_y = y+d[j+1];
                    if(n_x>=0 && n_x<m && n_y>=0 && n_y<n){
                        if(input[n_x][n_y]!=2){
                            int cost = input[n_x][n_y]==1?1:2;
                            if(dp[x][y]+cost<dp[n_x][n_y]) {
                                dp[n_x][n_y] = dp[x][y] + cost;
                                queue.offer(new int[]{n_x, n_y});
                            }
                        }
                    }
                }
            }
        }
        return dp[m-1][n-1]==Integer.MAX_VALUE?-1:dp[m-1][n-1];
    }
}