leetcode解题思路分析（六十八）587 - 593 题

古城微笑少年丶 2022-11-06 02:56 108阅读 0赞

1.  安装栅栏  
    在一个二维的花园中，有一些用 (x, y) 坐标表示的树。由于安装费用十分昂贵，你的任务是先用最短的绳子围起所有的树。只有当所有的树都被绳子包围时，花园才能围好栅栏。你需要找到正好位于栅栏边界上的树的坐标。

**凸包问题，常见解法有Jarvis, Graham, 单调链**

class Solution { 
    public:
        vector<vector<int>> outerTrees(vector<vector<int>>& points) { 
            int N = points.size();
            if (N < 4) {  return points; }
    
            // find left-most
            int left_most = 0;
            for (int i = 0; i < N; ++i) { 
                if (points[i][0] < points[left_most][0]) { 
                    left_most = i;
                }
            }
    
            // find hull
            using PII = vector<int>;
            auto hash_function = [](const vector<int> & o) { return hash<int>()(o[0]) ^ hash<int>()(o[1]); };
            unordered_set<PII, decltype(hash_function)> hull(0, hash_function);
            int p = left_most;
            do 
            { 
                int q = (p + 1) % N;
                // most anti-clockwise
                for (int i = 0; i < N; ++i) { 
                    if (orientation(points[p], points[i], points[q])<0) { 
                        q = i;
                    }
                }
    
                // in between
                for (int i = 0; i < N; ++i) { 
                    if (i != p && i != q && 0 == orientation(points[p], points[i], points[q]) && inBetween(
                        points[p], points[i], points[q])) { 
                        hull.emplace(points[i]);
                    }
                }
    
                hull.emplace(points[q]);
                p = q;
            } while (p!=left_most);
    
            vector<vector<int> > res;
            res.assign(hull.begin(), hull.end());
            return res;
        }
    
    private:
        int orientation(vector<int> &p, vector<int> &q, vector<int> &r) { 
            return (q[1] - p[1])*(r[0] - q[0]) - (q[0] - p[0])*(r[1] - q[1]);
        }
    
        bool inBetween(vector<int> &p, vector<int> &i, vector<int> &q) { 
            bool a = (i[0] >= p[0] && i[0] <= q[0]) || (i[0] >= q[0] && i[0] <= p[0]);
            bool b = (i[1] >= p[1] && i[1] <= q[1]) || (i[1] >= q[1] && i[1] <= p[1]);
    
            return a&&b;
        }
    };

1.  N 叉树的前序遍历  
    给定一个 N 叉树，返回其节点值的前序遍历 。

**对于N叉树的前序遍历，只要压栈的时候逆序压入子节点即可**

/* // Definition for a Node. class Node { public: int val; vector<Node*> children; Node() {} Node(int _val) { val = _val; } Node(int _val, vector<Node*> _children) { val = _val; children = _children; } }; */
    
    class Solution
    { 
        vector<int> m_val;
    public:
        vector<int> preorder(Node* root) 
        { 
            if (root == 0) return m_val;
    
            stack<Node*> tmpStack;
            tmpStack.push(root);
            
            while (tmpStack.size())
            { 
                Node* ptr = tmpStack.top();
                tmpStack.pop();
                m_val.push_back(ptr->val);
    
                for (int i = ptr->children.size() - 1; i >= 0; --i)
                { 
                    tmpStack.push(ptr->children[i]);
                }
            }
    
            return m_val;
        }
    };

1.  N 叉树的后序遍历  
    给定一个 N 叉树，返回其节点值的 后序遍历 。

**后序遍历可以先把父节点记录，然后逆序记录子节点，最后将数组逆序，即为后序遍历结果**

/* // Definition for a Node. class Node { public: int val; vector<Node*> children; Node() {} Node(int _val) { val = _val; } Node(int _val, vector<Node*> _children) { val = _val; children = _children; } }; */
    
    class Solution { 
    public:
        vector<int> postorder(Node* root) 
        { 
            std::vector<int> ret;
            std::stack<Node*> m_stack;
    
            if (root == NULL) return ret;
            m_stack.push(root);
    
            while (m_stack.size())
            { 
                Node* ptr = m_stack.top();
                m_stack.pop();
                ret.push_back(ptr->val);
    
                for (int i = 0; i < ptr->children.size(); i++)
                { 
                    m_stack.push(ptr->children[i]);
                }
            }
    
            reverse(ret.begin(), ret.end());
    
            return ret;
        }
    };

1.  标签验证器  
    给定一个表示代码片段的字符串，你需要实现一个验证器来解析这段代码，并返回它是否合法。合法的代码片段需要遵守以下的所有规则：

**用栈存储即可**

class Solution { 
        enum ProgramState { 
            A, B, C, D, E, F
        }program_state;
    
    public:
        Solution() { 
            program_state = ProgramState::A;
        }
        bool isValid(string code) { 
            int i = 0;
            stack<string> tags;
            string tag;
            char c;
            while (i < code.size()) { 
                c = code[i];
                switch (program_state) { 
                case ProgramState::A:
                    if (code[i] == '<') { 
                        program_state = ProgramState::B;
                        ++i;
                    }
                    else { 
                        return false;
                    }
                    break;
                case ProgramState::B:
                    if (code[i] >= 'A' and code[i] <= 'Z') { 
                        tag += code[i];
                        program_state = ProgramState::C;
                        ++i;
                    }
                    else { 
                        return false;
                    }
                    break;
                case ProgramState::C:
                    if (code[i] >= 'A' and code[i] <= 'Z') { 
                        tag += code[i];
                        ++i;
                    }
                    else if (code[i] == '>') { 
                        if (tag.size() > 9) { 
                            return false;
                        }
                        else { 
                            tags.push(tag);
                            tag.clear();
                            program_state = ProgramState::D;
                            ++i;
                        }
                    }
                    else { 
                        return false;
                    }
                    break;
                case ProgramState::D:
                    if (i < code.size() - 8 and code.substr(i, 9) == string("<![CDATA[")) { 
                        program_state = ProgramState::E;
                        i += 9;
                    }
                    else if (i < code.size() - 1 and code.substr(i, 2) == string("</")) { 
                        program_state = ProgramState::F;
                        i += 2;
                    }
                    else if (code[i] == '<') { 
                        program_state = ProgramState::B;
                        ++i;
                    }
                    else { 
                        ++i;
                    }
                    break;
                case ProgramState::E:
                    if (i < code.size() - 2 and code.substr(i, 3) == string("]]>")) { 
                        program_state = ProgramState::D;
                        i += 3;
                    }
                    else { 
                        ++i;
                    }
                    break;
                case ProgramState::F:
                    if (code[i] >= 'A' and code[i] <= 'Z') { 
                        tag += code[i];
                        ++i;
                    }
                    else if (code[i] == '>') { 
                        if (tag.size() > 9) { 
                            return false;
                        }
                        else { 
                            if (tags.top() != tag) { 
                                return false;
                            }
                            tags.pop();
                            tag.clear();
                            program_state = ProgramState::D;
                            ++i;
                            if(tags.empty() and i!=code.size()){ 
                                return false;
                            }
                        }
                    }
                    else { 
                        return false;
                    }
                    break;
                }
            }
            return tags.empty() and program_state == ProgramState::D;
        }
    };

1.  分数加减运算  
    给定一个表示分数加减运算表达式的字符串，你需要返回一个字符串形式的计算结果。 这个结果应该是不可约分的分数，即最简分数。 如果最终结果是一个整数，例如 2，你需要将它转换成分数形式，其分母为 1。所以在上述例子中, 2 应该被转换为 2/1。

**先对字符串进行解析，接着通分计算，然后再约分**

class Solution { 
    public:
        int gcd(int a, int b) 
        { 
            return b ? gcd(b, a % b) : a;
        }
        string fractionAddition(string expression) { 
            int n = 0;
            for (auto c: expression)
                if (c == '/')
                    n ++ ;
            expression = '+' + expression;
            int a = 0, b = 1, offset = 0;
            int c, d;
            char e;
            for (int i = 0; i < n; i ++ ) { 
                sscanf(expression.c_str() + offset, "%c%d/%d", &e, &c, &d);
                offset += (e + to_string(c) + '/' + to_string(d)).size();
                if (e == '-') c = -c;
                int x = a * d + b * c, y = b * d;
                int z = abs(gcd(x, y)); // 最大公约数
                a = x / z, b = y / z;
            }
    
            return to_string(a) + '/' + to_string(b);
        }
    };

1.  有效的正方形  
    给定二维空间中四点的坐标，返回四点是否可以构造一个正方形。一个点的坐标（x，y）由一个有两个整数的整数数组表示。

**可以通过简单的计算6条边的长度，然后如果满足4条长度相等、另两条长度相等，则即为正方形。**

class Solution { 
    public:
        bool validSquare(vector<int> &p1, vector<int> &p2, vector<int> &p3, vector<int> &p4) { 
            unordered_map<int, int> map;
            map[distance(p1, p2)]++;
            map[distance(p1, p3)]++;
            map[distance(p1, p4)]++;
            map[distance(p2, p3)]++;
            map[distance(p2, p4)]++;
            map[distance(p3, p4)]++;
            if (map.size() != 2) return false;
            for (auto &x : map) { 
                if (x.first == 0 || x.second != 2 && x.second != 4) return false;
            }
            return true;
        }
    
        int distance(const vector<int> &p1, const vector<int> &p2) { 
            int x = p1[0] - p2[0];
            int y = p1[1] - p2[1];
            return x * x + y * y;
        }
    };