精选留言(26)

• 
  Artisan

  2018-10-11

  二分之N平方是因为 replace 带来的时间复杂码？

  作者回复: 对的，replace本身的操作是 o(n) 的，所以最坏情况下会有产生 n^2 的复杂度。

  

   11
• 
  Hughie

  2019-01-14

  刷题的时候发现老师讲的使用map的实例答案并不对，elif判断应该判断stack为空或map对应，按照老师的思路用java实现了一下
  public boolean isValid(String s)
      {
         //---------------Use Map----------------------
         char[] chars=s.toCharArray();
         Stack<Character> stack=new Stack<Character>();
         Map<Character,Character> map= new HashMap<>();
         map.put(')','(');
         map.put(']','[');
         map.put('}','{');
         for(char c:chars){
             if(!map.containsKey(c)){
                stack.push(c);
             }
             else if(stack.isEmpty() || map.get(c)!=stack.pop()){
                 return false;
             }
         }
         return stack.isEmpty();
  
      }

  展开

   1

   10
• 
  他在她城断了弦

  2018-11-11

  用python解题虽然写起来简单，但是如果面试笔试的时候不让用高级语言岂不是一脸懵逼了。。

  

   5
• 
  李超

  2019-01-03

  C solution：Runtime: 0 ms, faster than 100.00% of C online submissions for Valid Parentheses.
  bool isValid(char* s) {
      
      int len = strlen(s);
      char *temp = malloc(sizeof(char)*(len+1)/2);
      int p = 0;
      
      for (int i = 0; i < len; i++) {
          
          if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
              temp[p] = s[i];
              p++;
          } else {
              if (p == 0) {
                  return false;
              } else {
                  if ((s[i] == ')' && temp[p-1] != '(') || (s[i] == ']' && temp[p-1] != '[') || (s[i] == '}' && temp[p-1] != '{')) {
                      return false;
                  } else {
                      temp[p-1] = '\0';
                      p--;
                  }
              }
          }
      }
      
      return strlen(temp) == 0;
  }

  展开

  作者回复: 赞👍🏻👍🏻

  

   2
• 
  Derek

  2018-12-11

  GO语言实现：
  
  type Stack []string
  
  func (s *Stack) Pop() string {
      ns := *s
      v := ns[len(ns)-1]
      *s = ns[:len(ns)-1]
      return v
  }
  
  func isValid(s string) bool {
      var stack Stack
      hash_map := map[string]string{
          ")":"(",
          "]":"[",
          "}":"{",
      }
      for _, b := range s {
          if _, ok := hash_map[string(b)]; !ok {
              stack = append(stack, string(b))
          } else if len(stack) == 0 || stack.Pop() != hash_map[string(b)] {
              return false
          }
      }
      return len(stack) == 0
  }

  展开

  作者回复: 👍🏻👍🏻👍🏻

  

   2
• 
  上神梵修

  2018-11-26

  如果用对称数组思想会不会更好呢：如果为奇数直接false，为偶数则从中间向两边遍历对比 。这样时间复杂度最大也只是n/2

  作者回复: ()(())

  

   2
• 
  布罗利

  2019-07-17

  根据老师思路 JavaScript实现：
  function isValid(str) {
    const stack = []
    const bracketsMap = { ')': '(', ']': '[', '}': '{' }
    for (let i = 0; i < str.length; i++) {
      const s = str[i]
      // 如果是左括号压入栈
      if (!(s in bracketsMap)) {
        stack.push(s)
      } else if (!stack.length || bracketsMap[s] !== stack.pop()) {
        return false
      }
    }
    return !stack.length
  }
  
  console.log(isValid('{}')) // true
  console.log(isValid('(){}')) // true
  console.log(isValid('({)}')) // false
  console.log(isValid('((({}))')) // false
  console.log(isValid('))')) // false
  

  展开

  

   1
• 
  Null

  2019-03-28

  swift 版本
  class Solution {
      func isValid(_ s: String) -> Bool {
          var stack:[String] = []
          var initialParentheses:[String: String] = [")":"(","]":"[","}":"{"]
          for c in s {
              if !initialParentheses.keys .contains(String(c)) {
                  stack.append(String(c));
              } else if stack.count > 0 && initialParentheses[String(c)] != stack.removeLast() {
                  return false
              }
          }
          
          if stack.count == 0 {
              return true;
          } else {
              return false
          }
      }
  }

  展开

  作者回复: 帅！ 最后一句可以简化：
  return stack.count == 0;

  

   1
