美文网首页java学习之路
leetCode进阶算法题+解析(八十八)

leetCode进阶算法题+解析(八十八)

作者: 唯有努力不欺人丶 | 来源:发表于2021-07-29 18:48 被阅读0次

    使括号有效的最少添加

    题目:给定一个由 '(' 和 ')' 括号组成的字符串 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中说:兵分两路,顶峰相见,让我瞬间有了当年看阿里云这群疯子的感动。该说不说,阿里文化真洗脑...

    相关文章

      网友评论

        本文标题:leetCode进阶算法题+解析(八十八)

        本文链接:https://www.haomeiwen.com/subject/mprbpltx.html