上岸算法LeetCode Weekly Contest 260解题报告

上岸算法 · 发表于 2021-9-26 17:58:10

登录后可回复主题

您需要登录才可以下载或查看，没有帐号？注册账号

x

【 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 解出数学表达式的学生分数】

解题思路

首先理一理总体的思路，我们需要做的事情有：

1. 求出表达式的正确值：Stack的方式解决
2. 求出表达式所有可能的值：区间型动态规划解决
3. 计算学生的得分：计分即可
代码展示

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;

}

帐号		自动登录	找回密码
密码			注册账号

[吹水聊天] 上岸算法LeetCode Weekly Contest 260解题报告

登录后可回复主题

浏览过的版块