刷题打卡，第 二十一 天
题目一、921. 使括号有效的最少添加
题目二、1706. 球会落何处
题目一、921. 使括号有效的最少添加
原题链接：921. 使括号有效的最少添加
题目描述：
只有满足下面几点之一，括号字符串才是有效的：
它是一个空字符串，或者
它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
它可以被写作 (A)，其中 A 是有效字符串。
给定一个括号字符串 s ，移动N次，你就可以在字符串的任何位置插入一个括号。
例如，如果 s = “()))” ，你可以插入一个开始括号为 “(()))” 或结束括号为 “())))” 。
返回 为使结果字符串 s 有效而必须添加的最少括号数。
/
示例 1：
输入：s = “())”
输出：1
/
示例 2：
输入：s = “(((”
输出：3
解题思路：
题目把要求讲述地很细致了，我们可以简单地理解为：要让字符串中没有多余的单边括号，我们最少要添加多少次对应的单边括号呢？
一开始我觉得十分简单，既然要让括号都对应起来，那就让左半边括号的数量等于右半边括号的数量不就行了？
于是我就很自信地遍历字符串的每一个字符：
当遇到左括号‘(’，就记录左括号数量left++；
当遇到右括号‘)’，就记录左括号数量right++；
最后返回差值…
结果提交结果是：
我忽略了一类重要的情况:那就是当左右括号顺序是错开的，上面的思路就完全错误啦。
比如：") (",需要返回的就不是差值0,而是2.
这么一来我们就需要另外想办法了，但是问题不大，思路很快就有啦，那就是利用栈结构来判断：
当遇到左括号'(',我们就将左括号入栈，等待对应的右括号')';
当遇到右括号')'，我们就要分为两种情况…
①栈中没有元素，也就是栈长度为0时，我们记录右括号')'的数量right++
②当栈中存在元素左括号(，我们将栈顶元素弹出，代表两个括号对应，抵消了。
当我们遍历完整个字符串，也就知道了最少需要添加多少个括号使得所有括号有效了：
我们需要right数量个的左括号'(' 和 栈长度数量个的右括号')'
栈记作 dq,则最少需要 添加right + dq.size()个括号
提交代码：
class Solution { public int minAddToMakeValid(String s) { char[] ch = s.toCharArray(); //字符串转化为字符数组 int right = 0; //用于记录单独的右括号个数 //创建栈，用于记录单独的左括号个数 Deque<Character> dq = new LinkedList<>(); for(char a : ch){ //遍历每一个字符 if(a == '(') //左括号入栈 dq.push(a); if(a == ')'){ //遇到右括号 if(dq.size() == 0){ //栈空，right++ ++right; }else{ //栈中有对应的左括号 dq.pop(); //栈顶弹出，左右括号对应抵消 } } } return right + dq.size(); //返回最少添加数 } }
提交结果：
题目二、1706. 球会落何处
原题链接：1706. 球会落何处
题目描述：
用一个大小为 m x n 的二维网格 grid 表示一个箱子。你有 n 颗球。箱子的顶部和底部都是开着的。
箱子中的每个单元格都有一个对角线挡板，跨过单元格的两个角，可以将球导向左侧或者右侧。
将球导向右侧的挡板跨过左上角和右下角，在网格中用 1 表示。
将球导向左侧的挡板跨过右上角和左下角，在网格中用 -1 表示。
在箱子每一列的顶端各放一颗球。每颗球都可能卡在箱子里或从底部掉出来。如果球恰好卡在两块挡板之间的 “V” 形图案，或者被一块挡导向到箱子的任意一侧边上，就会卡住。
返回一个大小为 n 的数组 answer ，其中 answer[i] 是球放在顶部的第 i 列后从底部掉出来的那一列对应的下标，如果球卡在盒子里，则返回 -1 。
/
示例 1：
输入：grid = [[1,1,1,-1,-1],[1,1,1,-1,-1],[-1,-1,-1,1,1],[1,1,1,1,-1],[-1,-1,-1,-1,-1]]
输出：[1,-1,-1,-1,-1]
解释：示例如图：
b0 球开始放在第 0 列上，最终从箱子底部第 1 列掉出。
b1 球开始放在第 1 列上，会卡在第 2、3 列和第 1 行之间的 “V” 形里。
b2 球开始放在第 2 列上，会卡在第 2、3 列和第 0 行之间的 “V” 形里。
b3 球开始放在第 3 列上，会卡在第 2、3 列和第 0 行之间的 “V” 形里。
b4 球开始放在第 4 列上，会卡在第 2、3 列和第 1 行之间的 “V” 形里。
/
示例 2：
输入：grid = [[-1]]
输出：[-1]
解释：球被卡在箱子左侧边上。
/
示例 3：
输入：grid = [[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1],[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1]]
输出：[0,1,2,3,4,-1]
解题思路：
题目要求我们返回一个大小为 n 的数组 answer 。
其中 answer[i] 是球放在顶部的第 i 列后从底部掉出来的那一列对应的下标；
如果球卡在盒子里，则返回 -1 ；
为了得到大小为 n 的数组 answer，我们就需要使用循环，从第一列的顶端开始遍历，将每一个位置都遍历一遍，同时记录下每一次的落点位置，最终返回数组 answer。
基本的思路出来的，但是难题根本未被解决，我们如何才能确定球的落点位置呢？
我们可以借助题目给到的例子观察：
①当前格子的值为1,代表接下来球会向右移动，也就是列数：col++
②当前格子的值为-1,代表接下来球会向左移动，也就是列数：col--
③当球体完成一次左移或者后移后，都会掉到下一行当中，也就是行数：row++
④当然，上面所有的情况都需要建立在：
移动后格子的值不变的情况下 以及 移动后位置不越界的情况下
当出现 移动后格子的值改变 或者 移动后位置越界 的情况时，代表：
球恰好卡在两块挡板之间的 “V” 形图案，或者被一块挡导向到箱子的任意一侧边上，卡住了，那么此次落点就记录为 -1
⑤当球没有被拦截下来而停止，最终从盒子底部掉落，我们就记录下掉落前的最后一刻，球在最后一行对应的列数col
当记录完从每一列顶部放入球后最终的落点位置时，我们直接返回记录数组answer
提交代码：
class Solution { public int[] findBall(int[][] grid) { int rows = grid.length; //获取行数 int cols = grid[0].length; //获取列数 int[] out = new int[cols]; //创建记录落点的数组，长度与列数相同 a:for(int i = 0;i < cols;++i){ //遍历球从每一列顶端放下的情况 int row = 0; //球从第一行开始移动 int col = i; //球在第i列顶端被放下 while(row < rows){ //球没有掉出网格时 int val = grid[row][col]; //获取球所在格子的挡板情况 if(val == 1){ //向着右侧 if(col+1 < cols) ++col; //如果向右没有越界，列数++，球右移 else{ out[i] = -1; //遇到箱子一侧，被拦截，记录-1 continue a; //进入下一次循环 } } //以下是挡板向着左侧的情况，步骤与上述基本一致 if(val == -1){ if(col-1 >= 0) --col; else{ out[i] = -1; continue a; } } //获取下一个位置的挡板情况 int next = grid[row][col]; //挡板位置情况相同，球下落 if(val == next) row++; //位置情况相反，形成 V字图案，球被拦截 else{ out[i] = -1; //记录-1 continue a; //进入下一次循环 } } out[i] = col; //记录底部掉落位置 } return out; //返回记录的数组out（题目要求的answer[]） } }
提交结果：
⚽求关注⚽ 作者🥇 .29. 🥇 的✔博客主页✔
⚽来刷题⚽ 记录每日LeetCode✔刷题专栏✔
您的点赞，收藏以及关注是对作者最大的鼓励喔 ~~
