数据结构 2016-7-15

[zhaokuohaha]

1. POJ1182
2. LeetCode 20

--> 好像有点简单了

[wolfogre]

LeetCode 20

#include <stack>

class Solution {
public:
    bool isValid(string s) {
        std::stack<char> test;
        for(auto ch : s){
            switch(ch){
                case ')':{
                    if(test.empty() || test.top() != '(')
                        return false;
                    test.pop();
                    break;
                }
                case ']':{
                    if(test.empty() || test.top() != '[')
                        return false;
                    test.pop();
                    break;
                }
                case '}':{
                    if(test.empty() || test.top() != '{')
                        return false;
                    test.pop();
                    break;
                }
                default:{
                    test.push(ch);
                }

            }
        }
        if(!test.empty())
            return false;
        return true;
    }
};

[SnackMen]

LeetCode 20 Valid Parentheses

public class Solution {
    public boolean isValid(String s) {
      char chars[] = s.toCharArray();
      Map<Character,Character> map = new HashMap<Character,Character>();
      map.put('(',')');
      map.put('[',']');
      map.put('{','}');
      Stack<Character> stack = new Stack<Character>();
      for(int i=0;i<chars.length;i++){
          if(map.containsKey(chars[i])){
              stack.push(chars[i]);
          }else if(map.containsValue(chars[i])){
              if(!stack.empty()&&map.get(stack.peek())==chars[i]){
                  stack.pop();
              }else{
                  return false;
              }
          }
      }
      return stack.empty();
    }
}

[wolfogre]

POJ 死活不过，呵呵，改到怀疑人生，放弃了

//
// Created by wolfogre on 16-7-15.
//

#ifndef ALGORITHMEXERCISE_POJ1182_H
#define ALGORITHMEXERCISE_POJ1182_H

//#define SUBMIT
#include <iostream>
#include <fstream>
#include <set>
#include <map>

using namespace std;

struct Tribe{
    int eat_tribe;
    set<int> clansman;
};

#define MAX 50001

Tribe *tribes[MAX];
int belong[50001];
int tribe_id_to_eat[50001];

int FindTribe(int a){
    return belong[a];
}

Tribe& GetTribe(int id){
    return *tribes[id];
}

int GetTribeIdToEat(int id){
    return tribe_id_to_eat[id];
}

void MergeTribe(int id1, int id2){
    int tribe_id_to_eat_id2 = GetTribeIdToEat(id2);
    if(tribe_id_to_eat_id2 != 0){
        GetTribe(tribe_id_to_eat_id2).eat_tribe = id1;
        tribe_id_to_eat[id1] = tribe_id_to_eat_id2;
    }

    Tribe id1_tribe = GetTribe(id1);
    Tribe id2_tribe = GetTribe(id2);
    for(set<int> ::iterator it =  id2_tribe.clansman.begin(); it != id2_tribe.clansman.end(); ++it){
        id1_tribe.clansman.insert(*it);
        belong[*it] = id1;
    }

    delete tribes[id2];
    tribes[id2] = NULL;
}

