/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    vector<int> res;
public:
    vector<int> preorderTraversal(TreeNode* root) {
        dfs(root);
        return res;
    }
    void dfs(TreeNode* root) {
        if(!root) return;
        res.push_back(root->val);
        dfs(root->left);
        dfs(root->right);
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        // preorder: root -> left ->right
        vector<int> res;
        stack<TreeNode*> stk;
        stk.push(root);

        while(!stk.empty()) {
            TreeNode* node = stk.top(); stk.pop();
            if(!node) continue;
            res.push_back(node->val);
            // 為了先處理左側，先 push 右側到 stack
            if(node->right) {
                stk.push(node->right);
            }
            // 利用 stack 的特性，最後再 push 左側
            if(node->left) {
                stk.push(node->left);
            }
        }
        return res;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        // 使用快慢指針尋找中間節點
        // 快指針每次移動兩步，慢指針每次移動一步，當快指針到達鏈表末尾時，慢指針剛好到達中間節點。
        ListNode *slow = head;
        ListNode *fast = head->next;
        while(fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        // 將中間節點之後的 linked list 反轉，以便後續可以交錯合併。
        ListNode* cur = slow->next;
        ListNode* prev = nullptr;

        while(cur) {
            ListNode* temp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = temp;
        }

        // 斷開前後兩個部分
        slow->next = nullptr;

        // 將前半部分和反轉後的後半部分交錯合併。
        ListNode *first = head;
        second = prev;
        while(second) {
            ListNode* node1 = first->next;
            ListNode* node2 = second->next;
            first->next = second;
            second->next = node1;
            first = node1;
            second = node2;
        }
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head)
    {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) return true;
        }
        return false;
    }
};

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict)
    {
        // Initialize a DP array to keep track of valid substrings

        // Iterate over each position in the string
        for ()
        {
            // Check each word in the dictionary
            for ()
            {
                // Ensure that the current index is sufficient to accommodate the word

                // Check if the current position `i` can be formed by the current word
                // We also need to ensure that `dp[i - word.size()]` is true if `i` is not the start of the string
                if ()
                {
                    // Check if the substring matches the current word
                    if ()
                    {
                        // Mark the current position as reachable
                        // No need to check further words for this position
                    }
                }
            }
        }
        // Return whether the entire string can be segmented into dictionary words
    }
};

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict)
    {
        int n = s.size();
        vector<bool> dp(n);
        for (int i = 0; i < n; i++)
        {
            for (auto& word : wordDict)
            {
                if (i < word.size() - 1) continue;
                if (i == word.size() - 1 || dp[i - word.size()])
                {
                    if (s.substr(i - word.size() + 1, word.size()) == word)
                    {
                        dp[i] = true; break;
                    }
                }
            }
        }
        return dp.back();
    }
};

class TrieNode {
public:
    // Indicates whether the node represents the end of a word
    // Array of child nodes, one for each letter of the alphabet

    TrieNode()
    {
        // Initialize the node as not the end of a word
        // Initialize all child pointers to nullptr
    }
};

class Solution {
private:
    // Root of the Trie

public:
    bool wordBreak(string s, vector<string>& wordDict)
    {
        // Build the Trie from the wordDict
        // Initialize a new Trie root
        for ()
        {
                // Convert character to index (0 for 'a', 1 for 'b', ..., 25 for 'z')
                // Create new TrieNode if needed
                // Move to the child node
            // Mark the end of the word
        }

        // Dynamic Programming array to store results of subproblems
        // Initialize DP array with false

        for ()
        {
            // Check if current position is valid (either start of string or can be reached by a valid word break)
            if ()
            {
                for ()
                {
                    // Break if the current character path does not exist in the Trie
                    // Move to the next TrieNode
                    // Mark as true if we reach the end of a valid word
                }
            }
        }
        // Return if the entire string can be segmented
    }
};

class TrieNode {
public:
    bool isWord;
    TrieNode* child[26];
    TrieNode()
    {
        isWord = false;
        for (int i = 0; i < 26; ++i)
        {
            child[i] = nullptr;
        }
    }
};

