leetcode101-150

0101

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root)return true;
        queue<TreeNode*>q;
        q.push(root->left), q.push(root->right);
        while(!q.empty()){
            TreeNode*l = q.front(); q.pop();
            TreeNode*r = q.front(); q.pop();
            if (!l && r) return false;
            if (l && !r) return false;
            if(l && r){
                if(l->val != r->val)return false;
                q.push(l->left), q.push(r->right);
                q.push(l->right), q.push(r->left);
            }
        }
        return true;
    }
};

0102

class Solution {
public:
    vector<int>vs[1010];
    void dfs(TreeNode*cur, int cnt){
        vs[cnt].push_back(cur->val);
        if(cur->left)dfs(cur->left, cnt + 1);
        if(cur->right)dfs(cur->right, cnt + 1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>>ans;
        if(!root)return ans;
        dfs(root, 1);
        int cnt = 1;
        while(!vs[cnt].empty())ans.push_back(vs[cnt++]);
        return ans;
    }
};

0103

class Solution {
public:
    vector<int>vs[1010];
    void dfs(TreeNode*cur, int cnt){
        vs[cnt].push_back(cur->val);
        if(cur->left)dfs(cur->left, cnt + 1);
        if(cur->right)dfs(cur->right, cnt + 1);
    }
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>>ans;
        if(!root)return ans;
        dfs(root, 1);
        int cnt = 1;
        while(!vs[cnt].empty()){
            if(cnt%2)ans.push_back(vs[cnt]);
            else {
                reverse(vs[cnt].begin(), vs[cnt].end());
                ans.push_back(vs[cnt]);
            }
            cnt++;
        }
        return ans;
    }
};

0104

class Solution {
public:
    int ans = 0;
    void dfs(TreeNode*cur, int cnt){
        ans = max(ans, cnt);
        if(cur->left)dfs(cur->left, cnt + 1);
        if(cur->right)dfs(cur->right, cnt + 1);
    }
    int maxDepth(TreeNode* root) {
        if(!root)return 0;
        dfs(root, 1);
        return ans;
    }
};

0105

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        return buildTreeAux(preorder, 0, n, inorder, 0, n);
    }
    TreeNode* buildTreeAux(vector<int>& preorder, int rt, int n, vector<int>& inorder, int l, int r) {
        int pos = -1;
        if (rt >= n || l >= n)return nullptr;
        for (int i = l; i < r; i++)if (inorder[i] == preorder[rt]) { pos = i; break; }
        int lcnt = pos - l;
        TreeNode* root = new TreeNode(preorder[rt]);
        root->left = buildTreeAux(preorder, rt + 1, rt + 1 + lcnt, inorder, l, pos);
        root->right = buildTreeAux(preorder, rt + 1 + lcnt, n, inorder, pos + 1, r);
        return root;
    }
};

0106

class Solution {
public:
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        int n = inorder.size() - 1;
        return buildTreeAux(inorder, postorder, 0, n, 0, n);
    }
    TreeNode* buildTreeAux(vector<int> &inorder, vector<int> &postorder, int l, int r, int o, int rt) {
        if (o > rt)return nullptr;
        int pos = -1;
        for (int i = l; i <= r; i++)if (inorder[i] == postorder[rt]) { pos = i; break; }
        TreeNode* node = new TreeNode(postorder[rt]);
        int rcnt = r - pos - 1;
        node->left = buildTreeAux(inorder, postorder, l, pos - 1, o, rt - 1 - rcnt - 1);
        node->right = buildTreeAux(inorder, postorder, pos + 1, r, rt - 1 - rcnt, rt - 1);
        return node;
    }
};

0107

