上岸算法LeetCode Weekly Contest 260解题报告
【 NO.1 增量元素之间的最大差值】解题思路
遍历数组维护全局最小值，若当前值较大就是一个合理的答案，遍历过程取最大的合理答案即可。
代码展示
public class Solution {
public int maximumDifference(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int res= -1;
int minNum = Integer.MAX_VALUE;
for (int n : nums) {
if (n > minNum) {
res = Math.max(n - minNum, res);
}
minNum = Math.min(minNum, n);
}
return res;
}
}
【 NO.2 网格游戏】
解题思路
注意到网格只有两行，所以第一个机器人需要选择的实际上就是从哪一列向下。在它确定了向下的那一列之后，第二个机器人要么只能拿到第一行开始部分的分数，要么只能拿到第一行结尾部分的分数。
代码展示
public class Solution {
public long gridGame(int[][] grid) {
if (grid == null || grid.length == 0 || grid.length == 0) {
return 0;
}
int n = grid.length;
long left = 0, rihgt = 0;
for (int i= 1; i < n; i++) {
rihgt += grid;
}
long res = rihgt;
for (int i = 1; i < n; i++) {
left += grid;
rihgt -= grid;
res = Math.min(res, Math.max(left, rihgt));
}
return res;
}
}
【 NO.3 判断单词是否能放入填字游戏内】
解题思路
模拟题，详情见注释。
代码展示
public class Solution {
public boolean placeWordInCrossword(char[][] board, String word) {
if (board == null || board.length == 0 || board.length == 0) {
return false;
}
int n = board.length;
int m = board.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
//从 (i, j) 开始，尝试水平地、垂直地放置单词
if (isValid(board, word, j, j + word.length() - 1, i, true) || isValid(board, word, i, i + word.length() - 1, j, false)) {
return true;
}
}
}
return false;
}
private boolean isValid(char[][] board, String word, int start, int end, int standard, boolean isHorizontal) {
//水平放置, standard代表行, 固定不动
if (isHorizontal) {
if (end > board.length - 1) {
return false;
}
//如果左边界不越界，检查左边界的元素是否合法
if (start - 1 >= 0 && (board == ' ' || Character.isLetter(board))) {
return false;
}
//如果右边界不越界，检查右边界的元素是否合法
if (end + 1 < board.length && (board == ' ' || Character.isLetter(board))) {
return false;
}
//至此，它的位置已确认是合法的了
//接下来，只需要判断 (standard, start) ~ (standard, end) 这个区间 "是否有障碍'#'
//正反都需要判断
return check(board, word, start, end, standard, true, false) || check(board, word, start, end, standard, true, true);
}
//垂直放置,standard 代表列, 固定
else {
if (end > board.length - 1) {
return false;
}
//如果上边界不越界，检查上边界的元素是否合法
if (start - 1 >= 0 && (board == ' ' || Character.isLetter(board))) {
return false;
}
//如果下边界不越界，检查下边界的元素是否合法
if (end + 1 < board.length && (board == ' ' || Character.isLetter(board))) {
return false;
}
//至此，它的位置已确认是合法的了
//接下来，只需要判断 (start, standard) ~ (end, standard) 这个区间 "是否有障碍'#'
//正反都要判断
return check(board, word, start, end, standard, false, false) || check(board, word, start, end, standard, false, true);
}
}
private boolean check(char[][] board, String word, int start, int end, int standard, boolean isHorizontal, boolean isReversed) {
if (isHorizontal) {
//正向模拟
if (!isReversed) {
for (int i = start; i <= end; i++) {
if (board == '#' || (Character.isLetter(board) && board != word.charAt(i - start))) {
return false;
}
}
}
//反向模拟
else {
for (int i = end; i >= start; i--) {
if (board == '#' || (Character.isLetter(board) && board != word.charAt(end - i))) {
return false;
}
}
}
}
else {
//正向模拟
if (!isReversed) {
for (int i = start; i <= end; i++) {
if (board == '#' || (Character.isLetter(board) && board != word.charAt(i - start))) {
return false;
}
}
}
//反向模拟
else {
for (int i = end; i >= start; i--) {
if (board == '#' || (Character.isLetter(board) && board != word.charAt(end - i))) {
return false;
}
}
}
}
return true;
}
}
【 NO.4 解出数学表达式的学生分数】
解题思路
首先理一理总体的思路，我们需要做的事情有：
1. 求出表达式的正确值：Stack的方式解决
2. 求出表达式所有可能的值：区间型动态规划解决
3. 计算学生的得分：计分即可
代码展示
public int scoreOfStudents(String s, int[] answers) {
int[] count = new int;
for (int ans : answers) {
count++;
}
Stack<Integer> stack = new Stack<>();
stack.push(s.charAt(0) - '0');
for (int i = 1; i < s.length(); i += 2) {
// 加法暂时不做，存在栈顶
if (s.charAt(i) == '+') {
stack.push(s.charAt(i + 1) - '0');
}
// 乘法直接运算
else {
stack.push(stack.pop() * (s.charAt(i + 1) - '0'));
}
}
int rihgtAns = 0;
while (stack.size() > 0) {
rihgtAns += stack.pop();
}
// 计算正确的人数积分
int res = count * 5;
// 枚举所有可能的计算结果
int n = s.length();
Set<Integer>[][] dp = new Set;
for (int i = 0; i < n + 2; i++) {
for (int j = 0; j < n + 2; j++) {
dp = new HashSet<>();
}
}
for (int j = 0; j < n; j += 2) {
dp.add(s.charAt(j) - '0');
}
// 区间型动态规划
for (int len = 2; len < n; len++) {
// 左端点 i
for (int i = 0; i + len < n; i += 2) {
// 枚举左半部分的长度
for (int leftLen = 0; leftLen < len; leftLen += 2) {
// left 表示左半部分的值
// right 表示右半部分的值
for (int left : dp) {
for (int right : dp) {
if (s.charAt(i + leftLen + 1) == '+') {
if (left + right <= 1000) {
dp.add(left + right);
}
} else {
if (left * right <= 1000) {
dp.add(left * right);
}
}
}
}
}
}
}
for (int points : dp) {
if (points != rihgtAns) {
res += 2 * count;
}
}
return res;
}
页:
[1]