文章目录

1.检查二进制字符串字段

2.使括号有效的最少添加

3.子域名访问计数

4.三等分

5.最大升序子数组和

6.青蛙跳台阶问题

7.股票的最大利润

8.括号的分数

关键字

动态规划、计数模拟栈、哈希表、双端队列ArrayDeque、括号匹配问题

1.检查二进制字符串字段

难度： ★ 链接：力扣

解题思路：

本题类似于观察找规律的题，列出所有可能情况找到题目所要表达的“言外之意”，符合题意的二进制字符串有如下两种情况：

不含连续的1组成，即：000000……

只含有一段由连续的1组成的字段，即：11111……00000……

通过观察可以发现符合题意的二进制字符串中都不含有“01”子串，因为含有01子串的二进制字符串都不符合题意，所以问题则转化为检查二进制字符串中是否含有“01”子串，含有则不合题意返回false,否则符合题意返回true，发现规律后本题即可迎刃而解！

解题代码：

class Solution {
    public boolean checkOnesSegment(String s) {
       return !s.contains("01");
    }
}

你没有看错，就一行简洁的代码AC！

2.使括号有效的最少添加

难度：★★ 链接：力扣

本质上就是一个括号匹配的问题，可以使用栈数据结构来解决，或者用计数来模拟栈

思路一：双端队列ArrayDeque实现栈

