使括號有效的最少添加

題目：給定一個由 '(' 和 ')' 括號組成的字符串 S，我們需要添加最少的括號（ '(' 或是 ')'，可以在任何位置），以使得到的括號字符串有效。從形式上講，只有滿足下面幾點之一，括號字符串才是有效的：它是一個空字符串，或者

它可以被寫成 AB （A 與 B 連接）, 其中 A 和 B 都是有效字符串，或者

它可以被寫作 (A)，其中 A 是有效字符串。

給定一個括號字符串，返回為使結(jié)果字符串有效而必須添加的最少括號數(shù)。

示例 1：
輸入："())"
輸出：1
示例 2：
輸入："((("
輸出：3
示例 3：
輸入："()"
輸出：0
示例 4：
輸入："()))(("
輸出：4
提示：
S.length <= 1000
S 只包含 '(' 和 ')' 字符。

思路：這個題怎么說呢，因為只包含左右兩個括號，所以歸根結(jié)底我們要做到的就是每一個左括號有對應(yīng)的右括號，同理右括號有對應(yīng)的左括號。其實我覺得實現(xiàn) 的方式還是挺多的。單純的用一個變量計算左右括號數(shù)量就可以了，我去代碼實現(xiàn)試試。
我差點都尋思我思路錯了，因為這個題簡單的離譜。沒想到一次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;
    }
}

就是簡單的兩種情況：如果是左括號可以最后結(jié)算。如果是右括號必須當時結(jié)算。然后代碼如上，這個比較簡單，直接下一題了。

三數(shù)之和的多種可能

題目：給定一個整數(shù)數(shù)組 A，以及一個整數(shù) target 作為目標值，返回滿足 i < j < k 且 A[i] + A[j] + A[k] == target 的元組 i, j, k 的數(shù)量。由于結(jié)果會非常大，請返回 結(jié)果除以 10^9 + 7 的余數(shù)。

示例 1：
輸入：A = [1,1,2,2,3,3,4,4,5,5], target = 8
輸出：20
解釋：
按值枚舉（A[i]，A[j]，A[k]）：
(1, 2, 5) 出現(xiàn) 8 次；
(1, 3, 4) 出現(xiàn) 8 次；
(2, 2, 4) 出現(xiàn) 2 次；
(2, 3, 3) 出現(xiàn) 2 次。
示例 2：
輸入：A = [1,1,2,2,2,2], target = 5
輸出：12
解釋：
A[i] = 1，A[j] = A[k] = 2 出現(xiàn) 12 次：
我們從 [1,1] 中選擇一個 1，有 2 種情況，
從 [2,2,2,2] 中選出兩個 2，有 6 種情況。
提示：
3 <= A.length <= 3000
0 <= A[i] <= 100
0 <= target <= 300

思路：這個因為數(shù)據(jù)范圍很小，所以可以用我很喜歡的一種方式：數(shù)組下標代替值，值代表出現(xiàn)的次數(shù)。因為范圍是1-100、所以101個數(shù)組元素就可以表示了。然后下一步就是三數(shù)確定前兩數(shù)。然后target-前兩數(shù)和就能知道存不存在三個數(shù)和是target。應(yīng)該是n方的時間復雜度。思路比較清晰，我去實現(xià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;//這個元素一次沒出現(xiàn)，沒有必要往下走了
            for(int j = i;j<cur.length;j++){
                if(cur[j] == 0) continue;//這個元素沒出現(xiàn)，也沒必要判斷
                int t = target-i-j;
                if(t < j) {
                    break;
                }else {
                    if(t > 100) continue;
                    //三數(shù)為同一個數(shù)的情況
                    if(t == i && t == j) {
                        res += ((long)cur[i] * (cur[i] - 1) * (cur[i] - 2)) / 6;
                        //三數(shù)，后兩個為同一個的情況
                    }else if(t == j) {
                        res += ((long)cur[j] * (cur[j] - 1)) / 2 * cur[i];;
                        //三數(shù)，前兩個為同一個的情況
                    }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);
    }
}

這個代碼性能還挺好，性能超過了百分之九十九。所以總的來說思路是對的。然后別的我就不看了。下一題了。

將字符串翻轉(zhuǎn)到單調(diào)遞增

題目：如果一個由 '0' 和 '1' 組成的字符串，是以一些 '0'（可能沒有 '0'）后面跟著一些 '1'（也可能沒有 '1'）的形式組成的，那么該字符串是單調(diào)遞增的。我們給出一個由字符 '0' 和 '1' 組成的字符串 S，我們可以將任何 '0' 翻轉(zhuǎn)為 '1' 或者將 '1' 翻轉(zhuǎn)為 '0'。返回使 S 單調(diào)遞增的最小翻轉(zhuǎn)次數(shù)。

示例 1：
輸入："00110"
輸出：1
解釋：我們翻轉(zhuǎn)最后一位得到 00111.
示例 2：
輸入："010110"
輸出：2
解釋：我們翻轉(zhuǎn)得到 011111，或者是 000111。
示例 3：
輸入："00011000"
輸出：2
解釋：我們翻轉(zhuǎn)得到 00000000。
提示：
1 <= S.length <= 20000
S 中只包含字符 '0' 和 '1'

