一共四道编程题（100分）+ 一道问答题（10分，关于设计模式的，直接跳过了）
第一题
两个怪兽血量分别为a，b
两个技能：
- 群体攻击，每个怪兽都受到x伤害
- 单体攻击，某个怪兽收到y伤害
a b x y 均在 [1, 20]
思路
这题比较简单，直接暴力，两个for循环即可
第二题
给一个字符串，对相邻的字符进行标记
满足标记的条件：
- 两个相邻字符相等，比如 aa
- 两个相邻字符相邻，比如 ts
标记a获得1分，标记b获得2分，标记z获得26分。已被标记过的字符不能再被标记，求最多的分数
example: s = abb 答案为4
思路
我这道题写的很复杂，感觉应该有更好的解法
对字符串进行遍历，从当前起点看后序有多少连续的可以被标记的字符，比如babbbzz
那么babbb就是连续的可以被标记的，但是我一次只能标记两个，所以最后一定是偶数个，那么需要去掉一个。在这个奇数长度的子串中，只有奇数位置的字符能被去掉，也就是第1，3，5个，去掉最小的（这里一样大）即可。
然后起点变成z继续遍历，找到zz，然后结束
--
更新：
使用dp才是正道，如果i 和 i-1是可以标记的，那么dp[i] = max(dp[i-1], dp[i-2] + 分数)
第三题
给一个数n，要求实现一个完全二叉树
要求：
- 节点权重分别为 1 - n
- 每个节点和其父亲节点的权重乘积为偶数（除了root）
输出一行数字，为该数的层序遍历
example：
/**
* n = 4
*
* 2
* 4 3
* 1
*/
输出 2 4 3 1思路
看起来很唬人，其实就是先输出偶数，后输出奇数。。。
比如n = 7，输出 2 4 6 1 3 5 7
第四题
给一个矩阵，0代表平地，1代表沼泽。小明在左上角，要到右下角。
每次可以选择向左，右，下移动
从平地到平地，沼泽到沼泽花费1
从平地到沼泽，沼泽到平地花费2
进入矩阵和离开矩阵没有花费，求最小花费
/**
* 1 0 0
* 1 1 1
* 0 0 1
*/
输出 4思路
难度不大，但是超时问题不知道怎么解决
矩阵长度最大为500
我用一个二维数组minTime记录每个节点被访问到时的花费，如果小于等于就更新，大于就提前结束，但还是超时
代码如下，希望大佬指点：
import java.util.*;
public class Main {
static int ans = Integer.MAX_VALUE;
static boolean[][] visited;
static int[][] minTime;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
int[][] map = new int[m][n];
minTime = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
map[i][j] = sc.nextInt();
minTime[i][j] = Integer.MAX_VALUE;
}
}
visited = new boolean[m][n];
dfs(map, null, 0, 0, -1);
System.out.println(ans);
}
public static void dfs(int[][] map, Integer pre, int i, int j, int total) {
if (i < 0 || i >= map.length || j < 0 || j >= map[0].length || visited[i][j]) {
return;
}
visited[i][j] = true;
int cur = map[i][j];
if (pre != null && cur != pre) {
total += 2;
} else {
total += 1;
}
if (total <= minTime[i][j]) {
minTime[i][j] = total;
} else {
visited[i][j] = false;
return;
}
if (i == map.length - 1 && j == map[0].length-1) {
ans = Math.min(ans, total);
}
dfs(map, cur, i+1, j, total);
dfs(map, cur, i, j+1, total);
dfs(map, cur, i, j-1, total);
visited[i][j] = false;
}
}评论 (27)