class Solution {
private:
    TrieNode* root = new TrieNode();
public:
    bool wordBreak(string s, vector<string>& wordDict)
    {
        root = new TrieNode();
        for (auto w : wordDict)
        {
            TrieNode* node = root;
            for (auto c : w)
            {
                if (!node->child[c - 'a'])
                {
                    node->child[c - 'a'] = new TrieNode();
                }
                node = node->child[c - 'a'];
            }
            node->isWord = true;
        }

        vector<bool> dp(s.size());
        for (int i = 0; i < s.size(); i++)
        {
            if (i == 0 || dp[i - 1])
            {
                TrieNode* node = root;
                for (int j = i; j < s.size(); j++)
                {
                    char c = s[j];
                    if (!node->child[c - 'a'])
                    {
                        break;
                    }
                    node = node->child[c - 'a'];
                    if (node->isWord) dp[j] = true;
                }
            }
        }
        return dp[s.size() - 1];
    }
};

class TrieNode {
public:
    TrieNode* child[26];
    bool isWord;
    TrieNode()
    {
        isWord = false;
        for (int i = 0; i < 26; ++i)
        {
            child[i] = nullptr;
        }
    }
};

class Solution {
private:
    TrieNode* root;
    int memo[300];
public:
    bool wordBreak(string s, vector<string>& wordDict)
    {
        root = new TrieNode();
        for (auto word: wordDict)
        {
            TrieNode* node = root;
            for (auto c : word)
            {
                if (!node->child[c - 'a'])
                {
                    node->child[c - 'a'] = new TrieNode();
                }
                node = node->child[c - 'a'];
            }
            node->isWord = true;
        }
        return dfs(s, 0);
    }

    bool dfs(string& s, int cur)
    {
        if (memo[cur] == 1) return false;

        if (cur == s.size()) return true;

        TrieNode* node = root;
        for (int i = cur; i < s.size(); ++i)
        {
            if (node->child[s[i] - 'a'])
            {
                node = node->child[s[i] - 'a'];
                if (node->isWord && dfs(s, i + 1))
                {
                    return true;
                }
            }
            else break;
        }

        memo[cur] = 1;
        return false;
    }
};

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
private:
    unordered_map<Node*, Node*> oldToNew;
public:
    Node* copyRandomList(Node* head)
    {
        return dfs(head);
    }

    Node* dfs(Node* node)
    {
        if (!node) return nullptr;
        if (oldToNew.count(node)) return oldToNew[node];

        // 如果沒有找到 node
        oldToNew[node] = new Node(node->val);
        oldToNew[node]->next = dfs(node->next);
        oldToNew[node]->random = dfs(node->random);
        return oldToNew[node];
    }
};

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (auto& num : nums)
            res ^= num;
        return res;
    }
};

/*
 * @lc app=leetcode id=135 lang=cpp
 *
 * [135] Candy
 *
 * https://leetcode.com/problems/candy/description/
 *
 * algorithms
 * Hard (43.78%)
 * Likes:    8018
 * Dislikes: 683
 * Total Accepted:    610.6K
 * Total Submissions: 1.4M
 * Testcase Example:  '[1,0,2]'
 *
 * There are n children standing in a line. Each child is assigned a rating
 * value given in the integer array ratings.
 *
 * You are giving candies to these children subjected to the following
 * requirements:
 *
 *
 * Each child must have at least one candy.
 * Children with a higher rating get more candies than their neighbors.
 *
 *
 * Return the minimum number of candies you need to have to distribute the
 * candies to the children.
 *
 *
 * Example 1:
 *
 *
 * Input: ratings = [1,0,2]
 * Output: 5
 * Explanation: You can allocate to the first, second and third child with 2,
 * 1, 2 candies respectively.
 *
 *
 * Example 2:
 *
 *
 * Input: ratings = [1,2,2]
 * Output: 4
 * Explanation: You can allocate to the first, second and third child with 1,
 * 2, 1 candies respectively.
 * The third child gets 1 candy because it satisfies the above two
 * conditions.
 *
 *
 *
 * Constraints:
 *
 *
 * n == ratings.length
 * 1 <= n <= 2 * 10^4
 * 0 <= ratings[i] <= 2 * 10^4
 *
 *
 */