class Solution {
public:
    vector<int>vs[1010];
    void dfs(TreeNode*cur, int cnt){
        vs[cnt].push_back(cur->val);
        if(cur->left)dfs(cur->left, cnt + 1);
        if(cur->right)dfs(cur->right, cnt + 1);
    }
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>>ans;
        if(!root)return ans;
        dfs(root, 1);
        int cnt = 1;
        while(!vs[cnt].empty())ans.push_back(vs[cnt++]);
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

0108

class Solution {
public:
    TreeNode* buildTree(vector<int>&nums, int l, int r){
        if(l > r)return nullptr;
        int m = (l + r) / 2;
        TreeNode* cur = new TreeNode(nums[m]);
        cur->left = buildTree(nums, l, m - 1);
        cur->right = buildTree(nums, m + 1, r);
        return cur;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        int n = nums.size() - 1;
        return buildTree(nums, 0, n);
    }
};

0109

class Solution {
public:
    TreeNode* buildTree(ListNode*head, ListNode *tail){
        if(head == tail)return nullptr;
        if(head->next == tail)return new TreeNode(head->val);
        ListNode *ptr = head, *tmp = head;
        while( tmp != tail && tmp->next != tail )ptr = ptr->next, tmp = tmp->next->next;
        TreeNode *cur = new TreeNode(ptr->val);
        cur->left = buildTree(head, ptr);
        cur->right = buildTree(ptr->next, tail);
        return cur;
    }
    TreeNode* sortedListToBST(ListNode* head) {
        return buildTree(head, nullptr);
    }
};

0110

class Solution {
public:
    int aux(TreeNode* root){
        if(!root)return 0;
        return max(aux(root->left), aux(root->right)) + 1;
    }
    bool isBalanced(TreeNode* root) {
        if(!root)return true;
        return isBalanced(root->left) && isBalanced(root->right) && abs(aux(root->left) - aux(root->right)) <= 1;
    }
};

0111

class Solution {
public:
    int minv = INT_MAX;
    void dfs(TreeNode* root, int cnt){
        if(root){
            if(root->left)dfs(root->left, cnt + 1);
            if(root->right)dfs(root->right, cnt + 1);
            if(!root->left && !root->right)minv = min(minv, cnt);
        }
    }
    int minDepth(TreeNode* root) {
        if(!root)return 0;
        dfs(root, 1);
        return minv;
    }
};

0112

class Solution {
public:
    bool bfs(TreeNode* rt, int&sum){
        queue<TreeNode*>q;
        q.push(rt);
        while(!q.empty()){
            TreeNode*cur = q.front(); q.pop();
            if(cur->val == sum&&!cur->left&&!cur->right)return true;
            if(cur->left)cur->left->val += cur->val, q.push(cur->left);            
            if(cur->right)cur->right->val += cur->val, q.push(cur->right);
        }
        return false;
    }
    bool hasPathSum(TreeNode* root, int sum) {
        if(!root)return 0;
        return bfs(root, sum);
    }
};

0113

class Solution {
public:
    struct node{
        TreeNode* cur;
        vector<int> path;
        int sum;
        node(TreeNode* x, int val):cur(x), sum(val) {}        
    };
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> ans;
        if(!root)return ans;
        queue<node> q;
        node s(root, root->val);
        s.path.push_back(root->val);
        q.push(s);
        while(!q.empty()){
            node cur = q.front(); q.pop();
            if(cur.cur->left){
                TreeNode *l = cur.cur->left;
                node c(l, cur.sum + l->val);
                c.path = cur.path;
                c.path.push_back(l->val);
                q.push(c);
            }
            if(cur.cur->right){
                TreeNode *r = cur.cur->right;
                node c(r, cur.sum + r->val);
                c.path = cur.path;
                c.path.push_back(r->val);
                q.push(c);
            }
            if(!cur.cur->left && !cur.cur->right && cur.sum == sum)ans.push_back(cur.path);
        }
        return ans;
    }
};

0114

class Solution {
public:
    void flatten(TreeNode* root) {
        while (root) {
            if (root->left && root->right) {
                TreeNode* l = root->left;
                while (l->right)l = l->right;
                l->right = root->right;
            }
            if(root->left)root->right = root->left;
            root->left = nullptr;
            root = root->right;
        }
    }
};

0116

class Solution {
public:
    void dfs(Node* root){
        if(!root->left && !root->right)return;
        root->left->next = root->right;
        if(root->next)root->right->next = root->next->left;
        else root->right->next = nullptr;
        dfs(root->left);
        dfs(root->right);
    }
    Node* connect(Node* root) {
        if(!root || (!root->left && !root->right))return root;
        dfs(root);
        return root;
    }
};

0117

class Solution {
public:
    Node* connect(Node* root) {
        connectAux(root);
        return root;
    }
    void connectAux(Node *root) {
        if (!root) return;
        Node tmp(INT_MIN, nullptr, nullptr, nullptr);
        for (Node *cur = root, *pre = &tmp; cur; cur = cur->next) {
            if (cur->left) pre->next = cur->left, pre = pre->next;
            if (cur->right) pre->next = cur->right, pre = pre->next;
        }
        connectAux(tmp.next);
    }
};

