网易笔试 通用技术A 2021/8/21
第一部分
既有ACM，也有核心模式
第一题
给个数组，给个M，求数组中所有比M小的组合数
输入：
7 -1 -1
9
输出：3
因为7和第一个-1，7和第二个-1，第一个-1 和第二个-1
100%过
import java.util.Arrays;
import java.util.Scanner;
/**
* @author keboom
* @date 2021/8/21
*/
public class Solution1 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] s = sc.nextLine().split(" ");
int[] nums = new int[s.length];
for (int i = 0; i < nums.length; i++) {
nums[i] = Integer.valueOf(s[i]);
}
int M = sc.nextInt();
// System.out.println(Arrays.toString(nums));
// System.out.println(M);
int res = sumBiggerM(nums, M);
System.out.println(res);
}
private static int sumBiggerM(int[] nums, int M) {
int res = 0;
for (int i = 0; i < nums.length-1; i++) {
for (int j = i+1; j < nums.length; j++) {
if (nums[i] + nums[j] <= M) {
res++;
}
}
}
return res;
}
} 第二题
L1 = a L2 = b L3 = c ................. L26 = z
Si = Si-1 + Li + reverse(invert(Si-1))
reverse 为翻转字符串，invert为反转每个字符比如a反转为z，b反转为y，c反转为x
S1 = a S2 = a + b + z = abz
S3 = abz + c + reverse(zya) = abzcayz
.......................
输入n为Sn的意思，k为Sn字符串第k个字符
输入：2 1
输出：a S2的第一个字符为a
输入：3 6
输出：y S3的第6个字符为y
100%过
/**
* @author keboom
* @date 2021/8/21
*/
public class Solution2 {
// si = si-1 + li + reverse(invert(si-1))
public char findKthBit(int n, int k) {
String[] dp = new String[n + 1];
dp[1] = "a";
for (int i = 2; i <= n; i++) {
char Li = (char) ('a' + i - 1);
dp[i] = dp[i - 1] + Li + reverse(invert(dp[i - 1]));
}
return dp[n].charAt(k-1);
}
public String reverse(String s) {
return new StringBuilder(s).reverse().toString();
}
public String invert(String s) {
StringBuilder sb = new StringBuilder();
for (char c : s.toCharArray()) {
char res = (char) ('z' - (c - 'a'));
sb.append(res);
}
return sb.toString();
}
public static void main(String[] args) {
// char res = 'z' - ('c' - 'a');
// System.out.println(res);
Solution2 s2 = new Solution2();
// String abz = s2.invert("abz");
// System.out.println(abz);
// System.out.println(s2.reverse("abc"));
// char Li = (char) ('a' + 2);
// System.out.println(Li);
char res = s2.findKthBit(4, 11);
System.out.println(res);
}
} 第三题
有一些小孩，他们有年龄，他们围成一圈，年龄高的小孩要比临近他的小孩多给纸张，求最少要给这些小孩多少纸张
输入：1 1 1
输出：3 三个小孩围一圈，年龄都相等，每人给一张
输入：1 2 3
输出：6 年龄为1的给1张，年龄为2的给两张，年龄为三的给三张
输入：5
输出：1 只有一个人就给一张
80%过，我的思路是不停的找年龄最小的，他的纸张应该是他临近的两个人中的纸张数大的+1，如果他跟他临近的两人年龄相等，那就不用+1
import java.util.*;
/**
* @author keboom
* @date 2021/8/21
*/
public class Solution3 {
//80 围成一圈小孩发纸，岁数大的要邻近的多发，求最少要多少只
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] s = sc.nextLine().split(" ");
int[] nums = new int[s.length];
int[][] map = new int[nums.length][2];
for (int i = 0; i < nums.length; i++) {
nums[i] = Integer.valueOf(s[i]);
map[i][0] = nums[i];
map[i][1] = i;
}
Arrays.sort(map, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
if (nums.length == 1) {
System.out.println(1);
return;
}
// System.out.println(map.toString());
int[] papers = new int[nums.length];
// System.out.println(Arrays.deepToString(map));
for (int[] ints : map) {
int index = ints[1];
int max = 0;
boolean isequals = false;
if (index == 0) {
max = Math.max(papers[papers.length - 1], papers[1]);
if (nums[index] == nums[papers.length - 1] || nums[index] == nums[1]) {
isequals = true;
}
} else if (index == papers.length - 1) {
max = Math.max(papers[index - 1], papers[0]);
if (nums[index] == nums[index - 1] || nums[index] == nums[0]) {
isequals = true;
}
} else {
max = Math.max(papers[index - 1], papers[index + 1]);
if (nums[index] == nums[index - 1] || nums[index] == nums[index + 1]) {
isequals = true;
}
}
papers[index] = isequals ? max : max + 1;
if (papers[index] == 0) {
papers[index] = 1;
}
}
int sum = 0;
for (int i : papers) {
sum += i;
}
System.out.println(sum);
}
} 第四题
给你一个二维矩阵，0表示水，1表示陆地，2表示障碍物
走水路要花2钱，走陆地要花1钱，障碍物没法走
求从左上角，到右下角要花的最少的钱，如果走不过去，那么就返回-1
左上角起始位置（0，0）不花钱，右下角终点是花钱的
输入：[[1,1,1,1,0],[0,1,0,1,0],[1,1,2,1,1],[0,2,0,0,1]]
输出：7 路径为 0,1--0,2--0,3--1,3--2,3--2,4--3,4
只过了50%，他报错说数组越界，不知道为啥？
import java.util.Arrays;
/**
* @author keboom
* @date 2021/8/21
*/
public class Solution4 {
public int minSailCost (int[][] input) {
int row = input.length;
int col = input[0].length;
int[][] dp = new int[row][col];
for (int i = 0; i < dp.length; i++) {
Arrays.fill(dp[i],-1);
}
dp[0][0] = 0;
for (int i = 1; i < row; i++) {
if (dp[i - 1][0] == -1 || input[i][0] == 2) {
dp[i][0] = -1;
} else {
int val = input[i][0] == 0 ? 2 : 1;
dp[i][0] = dp[i-1][0] + val;
}
}
for (int i = 1; i < col; i++) {
if (dp[0][i-1] == -1 || input[0][i] == 2) {
dp[i][0] = -1;
} else {
int val = input[0][i] == 0 ? 2 : 1;
dp[0][i] = dp[0][i-1] + val;
}
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
if (input[i][j] == 2 || (dp[i - 1][j] == -1 && dp[i][j - 1] == -1)) {
dp[i][j] = -1;
} else {
int val = input[i][j] == 0 ? 2 : 1;
if (dp[i - 1][j] == -1) {
dp[i][j] = dp[i][j-1] + val;
} else if (dp[i][j - 1] == -1) {
dp[i][j] = dp[i - 1][j] + val;
} else {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + val;
}
}
}
}
return dp[row-1][col-1];
}
// [[1,1,1,1,0],[0,1,0,1,0],[1,1,2,1,1],[0,2,0,0,1]]
public static void main(String[] args) {
int[][] input = {{1,1,1,1,0},{0,1,0,1,0},{1,1,2,1,1},{0,2,0,0,1}};
int res = new Solution4().minSailCost(input);
System.out.println(res);
}
} 第二部分
两种常见的软件开发模型并说出特点
如果有更好的答案，求分享哦~
在评论区打出来~