思路：這個我暫時的思路是肯定有一個分界線，前面是0.后面是1.所以重點是如何找到這個分界線。所以我的打算是用兩個數(shù)組記錄。一個是記錄1，從前往后算。一個是記錄0.從后往前算。然后每一個元素前面的1和后面的0的和最小，就是最小改變次數(shù)。思路大概是這樣，我去實現(xiàn)試試、
思路比較清晰，一次過的，貼代碼：

class Solution {
    public int minFlipsMonoIncr(String s) {
        char[] c = s.toCharArray();
        //前面的1和後面的0最小的結(jié)果就是最小次數(shù)
        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;
    }
}

思路就是我上面說的，而且代碼性能也不錯，我就不多說了，直接下一題。

和相同的二元子數(shù)組

題目：給你一個二元數(shù)組 nums ，和一個整數(shù) goal ，請你統(tǒng)計并返回有多少個和為 goal 的 非空 子數(shù)組。子數(shù)組 是數(shù)組的一段連續(xù)部分。

示例 1：
輸入：nums = [1,0,1,0,1], goal = 2
輸出：4
解釋：
有 4 個滿足題目要求的子數(shù)組：[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;
    }
}

硬生生的暴力法，我還想著這么寫不過我就換種思路，畢竟做的過程中我就覺得可以用前綴和來實現(xiàn)，不管怎么樣起碼比當前的效率好，我去實現(xiàn)試試。很好，過了，而且性能不錯，我先貼代碼：

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

本來這里的常規(guī)做法應(yīng)該是用map來記錄。但是我之前腦一抽，覺得3成10的四次方是3千，然后就自信用了數(shù)組。然后提交才發(fā)現(xiàn)是3w。但是代碼都寫了，所以，結(jié)果發(fā)現(xiàn)哪怕是3w數(shù)據(jù)范圍，也是數(shù)組的效率高。這個代碼超過了百分之八十的用戶，我再去看看性能第一的代碼：
好像是用的雙指針滑窗，我直接附上代碼：

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 的 方形 整數(shù)數(shù)組 matrix ，請你找出并返回通過 matrix 的下降路徑 的 最小和 。下降路徑 可以從第一行中的任何元素開始，并從每一行中選擇一個元素。在下一行選擇的元素和當前行所選元素最多相隔一列（即位于正下方或者沿對角線向左或者向右的第一個元素）。具體來說，位置 (row, col) 的下一個元素應(yīng)當是 (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來解決，因為盡量做到每一步都是最佳選項。只不過這個題和常規(guī)的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的點是取當前元素上一個可選值（左上，上，右上）最小的那個。這樣才能保證當前值是最小的。至于下一行用不用當前元素就是后面的事了。這個思路其實只要理明白了就很簡單的。然后我上面的代碼性能超過百分之八十，感覺不是特別好，但是也不差。我懷疑這個是我細節(jié)處理的問題，應(yīng)該不是思路上的問題，去看看性能第一的代碼：

class Solution {
    //備忘錄
        int[][] memo;
    public int minFallingPathSum(int[][] matrix) {
        //行數(shù)
        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];
        

        //狀態(tài)轉(zhuǎn)移,遞歸從上一行的三個可選項中找最小值加上,存值
        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，都是三選一。但是人家加了個備忘錄。別的也就那樣了，不多說了，下一題了。

最短的橋

題目：在給定的二維二進制數(shù)組 A 中，存在兩座島。（島是由四面相連的 1 形成的一個最大組。）現(xiàn)在，我們可以將 0 變?yōu)?1，以使兩座島連接起來，變成一座島。返回必須翻轉(zhuǎn)的 0 的最小數(shù)目。（可以保證答案至少是 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。這樣就可以很明顯區(qū)分出兩塊島了。方法也比較簡單，隨便找個1然后擴散到無可散。然后第二步橋的長度的話，隨便找一個島開始往外一個長度一個長度的擴散。一直到與另一個接壤說明橋就這么長。思路比較清楚，但是我個人感覺這個題可能代碼實現(xiàn)比較復雜。畢竟找其中一個島就用dfs，擴散應(yīng)該也是要的。我去代碼實現(xiàn)試試。
咋說呢，我現(xiàn)在的直覺賊準，感覺寫著麻煩，果然樣呀颯颯五十來行，先貼代碼：

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里就是一個遞歸。然后代碼雖然寫的很復雜，但是性能出乎意料的好，這個題難點也不是思路而是代碼，所以就不多說了，這個題過了。
本篇筆記就到這里，如果稍微幫到你了記得點個喜歡點個關(guān)注。也祝大家工作順順利利，身體健健康康！順便吐個槽，今天看到一句很燃的話，阿里的一個p9跳槽到開課吧，logo中說：兵分兩路，頂峰相見，讓我瞬間有了當年看阿里云這群瘋子的感動。該說不說，阿里文化真洗腦...