首页 > 试题广场 >

获取n维数组的最大深度

[编程题]获取n维数组的最大深度
  • 热度指数:4069 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
输入参数为字符串型的n维数组,数组的每一项值为数组 或 int型数字。请实现一个函数,可以获取列表嵌套列表的最大深度为多少。

输入描述:
输入参数为字符串型的 n维数组,列表的每一项值为数组 或 int型数字。数组内的数组,每一项值,也可以是数组 或 int型数字。


输出描述:
int型数字,表示数组嵌套的深度。
示例1

输入

[[1], [2,3,4], [5,[2,3]], [7], [0,[1,2,3,4],3,5], [1,3], [3,2,4]]

输出

3

说明

n维数组的深度为3
有括号的题目第一时间想到栈
s = raw_input()
count = []
m = 0
for i in s:
    if i == "[":
        count.append(i)
        if len(count)>m:
            m = len(count)

    elif i == "]":
        count.pop()
print m

发表于 2019-07-24 10:24:28 回复(0)
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

const int MAX_N = 1 << 16; // 65536

int main(const int argc, const char* const argv[]) {
  char input[MAX_N] = "";
  gets(input);
  
  char stk[20];
  int top = -1, ans = 0;
  
  const char* p = input;
  while (*p) {
    switch (*p) {
      case '[':
        *(stk + ++top) = '[';
        ans = fmax(ans, top + 1);
        break;
      case ']':
        --top;
        break;
      default:
        break;
    }
    ++p;
  }
  
  assert(top == -1);
  return fprintf(stdout, "%d", ans),  0;
}

发表于 2021-07-19 12:08:38 回复(0)
O(n)复杂度直接遍历一遍字符串即可,遇到左括号就深度+1,遇到右括号就先更新最大深度,并平衡掉一个左括号(即最近一次深度的自增1由于一对完整括号的出现而取消,需要重新在那个基础上再计算深度)。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] str = br.readLine().trim().toCharArray();
        int maxDepth = 0;
        int depth = 0;
        for(int i = 0; i < str.length; i++){
            if(str[i] == '['){
                // 遇到左括号就将深度+1
                depth ++;
            }else if(str[i] == ']'){
                // 遇到右括号先更新一下当前最大的深度,再平衡掉一个左括号重新计算当前的depth
                maxDepth = Math.max(maxDepth, depth);
                depth --;
            }
        }
        System.out.println(maxDepth);
    }
}


发表于 2021-02-27 15:06:09 回复(0)
Java解法
import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        Stack<Character> stack = new Stack<>();
        int maxSize=0;
        for (int i = 0,len =s.length(); i < len ; i++) {
            if (s.charAt(i)=='['){
                stack.push('[');
                maxSize=Math.max(maxSize,stack.size());
            }else if (s.charAt(i)==']')
                stack.pop();
        }
        System.out.println(maxSize);
    }
}


发表于 2020-03-01 16:32:31 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main(){
    string s;
    getline(cin, s);
    int n = s.length(), cnt=0, Max=0;
    for(int i=0;i<n;i++){
        if(s[i]=='[')
            cnt++;
        else if(s[i]==']')
            cnt--;
        Max = max(Max, cnt);
    }
    cout<<Max<<endl;
    return 0;
}

编辑于 2019-07-18 09:03:40 回复(2)
"""
括号配对
"""

if __name__ == "__main__":
    s = input()
    ans, tmp = 0, 0
    for c in s:
        if c == '[':
            tmp += 1
            ans = max(ans, tmp)
        elif c == ']':
            tmp -= 1
    print(ans)

发表于 2019-07-16 11:47:48 回复(0)
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        int count = 0, max = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '[') {
                count++;
                max = (max > count) ? max : count;
            } else if (s.charAt(i) == ']')
                count--;
        }
        System.out.println(max);
    }
}
编辑于 2019-07-15 17:01:56 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    getline(cin,s);
    int res=0,n=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='[')
        {
            n++;
            res=max(res,n);
        }
        else if(s[i]==']')
            n--;
    }
    cout<<res<<endl;
    return 0;
}

编辑于 2019-07-05 20:52:19 回复(0)
Java解答:
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        String s = input.nextLine();
        int depth = 0;
        int max = 0;
        for (int i = 0;i<s.length();i++){
            if (s.charAt(i) == '['){
                depth++;
            }else if (s.charAt(i) == ']'){
                depth--;
            }
            if (depth > max)
                max = depth;
        }
        System.out.println(max);
    }
}


发表于 2019-08-06 15:39:19 回复(0)
#include<bits/stdc++.h>
using namespace std;

char ch;
int main() {
    int left = 0;
    int ans = 0;
	while (cin >> ch) {
        if (ch == '[') {
            ++left;
            ans = max(ans, left);
        } else if (ch == ']') {
            --left;
        }	
	}
    cout << ans << endl;
	return 0;
}

发表于 2019-10-20 22:13:40 回复(0)
package main

