LeetCode刷题笔记(03.16-03.19)

Easy

[226] 翻转二叉树

tree

2022/03/16

/**
 * 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:
  TreeNode *invertTree(TreeNode *root) {
    if (!root) return nullptr;
    root->left = invertTree(root->left);
    root->right = invertTree(root->right);
    swap(root->left, root->right);
    return root;
    // 77/77 cases passed (0 ms)
    // Your runtime beats 100 % of cpp submissions
    // Your memory usage beats 41.71 % of cpp submissions (9.5 MB)
  }
};

[234] 回文链表

linked-list | two-pointers

2022/03/17

关于链表的反转

/**
 * 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) {
    auto slow = head, fast = head;
    while (fast) {
      fast = fast->next ? fast->next->next : fast->next;
      slow = slow->next;
    }
    if (!slow)
      return true;
    else {
      ListNode *beg = nullptr;
      ListNode *mid = slow;
      ListNode *end = slow->next;
      while (true) {
        mid->next = beg;
        if (!end) break;
        beg = mid;
        mid = end;
        end = end->next;
      }
      slow = mid;
    }
    while (head && slow) {
      if (head->val != slow->val) return false;
      head = head->next;
      slow = slow->next;
    }
    return true;
    // 86/86 cases passed (168 ms)
    // Your runtime beats 85.05 % of cpp submissions
    // Your memory usage beats 80.64 % of cpp submissions (111.3 MB)
    /* vector<int> val;
    while (head) {
      val.emplace_back(head->val);
      head = head->next;
    }
    for (int i = 0; i < val.size(); i++) {
      if (val[i] != val[val.size() - 1 - i]) {
        return false;
      }
    }
    return true; */
    // 86/86 cases passed (220 ms)
    // Your runtime beats 18.66 % of cpp submissions
    // Your memory usage beats 10.51 % of cpp submissions (125.3 MB)
  }
};

Medium

[221] 最大正方形

dynamic-programming

2022/03/16

和85题配合着看

class Solution {
 public:
  int maximalSquare(vector<vector<char>>& matrix) {
    vector<vector<int>> dp(matrix.size(), vector<int>(matrix[0].size(), 0));
    int maxSide = 0;
    for (int i = 0; i < matrix.size(); i++) {
      for (int j = 0; j < matrix[0].size(); j++) {
        dp[i][j] = matrix[i][j] - '0';
        if (i * j * dp[i][j] > 0) {
          dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
        }
        maxSide = max(maxSide, dp[i][j]);
      }
    }
    return maxSide * maxSide;
    // 77/77 cases passed (52 ms)
    // Your runtime beats 74.77 % of cpp submissions
    // Your memory usage beats 5.82 % of cpp submissions (17.8 MB)
  }
};

[236] 二叉树的最近公共祖先

tree

2022/03/17

思路

参考自代码随想录

遇到这个题目首先想的是要是能自底向上查找就好了，这样就可以找到公共祖先了。

那么二叉树如何可以自底向上查找呢？

回溯啊，二叉树回溯的过程就是从低到上。

后序遍历就是天然的回溯过程，最先处理的一定是叶子节点。

接下来就看如何判断一个节点是节点q和节点p的公共公共祖先呢。

如果找到一个节点，发现左子树出现结点p，右子树出现节点q，或者 左子树出现结点q，右子树出现节点p，那么该节点就是节点p和q的最近公共祖先。

使用后序遍历，回溯的过程，就是从低向上遍历节点，一旦发现如何这个条件的节点，就是最近公共节点了。

LCA

LCA(Least Common Ancestors)，即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先。

LCA算法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
 private:
  vector<TreeNode*> parents;
  bool search(TreeNode* root, TreeNode* node) {
    if (!root) return false;
    if (root == node) return true;
    return search(root->left, node) || search(root->right, node);
  }
  void bigSearch(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root) return;
    if (search(root, p) && search(root, q)) {
      parents.emplace_back(root);
    }
    bigSearch(root->left, p, q);
    bigSearch(root->right, p, q);
  }

 public:
  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    // LCA 问题
    if (!root) {
      return root;
    }
    if (root == p || root == q) {
      return root;
    }
    auto left = lowestCommonAncestor(root->left, p, q);
    auto right = lowestCommonAncestor(root->right, p, q);
    if (left && right) {
      return root;
    } else if (left) {
      return left;
    } else if (right) {
      return right;
    }
    return NULL;
    // 31/31 cases passed (12 ms)
    // Your runtime beats 94.44 % of cpp submissions
    // Your memory usage beats 66.43 % of cpp submissions (13.9 MB)
    /* bigSearch(root, p, q);
    return parents.back(); */
    // 31/31 cases passed (956 ms)
    // Your runtime beats 5.32 % of cpp submissions
    // Your memory usage beats 16 % of cpp submissions (16.3 MB)
  }
};

[238] 除自身以外数组的乘积

array

2022/03/19

class Solution {
 public:
  vector<int> productExceptSelf(vector<int>& nums) {
    vector<int> left(nums.size()), right(nums.size()), ans(nums.size());
    left[0] = nums[0];
    right[nums.size() - 1] = nums.back();
    for (int i = 1; i < nums.size(); i++) {
      left[i] = left[i - 1] * nums[i];
    }
    for (int i = nums.size() - 2; i >= 0; i--) {
      right[i] = right[i + 1] * nums[i];
    }
    ans[0] = right[1];
    ans[nums.size() - 1] = left[nums.size() - 2];
    for (int i = 1; i < nums.size() - 1; i++) {
      ans[i] = left[i - 1] * right[i + 1];
    }
    return ans;
    // 20/20 cases passed (20 ms)
    // Your runtime beats 72 % of cpp submissions
    // Your memory usage beats 26.42 % of cpp submissions (24.4 MB)
  }
};

[240] 搜索二维矩阵 II

binary-search | divide-and-conquer

2022/03/19

class Solution {
 public:
  bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int row = matrix.size() - 1;
    int col = 0;
    while (true) {
      if (matrix[row][col] == target) {
        return true;
      } else if (matrix[row][col] > target) {
        if (row == 0)
          break;
        else
          row--;
      } else {
        if (col == matrix[0].size() - 1)
          break;
        else
          col++;
      }
    }
    return false;
    // 129/129 cases passed (100 ms)
    // Your runtime beats 58.13 % of cpp submissions
    // Your memory usage beats 69.69 % of cpp submissions (14.4 MB)
  }
};

Hard

[239] 滑动窗口最大值

heap | sliding-window

2022/03/19

class Solution {
 private:
  class DQueue {
   private:
    deque<int> que;

   public:
    // 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
    // 同时pop之前判断队列当前是否为空。
    void pop(int value) {
      if (!que.empty() && value == que.front()) {
        que.pop_front();
      }
    }
    // 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
    // 这样就保持了队列里的数值是单调从大到小的了。
    void push(int value) {
      while (!que.empty() && value > que.back()) {
        que.pop_back();
      }
      que.push_back(value);
    }
    // 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
    int front() { return que.front(); }
  };

 public:
  vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> ans;
    DQueue dQueue;
    for (int i = 0; i < k; i++) {
      dQueue.push(nums[i]);
    }
    ans.emplace_back(dQueue.front());
    for (int i = 1; i + k - 1 < nums.size(); i++) {
      dQueue.push(nums[i + k - 1]);
      dQueue.pop(nums[i - 1]);
      ans.emplace_back(dQueue.front());
    }
    return ans;
    // 61/61 cases passed (232 ms)
    // Your runtime beats 48.68 % of cpp submissions
    // Your memory usage beats 84.64 % of cpp submissions (128.6 MB)
  }
};