• 
  小天宇风

  2019-02-16

  
  java : class Solution {
      // 自己实现版本1
      /*public boolean isValid(String s) {
  
          Stack<Character> stack = new Stack<>();
  
          for(int i = 0 ; i < s.length() ; i ++){
  
              char temp = s.charAt(i);
              if(temp == '(' || temp == '{' || temp == '['){
                  stack.push(temp);
                  continue;
              }else if(temp == ')' && (stack.isEmpty() || stack.pop() != '(')){
                  return false;
              }else if(temp == '}' && (stack.isEmpty() || stack.pop() != '{')){
                  return false;
              } else if(temp == ']' && (stack.isEmpty() || stack.pop() != '[')){
                  return false;
              }
          }
          if(!stack.isEmpty()){
              return false;
          }
          return true;
      }*/
      // 按老师讲的实现版本2
      public boolean isValid(String s) {
  
          Stack<Character> stack = new Stack<>();
          Map<Character,Character> map = new HashMap<>();
          map.put(')','(');
          map.put('}','{');
          map.put(']','[');
  
          for(char c : s.toCharArray()){
  
              if(!map.containsKey(c)){
                  stack.push(c);
              }else if( stack.isEmpty() || map.get(c) != stack.pop()){
                  return false;
              }
          }
          if(!stack.isEmpty()){
              return false;
          }
          return true;
      }
  }

  展开

  作者回复: 帅！

  

   1
• 
  unden

  2018-10-12

  第二种方法的空间复杂度是不是O(n^2)?

  作者回复: 对的，就是 O(n^2)

  

   1
• 
  熙桐么么哒

  2018-10-12

  想不到啊，如果没看过，根本想不到

  作者回复: 对的，这个题目的解法，不管算法本身上，还是写出来的程序代码，都比较给人启示。

  

   1
• 
  简单爱

  2018-10-11

  有点神奇啊

  

   1
• 
  博健-余光

  2019-10-22

  JavaScript搬
  var isValid = function(s) {
      var map = {
          ")": "(",
          "]": "[",
          "}": "{"
      } // 写一个字典，建立对应关系
      var stack = []
      for(let key of s){
          if(!map.hasOwnProperty(key)){
              stack.push(key)
          }else{
              if(stack.pop() != map[key]){
                  return false
              }
          }
      }
      return !stack.length;
  };

  展开

  作者回复: Cool!

  

  
• 
  小水滴

  2019-10-21

  是否需要判断栈中长度，如果大于一半就可以直接return false了呢？

  作者回复: 可以的。是一个不错的优化。

  

  
• 
  Geek_5541c1

  2019-10-07

  使用JS来实现该算法：
  
  var isValid = function(s) {
    var stack = [];
    // key 是右括号
    var paren_map = { ")": "(", "]": "[", "}": "{" };
    for (var c of s) {
      // 只把左括号放进stack
      if (!paren_map[c]) {
        stack.push(c);
        continue;
      }
      // 取出来与右括号进行匹配
      if (paren_map[c] != stack.pop()) {
        return false;
      }
    }
    return stack.length == 0;
  };

  展开

  

  
• 
  战五渣

  2019-05-24

  leetcode有点神奇啊，同样一份代码刷新一下页面再submit耗时会短一些，还有就是有些solution代码感觉和自己差不多，但是人家耗时就是更短，难道是我打开姿势不对嘛？

  

  
• 
  言十年

  2019-05-12

  phper写的golang版本，看了下性能不好。
  执行用时 : 16 ms, 在Valid Parentheses的Go提交中击败了12.87% 的用户
  内存消耗 : 2 MB, 在Valid Parentheses的Go提交中击败了54.31% 的用户
  
  func isValid(s string) bool {
      var stack []byte
      var sl = len(s)
      for i:=0;i<sl;i++ {
          l := len(stack)
          if l == 0 {
              stack = append(stack, s[i])
          } else {
              result := s[i] - stack[l-1]
              fmt.Println(result)
              if result>0 && result<3{
                  if len(stack) == 1 {
                      stack = []byte{}
                      continue
                  }
                  //出栈
                  stack = stack[:l-1]
              } else {
                  // 压栈
                  stack = append(stack, s[i])
              }
          }
          
      }
      return len(stack) == 0
  }

  展开

  作者回复: 帅

  

  
