50010702506256
分类:
.NET
看到一家公司的面试题，是计算一字符串中括号嵌套的层数。开始想简单了以为就是拿到括号出现的次数计算一下就行了，没有考虑到嵌套的各种情况
比如：
A{b}C 结果是0
{A{b}C} 结果是1
A{B{CD}f 结果0层只有一对有效，可以理解中间的括号只有一个
{{a}b{c}e{f}g} 结果是1(因为虽然有4对括号，其中三对都是在一起的)
{{a}b{m{jk{jh}s}e}g} 结果是3(虽然有5对括号，但是其中有2对是一级的)
开始的思路：连续出现的括号才算，否者就不算一个层级
这种思路不是太灵活，不是太清晰，也不是太好写算法。
改进一点的思路：找到左括号出现的位置，找到右括号出现的位置.出现一个左括号就+1，左括号中间出现右括号就减去1（这种算法有问题跳过看后面的）
也就说在两个左括号中间出现几次右括号就减几次
参考带如下：
public static int CalDeep(string str)
{
//深度
int deep = 0;
//左括号的位置记录
List<int> leftpoi = new List<int>();
//右括号的位置记录
List<int> rightpoi = new List<int>();
char[] chararray = str.ToArray();
//依次查找字符找到所有{的位置和}的位置
for (int i = 0; i < chararray.Length; i++)
{
char item = chararray[i];
if (item == '{')
{
leftpoi.Add(i);
}
if (item == '}')
{
rightpoi.Add(i);
}
}
if (leftpoi.Count == 0)
return 0;
//上一次左括号出现的坐标
int lastpoi = leftpoi[0];
foreach (int now in leftpoi)
{
//有几个左边的括号就+1
deep++;
//两个左括号中间有几个就减去几个
for (int i = lastpoi + 1; i < now; i++)
{
bool isfind = rightpoi.Exists(a => a == i);
if (isfind)
deep--;
}
lastpoi = now;
}
//处理括号不成对出现的情况
int slength = leftpoi.Count - rightpoi.Count;
if (deep > 0 && slength > 0)
{
deep = deep - slength;
}
//最外层不算
if (deep > 0)
deep = deep - 1;
return deep;
}树形的解法思路：用左右括号来构建一个树形结构，然后在计算数的深度即可（可以跳过没有写具体的算法）
出现左括号就放左子节点，出现右括号就右子节点
但是要注意，如果上一次是出现的左节点父节点还是上一次的，如果上一次出现的是右节点就往下移动一级
比如：{A{b}C} 树形大概的样子
{{a}b{c}eg}树形大概的样子
堆解题法：直接加减法：出现左括号就+1，又括号就-1，然后计算出现过的最大值-1就行了
这样的思路，清晰易懂，算法简单
思维分析：我们来分析几种情况
参考代码(不考虑括号不成对的情况)：
/// <summary>
/// 计算深度(不考虑括号不成对的情况)
/// </summary>
/// <param name="str"></param>
public static int CalDeep(string str)
{
if (string.IsNullOrEmpty(str))
return 0;
int deep = 0;
List<int> alldeep = new List<int>();
char[] chararray = str.ToArray();
foreach (char item in chararray)
{
//找到{就+1
if (item == '{')
deep++;
//找到}就减1
if (item == '}')
deep--;
//记录出现过的深度
alldeep.Add(deep);
}
//求最大值
alldeep.Sort();
int maxdeep = alldeep[alldeep.Count - 1];
if (maxdeep > 0)
maxdeep--;
return maxdeep;
}考虑到括号不成对的情况：
括号不成对其实也比较简单，直接最大值-括号出现的差值就ok了
/// <summary>
/// 计算深度(考虑到括号不成对的情况)
/// </summary>
/// <param name="str"></param>
/// <returns></returns>
public static int CalDeepNB(string str)
{
if (string.IsNullOrEmpty(str))
return 0;
int deep = 0;
List<int> alldeep = new List<int>();
char[] chararray = str.ToArray();
//左边的次数
int leftcount = 0;
//右边的次数
int rigtcount = 0;
foreach (char item in chararray)
{
//找到{就+1
if (item == '{')
{
deep++;
leftcount++;
}
//找到}就减1
if (item == '}')
{
deep--;
rigtcount++;
}
//记录出现过的深度
alldeep.Add(deep);
}
//求最大值
alldeep.Sort();
int maxdeep = alldeep[alldeep.Count - 1];
//如果左边比右边多，说明括号不完整,最大值减去差值
if (leftcount > rigtcount)
maxdeep = maxdeep - (leftcount - rigtcount);
if (maxdeep > 0)
maxdeep--;
return maxdeep;
}参考结果：
还有一种情况就是先出现右括号：比如｝｛｛a｝｛b｝｝ 右括号出现在最开始会影响最大值，直接干掉就好。
2021-6-8更新：
}{}{}{}{是几层的理解：可以理解成一层因为3对括号都没有嵌套，也可以理解成2层，第一个左括号和最后一个右括号匹配，但是我认为应该按照第一种理解，因为出现一对就应该匹配了，不然出现右括号就没意义了，相当于完全忽略右括号了，所以应该匹配到一对就算一对。
{{}}{ 这种最后出现左括号的可以不管，推理是（1，2，1，0，1）不影响我们取最大值2。不对如果左括号非常多{{{{{{}{这种就会有问题也要单独处理这种（1，2，3，4，5，6，5，6）最大值是6了但是其实只有一对括号所以要处理左右括号不对称的情况也要括号最后出现左括号的情况应该我们统计次数的时候会增加
{{}}}这种最后出现右括号的我们也可以不用管，推理是（1，2，1，0，-1），复数也不影响我们取最大值。
其实不用纠结最开始出现的左括号和结束时候出现的右括号，在最开始直接去掉即可。
但是{abcd}}{{}}这种如果在中间在出现这种多一个左括号就有问题，推理是（1，0，-1，0，1，0，-1），最大值就是1了，但是其实有2层括号的，问题就是出在那个-1上面多减去了一次。其实这里就跟我们最开始讨论的}{{}}这种情况一样，最开始出现的左括号应该去掉，因为没有任何一个和他匹配不用减去，所以出现负数我们认为这个左括号匹配不到右括号所以就不用减当0处理就好！nice
最后在贴一下代码吧：
/// <summary>
/// 计算深度(考虑到括号不成对的情况)
/// </summary>
/// <param name="str"></param>
/// <returns></returns>
public static int CalDeepNB(string str)
{
if (string.IsNullOrEmpty(str))
return 0;
//直接去掉最左边的左括号和最右边的右括号
str = str.TrimStart('}');
str = str.TrimEnd('{');
int deep = 0;
List<int> alldeep = new List<int>();
char[] chararray = str.ToArray();
//左边的次数
int leftcount = 0;
//右边的次数
int rigtcount = 0;
foreach (char item in chararray)
{
//找到{就+1
if (item == '{')
{
deep++;
leftcount++;
}
//找到}就减1
if (item == '}')
{
deep--;
rigtcount++;
if (deep < 0)
{
deep = 0;
rigtcount--;//无效括号不算个数
}
}
//记录出现过的深度
alldeep.Add(deep);
}
//求最大值
alldeep.Sort();
int maxdeep = alldeep[alldeep.Count - 1];
//如果左边比右边多，说明括号不完整,最大值减去差值
if (leftcount > rigtcount)
maxdeep = maxdeep - (leftcount - rigtcount);
if (maxdeep > 0)
maxdeep--;
return maxdeep;
}
static void Main(string[] args)
{
//Console.WriteLine(DateTime.Now);
//string str = "A{b}C";
//string str = "{A{b}C}";
//string str = "A{B{CD}}f}";//测试左边比右边多
//string str = "A{B{CD}}f}";//测试右边比左边多
//string str = "{{a}b{c}e{f}g}";
//string str = "{{a}b{m{jk{jh}s}e}g}";
//string str = "{a}}}}{c";//极端情况测试
//string str = "{{{a}}}}}}}{}c";//极端情况测试
//string str = "{asad{a}a{{{{sad}}}}a}s{{a}}}}}{A{}{AA}}}a}A";
//string str = "}{}{}{}{";
//string str = "{abcd}}{{}}";
string str = "{{{{{{}}{{{{";
//Console.WriteLine(Math.Abs(-1));
//int deep = CalDeep(str);
//Console.WriteLine(CalDeep2(str));
//Console.WriteLine(deep);
Console.WriteLine(CalDeepNB(str));
Console.ReadLine();
}over 吃饭去
直接找成对括号的解题方法
找到一个左括号就记录左括号，然后出现一层右括号就层级+1，然后在把这个左括号干掉
static void Main(string[] args)
{
//string dd1 = "{{{}}";
string dd = "}}{{{}}{{{";
int numbedr = 0; //计算陈数 }}}
int max = 0; //最大层数 {{{{
List<string> val = new List<string>();
foreach (var item in dd)
{
if (item=='{')
{
numbedr = 0;
val.Add(item.ToString());
}
//上一次出现左括号，这次出现右括号就加一层，并且把上次的左括号去掉。因为要成对出现必须要先出去左括号在出现右括号
if (item=='}'&&val.Count>0)
{
numbedr++;
val.Remove(val[val.Count-1]);
}
if (max<numbedr)
{
max = numbedr;
}
}
Console.WriteLine(max);
Console.ReadLine();
}欢迎加群讨论技术，群：677373950(满了，可以加，但通过不了)，2群：656732739