LeetCode HOT 100 --- 2021/7/28

本是古典何须时尚 2022-09-01 13:48 21阅读 0赞

### 目录 ###

*  两数之和
 *  有效的括号
 *  合并两个有序链表
 *  最大子序和
 *  爬楼梯
 *  二叉树的中序遍历
 *  对称二叉树
 *  二叉树的最大深度
 *  买卖股票的最佳时机
 *  只出现一次的数字
 *  环形链表
 *  最小栈
 *  相交链表
 *  多数元素
 *  翻转二叉树
 *  回文链表
 *  比特位计数
 *  找到所有数组中消失的数字
 *  汉明距离
 *  二叉树的直径

# 两数之和 #

[两数之和][Link 1]

# 有效的括号 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70]  
分析：  
  利用栈判断括号是否合法：遍历括号序列，遇到左括号进栈，遇到右括号出栈匹配。  
代码：

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;
            }
        }
    };

# 合并两个有序链表 #

[合并两个有序链表][Link 2]

# 最大子序和 #

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

# 爬楼梯 #

[爬楼梯][Link 2]

# 二叉树的中序遍历 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 1]  
分析：  
  二叉树的中序遍历。  
代码：

# 对称二叉树 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 2]  
分析：  
  利用队列：初始时将根节点入队两次，当队列不为空时：出队两次得到节点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 55 - I.]

# 买卖股票的最佳时机 #

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

# 只出现一次的数字 #

[只出现一次的数][Link 3]

# 环形链表 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 3]  
方法一：  
  遍历链表的所有节点，如果当前节点在集合中，说明访问到了之前访问过的节点，必然存在环，否则就将该节点加入集合。  
代码：

/** * 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 42.]

# 相交链表 #

[剑指 Offer 52. 两个链表的第一个公共节点][Offer 55 - I.]

# 多数元素 #

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

# 翻转二叉树 #

[剑指 Offer 27. 二叉树的镜像][Offer 42.]

# 回文链表 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 4]  
方法一：  
  暴力模拟：先保存好链表中所有节点的值，随后判断是否是回文链表。  
代码：

/** * 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;
        }
    };

# 比特位计数 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 5]  
方法一：  
  利用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;
        }
    };

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 6]  
方法一：  
  暴力求解。  
代码：

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;
        }
    };

# 汉明距离 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 7]  
方法一：  
  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);
        }
    };

# 二叉树的直径 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 8]  
分析：  
  求出以某个节点为父节点的左右子树的高度L和R，最终结果即为所有节点L + R的最大值。  
代码：

[Link 1]: https://blog.csdn.net/Cyril_KI/article/details/119120150
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70]: /images/20220829/b665cfac30dd46a5b4ffadf6420028b0.png
[Link 2]: https://blog.csdn.net/Cyril_KI/article/details/118827493
[Offer 42.]: https://blog.csdn.net/Cyril_KI/article/details/118863971
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 1]: /images/20220829/2b025c4b89f645d0815bf27816e540e5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 2]: /images/20220829/c9e66e418dda48a99e9363c57008fd71.png
[Offer 55 - I.]: https://blog.csdn.net/Cyril_KI/article/details/118890177
[Offer 63.]: https://blog.csdn.net/Cyril_KI/article/details/119028893
[Link 3]: https://blog.csdn.net/Cyril_KI/article/details/118853036
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 3]: /images/20220829/043f6244a9e4451ab76956be2a714bc8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 4]: /images/20220829/fe3002fbe34d463397414edcd59f43f9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 5]: /images/20220829/692ce69435ee4e3fa2aa5842ba156984.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 6]: /images/20220829/bda3b687a6fe41c784daf4a8106834fd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 7]: /images/20220829/063b05965db9426d9fb2698259a3048e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 8]: /images/20220829/d79528ab08a94a619207ea18f895b497.png