int Poj1182() {
#ifndef SUBMIT
    ifstream fin("input");
#endif
    int n, k;
    int false_count = 0;
    int new_tribe_id = 0;

    for(int i = 0; i < MAX; ++i){
        belong[i] = 0;
        tribes[i] = NULL;
        tribe_id_to_eat[i] = 0;
    }

#ifndef SUBMIT
    fin >> n >> k;
#else
    cin >> n >> k;
#endif

    while(k-- > 0){
        int action, a, b;
#ifndef SUBMIT
        fin >> action >> a >> b;
        if(k % 10000 == 0)
            cout << k << endl;
#else
        cin >> action >> a >> b;
#endif

        if(a > n || b > n || (a == b && action == 2)){
            ++false_count;
            continue;
        }
        int a_tribe = FindTribe(a);
        int b_tribe = FindTribe(b);

        if(action == 1 && a_tribe != 0 && b_tribe != 0){
            if(a_tribe == b_tribe){
                continue;
            }
            ++false_count;
            continue;
        }
        if(action == 1 && a_tribe != 0 && b_tribe == 0){
            GetTribe(a_tribe).clansman.insert(b);
            belong[b] = a_tribe;
            continue;
        }
        if(action == 1 && a_tribe == 0 && b_tribe != 0){
            GetTribe(b_tribe).clansman.insert(a);
            belong[a] = b_tribe;
            continue;
        }
        if(action == 1 && a_tribe == 0 && b_tribe == 0){
            Tribe* new_tribe = new Tribe;
            new_tribe->eat_tribe = 0;
            new_tribe->clansman.insert(a);
            new_tribe->clansman.insert(b);
            tribes[++new_tribe_id] = new_tribe;
            belong[a] = belong[b] = new_tribe_id;
            continue;
        }
        if(action == 2 && a_tribe != 0 && b_tribe != 0){
            if(GetTribe(a_tribe).eat_tribe == b_tribe)
                continue;
            if(GetTribe(a_tribe).eat_tribe == 0){
                int tribe_id_to_eat_b = GetTribeIdToEat(b_tribe);
                if(tribe_id_to_eat_b != 0){
                    MergeTribe(tribe_id_to_eat_b, a_tribe);
                    continue;
                } else{
                    GetTribe(a_tribe).eat_tribe = b_tribe;
                    tribe_id_to_eat[b_tribe] = a_tribe;
                    continue;
                }
            }
            ++false_count;
            continue;
        }
        if(action == 2 && a_tribe != 0 && b_tribe == 0){
            Tribe a_t = GetTribe(a_tribe);
            if(a_t.eat_tribe != 0){
                GetTribe(a_t.eat_tribe).clansman.insert(b);
                belong[b] = a_tribe;
                continue;
            }
            Tribe *new_tribe = new Tribe;
            new_tribe->eat_tribe = 0;
            new_tribe->clansman.insert(b);

            tribes[++new_tribe_id] = new_tribe;
            belong[b] = new_tribe_id;
            GetTribe(a_tribe).eat_tribe = new_tribe_id;
            tribe_id_to_eat[new_tribe_id] = a_tribe;
            continue;
        }
        if(action == 2 && a_tribe == 0 && b_tribe != 0){
            int tribe_id_to_eat_b = GetTribeIdToEat(b_tribe);
            if(tribe_id_to_eat_b != 0){
                GetTribe(tribe_id_to_eat_b).clansman.insert(a);
                belong[a] = tribe_id_to_eat_b;
                continue;
            }
            Tribe* new_tribe = new Tribe;
            new_tribe->eat_tribe = b_tribe;

            new_tribe->clansman.insert(a);
            tribes[++new_tribe_id] = new_tribe;
            belong[a] = new_tribe_id;
            tribe_id_to_eat[b_tribe] = new_tribe_id;
            continue;
        }
        if(action == 2 && a_tribe == 0 && b_tribe == 0){
            Tribe *new_tribe1 = new Tribe;
            new_tribe1->eat_tribe = 0;
            new_tribe1->clansman.insert(b);
            tribes[++new_tribe_id] = new_tribe1;
            belong[b] = new_tribe_id;

            Tribe *new_tribe2 = new Tribe;
            new_tribe2->eat_tribe = new_tribe_id;
            new_tribe2->clansman.insert(a);
            tribes[++new_tribe_id] = new_tribe2;
            tribe_id_to_eat[new_tribe_id - 1] = new_tribe_id;
            belong[a] = new_tribe_id;
        }
    }
    cout << false_count;
    return 0;
}
#endif //ALGORITHMEXERCISE_POJ1182_H

[wolfogre]

我用Excel生成的极限测试数据，可以用来测速度，测试数据的正确答案你猜。

input.zip

[dayang]

//[AC] LeetCode 20
var isValid = function (s) {

    function compare(s1,s2) {
        return (s1 === '(' && s2 === ')') || (s1 === '[' && s2 === ']') || (s1 === '{' && s2 === '}');
    }

    if (s.length % 2 !== 0)
        return false;
    var stack = [];
    for (var i = 0; i < s.length; i++) {
        if (i === 0) {
            stack.push(s[i]);
        } else {
            compare(stack[stack.length - 1], s[i]) ? stack.pop() : stack.push(s[i]);
        }
    }

    return stack.length > 0 ? false : true;
};

[zhaokuohaha]

Leetcode20 - CSharp

public class Solution
{
    Stack<char> sta = new Stack<char>();
    public bool pair(char a, char b)
    {
        return (a == '(' && b == ')') || (a == '[' && b == ']') || (a == '{' && b == '}');
    }
    public bool IsValid(string s)
    {
        foreach(char item in s)
        {

            if(sta == null || sta.Count == 0)
            {
                sta.Push(item);
                continue;
            }

            if(pair(sta.Peek(), item)){
                sta.Pop();
            }
            else
            {
                sta.Push(item);
            }
        }
        if (sta.Count > 0)
            return false;
        return true;
    }
}

简化

public class Solution
{
    Stack<char> sta = new Stack<char>();
    public bool pair(char a, char b)
    {
        return (a == '(' && b == ')') || (a == '[' && b == ']') || (a == '{' && b == '}');
    }
    public bool IsValid(string s)
    {
        foreach(char item in s)
        {

            if(sta!=null && sta.Count >0 && pair(sta.Peek(), item)){
                sta.Pop();
            }
            else
            {
                sta.Push(item);
            }
        }
        if (sta.Count > 0)
            return false;
        return true;
    }
}