[数据结构与算法]LeetCode HOT 100 --- 2021/7/28

两数之和

两数之和

有效的括号

分析：
??利用栈判断括号是否合法：遍历括号序列，遇到左括号进栈，遇到右括号出栈匹配。
代码：

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for(int i = 0; i < s.size(); i++) {
            char temp = s[i];
            if(temp == '(' || temp == '[' || temp == '{') {
                st.push(temp);
            }else {
                if(st.empty()) {
                    return false;
                }else {
                    char mat = st.top();
                    st.pop();
                    char a[2];
                    a[0] = mat, a[1] = temp;
                    string x(a, a + 2);
                    if(x == "()" || x == "{}" || x == "[]") {
                        continue;
                    }else {
                        return false;
                    }
                }
            }
        }
        if(st.empty()) {
            return true;
        }else {
            return false;
        }
    }
};

合并两个有序链表

合并两个有序链表

最大子序和

剑指 Offer 42. 连续子数组的最大和

爬楼梯

爬楼梯

二叉树的中序遍历

分析：
??二叉树的中序遍历。
代码：

/**
 * 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> inorderTraversal(TreeNode* root) {
        if(root) {
            inorderTraversal(root->left);
            res.push_back(root->val);
            inorderTraversal(root->right);
        }else {
            return res;
        }
        return res;
    }
};

对称二叉树

分析：
??利用队列：初始时将根节点入队两次，当队列不为空时：出队两次得到节点p和q，比较pq是否一致，不一致返回false，否则依次将p->left、q->right、p->right、q->left入队（对称性）。
代码：

/**
 * 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:
    bool check(TreeNode* u, TreeNode* v) {
        queue<TreeNode*> que;
        que.push(u);
        que.push(v);
        while(!que.empty()) {
            TreeNode* p = que.front();
            que.pop();
            TreeNode* q = que.front();
            que.pop();
            if(p == NULL && q == NULL) {
                continue;
            }
            if(p == NULL || q == NULL || p->val != q->val) {
                return false;
            }
            que.push(p->left);
            que.push(q->right);
            que.push(p->right);
            que.push(q->left);  
        }
        return true;
    }
    
    bool isSymmetric(TreeNode* root) {
        return check(root, root);
    }
};

二叉树的最大深度

剑指 Offer 55 - I. 二叉树的深度

买卖股票的最佳时机

剑指 Offer 63. 股票的最大利润

只出现一次的数字

只出现一次的数

环形链表

方法一：
??遍历链表的所有节点，如果当前节点在集合中，说明访问到了之前访问过的节点，必然存在环，否则就将该节点加入集合。
代码：

/**
 * 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) {
        unordered_set<ListNode*> st;
        while(head) {
            if(st.count(head) != 0) {
                return true;
            }
            st.insert(head);
            head = head->next;
        }
        return false;
    }
};

方法二：
??参考官方题解：具体地，我们定义两个指针，一快一满。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。
代码：

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

最小栈

剑指 Offer 30. 包含min函数的栈

相交链表

剑指 Offer 52. 两个链表的第一个公共节点

多数元素

剑指 Offer 39. 数组中出现次数超过一半的数字

翻转二叉树

剑指 Offer 27. 二叉树的镜像

回文链表

方法一：
??暴力模拟：先保存好链表中所有节点的值，随后判断是否是回文链表。
代码：

/**
 * 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:
    bool isPalindrome(ListNode* head) {
        vector<int> res;
        while(head) {
            res.push_back(head->val);
            head = head->next;
        }
        for(int i = 0, j = res.size() - 1; i < j; i++, j--) {
            if(res[i] != res[j]) {
                return false;
            }
        }
        return true;
    }
};

方法二：
??参考官方题解：我们将链表后半部分翻转，比如链表原来为1->2->3->4->5->null，翻转后变为1->2->3<-4<-5，翻转后再判断是否为回文链表。具体来说，第一步：寻找到中间节点，可用利用快慢指针，慢指针一次走一步，快指针一次走两步，快慢指针同时出发，当快指针移动到链表的末尾时，慢指针恰好到链表的中间，最后通过慢指针将链表分为两部分。第二步：将后半部分翻转。第三部分：比较。第四部分：恢复。
代码：

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head == nullptr) {
            return true;
        }

        // 找到前半部分链表的尾节点并反转后半部分链表
        ListNode* firstHalfEnd = endOfFirstHalf(head);
        ListNode* secondHalfStart = reverseList(firstHalfEnd->next);

        // 判断是否回文
        ListNode* p1 = head;
        ListNode* p2 = secondHalfStart;
        bool result = true;
        while (result && p2 != nullptr) {
            if (p1->val != p2->val) {
                result = false;
            }
            p1 = p1->next;
            p2 = p2->next;
        }        

        // 还原链表并返回结果
        firstHalfEnd->next = reverseList(secondHalfStart);
        return result;
    }

    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr != nullptr) {
            ListNode* nextTemp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    ListNode* endOfFirstHalf(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast->next != nullptr && fast->next->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
};

比特位计数

方法一：
??利用bitset将整数转为二进制形式的字符串，再计数。
代码：

class Solution {
public:
    
    int get(int n) {
        int res = 0;
        while(n) {
            if(n % 2 == 1) {
                res++;
            }
            n /= 2;
        }
        return res;
    }
    
    vector<int> countBits(int n) {
        vector<int> res;
        for(int i = 0; i <= n; i++) {
            res.push_back(get(i));
        }
        return res;
    }
};

方法二：
??x = x & (x - 1)会将x最低位的1变为0，可以利用该方法统计1的个数。
代码：

class Solution {
public:
    
    int get(int n) {
        int res = 0;
        while(n) {
            n = n & (n - 1);
            res++;
        }
        return res;
    }
    
    vector<int> countBits(int n) {
        vector<int> res;
        for(int i = 0; i <= n; i++) {
            res.push_back(get(i));
        }
        return res;
    }
};

找到所有数组中消失的数字

方法一：
??暴力求解。
代码：

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        //暴力
        int n = nums.size();
        unordered_map<int, int> mp;
        vector<int> res;
        for(int i = 0; i < n; i++) {
            mp[nums[i]]++;
        }
        for(int i =1; i <= n; i++) {
            if(mp.count(i) == 0) {
                res.push_back(i);
            }
        }
        return res;
    }
};

方法二：
??原地修改：见代码注释。
代码：

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int n = nums.size();
        vector<int> res;
        for(int x : nums) {
            int k = (x - 1) % n;
            nums[k] += n;   //被加表示k + 1出现过
        }
        for(int i =0; i < n; i++) {
            if(nums[i] <= n) {
                res.push_back(i + 1);
            }
        }
        return res;
    }
};

汉明距离

方法一：
??bitset。
代码：

class Solution {
public:
    int hammingDistance(int x, int y) {
        bitset<32> p(x), q(y);
        string m = p.to_string(), n = q.to_string();
        int res = 0;
        for(int i = 0; i < 32; i++) {
            if(m[i] != n[i]) {
                res++;
            }
        }
        return res;
    }
};

分析：
??x ^ y中1的个数即为汉明距离，__builtin_popcount用于统计1的个数。
代码：

class Solution {
public:
    int hammingDistance(int x, int y) {
        return __builtin_popcount(x ^ y);
    }
};

二叉树的直径

分析：
??求出以某个节点为父节点的左右子树的高度L和R，最终结果即为所有节点L + R的最大值。
代码：

/**
 * 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:
    int ans = 0;
    int depth(TreeNode* rt) {
        if(rt == NULL) {
            return 0;
        }
        int left = depth(rt->left);
        int right = depth(rt->right);
        ans = max(left + right, ans);
        return max(left, right) + 1;//返回深度
    }
    int diameterOfBinaryTree(TreeNode* root) {
        depth(root);
        return ans;
    }
};