文章目录
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();
}
}思路二：计数模拟栈
统计左括号的个数，遇到右括号则判断左括号数是否大于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;
}
}
在迈向算法高级菜鸟的道路上不断跋涉！