20. Valid Parentheses / 71. Simplify Path

2019-11-10 18:32:55

字體：大中小

來源：轉載

供稿：網友

Valid Parentheses題目描述代碼實現Simplify Path題目描述代碼實現

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.

代碼實現

class Solution {public: bool isValid(string s) { int s_len = s.size(); stack<char> tmp; for(int i = 0; i < s_len; i++) { if(s[i] == '(' || s[i] == '{' || s[i] == '[') { tmp.push(s[i]); } else { if(tmp.empty()) return false; char t = tmp.top(); tmp.pop(); if(s[i] == ')' && t != '(') return false; if(s[i] == ']' && t != '[') return false; if(s[i] == '}' && t != '{') return false; } } return tmp.empty()?true:false; }};class Solution {public: bool isValid(string s) { stack<char> paren; for (char& c : s) { switch (c) { case '(': case '{': case '[': paren.push(c); break; case ')': if (paren.empty() || paren.top()!='(') return false; else paren.pop(); break; case '}': if (paren.empty() || paren.top()!='{') return false; else paren.pop(); break; case ']': if (paren.empty() || paren.top()!='[') return false; else paren.pop(); break; default: ; // pass } } return paren.empty() ; }};

71. Simplify Path

題目描述

Given an absolute path for a file (Unix-style), simplify it.For example,path = "/home/", => "/home"path = "/a/./b/../../c/", => "/c"click to show corner cases.Corner Cases:Did you consider the case where path = "/../"?In this case, you should return "/".Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".In this case, you should ignore redundant slashes and return "/home/foo".

代碼實現

class Solution {public: string simplifyPath(string path) { string res, tmp; vector<string> stk; stringstream ss(path); while(getline(ss,tmp,'/')) { if (tmp == "" || tmp == ".") continue; if (tmp == ".." && !stk.empty()) stk.pop_back(); else if (tmp != "..") stk.push_back(tmp); cout << tmp << endl; } for(auto str : stk) res += "/"+str; return res.empty() ? "/" : res; }};class Solution {public: string simplifyPath(string path) { string result="", token; stringstream ss(path); vector<string> tokens; while(getline(ss, token, '/')){ if(token=="." || token=="") continue; else if(token==".."){ if(tokens.size()) tokens.pop_back(); } else tokens.push_back(token); } if(!tokens.size()) return "/"; for(int i=0; i<tokens.size(); ++i) result += '/' + tokens[i]; return result; }};

在這里需要注意的是我們使用了stringstream和getline的用法來切割字符串。

上一篇：Django+Ajax+jQuery實現網頁動態更新

下一篇：數組排序問題（數字字符串排序）