// @lc code=start
class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> candy(n, 1);

        for (int i = 1; i < n; ++i) {
            if (ratings[i] > ratings[i - 1]) {
                candy[i] = candy[i - 1] + 1;
            }
        }

        for (int i = n - 2; i >= 0; --i) {
            if (ratings[i] > ratings[i + 1]) {
                candy[i] = max(candy[i], candy[i + 1] + 1);
            }
        }
        return accumulate(candy.begin(), candy.end(), 0);
    }
};
// @lc code=end

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost)
    {
        // If the total cost is greater than the total gas available,
        // it's impossible to complete the circuit, so return -1

        // Variables to track the starting gas station and the remaining gas

        // Iterate through each gas station
        for ()
        {
            // Update the remaining gas after reaching the current station

            // If the remaining gas is negative, we cannot reach the next station from the current start
            // So, reset the remaining gas and set the new start to the next station
        }
        // Return the starting gas station index
    }
};

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost)
    {
        if (accumulate(cost.begin(), cost.end(), 0) > accumulate(gas.begin(), gas.end(), 0))
        {
            return -1;
        }
        int start = 0, remaining = 0;
        for (int i = 0; i < gas.size(); i++)
        {
            remaining += gas[i] - cost[i];
            if (remaining < 0)
            {
                remaining = 0;
                start = i + 1;
            }
        }
        return start;
    }
};

/*
 * @lc app=leetcode id=133 lang=cpp
 *
 * [133] Clone Graph
 *
 * https://leetcode.com/problems/clone-graph/description/
 *
 * algorithms
 * Medium (59.77%)
 * Likes:    9886
 * Dislikes: 4002
 * Total Accepted:    1.5M
 * Total Submissions: 2.5M
 * Testcase Example:  '[[2,4],[1,3],[2,4],[1,3]]'
 *
 * Given a reference of a node in a connected undirected graph.
 *
 * Return a deep copy (clone) of the graph.
 *
 * Each node in the graph contains a value (int) and a list (List[Node]) of its
 * neighbors.
 *
 *
 * class Node {
 * ⁠   public int val;
 * ⁠   public List<Node> neighbors;
 * }
 *
 *
 *
 *
 * Test case format:
 *
 * For simplicity, each node's value is the same as the node's index
 * (1-indexed). For example, the first node with val == 1, the second node with
 * val == 2, and so on. The graph is represented in the test case using an
 * adjacency list.
 *
 * An adjacency list is a collection of unordered lists used to represent a
 * finite graph. Each list describes the set of neighbors of a node in the
 * graph.
 *
 * The given node will always be the first node with val = 1. You must return
 * the copy of the given node as a reference to the cloned graph.
 *
 *
 * Example 1:
 *
 *
 * Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
 * Output: [[2,4],[1,3],[2,4],[1,3]]
 * Explanation: There are 4 nodes in the graph.
 * 1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val =
 * 4).
 * 2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val =
 * 3).
 * 3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val =
 * 4).
 * 4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val =
 * 3).
 *
 *
 * Example 2:
 *
 *
 * Input: adjList = [[]]
 * Output: [[]]
 * Explanation: Note that the input contains one empty list. The graph consists
 * of only one node with val = 1 and it does not have any neighbors.
 *
 *
 * Example 3:
 *
 *
 * Input: adjList = []
 * Output: []
 * Explanation: This an empty graph, it does not have any nodes.
 *
 *
 *
 * Constraints:
 *
 *
 * The number of nodes in the graph is in the range [0, 100].
 * 1 <= Node.val <= 100
 * Node.val is unique for each node.
 * There are no repeated edges and no self-loops in the graph.
 * The Graph is connected and all nodes can be visited starting from the given
 * node.
 *
 *
 */

// @lc code=start
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/

class Solution {
private:
    unordered_map<Node*, Node*> oldToNew;
public:
    Node* cloneGraph(Node* node)
    {
        if (!node) return nullptr;
        if (oldToNew.count(node)) return oldToNew[node];

        oldToNew[node] = new Node(node->val);

        for (auto& nei : node->neighbors)
        {
            oldToNew[node]->neighbors.push_back(cloneGraph(nei));
        }
        return m[node];
    }
};
// @lc code=end