leetCode进阶算法题+解析（八十八）
使括号有效的最少添加
题目：给定一个由 '(' 和 ')' 括号组成的字符串 S，我们需要添加最少的括号（ '(' 或是 ')'，可以在任何位置），以使得到的括号字符串有效。从形式上讲，只有满足下面几点之一，括号字符串才是有效的：它是一个空字符串，或者
它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
它可以被写作 (A)，其中 A 是有效字符串。
给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。
示例 1：
输入："())"
输出：1
示例 2：
输入："((("
输出：3
示例 3：
输入："()"
输出：0
示例 4：
输入："()))(("
输出：4
提示：
S.length <= 1000
S 只包含 '(' 和 ')' 字符。
思路：这个题怎么说呢，因为只包含左右两个括号，所以归根结底我们要做到的就是每一个左括号有对应的右括号，同理右括号有对应的左括号。其实我觉得实现 的方式还是挺多的。单纯的用一个变量计算左右括号数量就可以了，我去代码实现试试。
我差点都寻思我思路错了，因为这个题简单的离谱。没想到一次ac，而且性能超过百分百，直接贴代码：
class Solution {
public int minAddToMakeValid(String s) {
int flag = 0;
int ans = 0;
for(char c:s.toCharArray()){
if(c == ')'){
flag--;
if(flag<0){
ans -= flag;//）前必须有（。所以这个必须添加
flag = 0;
}
}else {
flag++;
}
}
ans += flag;
return ans;
}
}
就是简单的两种情况：如果是左括号可以最后结算。如果是右括号必须当时结算。然后代码如上，这个比较简单，直接下一题了。
三数之和的多种可能
题目：给定一个整数数组 A，以及一个整数 target 作为目标值，返回满足 i < j < k 且 A[i] + A[j] + A[k] == target 的元组 i, j, k 的数量。由于结果会非常大，请返回 结果除以 10^9 + 7 的余数。
示例 1：
输入：A = [1,1,2,2,3,3,4,4,5,5], target = 8
输出：20
解释：
按值枚举（A[i]，A[j]，A[k]）：
(1, 2, 5) 出现 8 次；
(1, 3, 4) 出现 8 次；
(2, 2, 4) 出现 2 次；
(2, 3, 3) 出现 2 次。
示例 2：
输入：A = [1,1,2,2,2,2], target = 5
输出：12
解释：
A[i] = 1，A[j] = A[k] = 2 出现 12 次：
我们从 [1,1] 中选择一个 1，有 2 种情况，
从 [2,2,2,2] 中选出两个 2，有 6 种情况。
提示：
3 <= A.length <= 3000
0 <= A[i] <= 100
0 <= target <= 300
思路：这个因为数据范围很小，所以可以用我很喜欢的一种方式：数组下标代替值，值代表出现的次数。因为范围是1-100、所以101个数组元素就可以表示了。然后下一步就是三数确定前两数。然后target-前两数和就能知道存不存在三个数和是target。应该是n方的时间复杂度。思路比较清晰，我去实现试试。
第一版代码：
class Solution {
public int threeSumMulti(int[] arr, int target) {
long res = 0;
int[] cur = new int[101];
for(int i : arr) cur[i]++;
for(int i = 0;i<cur.length;i++){
if(cur[i] == 0) continue;//这个元素一次没出现，没有必要往下走了
for(int j = i;j<cur.length;j++){
if(cur[j] == 0) continue;//这个元素没出现，也没必要判断
int t = target-i-j;
if(t < j) {
break;
}else {
if(t > 100) continue;
//三数为同一个数的情况
if(t == i && t == j) {
res += ((long)cur[i] * (cur[i] - 1) * (cur[i] - 2)) / 6;
//三数，后两个为同一个的情况
}else if(t == j) {
res += ((long)cur[j] * (cur[j] - 1)) / 2 * cur[i];;
//三数，前两个为同一个的情况
}else if(i == j) {
res += ((long)cur[i] * (cur[i] - 1) )/2 * cur[t];
}else {
res += (long)cur[i] * cur[j] * cur[t];
}
}
}
}
return (int)(res%1000000007);
}
}
这个代码性能还挺好，性能超过了百分之九十九。所以总的来说思路是对的。然后别的我就不看了。下一题了。
将字符串翻转到单调递增
题目：如果一个由 '0' 和 '1' 组成的字符串，是以一些 '0'（可能没有 '0'）后面跟着一些 '1'（也可能没有 '1'）的形式组成的，那么该字符串是单调递增的。我们给出一个由字符 '0' 和 '1' 组成的字符串 S，我们可以将任何 '0' 翻转为 '1' 或者将 '1' 翻转为 '0'。返回使 S 单调递增的最小翻转次数。
示例 1：
输入："00110"
输出：1
解释：我们翻转最后一位得到 00111.
示例 2：
输入："010110"
输出：2
解释：我们翻转得到 011111，或者是 000111。
示例 3：
输入："00011000"
输出：2
解释：我们翻转得到 00000000。
提示：
1 <= S.length <= 20000
S 中只包含字符 '0' 和 '1'
思路：这个我暂时的思路是肯定有一个分界线，前面是0.后面是1.所以重点是如何找到这个分界线。所以我的打算是用两个数组记录。一个是记录1，从前往后算。一个是记录0.从后往前算。然后每一个元素前面的1和后面的0的和最小，就是最小改变次数。思路大概是这样，我去实现试试、
思路比较清晰，一次过的，贴代码：
class Solution {
public int minFlipsMonoIncr(String s) {
char[] c = s.toCharArray();
//前面的1和後面的0最小的結果就是最小次數
int[] one = new int[s.length()+1];
int[] zero = new int[s.length()+1];
for(int i = 0;i<c.length;i++) one[i+1] = one[i]+(c[i]=='1'?1:0);
for(int i = c.length-1;i>=0;i--) zero[i] = zero[i+1] + (c[i] == '0'?1:0);
int ans = Integer.MAX_VALUE;
for(int i = 0;i<one.length;i++) ans = Math.min(ans,one[i]+zero[i]);
return ans;
}
}
思路就是我上面说的，而且代码性能也不错，我就不多说了，直接下一题。
和相同的二元子数组
题目：给你一个二元数组 nums ，和一个整数 goal ，请你统计并返回有多少个和为 goal 的 非空 子数组。子数组 是数组的一段连续部分。
示例 1：
输入：nums = [1,0,1,0,1], goal = 2
输出：4
解释：
有 4 个满足题目要求的子数组：[1,0,1]、[1,0,1,0]、[0,1,0,1]、[1,0,1]
示例 2：
输入：nums = [0,0,0,0,0], goal = 0
输出：15
提示：
1 <= nums.length <= 3 * 104
nums[i] 不是 0 就是 1
0 <= goal <= nums.length
思路：这个题怎么说呢，难倒是不难。我最直接的想法就是每个元素作为开始去遍历。就是不知道会不会超时，我去试试。
第一版代码：
class Solution {
public int numSubarraysWithSum(int[] nums, int goal) {
int ans = 0;
for(int i = 0;i<nums.length;i++){
int sum = 0;
for(int j = i;j<nums.length;j++){
sum += nums[j];
if(sum == goal) ans++;
if(sum>goal) break;
}
}
return ans;
}
}
硬生生的暴力法，我还想着这么写不过我就换种思路，毕竟做的过程中我就觉得可以用前缀和来实现，不管怎么样起码比当前的效率好，我去实现试试。很好，过了，而且性能不错，我先贴代码：
class Solution {
public int numSubarraysWithSum(int[] nums, int S) {
int[] arr = new int[30000];
arr[0] = 1;
int sum = 0;
int ans = 0;
for(int i=0;i<nums.length;i++){
sum += nums[i];
if(sum-S>=0) ans += arr[sum-S];
arr[sum]++;
}
return ans;
}
}
本来这里的常规做法应该是用map来记录。但是我之前脑一抽，觉得3成10的四次方是3千，然后就自信用了数组。然后提交才发现是3w。但是代码都写了，所以，结果发现哪怕是3w数据范围，也是数组的效率高。这个代码超过了百分之八十的用户，我再去看看性能第一的代码：
好像是用的双指针滑窗，我直接附上代码：
class Solution {
public int numSubarraysWithSum(int[] nums, int goal) {
int n = nums.length;
int l1 = 0, l2 = 0, s1 = 0, s2 = 0, r = 0, res = 0;
while (r < n) {
s1 += nums[r];
s2 += nums[r];
while (l1 <= r && s1 > goal)
s1 -= nums[l1++];
while (l2 <= r && s2 >= goal)
s2 -= nums[l2++];
r ++;
res += l2 - l1;
}
return res;
}
}
这个代码我也不太想要细看了，直接下一题吧。
下降路径最小和
题目：给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
示例 1：
输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出：13
解释：下面是两条和最小的下降路径，用加粗标注：
[[2,1,3], [[2,1,3],
[6,5,4], [6,5,4],
[7,8,9]] [7,8,9]]
示例 2：
输入：matrix = [[-19,57],[-40,-5]]
输出：-59
解释：下面是一条和最小的下降路径，用加粗标注：
[[-19,57],
[-40,-5]]
示例 3：
输入：matrix = [[-48]]
输出：-48
提示：
n == matrix.length
n == matrix[i].length
1 <= n <= 100
-100 <= matrix[i][j] <= 100
思路：盲猜这道题要用dp来解决，因为尽量做到每一步都是最佳选项。只不过这个题和常规的dp相比是二维的。而且上一步的选择决定当前选择而已。有了大概的思路，我去写代码试试。
附上第一版代码：
class Solution {
public int minFallingPathSum(int[][] matrix) {
int n = matrix.length;
for(int i = 1;i<n;i++){
for(int j = 0;j<n;j++){
int temp = matrix[i-1][j];
if(j>0) temp = Math.min(matrix[i-1][j-1],temp);
if(j<n-1) temp = Math.min(matrix[i-1][j+1],temp);
matrix[i][j] += temp;
}
}
int ans = Integer.MAX_VALUE;
for(int i:matrix[n-1]){
ans = Math.min(i,ans);
}
return ans;
}
}
这个题怎么说呢，典型dp，而dp的点是取当前元素上一个可选值（左上，上，右上）最小的那个。这样才能保证当前值是最小的。至于下一行用不用当前元素就是后面的事了。这个思路其实只要理明白了就很简单的。然后我上面的代码性能超过百分之八十，感觉不是特别好，但是也不差。我怀疑这个是我细节处理的问题，应该不是思路上的问题，去看看性能第一的代码：
class Solution {
//备忘录
int[][] memo;
public int minFallingPathSum(int[][] matrix) {
//行数
int n = matrix.length;
int res = Integer.MAX_VALUE;
//备忘录初始化，此值需要在[-10000,10000]之外
memo = new int[n][n];
for(int i = 0; i < n; i++) {
Arrays.fill(memo[i], 66666);
}
//终点在最后一行，某列为最小路径和
for (int j = 0; j < n; j++) {
res = Math.min(res, dp(matrix, n - 1, j));
}
return res;
}
public int dp(int[][] matrix, int i, int j) {
//非法索引检查，返回大于10000的特殊值，并且无法在取最小过程取到的值
if (i < 0 || j < 0 || i >= matrix.length || j >= matrix[0].length)
return 99999;
//base case
if (i == 0)
return matrix[i][j];
//检查备忘录
if (memo[i][j] != 66666)
return memo[i][j];
//状态转移,递归从上一行的三个可选项中找最小值加上,存值
memo[i][j] = matrix[i][j] + min(dp(matrix, i - 1, j - 1), dp(matrix, i - 1, j), dp(matrix, i - 1, j + 1));
return memo[i][j];
}
public int min(int a, int b, int c) {
return Math.min(a, Math.min(b, c));
}
}
啪啪打脸，百分之六十的思路是一样的，都是dp，都是三选一。但是人家加了个备忘录。别的也就那样了，不多说了，下一题了。
最短的桥
题目：在给定的二维二进制数组 A 中，存在两座岛。（岛是由四面相连的 1 形成的一个最大组。）现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。返回必须翻转的 0 的最小数目。（可以保证答案至少是 1 。）
示例 1：
输入：A = [[0,1],[1,0]]
输出：1
示例 2：
输入：A = [[0,1,0],[0,0,0],[0,0,1]]
输出：2
示例 3：
输入：A = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
输出：1
提示：
2 <= A.length == A[0].length <= 100
A[i][j] == 0 或 A[i][j] == 1
思路：这个题我目前的想法是分两步：第一步把其中一块岛的所有的1变成2。这样就可以很明显区分出两块岛了。方法也比较简单，随便找个1然后扩散到无可散。然后第二步桥的长度的话，随便找一个岛开始往外一个长度一个长度的扩散。一直到与另一个接壤说明桥就这么长。思路比较清楚，但是我个人感觉这个题可能代码实现比较复杂。毕竟找其中一个岛就用dfs，扩散应该也是要的。我去代码实现试试。
咋说呢，我现在的直觉贼准，感觉写着麻烦，果然样呀飒飒五十来行，先贴代码：
class Solution {
public int shortestBridge(int[][] grid) {
int n = grid.length;
boolean flag = true;
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
if(grid[i][j] == 1){
dfs(grid,i,j);
flag = false;
break;
}
}
if(!flag) break;
}
return isOk(grid,2)-2;
}
public int isOk(int[][] grid,int ans){
int n = grid.length;
while (true){
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
if(grid[i][j] == ans){
if(i>0 ){
if(grid[i-1][j] == 1) return ans;
if(grid[i-1][j] == 0) grid[i-1][j] = ans+1;
}
if(i<grid.length-1) {
if(grid[i+1][j] == 1)return ans;
if(grid[i+1][j] == 0) grid[i+1][j] = ans+1;
}
if(j>0){
if(grid[i][j-1] == 1) return ans;
if(grid[i][j-1] == 0) grid[i][j-1] = ans+1;
}
if(j<grid.length-1) {
if( grid[i][j+1] == 1) return ans;
if(grid[i][j+1] == 0) grid[i][j+1] = ans+1;
}
}
}
}
ans++;
}
}
public void dfs(int[][] grid,int i,int j){
grid[i][j] = 2;
if(i>0 && grid[i-1][j] == 1) dfs(grid,i-1,j);
if(i<grid.length-1 && grid[i+1][j] == 1) dfs(grid,i+1,j);
if(j>0 && grid[i][j-1] == 1) dfs(grid,i,j-1);
if(j<grid.length-1 && grid[i][j+1] == 1) dfs(grid,i,j+1);
}
}
思路和我之前说的差不多，分两步，死去活来dfs。第二步其实while里就是一个递归。然后代码虽然写的很复杂，但是性能出乎意料的好，这个题难点也不是思路而是代码，所以就不多说了，这个题过了。
本篇笔记就到这里，如果稍微帮到你了记得点个喜欢点个关注。也祝大家工作顺顺利利，身体健健康康！顺便吐个槽，今天看到一句很燃的话，阿里的一个p9跳槽到开课吧，logo中说：兵分两路，顶峰相见，让我瞬间有了当年看阿里云这群疯子的感动。该说不说，阿里文化真洗脑...
