每天几道高频算法题-DAY1-蒲公英云

从今天开始每天做几道高频算法题备战秋招如果有算法还没刷题的(买不起LeetCode会员的) 可以和我一起刷

题目一

给定一个有序数组arr,从左到右依次表示X轴上从左往右点的位置,给定一个正整数K，返回如果有一根长度为K的绳子，最多能盖住几个点绳子的边缘点碰到X轴上的点，也算盖住

思路1:

最暴力解的话就是把绳子的开头放在每一个点上然后遍历出结果之后选一个最大值这样的话时间复杂度会达到O(N)

思路2:

这个方法是使用了滑动窗口法的变种,维护一个数组作为窗口,先以arr[0]为窗口的头部

然后判断窗口最多能拓展到哪个节点然后窗口左侧滑动一个单位(就是以arr[1]开头了本质上是窗口头部向右走了一个元素),然后再看窗口最远可以包含住哪个节点,用max抓住以每个数为开头的最大节点;

public static int MaxPoint(int K,int [] arr) {
        int left = 0;
        int right = 1;
        int max = Integer.MIN_VALUE;
        while(left<arr.length) {
        while(right<arr.length) {
            if(arr[right] - arr[left]<=K) {        
                right++;
            }else {
                break;
            }
        }
        max = Math.max((right-left),max);
        left++;
        }
        return max;
    }

题目二

括号有效配对是指:
1)任何一个左括号都能找到和其正确配对的右括号
2)任何一个右括号都能找到和其正确配对的左括号
有效的: (())()()(()())等
无效的:(())(等
问题一:怎么判断一个括号字符串有效?
问题二:如果一个括号字符串无效，返回至少填几个字符能让其整体有效

问题三:返回一个括号字符串中,最长的括号有效长度() 红色困难

问题一

很简单问题1 无论是单调栈法还是遍历法都可以这里只做最优解

我们定一个整形初始为0 遍历字符串遇到一个左括号加1遇到一个右括号减1 但是如果它变成负数了直接跳出循环返回为假

对于左括号来说只要右边有和它配对的右括号就算有效

但是对于右括号来说如果它的左边没有和它配对的左括号那后面有一万个左括号也不好使了

public static boolean Islegal(String string) {
        int count = 0;
        char [] chars = string.toCharArray();
        for (char c : chars) {
            if(c=='(') {
                count++;
            }
            else if(c==')') {
                count--;
            }
            if(count<0) {
                return false;
            }
        }
        if(count==0) {
            return true;
        }
        return false;
    }

问题二

public static int Islegal(String string) {
        int count = 0;
        int result = 0;
        char [] chars = string.toCharArray();
        for (char c : chars) {
            if(c=='(') {
                count++;
            }
            else if(c==')') {
                count--;
            }
            if(count<0) {
                result++;
                count = 0;
            }
        }
        result += count;
        return result;
    }

和问题一大概流程一致需要注意的点是当count<0的时候表示现在有一个)没有匹配所以我们要立刻把result加一因为如果不处理的话后面会有一个左括号加上然后result变成0 这很显然是逻辑不通的例:)( 这样虽然result为0 但实际上并不合规

问题三

最暴力的解法是遍历以每一个字符结尾(或开头)的字符串然后找出最大值,经典O(N²)复杂度

有只遍历字符串一遍的做法

创建一个与字符数组等长的数组每个数组的元素放以当前位置结尾的最长有效字符串

仅仅是这样的话似乎和全遍历没啥区别优化在于

1.以左括号结尾的字符串以当前位置结尾的最长有效字符串长度肯定为0(此后用’值’来表示)

2.以右括号结尾的字符串的值,假设当前位置为M位看它前一位假如说前一位的值为N 那么就看往前推N位的情况(M-N-1位)

如果M-N-1位是左括号说明有效那么当前位置的值就是N的值+2 然后再往前看一位M-N位的值把它也加上

如果M-N+1位是右括号很遗憾当前位置的值为0

public int longestValidParentheses(String s) {
            if(s==null||s.length()<2){
                return 0;
            }
      char [] chars = s.toCharArray();
        int [] arr = new int [chars.length];
        arr[0] = 0;
        int max = 0;
        for(int i = 1;i<arr.length;i++) {
            if(chars[i]=='(') {
                arr[i] = 0;//其实不用这一步 默认就是0
            }else if(chars[i]==')') {
                int t = i - arr[i-1] - 1;
                if(t>=0&&chars[t]=='(') {
                    arr[i] = arr[i-1]+2+(t>0?arr[t-1]:0);
                }
            }
            max = Math.max(max, arr[i]);
        }
        return max;
    }

力扣链接原题在这里

第三题

有一些排成一行的正方形。每个正方形已经被染成红色或者绿色。现在可以选择任意一个正方形然后用这两种颜色的任意一种进行染色，这个正方形的颜色将会被覆盖，目标是在完成染色之后，每个红色R都比每个绿色G距离最左侧近。返回最少需要涂染几个正方形。如样例所示:s= RGRGR我们涂染之后变成RRRG满足要求了涂染的个数为2,没有比这个更好的涂染方案

这里的每个红色R比绿色G距离左侧近说人话就是所有的红色都应该在绿色的左边

最暴力的解法是我们遍历每两个格子之间的分界线(包括第一个格子前和最后一个格子后)

然后把分界线前面全涂成红色分界线后面全涂成绿色复杂度是O(N²)

优化解法就是先过一遍字符串然后做一个预处理数组某位置左侧有多少个G 右侧有多少个R

然后再拿着这个结果去遍历分界线就变得简单了

具体实现的话还可以优化一下先遍历下字符串看看R总共有多少个这样从左往右结算的时候不仅能得出左侧的G有多少个又能得出右侧的R有多少个每个位置都计算要涂多少个格子然后用一个MIN抓住最小的

public static int MinMethod(String string) {
        char [] chars = string.toCharArray();
        int LeftG = 0;
        int RightR = 0;
        int RALL = 0 ;
        for (char c : chars) {
            RALL += c=='R'?1:0;
        }
        int min = RALL;//对应着把所有的R都涂了 也就是以第一位之前为分界线
        RightR = RALL;
        for (char c :chars) {
            LeftG += (c=='G'?1:0);
            RightR -= (c=='R'?1:0);
            min = Math.min(LeftG+RightR, min);
        }
        return min;
    }