遍历字符串，如果是”)”，则检查当前栈是否为空并且栈顶元素是否是”(“，如果是则匹配成功，将处于栈顶的”(“出栈，如果匹配失败则将当前字符入栈，表示待匹配。当循环结束，栈中剩余元素即为需要待匹配的括号数，也是使得整个字符串s变有效而所需最少的添加括号数

代码：

class Solution {
    public int minAddToMakeValid(String s) {
        Deque<Character>arr=new ArrayDeque<>();
        for(char ch:s.toCharArray()){
            if(ch==')'&&!arr.isEmpty()&&arr.peek()=='('){
                arr.pop();//将与当前右括号匹配的栈顶元素左括号出栈
            }else{
                //如果不符合上述条件将当前字符入栈
                arr.push(ch);
            }
        }
        return arr.size();
    }
}

ArrayDeque()方法总结（Java语言）

思路二：计数模拟栈

统计左括号的个数，遇到右括号则判断左括号数是否大于0，是则将当前的右括号与离其最近的左括号进行匹配，左括号个数减一；如果无法匹配说明当前的右括号前面没有左括号与之进行匹配，需要进行额外添加才能使之有效，将这种情况进行计数存在res中，最后判断左括号的数目是否大于0，大于0则说明没有相应的右括号与之匹配，将这种情况也加入到res中

代码：

class Solution {
    public int minAddToMakeValid(String s) {
        //统计左括号的个数，依次将离它最近的右括号与其进行匹配
        int n=s.length();
        int leftsum=0,res=0;
        for(int i=0;i<n;i++){
            if(s.charAt(i)=='('){
                leftsum++;
            }else{
                if(leftsum>0){
                    leftsum--;
                }else{
                    res++;
                }
            }
        }
        return leftsum>0?res+leftsum:res;
    }
}

3.子域名访问计数

难度：★★ 链接：力扣

解题思路：

本题题意不难理解，就是计数。可以考虑使用哈希表法，以子域名为“键”，以其被访问的次数为“值”，从而构成键值对的形式，最后遍历哈希表统计每个“键”，即子域名在哈希表中出现的总个数，最后将访问次数与子域名拼接成字符串添加至ArrayList中返回。使用哈希表法前提是熟练使用哈希表相关的一些常用方法，本题用到了以下方法：

s.indexOf(Character ch) 返回字符ch在字符串s中第一次出现的位置的下标号

s.length() 返回字符串s的长度

s.substring(a,b)字符串的截取，注意左闭右开，即只截取字符串s中区间为[a,b)的子串

map.getOrDefault(Key1,value1) 遍历哈希表查询是否存在“键”为Key1的元素，若存在则返回其value值，否则返回指定的默认值value1

s.indexOf(Character ch,int a) 在字符串s中，从下标为a的地方开始查询字符ch第一次出现的位置的下标号

Map.Entry<String, String>的意思是一个泛型，表示Entry里装的是两个string的字符串，分别是allrecordmap的key和value。

Map.Entry是Map的一个内部接口。Map.entrySet（）是将map里的每一个键值对取出来封装成一个Entry对象在存到一个Set里面。Map提供了一些常用方法，如keySet()、entrySet()等方法

解题代码：

class Solution {
    public List<String> subdomainVisits(String[] cpdomains) {
        //哈希表的应用,以子域名字符串为键值
        List<String>res=new ArrayList<String>();
        Map<String,Integer>map=new HashMap<String,Integer>();
        for(String cp:cpdomains){
            //先找到空格的位置
            int space=cp.indexOf(" ");
            int len=cp.length();
            //获取网站域名的访问次数
            int rep=Integer.parseInt(cp.substring(0,space));
            //使用哈希表的getOrDefault方法来遍历哈希表中是否存在当前键值的元素，存在则返回其value与当前rep相加，否则默认为0
            String key1=cp.substring(space+1,len);
            int value1=map.getOrDefault(key1,0)+rep;
            //存入哈希集合
            map.put(key1,value1);
            //找到空格后的第一个点，从而找到了二级域名,若未找到则返回-1
            int spot=cp.indexOf(".",space+1);
            while(spot!=-1){
                String key2=cp.substring(spot+1,len);
                int value2=map.getOrDefault(key2,0)+rep;
                map.put(key2,value2);
                //寻找下一个点的位置，从而找到更高级别的域名
                spot=cp.indexOf(".",spot+1);
            }
        }
         for(Map.Entry<String,Integer> entry:map.entrySet()){
                String result=entry.getValue()+" "+entry.getKey();
                res.add(result);
            }
         return res;
    }
}

4.三等分

难度：★★★ 链接：力扣

解题思路：

本题思路不难，就是三等分后判断每一段的二进制值是否相等。但是这个等分的操作很有讲究，首先由于数组中只含有0和1，要想统计其中1的个数，只需要将其求和即可，代码中调用了Arrays的方法，Arrays.stream().sum()来快速地计算数组的和。

因为是三等分，每一块二进制数中1的个数应该是相等的，所以我们先判断1的个数是否是3的倍数，如果不是显然不合题意。如果为0即数字中全是0组成，则返回[0,2]或者[0,3]等等都行，因为所有的0只要三等分最终的二进制值还是0都是相等的；

下面确定所有1中以sum/3为一块的第一个1在整个数组中的下标

然后确定每一块二进制的长度len，因末尾固定，所以用数组长度减去第三个1出现的位置即可

最后分别比较以三个1为开始，以len为长度的二进制子串是否相等即可

解题代码：

class Solution {
    public int[] threeEqualParts(int[] arr) {
        //因为数组中只有0和1,所以用该方法对其求和，求得的和即为数组中1的个数
        int sum = Arrays.stream(arr).sum();
        if (sum % 3 != 0) {
            return new int[]{-1, -1};
        }
        if (sum == 0) {
            return new int[]{0, 2};
        }

        int partial = sum / 3;
        int first = 0, second = 0, third = 0, cur = 0;
        //分别寻找1的序列中区间长度为partial的三段的第一个1出现的位置
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 1) {
                if (cur == 0) {
                    first = i;
                } else if (cur == partial) {
                    second = i;
                } else if (cur == 2 * partial) {
                    third = i;
                }
                cur++;
            }
        }
        //计算每一段二进制数的长度为len
        int len = arr.length - third;
        if (first + len <= second && second + len <= third) {
            int i = 0;
            while (third + i < arr.length) {
                //对应位置上的值不相等则最终的值也不会相等直接返回错误信息
                if (arr[first + i] != arr[second + i] || arr[first + i] != arr[third + i]) {
                    return new int[]{-1, -1};
                }
                i++;
            }
            return new int[]{first + len - 1, second + len};
        }
        return new int[]{-1, -1};
    }
}

5.最大升序子数组和

难度： ★ 链接：力扣

解题思路：

简单模拟过程即可，遇到升序则累加，否则从当前位置开始寻找下一个升序序列，记录每一段升序序列的和，更新最大值

解题代码:

class Solution {
    public int maxAscendingSum(int[] nums) {
        //简单模拟
        int n=nums.length;
        int maxsum=nums[0],current=nums[0];
        for(int i=1;i<n;i++){
            if(nums[i]>nums[i-1]){
                //符合升序特征则累加
                current+=nums[i];
            }else{
                //不符合则从当前元素开始寻找升序序列
                current=nums[i];
            }
            //记录并更新最大升序序列的和
            maxsum=Math.max(maxsum,current);
        }
        return maxsum;
    }
}