0118

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<int>v1 = { 1 };
        vector<int>v2 = { 1, 1 };
        vector<vector<int>>ans;
        if(!numRows)return ans;
        else if(numRows == 1){ ans.push_back(v1); return ans; }
        else if(numRows == 2){ ans.push_back(v1), ans.push_back(v2); return ans; }
        else ans.push_back(v1), ans.push_back(v2);
        numRows -= 2;
        while(numRows--) {
            vector<int>tmp = { 1 };
            vector<int>pre = *(ans.rbegin());
            for(int i = 0, j = 1; j < pre.size(); i++, j++)tmp.push_back(pre[i] + pre[j]);
            tmp.push_back(1);
            ans.push_back(tmp);
        }
        return ans;
    }
};

0119

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int>ans{ 1 };
        for(int i = 1; i <= rowIndex; i++){
            int k = i;
            long long tmp1 = 1, tmp2 = 1;
            for(int j = 1; j <= k; j++) {
                tmp1 *= (rowIndex - j + 1);
                tmp2 *= j;
                if(tmp1 % tmp2 == 0)tmp1 /= tmp2, tmp2 = 1;
            }
            ans.push_back(tmp1 / tmp2);
        }
        return ans;
    }
};

0120（这题我嫌形参名字太长直接改了）

class Solution {
public:
    int minimumTotal(vector<vector<int>>& tri) {
        for(int i = tri.size() - 1; i >= 0; i--)
            for(int j = 0; j < i; j++)
                tri[i - 1][j] = min(tri[i - 1][j] + tri[i][j], tri[i - 1][j] + tri[i][j + 1]);
        return tri[0][0];
    }
};

0121

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxv = 0, tmp = INT_MAX;
        for(auto &i : prices)
            if(i < tmp)tmp = i;
            else maxv = max(maxv, i - tmp);
        return maxv;
    }
};

0122

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        prices.push_back(INT_MIN);
        int ans = 0, tmp = prices[0], n = prices.size();;
        for(int i = 1; i < n; i++)
            if(prices[i] < prices[i - 1])ans += prices[i - 1] - tmp, tmp = prices[i];
        return ans;
    }
};

0124

class Solution {
public:
    int dfs(TreeNode*root, int&maxv){
        if(!root)return 0;
        int l = dfs(root->left, maxv), r = dfs(root->right, maxv);
        maxv = max(maxv, l + r + root->val);
        return max(0, max(l, r) + root->val);
    }
    int maxPathSum(TreeNode* root) {
        int maxv = INT_MIN;
        dfs(root, maxv);
        return maxv;
    }
};

0125

class Solution {
public:
    bool isPalindrome(string s) {
        char tmp1[100010], tmp2[100010];
        int cnt = 0;
        for(auto &i : s)if(isalnum(i))tmp1[cnt++] = toupper(i);
        strcpy(tmp2, tmp1);
        reverse(tmp1, tmp1 + cnt);
        return !strcmp(tmp1, tmp2);
    }
};

0127

class Solution {
public:
    struct node{
        string _s;
        int cnt;
        node(string s) : _s(s), cnt(0){}        
        node(string s, int val) : _s(s), cnt(val){}
    };
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        map<string, int> mp;
        if((find(wordList.begin(), wordList.end(), endWord) == wordList.end()))return 0;
        node s(beginWord, 1);
        queue<node>q;
        q.push(s);
        while(!q.empty()){
            node cur = q.front(); q.pop();
            for(auto &i : wordList) {
                int cnt = 0;
                for(int j = 0; j < cur._s.size(); j++)if(i[j] != cur._s[j])cnt++;
                if(cnt == 1) {
                    if(i != endWord && !mp.count(i)) {
                        q.push(node(i, cur.cnt + 1));
                        mp[i]++;
                    }
                    else if(i == endWord)return cur.cnt + 1;
                }
            }
        }
        return 0;
    }
};

0129

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        int ans = 0;
        if(!root)return ans;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            TreeNode* cur = q.front(); q.pop();
            if(!cur->left && !cur->right)ans += cur->val;
            if(cur->left)cur->left->val += cur->val * 10, q.push(cur->left);      
            if(cur->right)cur->right->val += cur->val * 10, q.push(cur->right);
        }
        return ans;
    }
};

0130

