[LeetCode]20.ValidParentheses-创新互联
20. Valid Parentheses
成都创新互联公司坚持“要么做到,要么别承诺”的工作理念,服务领域包括:成都做网站、网站设计、企业官网、英文网站、手机端网站、网站推广等服务,满足客户于互联网时代的松原网站设计、移动媒体设计的需求,帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴!Given a string containing just the characters '('
, ')'
, '{'
, '}'
, '['
and ']'
, determine if the input string is valid.
The brackets must close in the correct order, "()"
and "()[]{}"
are all valid but "(]"
and "([)]"
are not.
题意:
括号字符串的匹配。
栈的特性:
后进先出。
栈的头文件:
struct stack
{
char elem;
struct stack *next;
};
栈的大小:
在64位系统上:sizeof(char) = 1,sizeof(struct stack *) = 8,sizeof(struct stack) = 16;
在32位系统上:sizeof(char) = 1,sizeof(struct stack *) = 4,sizeof(struct stack) = 8;
64位系统的地址是64位的,即8字节;32位系统的地址是32的,即4字节。所以sizeof(struct stack *)分别是8字节和4字节。虽然sizeof(char)都为一字节。由于结构体存在字节对齐,所以sizeof取出的结构体大小是结构体大元素的整数倍。所以结构体大小是16字节和8字节。
push入栈,pop出栈,top获取栈顶元素。getLen函数如果栈为空,则返回一;否则返回零。
思路:
如果元素是'(','{'或'['则直接入栈;如果是元素是')',则判断栈顶,如果栈顶元素是'('则'('出栈。'}'和']'一样处理。
struct stack { char elem; struct stack *next; }; struct stack *push(struct stack *head, char c) { struct stack *node = NULL; node = (struct stack *)malloc(sizeof(struct stack)); if ( node == NULL ) { return NULL; } node->elem = c; if ( head == NULL ) { node->next = NULL; head = node; } else { node->next = head; } return node; } char top(struct stack *head) { if ( !head ) { return 0; } return head->elem; } struct stack *pop(struct stack *head) { if ( !head ) { return NULL; } char val = head->elem; struct stack *delete = head; head = head->next; free(delete); return head; } int getLen(struct stack *head) { return head == NULL ? 1 : 0; } bool isValid(char* s) { struct stack *head = NULL; while ( *s ) { if ( *s == '(' || *s == '{' || *s == '[' ) { head = push(head, *s); } if ( *s == ')' ) { if ( top(head) == '(' ) { head = pop(head); } else { head = push(head, *s); } } if ( *s == '}' ) { if ( top(head) == '{' ) { head = pop(head); } else { head = push(head, *s); } } if ( *s == ']' ) { if ( top(head) == '[' ) { head = pop(head); } else { head = push(head, *s); } } s++; } return getLen(head); }
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
本文题目:[LeetCode]20.ValidParentheses-创新互联
新闻来源:http://myzitong.com/article/cshjjh.html