4
上岸算法LeetCode Weekly Contest 260解题报告
source link: https://segmentfault.com/a/1190000040741787
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
上岸算法LeetCode Weekly Contest 260解题报告
发布于 6 分钟前
【 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[0].length == 0) {
return 0;
}
int n = grid[0].length;
long left = 0, rihgt = 0;
for (int i = 1; i < n; i++) {
rihgt += grid[0][i];
}
long res = rihgt;
for (int i = 1; i < n; i++) {
left += grid[1][i - 1];
rihgt -= grid[0][i];
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[0].length == 0) {
return false;
}
int n = board.length;
int m = board[0].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[0].length - 1) {
return false;
}
// 如果左边界不越界，检查左边界的元素是否合法
if (start - 1 >= 0 && (board[standard][start - 1] == ' ' || Character.isLetter(board[standard][start - 1]))) {
return false;
}
// 如果右边界不越界，检查右边界的元素是否合法
if (end + 1 < board[0].length && (board[standard][end + 1] == ' ' || Character.isLetter(board[standard][end + 1]))) {
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[start - 1][standard] == ' ' || Character.isLetter(board[start - 1][standard]))) {
return false;
}
// 如果下边界不越界，检查下边界的元素是否合法
if (end + 1 < board.length && (board[end + 1][standard] == ' ' || Character.isLetter(board[end + 1][standard]))) {
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[standard][i] == '#' || (Character.isLetter(board[standard][i]) && board[standard][i] != word.charAt(i - start))) {
return false;
}
}
}
// 反向模拟
else {
for (int i = end; i >= start; i--) {
if (board[standard][i] == '#' || (Character.isLetter(board[standard][i]) && board[standard][i] != word.charAt(end - i))) {
return false;
}
}
}
}
else {
// 正向模拟
if (!isReversed) {
for (int i = start; i <= end; i++) {
if (board[i][standard] == '#' || (Character.isLetter(board[i][standard]) && board[i][standard] != word.charAt(i - start))) {
return false;
}
}
}
// 反向模拟
else {
for (int i = end; i >= start; i--) {
if (board[i][standard] == '#' || (Character.isLetter(board[i][standard]) && board[i][standard] != word.charAt(end - i))) {
return false;
}
}
}
}
return true;
}
【 NO.4 解出数学表达式的学生分数】
首先理一理总体的思路，我们需要做的事情有：
- 求出表达式的正确值：Stack的方式解决
- 求出表达式所有可能的值：区间型动态规划解决
- 计算学生的得分：计分即可
代码展示
public int scoreOfStudents(String s, int[] answers) {
int[] count = new int[1024];
for (int ans : answers) {
count[ans]++;
}
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[rihgtAns] * 5;
// 枚举所有可能的计算结果
int n = s.length();
Set<Integer>[][] dp = new Set[n + 2][n + 2];
for (int i = 0; i < n + 2; i++) {
for (int j = 0; j < n + 2; j++) {
dp[i][j] = new HashSet<>();
}
}
for (int j = 0; j < n; j += 2) {
dp[j][j].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[i][i + leftLen]) {
for (int right : dp[i + leftLen + 2][i + len]) {
if (s.charAt(i + leftLen + 1) == '+') {
if (left + right <= 1000) {
dp[i][i + len].add(left + right);
}
} else {
if (left * right <= 1000) {
dp[i][i + len].add(left * right);
}
}
}
}
}
}
}
for (int points : dp[0][n - 1]) {
if (points != rihgtAns) {
res += 2 * count[points];
}
}
return res;
}Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK