keeping going~

589. N-ary Tree Preorder Traversal

Analysis

N 叉树的先序遍历，直接递归。

Code

method 1

class Solution {
public:
    void pre(Node *root, vector<int>& ret) {
        if(!root) return;
        ret.push_back(root->val);
        for(int i = 0; i < root->children.size(); i++) {
            pre(root->children[i], ret);
        }
    }
    vector<int> preorder(Node* root) {
        vector<int> ret;
        pre(root, vector<int>& ret);
        return ret;
    }
};

对这道题的递归过程倒是很清楚，哈哈。

method 2

借助栈也可以来完成，由于孩子结点可能有多个，所以需要用 map 来记录一下访问到了那个孩子结点。

class Solution {
public:
    vector<int> preorder(Node* root) {
        vector<int> ret;
        if(!root) return ret;
        stack<Node*> st;
        unordered_map<Node*, int> ht;
        Node *node = root;
        while(!st.empty() || node != nullptr) {
            while(node != nullptr) {
                ret.push_back(node->val);
                st.push(node);
                if(node->children.size() > 0) {
                    ht[node] = 0;
                    node = node->children[0];
                } else node = nullptr;
            }
            node = st.top();
            int index = (ht.count(node) ? ht[node] : -1) + 1;
            if(index < node->children.size()) {
                ht[node] = index;
                node = node->children[index];
            } else {
                st.pop();
                ht.erase(node);
                node = nullptr;
            }
        }
        return ret;
    }
};

可以发现，因为每次需要保持左边的结点先访问，所以要先将左边第一个结点入栈。结合栈先进后出的特点，不妨一次性将结点的孩子全部逆序入栈，这样栈顶元素就是需要访问的最左边的元素。

class Solution {
public:
    vector<int> preorder(Node* root) {
        vector<int> ret;
        if(!root) return ret;
        stack<Node*> st;
        st.push(root);
        while(!st.empty()) {
            Node *node = st.top();
            st.pop();
            ret.push_back(node->val);
            for(auto it = node->children.rbegin(); it != node->children.rend(); it++) {
                st.push(*it);
            }
        }
        return ret;
    }
};

496. Next Greater Element I

Analysis

这个题有点麻烦，先找出 $nums1[i]$ 在 $nums2$ 中的位置（也就是 $nums2[j]$），然后在找出 $nums2[j]$ 之后第一个比 $nums2[j]$ 大的数。

Code

method 1

数量级不大，直接暴力解决。

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ret;
        ret.resize(nums1.size());
        for(int i = 0;i < nums1.size(); i++) {
            bool flag1 = false, flag2 = false;
            for(int j = 0; j < nums2.size(); j++) {
                if(nums2[j] == nums1[i]) flag1 = true;
                if(flag1 && nums2[j] > nums1[i]) {
                    ret[i] = nums2[j];
                    flag2 = true;
                    break;
                }
            }
            if(!flag2) ret[i] = -1;
        }
        return ret;
    }
};

使用 2 个 bool 变量来协助查找，就不用重复遍历 nums2 了，这样总体时间复杂度是 $O(nums1.length × nums2.length)$。

method 2

还有一个进阶提示，问有没有 $O(nums1.length + nums2.length)$ 的解法，也不知道这个提示要求的是时间复杂度还是空间复杂度。
看了一下题解，原来是时间复杂度啊。
要达到这样的时间复杂度，需要借助一种新的思想——单调栈（Monotonic Stack）。当然了，本质上还是用栈，只不过先遍历 $nums2$ 将所有数字后面第一个比它大的数都找到，然后在遍历 $nums1$，为了方便查询，借助一下哈希表。

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> st;
        unordered_map<int, int> ht;
        for(int i = nums2.size() - 1; i >= 0; i--) {
            int num = nums2[i];
            while(!st.empty() && num >= st.top()) st.pop();
            ht[num] = st.empty() ? -1 : st.top();
            st.push(num);
        }
        vector<int> ret;
        for(int i = 0; i < nums1.size(); i++) {
            ret.push_back(ht[nums1[i]]);
        }
        return ret;
    }
};

em...好好体会一下栈的这种应用。

1232. Check If It Is a Straight Line

Analysis

这个题好像在考一次函数的知识点，这好像是初中数学。

Code

直接用前 2 个点求出一次函数的方程，然后验证后面的点是否在上面即可。

class Solution {
public:
    bool checkStraightLine(vector<vector<int>>& coordinates) {
        double k, b, diff1, diff2;
        diff1 = coordinates[1][1] - coordinates[0][1];
        diff2 = coordinates[1][0] - coordinates[0][0];
        if(diff1 == 0) {
            for(int i = 0; i < coordinates.size() - 1; i++) {
                if(coordinates[i][1] != coordinates[i + 1][1]) return false;
            }
        } else if(diff2 == 0) {
            for(int i = 0; i < coordinates.size() - 1; i++) {
                if(coordinates[i][0] != coordinates[i + 1][0]) return false;
            }
        } else {
            k = diff1 / diff2;
            b = coordinates[0][1] - k * coordinates[0][0];
            for(int i = 2; i < coordinates.size(); i++) {
                if(coordinates[i][1] != b + k * coordinates[i][0]) return false;
            }
        }
        return true;
    }
};

注意几个点：

坐标轴上的点也能连成一条直线。
形如 $y = 2, x = 1$ 这样与坐标轴垂直的线也符合题意。
注意求斜率时，$x$ 不能为 0。

实际上为了避免上面的问题，完全可以不求斜率。因为直线还有其他形式的方程，所以使用其他方程就可以得到不一样的代码。

class Solution {
public:
    bool checkStraightLine(vector<vector<int>>& coordinates) {
        int deltax = coordinates[0][0], deltay = coordinates[0][1];
        for(int i = 0; i < coordinates.size(); i++) {
            coordinates[i][0] -= deltax;
            coordinates[i][1] -= deltay;
        }
        int A = coordinates[1][1], B = -coordinates[1][0];
        for(int i = 2; i < coordinates.size(); i++) {
            if(coordinates[i][0] * A + coordinates[i][1] * B != 0) return false;
        }
        return true;
    }
};

上面的代码将第一个点平移到原点，其他点平移了第一个点的距离。这样利用直先的一般式（$y = Ax + By + C$）求 A 和 B 时，任意一个点的横纵坐标改变一下符号就可以了，这就省去了求斜率的过程。

当然了，还可以用直线的两点式（$\frac{y-y1}{x-x1} = \frac{y-y2}{x-x2}$）来求。

class Solution {
public:
    bool checkStraightLine(vector<vector<int>>& coordinates) {
        for(int i = 2; i < coordinates.size(); i++) {
            if(
                (coordinates[i][0] - coordinates[0][0]) * 
                (coordinates[i][1] - coordinates[1][1]) !=
                (coordinates[i][0] - coordinates[1][0]) *
                (coordinates[i][1] - coordinates[0][1])
                ) return false;
        }
        return true;
    }
};