剑轩

找到字符串中括号的嵌套层数

发表于:2019/8/16 11:36


看到一家公司的面试题,是计算一字符串中括号嵌套的层数。开始想简单了以为就是拿到括号出现的次数计算一下就行了,没有考虑到嵌套的各种情况

比如:

  A{b}C                      结果是0

  {A{b}C}                    结果是1

 {{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}} 

右括号出现在最开始会影响最大值,直接干掉就好

over 吃饭去




关于TNBLOG
TNBLOG,技术分享
App store Android
精彩评论
{{item.replyName}}
{{item.content}}
{{item.time}}
{{subpj.replyName}}
@{{subpj.beReplyName}}{{subpj.content}}
{{subpj.time}}
猜你喜欢