【 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;}