• Leetcode刷题笔记--Hot61-70

    目录

    1--课程表（207）

    2--实现Trie（前缀树）（208）

    3--数组中的第K个最大的元素（215）

    4--最大正方形（221）

    5--翻转二叉树（226）

    6--回文链表（234）

    7--二叉树的最近公共祖先（236）

    8--除自身以外数组的乘积（238）

    9--滑动窗口最大值（239）

    10--搜索二维矩阵II（240）

    1--课程表（207）

    主要思路：

            用 in 记录每一门课程剩余的先修课程个数，当剩余先修课程个数为0时，将该课程加入到队列q中。

            每修队列q中的课程，以该课程作为先修课程的所有课程，其剩余先修课程个数减1；

            不断将剩余先修课程数为0的课程加入到队列q中，当队列为空时，若修的课程数等于总课程数，则返回true，否则返回false；

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. class Solution {
    6. public:
    7.     bool canFinish(int numCourses, std::vectorint>>& prerequisites) {
    8.         std::vectorint>> out; // 存储每一个先修课程对应的课程
    9.         std::vector<int> in; // 存储每一个课程对应的剩余先修课程的个数
    10.         std::queue<int> q; // 存储可以修的课程
    11.  
    12.         out.resize(numCourses);
    13.         in.resize(numCourses);
    14.  
    15.         // 初始化
    16.         for(auto pair : prerequisites){
    17.             int cur = pair[0]; // 当前课程
    18.             int pre = pair[1]; // 当前课程的先修课程
    19.             out[pre].push_back(cur); // 初始化out
    20.             in[cur]++;
    21.         }
    22.  
    23.         // 选取可以直接修的课程加入到队列q中
    24.         for(int i = 0; i < numCourses; i++){
    25.             if(in[i] == 0) q.push(i);
    26.         }
    27.  
    28.         int num = 0; // 已经修过的课程数
    29.         while(!q.empty()){
    30.             int tmp = q.front(); // 修弹出的课程
    31.             q.pop();
    32.             num++;
    33.             // 以tmp作为先修课程的课程，其剩余的先修课程数减1
    34.             for(auto course : out[tmp]){
    35.                 in[course] --;
    36.                 if(in[course] == 0) q.push(course); // course没有需要先修的课程了，因此可以加入到队列q中
    37.             }
    38.         }
    39.         if(num == numCourses) return true;
    40.         else return false;
    41.     }
    42. };
    43.  
    44. int main(int argc, char* argv[]){
    45.     // numCourses = 2, prerequisites = [[1,0],[0,1]]
    46.     std::vectorint>> test = {{1, 0}, {0, 1}};
    47.     int numCourses = 2;
    48.     Solution S1;
    49.     bool res = S1.canFinish(numCourses, test);
    50.     if(res) std::cout << "true" << std::endl;
    51.     else std::cout << "false" << std::endl;
    52.     return 0;
    53. }

    2--实现Trie（前缀树）（208）

    主要思路：

            参考之前的笔记：前缀树的实现

    3--数组中的第K个最大的元素（215）

    主要思路：

            基于随机化的快排（即随机选取基准元素）划分数组，其时间复杂度为O(n)；

            根据第K个最大的元素在哪一个数组，继续递归随机化快排，直到找到第K个最大的元素。

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. class Solution {
    6. public:
    7.     int findKthLargest(std::vector<int>& nums, int k){
    8.         return quickSelect(nums, k);
    9.     }
    10.  
    11.     int quickSelect(std::vector<int>& nums, int k){
    12.         std::vector<int> large;
    13.         std::vector<int> equal;
    14.         std::vector<int> less;
    15.  
    16.         // 随机选取基准元素
    17.         int pivot = nums[rand() % nums.size()]; // 返回[0, nums.size()-1]范围内的一个随机数
    18.         for(int num : nums){
    19.             if(num > pivot) large.push_back(num);
    20.             else if(num == pivot) equal.push_back(num);
    21.             else less.push_back(num);
    22.         }
    23.  
    24.         // large, equal, less
    25.         // 第k大的元素在large中
    26.         if(k <= large.size()) return quickSelect(large, k);
    27.         // 第k大的元素在less中
    28.         else if(k > (nums.size() - less.size())) return quickSelect(less, k-(nums.size() - less.size()));
    29.         else return pivot;
    30.     }
    31. };
    32.  
    33. int main(int argc, char *argv[]){ 
    34.     // [3, 2, 1, 5, 6, 4], k = 2
    35.     std::vector<int> test = {3, 2, 1, 5, 6, 4};
    36.     int k = 2;
    37.     Solution S1;
    38.     int res = S1.findKthLargest(test, k);
    39.     std::cout << res << std::endl;
    40.     return 0;
    41. }

    4--最大正方形（221）

    主要思路：

            基于动态规划，dp[i][j]表示以(i, j)为右下角，所构成正方形的最大边长。

            状态转移方程: dp[i][j] = std::min(dp[i-1][j-1], std::min(dp[i-1][j], dp[i][j-1])) + 1;

            具体推导参考: 统计全为 1 的正方形子矩阵

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int maximalSquare(std::vectorchar>>& matrix) {
    7.         // dp[i][j]表示以(i, j)作为右下角构成正方形的最大边长
    8.         std::vectorint>> dp(matrix.size(), std::vector<int>(matrix[0].size(), 0));
    9.         // 初始化
    10.         int max = 0;
    11.         for(int i = 0; i < matrix.size(); i++){
    12.             if(matrix[i][0] == '1'){
    13.                 dp[i][0] = 1;
    14.                 max = 1;
    15.             }
    16.         }
    17.         for(int j = 0; j < matrix[0].size(); j++){
    18.             if(matrix[0][j] == '1'){
    19.                 dp[0][j] = 1;
    20.                 max = 1;
    21.             }
    22.         }
    23.         for(int i = 1; i < matrix.size(); i++){
    24.             for(int j = 1; j < matrix[0].size(); j++){
    25.                 if(matrix[i][j] == '1'){
    26.                     dp[i][j] = std::min(dp[i-1][j-1], std::min(dp[i-1][j], dp[i][j-1])) + 1;
    27.                 }
    28.                 max = std::max(max, dp[i][j]);
    29.             }
    30.         }
    31.         return max * max; // 返回面积
    32.     }
    33. };
    34.  
    35. int main(int argc, char *argv[]){ 
    36.     // matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
    37.     std::vectorchar>> test = {{'1', '0', '1', '0', '0'}, {'1', '0', '1', '1', '1'}, 
    38.                                            {'1', '1', '1', '1', '1'}, {'1', '0', '0', '1', '0'}};
    39.     Solution S1;
    40.     int res = S1.maximalSquare(test);
    41.     std::cout << res << std::endl;
    42.     return 0;
    43. }

    5--翻转二叉树（226）

    主要思路：

            递归交换左右子树即可。

    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* invertTree(TreeNode* root) {
    17.         return dfs(root);
    18.     }
    19.  
    20.     TreeNode* dfs(TreeNode* root){
    21.         if(root == nullptr) return nullptr;
    22.         TreeNode* left = dfs(root->right);
    23.         TreeNode* right = dfs(root->left);
    24.         root->left = left;
    25.         root->right = right;
    26.         return root;
    27.     }
    28. };
    29.  
    30. int main(int argc, char *argv[]){ 
    31.     // root = [4, 2, 7, 1, 3, 6, 9]
    32.     TreeNode *Node1 = new TreeNode(4);
    33.     TreeNode *Node2 = new TreeNode(2);
    34.     TreeNode *Node3 = new TreeNode(7);
    35.     TreeNode *Node4 = new TreeNode(1);
    36.     TreeNode *Node5 = new TreeNode(3);
    37.     TreeNode *Node6 = new TreeNode(6);
    38.     TreeNode *Node7 = new TreeNode(9);
    39.  
    40.     Node1->left = Node2;
    41.     Node1->right = Node3;
    42.     Node2->left = Node4;
    43.     Node2->right = Node5;
    44.     Node3->left= Node6;
    45.     Node3->right = Node7;
    46.  
    47.     Solution S1;
    48.     TreeNode *res = S1.invertTree(Node1);
    49.     // 层次遍历打印
    50.     std::queue q;
    51.     q.push(res);
    52.     while(!q.empty()){
    53.         TreeNode* top = q.front();
    54.         q.pop();
    55.         std::cout << top->val << " ";
    56.         if(top->left != nullptr) q.push(top->left);
    57.         if(top->right != nullptr) q.push(top->right);
    58.     }
    59.     std::cout << std::endl;
    60.     return 0;
    61. }

    6--回文链表（234）

    主要思路：

            基于快慢指针，将链表划分为两部分，判断两部分是否相同即可。

            其中第一部分为链表的前半部分，在快慢指针遍历的时候需要重构链表，将指针前指。

    1. #include 
    2. #include 
    3.  
    4. struct ListNode {
    5.     int val;
    6.     ListNode *next;
    7.     ListNode() : val(0), next(nullptr) {}
    8.     ListNode(int x) : val(x), next(nullptr) {}
    9.     ListNode(int x, ListNode *next) : val(x), next(next) {}
    10. };
    11.  
    12. class Solution {
    13. public:
    14.     bool isPalindrome(ListNode* head) {
    15.         // 1 2 2 1
    16.         // 1 2 1 2 1  
    17.         ListNode* slow = head;
    18.         ListNode* fast = head->next;
    19.         ListNode* pre = nullptr;
    20.         ListNode* next = nullptr;
    21.         while(fast != nullptr){
    22.             // 前指
    23.             next = slow->next;
    24.             slow->next = pre;
    25.             pre = slow;
    26.             slow = next;
    27.  
    28.             fast = fast->next;
    29.             if(fast == nullptr){
    30.                 break;
    31.             }
    32.             fast = fast->next;  
    33.             if(fast == nullptr){
    34.                 slow = slow->next;
    35.             }  
    36.         }
    37.         while(slow != nullptr && pre != nullptr){
    38.             if(slow->val != pre->val) return false;
    39.             slow = slow->next;
    40.             pre = pre->next;
    41.         }
    42.         return true;
    43.     }
    44. };
    45.  
    46. int main(int argc, char *argv[]){ 
    47.     // head = [1, 2, 1, 2, 1]
    48.     ListNode *Node1 = new ListNode(1);
    49.     ListNode *Node2 = new ListNode(2);
    50.     ListNode *Node3 = new ListNode(1);
    51.     ListNode *Node4 = new ListNode(2);
    52.     ListNode *Node5 = new ListNode(1);
    53.  
    54.     Node1->next = Node2;
    55.     Node2->next = Node3;
    56.     Node3->next = Node4;
    57.     Node4->next = Node5;
    58.  
    59.     Solution S1;
    60.     bool res = S1.isPalindrome(Node1);
    61.     if(res) std::cout << "true" << std::endl;
    62.     else std::cout << "false" << std::endl;
    63.  
    64.     return 0;
    65. }

    7--二叉树的最近公共祖先（236）

    主要思路：

            经典二叉数递归搜索。之前笔记分析过很多次了，主要思想就是递归找到目标节点，返回即可。

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

    8--除自身以外数组的乘积（238）

    主要思路：

            遍历两遍，第一遍求解L[i]，L[i]表示第i位左边所有数的乘积；第二遍求解R[i]，R[i]表示第i位右边所有数的乘积。

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     std::vector<int> productExceptSelf(std::vector<int>& nums) {
    7.         // 先计算L[i], L[i]表示第i位左边所有数的乘积
    8.         std::vector<int> res(nums.size(), 0);
    9.         res[0] = 1;
    10.         for(int i = 1; i < nums.size(); i++){
    11.             res[i] = res[i-1] * nums[i-1];
    12.         }
    13.         // 再计算R[i], R[i]表示第i位右边所有数的乘积
    14.         int R = 1;
    15.         for(int i = nums.size() - 1; i >= 0; i--){
    16.             res[i] = res[i] * R;
    17.             R = R*nums[i];
    18.         }
    19.         return res;
    20.     }
    21. };
    22.  
    23. int main(int argc, char argv[]){
    24.     // nums = [1, 2, 3, 4]
    25.     std::vector<int> test = {1, 2, 3, 4};
    26.     Solution S1;
    27.     std::vector<int> res = S1.productExceptSelf(test);
    28.     for(int num : res) std::cout << num << " ";
    29.     std::cout << std::endl;
    30.     return 0;
    31. }

    9--滑动窗口最大值（239）

    主要思路：

            经典单调队列，二刷一次过！！

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. class Solution {
    6. public:
    7.     std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
    8.         std::deque<int> max;
    9.         std::vector<int> res;
    10.         for(int i = 0; i < k; i++){
    11.             if(max.empty()) max.push_back(nums[i]);
    12.             else{
    13.                 while(!max.empty() && nums[i] > max.back()){ // 弹出不可能成为最大值的值
    14.                     max.pop_back();
    15.                 }
    16.                 max.push_back(nums[i]);
    17.             }
    18.         }
    19.         for(int i = k; i < nums.size(); i++){
    20.             res.push_back(max.front());
    21.             int left_val = nums[i - k];
    22.             if(left_val == max.front()){ // 判断当前离开窗口的值是否等于队头的值
    23.                 max.pop_front();  
    24.             }
    25.             while(!max.empty() && nums[i] > max.back()){ // 弹出比当前准备进队值要小的元素
    26.                 max.pop_back();
    27.             }
    28.             max.push_back(nums[i]);
    29.         }
    30.         res.push_back(max.front());
    31.         return res;
    32.     }
    33. };
    34.  
    35. int main(int argc, char argv[]){
    36.     // nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
    37.     int k = 3;
    38.     std::vector<int> test = {1, 3, -1, -3, 5, 3, 6, 7};
    39.     Solution S1;
    40.     std::vector<int> res = S1.maxSlidingWindow(test, k);
    41.     for(auto num : res){
    42.         std::cout << num << " ";
    43.     }
    44.     std::cout << std::endl;
    45.     return 0;
    46. }

    10--搜索二维矩阵II（240）

    主要思路：

            从右上角开始搜索，当matrix[x][y] > target 时，y--；当matrix[x][y] < target时，x++；当matrix[x][y] == target时，返回true；

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     bool searchMatrix(std::vectorint>>& matrix, int target) {
    7.         int m = matrix.size(), n = matrix[0].size();
    8.         // 从右上角开始搜索
    9.         int x = 0, y = n - 1;
    10.         while(x < m && y >= 0){
    11.             if(matrix[x][y] == target) return true;
    12.             else if(matrix[x][y] > target) y--;
    13.             else x++; // matrix[x][y] < target
    14.         }
    15.         return false;
    16.     }
    17. };
    18.  
    19. int main(int argc, char* argv[]){
    20.     // matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
    21.     std::vectorint>> test = {{1, 4, 7, 11, 15}, {2, 5, 8, 12, 19},
    22.                          {3, 6, 9, 12, 19}, {10, 13, 14, 17, 24}, {18, 21, 23, 26, 30}};
    23.     int target = 5;
    24.     Solution S1;
    25.     bool res = S1.searchMatrix(test, target);
    26.     if(res) std::cout << "true" << std::endl;
    27.     else std::cout << "false" << std::endl;
    28.     return 0;
    29. }

  • 相关阅读:
    C++ Reference: Standard C++ Library reference: C Library: cwchar: wcsncpy
    多标签页文件管理器 - Win系统
    阴影进阶，实现更加的立体的阴影效果！
    MongoDB的介绍和使用
    RabbitMQ学习笔记——消息转化器
    Network: use `--host` to expose
    Leetcode中等：137. 只出现一次的数字II
    python实现冒泡排序
    (四)线性插值
    【原创】辟谣，实测MyBatisPlus批量新增更新方法确实有效，且可单独使用无需跟随IService
  • 原文地址：https://blog.csdn.net/weixin_43863869/article/details/133829342