6.青蛙跳台阶问题

难度： ★ 链接：力扣

解题思路:

动态规划法，找到状态之间的联系。因为青蛙跳上第n级台阶的最后一步只有两种情况：跳1级或者跳2级到达第n级台阶，所以状态转移方程为：f(n)=f(n-1)+f(n-2) , f(n)表示跳到当前n级台阶总共的方法数，其等于前面跳上n-1级台阶与跳上n-2级台阶的方法数之和。另外注意动态规划的边界条件，如本题当n为0或者1时，显然只有一种方法，则直接返回。注意要将每次结果对1e9+7的取余

解题代码：

class Solution {
    public int numWays(int n) {
        int dp[]=new int[n+1];
        if(n==0||n==1){
            return 1;
        }
        if(n==2){
            return 2;
        }
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++){
            dp[i]=(dp[i-1]+dp[i-2])%1000000007;
        }
        return dp[n];
    }
}

7.股票的最大利润

难度：★★ 链接：力扣

思路一:

蛮力法进行简单的模拟

代码：

class Solution {
    public int maxProfit(int[] prices) {
        //暴力法
        int max=0;
        int n=prices.length;
        for(int i=0;i<n-1;i++){
            int sum=0;
            for(int j=i+1;j<n;j++){
                if(prices[j]>prices[i]){
                    sum=Math.max(sum,prices[j]-prices[i]);
                }
            }
            max=sum>max?sum:max;
        }
        return max;
    }
}

思路二：动态规划法

动态规划数组dp[],d[i]表示的是前i天内获得的最大利润，其值有两种情况：前i-1天获得的最大值较大或者当天即第i天的时候卖出得到的利润prices[i]-cost较大，cost为买入股票时候的股价即成本，所以可以得到状态转移方程为：dp[i]=max(dp[i-1],prices[i]-cost) 注意边界条件：当数组内只有一个元素时，只能买入无法卖出显然不合题意，直接返回0

代码：

class Solution {
    public int maxProfit(int[] prices) {
        //动态规划法:定义dp[i]表示前i天能获得的最大利润
        int n=prices.length;
        int dp[]=new int[n];
        if(n<2) return 0;
        int cost=prices[0];//初始化成本，假设第1天准备卖出
        for(int i=1;i<n;i++){
            dp[i]=Math.max(dp[i-1],prices[i]-cost);
            //更新成本，取价格较低的股价买入作为成本，准备下一次的抛售
            cost=Math.min(prices[i],cost);
        }
        return  dp[n-1];
    }
}

8.括号的分数

难度：★★ 链接：力扣

思路一：栈

我们可以将平衡字符串看做是一个空的字符串加上本身，定义空字符串的分数为0，并且定义一个栈res来记录平衡字符串的分数，在开始之前将空字符串的分数0进栈，在遍历字符串过程中：

遇到左括号，那么我们需要计算该左括号内部的子平衡括号字符串A的分数，我们也要先压入分数 0，表示 A 前面的空字符串的分数

遇到右括号，说明该右括号内部的子平衡括号字符串 A的分数已经计算出来了，我们将它弹出栈，并保存到变量 v中。如果 v=0, 那么说明子平衡括号字符串 A 是空串，(A) 的分数为 1，否则 (A) 的分数为 2*V，然后将 (A) 的分数加到栈顶元素上

代码：

class Solution {
    public int scoreOfParentheses(String s) {
        //双端队列实现栈
        Deque<Integer>res=new ArrayDeque<>();
        res.push(0);
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('){
                res.push(0);
            }else{
                int v=res.pop();
                int top=res.pop()+Math.max(2*v,1);
                res.push(top);
            }
        }
        return res.peek();//返回栈顶元素即为括号的最终的分数
    }
}

思路二：根据深度计算分数和

根据题意，s 的分数与 1 分的 () 有关。对于每个 ()，它的最终分数与它所处的深度有关，如果深度为 bal，那么它的最终分数为 2^bal。我们统计所有 () 的最终分数和即可。

代码：

class Solution {
    public int scoreOfParentheses(String s) {
        //根据深度计算最终的括号分数
        int n=s.length();
        int res=0,depth=0;
        for(int i=0;i<n;i++){
              //计算深度
              depth+=s.charAt(i)=='('?1:-1;
              if(s.charAt(i)==')'&&s.charAt(i-1)=='('){
                  res+=Math.pow(2,depth);
              }
        }
        return res;
    }
}