乐趣区

关于leetcode:上岸算法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[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;

}
退出移动版