首页 > 网易笔试记录
头像
myorange
编辑于 2021-08-21 20:55
+ 关注

网易笔试记录

1题 数组arr中两个数和不大于给定值m的对数。
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<Integer> numList = new ArrayList<>();
        while(sc.hasNextInt()) {
            numList.add(sc.nextInt());
        }
        int n = numList.size() - 1;
        int m = numList.get(numList.size() - 1);
        int count = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (numList.get(i) + numList.get(j) <= m) {
                    count++;
                }
            }
        }
        System.out.println(count);
    }

}


2 字符串生成公式S_n= S_(n-1) + Li + reverse(invert(S_(n-1)),其中S_1 = "a",求第n个串的第k个字符。我在推导如何降低空间复杂度,花了些时间,打算先交一发看下一题,没想到暴力可以过。
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 返回Sn的第k位字符
     * @param n int整型 Sn的n
     * @param k int整型 需要返回的字符下标位
     * @return char字符型
     */
    public char findKthBit(int n, int k) {
        StringBuilder s = new StringBuilder();
        s.append("a");
        for (int i = 2; i <= n; ++i) {
            String pre = s.toString();
            s.append(getLi(i)).append(invert(pre));
        }
        return s.charAt(k-1);
    }

    private char getLi(int i) {
        return (char)('a' + (i - 1));
    }

    private String invert(String x) {
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < x.length(); ++i) {
            res.append((char)('z' - (x.charAt(i) - 'a')));
        }
        return res.reverse().toString();
    }
}
3 题 分发糖果
leetcode 135 
4 题 BFS求最短路
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public static void main(String[] args) {
        int res = new Solution().minSailCost(new int[][]{{1, 1, 1, 1, 0}, {0, 1, 0, 1, 0}, {1, 1, 2, 1, 1}, {0, 2, 0, 0, 1}});
        System.out.println(res);
    }

    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * <p>
     * 计算最小航行费用
     *
     * @param input int整型二维数组 二维网格
     * @return int整型
     */
    public int minSailCost(int[][] input) {
        if (input.length == 0 || input[0].length == 0) return 0;
        int n = input.length, m = input[0].length;
        Queue<Position> que = new LinkedList<>();
        int[][] dp = new int[n][m];
        int MAXV = 0x7f7f7f7f;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                dp[i][j] = MAXV;
            }
        }
        dp[0][0] = 0;
        que.add(new Position(0, 0));
        int[][] dir = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while (!que.isEmpty()) {
            Position point = que.remove();
            int cost = dp[point.x][point.y];
            for (int i = 0; i < 4; ++i) {
                int xx = point.x + dir[i][0];
                int yy = point.y + dir[i][1];
                if (xx >= 0 && xx < n && yy >= 0 && yy < m && input[xx][yy] != 2
                        && cost + (2 - input[xx][yy]) < dp[xx][yy]) {
                    dp[xx][yy] = cost + (2 - input[xx][yy]);
                    que.add(new Position(xx, yy));
                }
            }
        }
        return dp[n-1][m-1] == MAXV ? -1: dp[n-1][m-1];
    }

    static class Position {
        int x, y;

        public Position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}


全部评论

(1) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