• Leetcode刷题笔记--Hot41-50

    目录

    1--二叉树的层序遍历（102）

    2--二叉树的最大深度（104）

    3--从前序与中序遍历序列构造二叉树（105）

    4--二叉树展开为链表（114）

    5--买卖股票的最佳时机（121）

    6--二叉树中的最大路径和（124）

    7--最长连续序列（128）

    8--只出现一次的数字（136）

    9--单词拆分（139）

    10--环形链表（141）

    1--二叉树的层序遍历（102）

    主要思路：

            经典广度优先搜索，基于队列；

            对于本题需要将同一层的节点放在一个数组中，因此遍历的时候需要用一个变量 nums 来记录当前层的节点数，即 nums 等于队列元素的数目；

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. struct TreeNode {
    6.     int val;
    7.     TreeNode *left;
    8.     TreeNode *right;
    9.     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    10.     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    11.     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    12. };
    13.  
    14. class Solution {
    15. public:
    16.     std::vectorint>> levelOrder(TreeNode* root) {
    17.         std::vectorint>> res;
    18.         if(root == nullptr) return res;
    19.         std::queue q;
    20.         q.push(root);
    21.         while(!q.empty()){
    22.             int nums = q.size(); // 当前层的节点数
    23.             std::vector<int> tmp;
    24.             while(nums > 0){ // 遍历处理同一层
    25.                 TreeNode *cur = q.front();
    26.                 q.pop();
    27.                 tmp.push_back(cur->val);
    28.  
    29.                 if(cur->left != nullptr) q.push(cur->left);
    30.                 if(cur->right != nullptr) q.push(cur->right);
    31.                 
    32.                 nums--;
    33.             }
    34.             res.push_back(tmp); // 记录当前层的元素
    35.         }
    36.         return res;
    37.     }
    38. };
    39.  
    40. int main(int argc, char* argv[]){
    41.     // root = [1, null, 2, 3]
    42.     TreeNode *Node1 = new TreeNode(3);
    43.     TreeNode *Node2 = new TreeNode(9);
    44.     TreeNode *Node3 = new TreeNode(20);
    45.     TreeNode *Node4 = new TreeNode(15);
    46.     TreeNode *Node5 = new TreeNode(7);
    47.     Node1->left = Node2;
    48.     Node1->right = Node3;
    49.     Node3->left = Node4;
    50.     Node3->right = Node5;
    51.  
    52.     Solution S1;
    53.     std::vectorint>> res = S1.levelOrder(Node1);
    54.     for(auto item : res) {
    55.         for (int v : item) std::cout << v << " ";
    56.         std::cout << std::endl;
    57.     }
    58.     return 0;
    59. }

    2--二叉树的最大深度（104）

    主要思路：

            递归计算左右子树的深度，选取两者最大值 +1 返回；

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. struct TreeNode {
    6.     int val;
    7.     TreeNode *left;
    8.     TreeNode *right;
    9.     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    10.     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    11.     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    12. };
    13.  
    14. class Solution {
    15. public:
    16.     int maxDepth(TreeNode* root) {
    17.         if(root == nullptr) return 0;
    18.         int res = dfs(root);
    19.         return res;
    20.     }
    21.  
    22.     int dfs(TreeNode* root){
    23.         if(root == nullptr) return 0;
    24.         int left_height = dfs(root->left);
    25.         int right_height = dfs(root->right);
    26.         int cur_height = std::max(left_height, right_height) + 1;
    27.         return cur_height;
    28.     }
    29. };
    30.  
    31. int main(int argc, char* argv[]){
    32.     // root = [3,9,20,null,null,15,7]
    33.     TreeNode *Node1 = new TreeNode(3);
    34.     TreeNode *Node2 = new TreeNode(9);
    35.     TreeNode *Node3 = new TreeNode(20);
    36.     TreeNode *Node4 = new TreeNode(15);
    37.     TreeNode *Node5 = new TreeNode(7);
    38.  
    39.     Node1->left = Node2;
    40.     Node1->right = Node3;
    41.     Node3->left = Node4;
    42.     Node3->right = Node5;
    43.  
    44.     Solution S1;
    45.     int res = S1.maxDepth(Node1);
    46.     std::cout << res << std::endl;
    47.     return 0;
    48. }

    3--从前序与中序遍历序列构造二叉树（105）

    主要思路：

            思路类似于根据中序和后序遍历来构建二叉树；

            对于本题，前序遍历的顺序是：根→左→右，则前序遍历的第一个节点是根节点；

            中序遍历的顺序是：左→根→右，遍历中序数组找到根节点的位置，根据根节点的位置划分左右子树；

            根据左右子树的大小划分前序遍历得到前序遍历的左右子树，递归构建左右子树即可；

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. struct TreeNode {
    6.     int val;
    7.     TreeNode *left;
    8.     TreeNode *right;
    9.     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    10.     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    11.     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    12. };
    13.  
    14. class Solution {
    15. public:
    16.     TreeNode* buildTree(std::vector<int>& preorder, std::vector<int>& inorder) {
    17.         TreeNode* res = dfs(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);
    18.         return res;
    19.     }
    20.  
    21.     TreeNode* dfs(std::vector<int>& preorder, int p_st, int p_en, std::vector<int>& inorder, int i_st, int i_en){
    22.         if(p_st > p_en || i_st > i_en){
    23.             return nullptr;
    24.         }
    25.  
    26.         // 头结点
    27.         TreeNode *root = new TreeNode(preorder[p_st]);
    28.         // 划分中序
    29.         int pos = -1; // 中序遍历中根节点的位置索引
    30.         for(int i = i_st; i <= i_en; i++){
    31.             if(inorder[i] == root->val){
    32.                 pos = i;
    33.                 break;
    34.             }
    35.         }
    36.         // 左子树的大小
    37.         int left_size = pos - i_st;
    38.         // 右子树的大小
    39.         int right_size = i_en - pos;
    40.  
    41.         root->left = dfs(preorder, p_st+1, p_st+left_size, inorder, i_st, pos-1);
    42.         root->right = dfs(preorder, p_st+left_size+1, p_en, inorder, pos+1, i_en);
    43.         return root;
    44.     }
    45. };
    46.  
    47. int main(int argc, char* argv[]){
    48.     // preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
    49.     std::vector<int> preorder = {3, 9, 20, 15, 7};
    50.     std::vector<int> inorder = {9, 3, 15, 20, 7};
    51.     
    52.     Solution S1;
    53.     TreeNode* res = S1.buildTree(preorder, inorder);
    54.  
    55.     // 层次遍历打印
    56.     std::queue q;
    57.     q.push(res);
    58.     while(!q.empty()){
    59.         TreeNode* tmp = q.front();
    60.         q.pop();
    61.         std::cout << tmp->val << " ";
    62.         if(tmp->left != nullptr) q.push(tmp->left);
    63.         if(tmp->right != nullptr) q.push(tmp->right);
    64.     }
    65.     std::cout << std::endl;
    66.     return 0;
    67. }

    4--二叉树展开为链表（114）

    主要思路：

            根据前序遍历的顺序，遍历二叉树，使用一个指针表示当前遍历到的节点的前驱节点，例如图中 2 的前驱节点是 1，4 的前驱节点是 3（根据前序遍历）；

            将前驱节点的左孩子为 nullptr，右孩子为当前遍历到的节点；根据前序遍历的顺序，递归更新前驱节点、左孩子和右孩子即可；

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. struct TreeNode {
    6.     int val;
    7.     TreeNode *left;
    8.     TreeNode *right;
    9.     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    10.     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    11.     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    12. };
    13.  
    14. class Solution {
    15. public:
    16.     void flatten(TreeNode* root) {
    17.         dfs(root);
    18.     }
    19.  
    20.     void dfs(TreeNode* cur){
    21.         if(cur == nullptr) return;
    22.         pre->left = nullptr; // 前驱节点的左孩子指向 nullptr
    23.         // 根
    24.         pre->right = cur; // 前驱节点的右孩子指向当前遍历到的节点
    25.         pre = cur; // 更新前驱节点
    26.  
    27.         TreeNode* left = cur->left;
    28.         TreeNode* right = cur->right;
    29.  
    30.         dfs(left); // 递归处理左子树
    31.         dfs(right); // 递归处理右子树
    32.     }
    33. private:
    34.     TreeNode* pre = new TreeNode(-1); // 前序遍历的前驱节点
    35. };
    36.  
    37. int main(int argc, char* argv[]){
    38.     // root = [1,2,5,3,4,null,6]
    39.     TreeNode* Node1 = new TreeNode(1);
    40.     TreeNode* Node2 = new TreeNode(2);
    41.     TreeNode* Node3 = new TreeNode(5);
    42.     TreeNode* Node4 = new TreeNode(3);
    43.     TreeNode* Node5 = new TreeNode(4);
    44.     TreeNode* Node6 = new TreeNode(6);
    45.  
    46.     Node1->left = Node2;
    47.     Node1->right = Node3;
    48.     Node2->left = Node4;
    49.     Node2->right = Node5;
    50.     Node3->right = Node6;
    51.  
    52.     Solution S1;
    53.     S1.flatten(Node1);
    54.     TreeNode* tmp = Node1;
    55.     while(tmp -> right != nullptr){
    56.         std::cout << tmp->val << " ";
    57.         tmp = tmp->right;
    58.     }
    59.     std::cout << std::endl;
    60.     return 0;
    61. }

    5--买卖股票的最佳时机（121）

    主要思路：
            计算截止到第 i 天的最低买入价格和最高的利润，不断更新即可；

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int maxProfit(std::vector<int>& prices) {
    7. 		int min_cost = prices[0];
    8. 		int max_profit = 0;
    9. 		for(int i = 0; i < prices.size(); i++){
    10. 			min_cost = std::min(min_cost, prices[i]);
    11. 			max_profit = std::max(max_profit, prices[i] - min_cost);
    12. 		}
    13. 		return max_profit;
    14.     }
    15. };
    16.  
    17. int main(int argc, char *argv[]) {
    18. 	// [7, 1, 5, 3, 6, 4]
    19. 	std::vector<int> test = {7, 1, 5, 3, 6, 4};
    20. 	Solution S1;
    21. 	int res = S1.maxProfit(test);
    22. 	std::cout << res << std::endl;
    23. 	return 0;
    24. }

    6--二叉树中的最大路径和（124）

    主要思路：

            采用二叉树深度递归搜索，对于每一个结点，其最大路径和可能为以下四种情况：cur + cur->left, cur + cur->right, cur, cur + cur->left + cur->right；

            对于每一个结点，其返回给上层的最大路径，可能为以下三种情况：cur + cur->left, cur + cur->right, cur；

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. struct TreeNode {
    6.     int val;
    7.     TreeNode *left;
    8.     TreeNode *right;
    9.     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    10.     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    11.     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    12. };
    13.  
    14. class Solution {
    15. public:
    16.     int maxPathSum(TreeNode* root) {
    17. 		dfs(root);
    18. 		return max;
    19.     }
    20.  
    21. 	int dfs(TreeNode* root){
    22. 		if(root == nullptr) return 0;
    23. 		int left = dfs(root->left);
    24. 		int right = dfs(root->right);
    25. 		int cur_sum = std::max(
    26. 						std::max(
    27. 							std::max(left + root->val, right + root->val), 
    28. 								left + right + root->val),
    29. 									root->val);
    30. 		max = std::max(cur_sum, max);
    31. 		int ret_sum = std::max(std::max(left + root->val, right + root->val), root->val);
    32. 		return ret_sum;
    33. 	}
    34. private:
    35. 	int max = INT_MIN;
    36. };
    37.  
    38. int main(int argc, char *argv[]) {
    39. 	// root = [1, 2, 3]
    40. 	TreeNode* Node1 = new TreeNode(1);
    41. 	TreeNode* Node2 = new TreeNode(2);
    42. 	TreeNode* Node3 = new TreeNode(3);
    43. 	Node1->left = Node2;
    44. 	Node1->right = Node3;
    45. 	Solution S1;
    46. 	int res = S1.maxPathSum(Node1);
    47. 	std::cout << res << std::endl;
    48. 	return 0;
    49. }

    7--最长连续序列（128）

    主要思路：

            利用 unordered_set 实现元素的去重，遍历数组 nums，只处理连续序列最左边的元素（根据其上一个元素是否在 unordered_set 中存在），循环查询其下一个元素是否存在，存在则序列长度 +1；

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. class Solution {
    6. public:
    7.     int longestConsecutive(std::vector<int>& nums) {
    8. 		std::unordered_set<int> set;
    9. 		for(int & num : nums){ // 利用 unordered_set 去重
    10. 			set.insert(num);
    11. 		}
    12.  
    13. 		int max_len = 0;
    14. 		for(int i = 0; i < nums.size(); i++){
    15. 			int cur_len = 1;
    16. 			int cur_num = nums[i];
    17. 			if(set.count(cur_num - 1) == 0){ // 连续子序列左边界元素，不是左边界元素则跳过，确保每一个元素只遍历一次
    18. 				while(set.count(cur_num + 1) != 0){ // 利用 unordered_set 实现 O(1) 查询
    19. 					cur_len++; // 长度++
    20. 					cur_num = cur_num + 1; // 右移
    21. 				}
    22. 				max_len = std::max(max_len, cur_len); // 更新最大长度
    23. 			}
    24. 		}
    25. 		return max_len;
    26.     }
    27. };
    28.  
    29. int main(int argc, char *argv[]) {
    30. 	// nums = [100, 4, 200, 1, 3, 2]
    31. 	std::vector<int> test = {100, 4, 200, 1, 3, 2};
    32. 	Solution S1;
    33. 	int res = S1.longestConsecutive(test);
    34. 	std::cout << res << std::endl;
    35. 	return 0;
    36. }

    8--只出现一次的数字（136）

    主要思路：

               按位异或，出现两次的数字会两两对消，最后只剩下出现过一次的数字；     

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int singleNumber(std::vector<int>& nums) {
    7. 		int res = 0;
    8. 		for(int num : nums){
    9. 			res = res ^ num; // 按位异或
    10. 		}	
    11. 		return res;
    12.     }
    13. };
    14.  
    15. int main(int argc, char *argv[]) {
    16. 	// nums = [4, 1, 2, 1, 2]
    17. 	std::vector<int> test = {4, 1, 2, 1, 2};
    18. 	Solution S1;
    19. 	int res = S1.singleNumber(test);
    20. 	std::cout << res << std::endl;
    21. 	return 0;
    22. }

    9--单词拆分（139）

    主要思路：

            基于动态规划，dp[i] 表示字符串 s 前 i 个字符匹配（即可以由字典的字符串构建而成）；

            初始化 dp[0] = true； 

            状态转移方程为：dp[i] == dp[j] && s.substr(j, i-j)，0 <= j <= i，只要有一个情况匹配即可；

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5.  
    6. class Solution {
    7. public:
    8.     bool wordBreak(std::string s, std::vector& wordDict) {
    9. 		std::unordered_set hash;
    10. 		for(std::string str : wordDict){
    11. 			hash.insert(str);
    12. 		}
    13. 		
    14. 		std::vector<bool> dp(s.length() + 1, 0); // dp[i] 表示前 i 个字符构成的字符串匹配
    15. 		// 初始化
    16. 		dp[0] = true;
    17. 		// 遍历
    18. 		for(int i = 1; i <= s.length(); i++){
    19. 			for(int j = 0; j <= i; j++){
    20. 				if (dp[j] && hash.find(s.substr(j, i - j)) != hash.end()) { // 前 j 个字符匹配，且后 i -j 个字符也匹配 
    21.                     dp[i] = true;
    22.                     break; // 找到一种情况就 break
    23.                 }
    24. 			}
    25. 		}
    26. 		return dp[s.length()];
    27.     }
    28. };
    29.  
    30. int main(int argc, char *argv[]) {
    31. 	// s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
    32. 	std::string str = "catsandog";
    33. 	std::vector wordDict = {"cats", "dog", "sand", "and", "cat"};
    34. 	Solution S1;
    35. 	bool res = S1.wordBreak(str, wordDict);
    36. 	if(res) std::cout << "true" << std::endl;
    37. 	else std::cout << "false" << std::endl; 
    38. 	return 0;
    39. }

    10--环形链表（141）

    主要思路：

            经典快慢指针，判断两个指针是否相遇即可；

    1. #include 
    2.  
    3. struct ListNode {
    4.     int val;
    5.     ListNode *next;
    6.     ListNode(int x) : val(x), next(NULL) {}
    7. };
    8.  
    9. class Solution {
    10. public:
    11.     bool hasCycle(ListNode *head) {
    12. 		if(head == nullptr) return false;
    13.         ListNode* slow = head;
    14. 		ListNode* fast = head;
    15. 		while(fast != nullptr && fast->next != nullptr){
    16. 			fast = fast->next->next;
    17. 			slow = slow->next;
    18. 			if(fast == slow) return true;
    19. 		}
    20. 		return false;
    21.     }
    22. };
    23.  
    24. int main(int argc, char *argv[]) {
    25. 	// head = [3,2,0,-4], pos = 1
    26. 	ListNode *Node1 = new ListNode(3);
    27. 	ListNode *Node2 = new ListNode(2);
    28. 	ListNode *Node3 = new ListNode(0);
    29. 	ListNode *Node4 = new ListNode(-4);
    30.  
    31. 	Node1->next = Node2;
    32. 	Node2->next = Node3;
    33. 	Node3->next = Node4;
    34. 	Node4->next = Node2;
    35.  
    36. 	Solution S1;
    37. 	int res = S1.hasCycle(Node1);
    38. 	if(res) std::cout << "true" << std::endl;
    39. 	else std::cout << "false" << std::endl;
    40. 	return 0;
    41. }

  • 相关阅读:
    【SpringBoot项目】SpringBoot+MyBatis+MySQL电脑商城
    关于rdflib解析三元组介绍
    成都理工大学_Python程序设计_第2章
    【计算机网络】万字总结
    中国智能汽车“芯”的崛起
    Linux入门之使用 ps 查看系统进程
    一分钟学一个 Linux 命令 - cat 和 tail
    内核驱动mmap Handler利用技术（二）
    RT-Thread上部署TinyMaix推理框架，使MCU赋予AI能力
    数组array 和 &array的区别
  • 原文地址：https://blog.csdn.net/weixin_43863869/article/details/132724627