import (
    "fmt"
    "os"
    "bufio"
)

var in=bufio.NewReader(os.Stdin)

func main() {
    s,_:=in.ReadString('\n')
    stk:=[]byte{}
    max:=0
    for _,ch:=range []byte(s){
        if ch=='['||ch==']'{
            if len(stk)>0&&stk[len(stk)-1]=='['&&ch==']'{
                stk=stk[:len(stk)-1]
            }else{
                stk=append(stk,ch)
            }
        }
        if len(stk)>max{
            max=len(stk)
        }
    }
    fmt.Print(max)
}

发表于 2023-03-20 22:03:26 回复(0)
改造
发表于 2022-06-24 04:01:02 回复(0)
#include <iostream>
#include <string>

int getMax(std::string exp)
{
	int result = 0, temp = 0;
	for (char x : exp)
	{
		if (x == '[')
		{
			temp++;
			if (temp > result)
			{
				result = temp;
			}
		}
		else if (x == ']')
		{
			temp--;
		}
	}
	return result;
}

int main()
{
	std::string exp;
	std::getline(std::cin, exp);
	std::cout << getMax(exp) << std::endl;
	return 0;
}

发表于 2020-07-25 14:13:30 回复(0)

s = input()
maxdp = 0
temp = 0
for i in range(len(s)):
    if s[i] == '[':
        temp += 1
        maxdp = max(maxdp,temp)
    elif s[i] == ']':
        temp -= 1
print(maxdp)

编辑于 2020-07-15 15:57:53 回复(0)
#include<iostream>
(720)#include<string>
#include<stack>
(850)#include<algorithm>

using namespace std;
const int MaxLen = 100000;
int main(void){
    string s;
    string temp;
    stack<char> st;
    int ans = 0;
    char str[MaxLen];
    while (scanf("%s", str) == 1){
        string s1(str);
        temp += s1;
    }
    for (int i = 0; i < temp.size(); i++){
        if (temp[i] == '[')
            st.push('[');
        else if(temp[i] == ']'){
            ans = max(ans, int(st.size()));
            st.pop();
        }
    }
    cout<<ans<<endl;
    return 0;
}

发表于 2020-05-09 20:38:08 回复(0)
依次遍历,遇见' [ '进栈遇见' ] '出栈,遍历中栈长度的最大值即为深度
def find(s):
    q=[]
    res=0
    for i in s:
        if i=='[':
            q.append(i)
        elif i==']':
            q.pop()
        res=max(res,len(q))
    print(res)
find(input())


发表于 2020-05-05 11:59:24 回复(0)
一种笨办法,但是我觉得可行?
var arr=eval(readline())
// 提示 请检查是否存在语法错误或者数组越界非法访问等情况
// 通过率只有86%,什么原因??
function  mynum(arr){
    // 数组
    if(Object.prototype.toString.call(arr)=='[object Array]'){
        if(arr.length==0){
            return 1
        }else{
            let myarr=[]
            arr.forEach((item)=>{
                if(Object.prototype.toString.call(item)=='[object Array]'){
                    myarr.push(mynum(item))
                }else{
                    myarr.push(0)
                }
            })
            return 1+Math.max.apply(null,myarr)
        }
    }else{
        // 不是数组的时候返回 0
        return 0
    }
}
console.log(mynum(arr))

发表于 2020-04-07 17:53:31 回复(0)
#include <iostream>
#include <string>
using namespace std;
int arrayMaxDepth(string s)
{
    int i = 0;
	int maxDepth = 0;
	int temp = 0;
	while (s[i] != '\0'){
		if (s[i] == '['){	
			temp++;
			i++;
		}
		else if (s[i] == ']') {
			temp--;
			i++;
		}
		else {
			i++;
		}
		if (temp > maxDepth){
			maxDepth = temp;
		}
	}
    
    return maxDepth;
}

int main()
{
	string s;
	getline(cin,s);
        cout << arrayMaxDepth(s);
	return 0;
}

编辑于 2020-03-07 22:29:57 回复(0)
import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String str = bf.readLine();
        int count = 0;
        int max = 0;
        for(int i =0;i < str.length();i++){
            if(str.charAt(i) == '['){
                count++;
                if(count > max){
                    max = count;
                }
            }
            if(str.charAt(i) == ']'){
                count--;
            }
        }
        System.out.println(max);
    }
}
leetcode上面的一道题很类似,拿走不谢:https://leetcode-cn.com/problems/remove-outermost-parentheses/
发表于 2020-03-04 19:42:50 回复(0)
import java.util.Stack;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String arrStr = input.nextLine();
        int length = 0;
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < arrStr.length(); i++) {
            char ch = arrStr.charAt(i);
            if (ch == '[') {
                stack.push(ch);
                if (stack.size() > length) {
                    length = stack.size();
                }
            } else if (ch == ']') {
                stack.pop();
            }
        }
        System.out.println(length);
    }
}

发表于 2019-12-13 09:16:58 回复(1)