class Solution {
public:
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    void bfs(int x, int y, int &n, int &m, vector<vector<char>>& board) {
        queue<pair<int, int>>q;
        q.push({x, y});
        board[x][y] = '#';
        while(!q.empty()) {
            pair<int, int> cur = q.front(); q.pop();
            int tmpx, tmpy;
            for(int i = 0; i < 4; i++) {
                tmpx = cur.first + dx[i], tmpy = cur.second + dy[i];
                if(tmpx >= 0 && tmpx < n && tmpy >= 0 && tmpy < m && board[tmpx][tmpy] == 'O')board[tmpx][tmpy] = '#', q.push({tmpx, tmpy});
            }
        }
    }
    void solve(vector<vector<char>>& board) {
        if(board.empty() || board[0].empty())return;
        int n = board.size(), m = board[0].size();
        for(int i = 0; i < m; i++) {
            if(board[0][i] == 'O')bfs(0, i, n, m, board);
            if(board[n - 1][i] == 'O')bfs(n - 1, i, n, m, board);
        }
        for(int i = 1; i < n; i++) {
            if(board[i][0] == 'O')bfs(i, 0, n, m, board);            
            if(board[i][m - 1] == 'O')bfs(i, m - 1, n, m, board);
        }
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                if(board[i][j] == '#')board[i][j] = 'O';
                else if(board[i][j] == 'O')board[i][j] = 'X';
    }
};

0131

class Solution {
public:
    vector<vector<string>>ans;
    vector<string>tmp;
    void aux(string &s, int l, int r) {
        if(l >= r){ ans.push_back(tmp); return; }
        for(int k = l; k < r; k++) {
            string tmp1(s.begin() + l, s.begin() + k + 1);
            bool flag = true;
            for(int j = 0; j <= (k + 1 - l) / 2; j++)
                if(tmp1[j] != tmp1[k - l - j]){ flag = false; break; }
            if(flag) {
                tmp.push_back(tmp1);
                aux(s, k + 1, r);
                tmp.erase(tmp.end() - 1);
            }
        }
    }
    vector<vector<string>> partition(string s) {
        if(s.empty())return ans;
        aux(s, 0, s.size());
        return ans;
    }
};

0134

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        for(int i = 0; i < n; i++)gas[i] -= cost[i];
        for(int i = 0; i < n; i++) {
            int tmp = 0;
            for(int j = i; 1 ;j++) {
                tmp += gas[j % n];
                if(tmp < 0)break;
                if(j != i && j % n == i)break;
            }
            if(tmp >= 0)return i;
        }
        return -1;
    }
};

0136

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

0137

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            int tmp = 0;
            for(auto &n : nums)tmp += (n >> i) & 1;
            ans |= (tmp % 3) << i;
        }
        return ans;
    }
};

0138

class Solution {
public:
    unordered_map<Node*, Node*>mp;
    Node *copyRandomList(Node *head) {
        if(!head) return nullptr;
        if(mp[head] != nullptr) return mp[head];
        mp[head] = new Node(head->val);
        mp[head]->next = copyRandomList(head->next);
        mp[head]->random = copyRandomList(head->random);
        return mp[head];
    }
};

0139

class Solution {
public:
    bool dp[1010];
    bool wordBreak(string s, vector<string>& wordDict) {
        dp[0] = true;
        for(int i = 1; i <= s.size(); i++) {
            for(int j = 0; j < i; j++) {
                if(dp[j]) {
                    string tmp = s.substr(j, i - j);
                    if(find(wordDict.begin(), wordDict.end(), tmp) != wordDict.end()){ dp[i] = true; break; }
                }
            }
        }
        return dp[s.size()];
    }
};

0141

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(!head || !head->next)return false;
        ListNode *slow = head, *fast = head;
        slow = slow->next, fast = fast->next->next;
        while(slow && fast && fast->next && slow != fast)slow = slow->next, fast = fast->next->next;
        if(!slow || !fast || slow != fast)return false;
        else return true;
    }
};

0142

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(!head)return head;
        ListNode *slow = head, *fast = head, *ans = head;
        while (fast->next && fast->next->next) {
            slow = slow->next, fast = fast->next->next;
            if (slow == fast) {
                while(slow != ans) {
                    slow  = slow->next;
                    ans = ans->next;
                }
                return ans;
            }
        }
        return nullptr;
    }
};

0143

class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head || !head->next)return;
        ListNode*l1 = head, *l2 = head->next;
        while(l2 && l2->next)l1 = l1->next, l2 = l2->next->next;
        ListNode n(0);
        n.next = l1->next;
        l1->next = nullptr;
        ListNode *pre = &n, *cur = n.next;
        while(cur->next) {
            ListNode *tmp = pre->next;
            pre->next = cur->next;
            cur->next = cur->next->next;
            pre->next->next = tmp;
        }
        for (l1 = head, l2 = n.next; l1; ) {
            auto tmp = l1->next;
            l1 = l1->next = l2;
            l2 = tmp;
        }
    }
};