• 
  小天宇风

  2019-02-16

  自己实现的java版本：
  public boolean isValid(String s) {
          
          Stack<Character> stack = new Stack<>();
  
          for(int i = 0 ; i < s.length() ; i ++){
  
              char temp = s.charAt(i);
              if(temp == '(' || temp == '{' || temp == '['){
                  stack.push(temp);
                  continue;
              }else if(temp == ')' && (stack.isEmpty() || stack.pop() != '(')){
                  return false;
              }else if(temp == '}' && (stack.isEmpty() || stack.pop() != '{')){
                  return false;
              } else if(temp == ']' && (stack.isEmpty() || stack.pop() != '[')){
                  return false;
              }
          }
          if(!stack.isEmpty()){
              return false;
          }
          return true;
      }

  展开

  作者回复: 帅！！

  

  
• 
  Trevor.赤

  2019-01-12

  上一个复制错了
  type ListNode2 struct {
      Val int
      Next *ListNode2
  }
  type Stack struct {
      Head *ListNode2
      Tail *ListNode2
  }
  
  func push(stack *Stack, nodev int) {
      var node ListNode2
      node.Val = nodev
      node.Next = nil
      if stack.Tail == nil {
          stack.Head = &node
          stack.Tail = &node
          return
      }
      node.Next = stack.Head
      stack.Head = &node
  }
  
  func pop(stack *Stack) int {
      if stack.Head == nil {
          return -1
      }
      s := stack.Head.Val
      stack.Head = stack.Head.Next
      return s
  }
  
  func isValid(s string) bool {
      var stack Stack
      m := map[int]int{
          '(': ')',
          '{': '}',
          '[': ']',
      }
      for _, t := range s {
          v, ok := m[int(t)]
          if ok {
              push(&stack, int(t))
          } else {
              v, ok = m[pop(&stack)]
              if !ok {
                  return false
              } else if v == int(t) {
                  continue
              } else {
                  return false
              }
          }
      }
      if stack.Head == nil {
          return true
      } else {
          return false
      }
  }
  
  func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
      if l1.Next == nil && l1.Val == 0 {
          return l2
      }
      if l2.Next == nil && l2.Val == 0 {
          return l1
      }
      var pcur, pfront, pcur2 *ListNode
      var nfront ListNode
      nfront.Val = 0
      nfront.Next = nil
      pcur = &nfront
      pfront = pcur
      var sum int
      for l1 != nil || l2 != nil {
          x, y := 0, 0
          if l1 != nil {
              x = l1.Val
          }
          if l2 != nil {
              y = l2.Val
          }
          pcur.Val = (x + y + sum) % 10
          fmt.Print(x, y, sum, pcur.Val)
          var nnext ListNode
          pcur.Next = &nnext
          pcur2 = pcur
          pcur = &nnext
          sum = (x + y + sum) / 10
  
          //fmt.Print(pcur.Val)
          //fmt.Print(sum)
          if l1 != nil {
              l1 = l1.Next
          }
          if l2 != nil {
              l2 = l2.Next
          }
      }
      if sum == 1 {
          pcur.Val = 1
      }
      //fmt.Print(pcur.Val)
      if pcur.Val == 0 {
          pcur2.Next = nil
      }
      return pfront
  }
  
  //是否有环
  func hasCycle(head *ListNode) bool {
      var slow, fast *ListNode
      slow = head
      fast = head
      for fast != nil && fast.Next != nil {
          slow = slow.Next
          fast = fast.Next.Next
          if fast == slow {
              return true
          }
      }
      return false
  }

  展开

  

  
• 
  Trevor.赤

  2019-01-12

  type ListNode2 struct {
      Val int
      Next *ListNode2
  }
  type Stack struct {
      Head *ListNode2
      Tail *ListNode2
  }
  
  func push(stack *Stack, nodev int) {
      var node ListNode2
      node.Val = nodev
      node.Next = nil
      if stack.Tail == nil {
          stack.Head = &node
          stack.Tail = &node
          return
      }
      node.Next = stack.Head
      stack.Head = &node
  }
  
  func pop(stack *Stack) int {
      if stack.Head == nil {
          return -1
      }
      s := stack.Head.Val
      stack.Head = stack.Head.Next
      return s
  }
  
  func isValid(s string) bool {
      var stack Stack
      var m map[int]int
      m = make(map[int]int) {'(':')','{':'}','[':']'}
      for _, t := range s {
          v, ok := m[int(t)]
          if ok {
              push(&stack, int(t))
          } else {
              v, ok = m[pop(&stack)]
              if !ok {
                  return false
              } else if v == int(t) {
                  continue
              } else {
                  return false
              }
          }
      }
      if stack.Head == nil {
          return true
      } else {
          return false
      }
  }

  展开

  

  