LeetCode刷題筆記(03.02-03.15)

今後的刷題筆記都不再單獨放置了，全部放在一起，節省空間

每道題後標註的日期均爲上傳日期，不是完成日期

ps:文件太大了，格式化很麻烦，所以还是分开吧

Easy

[202] 快乐数

hash-table | math

2022/03/02

class Solution {
 public:
  bool isHappy(int n) {
    if (n == 1) {
      return 1;
    }
    if (n > 1 && n <= 4) {
      return 0;
    }
    int num = 0;
    while (n) {
      num += (n % 10) * (n % 10);
      n /= 10;
    }
    return isHappy(num);
    // 402/402 cases passed (0 ms)
    // Your runtime beats 100 % of cpp submissions
    // Your memory usage beats 94.2 % of cpp submissions (5.7 MB)
    //主体部分是很简单的，只是要注意如果输入的正整数在某个递归之后小于等于4并且大于1，那么他就不是快乐数
  }
};

[94] 二叉树的中序遍历

hash-table | stack | tree

2022/03/07

关于迭代：迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程

关于 STL - emplace 与 push 的区别：

设置数据结构 data

//假设栈内的数据类型是data
class data {
  int a;
  int b;
public:
  data(int x, int y):a(x), b(y) {}
};

1. push 的操作可以直接用于 emplace

   //push
   data d(1,2);
   S.push(d) 或 S.emplace(d);
   

2. 在传入时候构造对象

   S.push(data(1,2));
   S.emplace(data(1,2));
   

3. emplace 可以直接传入构造对象需要的元素，然后自己调用其构造函数！

   S.emplace(1,2)
   

意思是，emplace 这样接受新对象的时候，自己会调用其构造函数生成对象然后放在容器内（比如这里传入了 1，2，它则会自动调用一次 data(1,2))

而 push，只能让其构造函数构造好了对象之后，再使用复制构造函数！

相当于 emplace 直接把原料拿进家，造了一个。而 push 是造好了之后，再复制到自己家里，多了复制这一步。

所以 emplace 相对于 push，使用第三种方法会更节省内存。

注意：

emplace_back(type) 对应 push_back(type)
emplace(i, type) 对应于 insert(type, i)
emplace_front(type) 对应于 push_front()

但是！对于 stack 和 queue，只有 push 操作，所以也只有 emplace 操作，此时它们是相对应的。

/**
 * 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:
  vector<int> inorderTraversal(TreeNode *root) {
    /* if (!root) return {};
    vector<int> left, right;
    left = inorderTraversal(root->left);
    right = inorderTraversal(root->right);
    left.push_back(root->val);
    left.insert(left.end(), right.begin(), right.end());
    return left;
    // 70/70 cases passed (0 ms)
    // Your runtime beats 100 % of cpp submissions
    // Your memory usage beats 7.08 % of cpp submissions (9.2 MB)
    //*递归算法，可以看到用了许多栈空间 */
    stack<TreeNode *> treeNodeStack;
    vector<int> ans;
    while (root || !treeNodeStack.empty()) {
      while (root) {
        treeNodeStack.push(root);
        root = root->left;
      }
      auto node = treeNodeStack.top();
      treeNodeStack.pop();
      ans.emplace_back(node->val);
      root = node->right;
    }
    return ans;
    // 70/70 cases passed (0 ms)
    // Your runtime beats 100 % of cpp submissions
    // Your memory usage beats 36.4 % of cpp submissions (8.2 MB)
    //*迭代算法
  }
};

[101] 对称二叉树

tree | depth-first-search | breadth-first-search

2022/03/08

利用深搜解决

/**
 * 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:
  bool function(TreeNode *leftRoot, TreeNode *rightRoot) {
    if (rightRoot && leftRoot) {
      if (rightRoot->val != leftRoot->val)
        return false;
      else {
        return function(leftRoot->left, rightRoot->right) &&
               function(leftRoot->right, rightRoot->left);
      }
    } else if (rightRoot || leftRoot) {
      return false;
    } else {
      return true;
    }
  }

 public:
  bool isSymmetric(TreeNode *root) {
    return function(root->left, root->right);
    // 197/197 cases passed (0 ms)
    // Your runtime beats 100 % of cpp submissions
    // Your memory usage beats 48.8 % of cpp submissions (16 MB)
  }
};

[104] 二叉树的最大深度

tree | depth-first-search

2022/03/08

超级无敌螺旋托马斯火箭简单的递归

/**
 * 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:
  int maxDeep = 0;
  void findMaxDeep(TreeNode *root, int deep) {
    if (!root) {
      maxDeep = max(maxDeep, deep);
      return;
    }
    findMaxDeep(root->left, deep + 1);
    findMaxDeep(root->right, deep + 1);
  }

 public:
  int maxDepth(TreeNode *root) {
    findMaxDeep(root, 0);
    return maxDeep;
    // 39/39 cases passed (4 ms)
    // Your runtime beats 91.71 % of cpp submissions
    // Your memory usage beats 93.72 % of cpp submissions (18.3 MB)
  }
};

[160] 相交链表

linked-list

2022/03/13

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
 public:
  ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    vector<ListNode *> listA, listB;
    while (headA) {
      listA.emplace_back(headA);
      headA = headA->next;
    }
    while (headB) {
      listB.emplace_back(headB);
      headB = headB->next;
    }
    int posA = listA.size() - 1, posB = listB.size() - 1;
    for (; posA >= 0 && posB >= 0; posA--, posB--) {
      if (listA[posA] != listB[posB]) {
        break;
      }
    }
    return posA >= 0 ? listA[posA]->next : listA[0];
    // 39/39 cases passed (28 ms)
    // Your runtime beats 99.64 % of cpp submissions
    // Your memory usage beats 20.93 % of cpp submissions (16.4 MB)
  }
};

[169] 多数元素

array | divide-and-conquer | bit-manipulation

2022/03/14

摩尔投票法：

核心就是对拼消耗。

玩一个诸侯争霸的游戏，假设你方人口超过总人口一半以上，并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。

那就大混战呗，最差所有人都联合起来对付你（对应你每次选择作为计数器的数都是众数），或者其他国家也会相互攻击（会选择其他数作为计数器的数），但是只要你们不要内斗，最后肯定你赢。

最后能剩下的必定是自己人。

class Solution {
 public:
  int majorityElement(vector<int>& nums) {
    // 从第一个数开始count=1，遇到相同的就加1，遇到不同的就减1，减到0就重新换个数(当下的数)开始计数，总能找到最多的那个
    int ans, count = 0;
    for (int i = 0; i < nums.size(); i++) {
      if (count == 0) {
        ans = nums[i];
        count++;
      } else {
        count += nums[i] == ans ? 1 : -1;
      }
    }
    return ans;
    // 43/43 cases passed (12 ms)
    // Your runtime beats 91.53 % of cpp submissions
    // Your memory usage beats 74.89 % of cpp submissions (19.1 MB)
  }
};

Medium

[201] 数字范围按位与

bit-manipulation

2022/03/02

_解法看註釋就行了，挺無語的_

class Solution {
 public:
  int rangeBitwiseAnd(int left, int right) {
    //*当一个数+1时，总会有这么一个规律“某一位后的数字，全部被置为相反数”
    //*即前缀一样
    int i = 0;
    while (left < right) {
      left >>= 1;
      right >>= 1;
      i++;
    }
    return left << i;
    // 8268/8268 cases passed (4 ms)
    // Your runtime beats 92.23 % of cpp submissions
    // Your memory usage beats 90.58 % of cpp submissions (5.7 MB)
    /* if (left == right) return left;
    int capturer = 0b01000000000000000000000000000000;
    int ans = 0b01111111111111111111111111111111;
    for (int i = 0; i < 31; i++) {
      for (int j = left; j <= right; j++) {
        if (j < 0) break;
        if (!(int)(j & capturer)) {
          ans ^= capturer;
          break;
        }
      }
      capturer >>= 1;
    }
    return ans;
    //! Time Limit Exceeded */
  }
};

[384] 打乱数组

Unknown(_不是我標錯 tag 了，那上面就是這個_)

2022/03/02

無語子，與其說是考驗算法，不如說是考驗隨機函數的用法

class Solution {
 private:
  vector<int> sample;

 public:
  Solution(vector<int>& nums) { sample = nums; }

  vector<int> reset() { return sample; }

  vector<int> shuffle() {
    vector<int> tmp = sample;
    vector<int> ans;
    int length = tmp.size();
    for (int i = length; i > 0; i--) {
      int index = rand() % i;
      ans.push_back(tmp[index]);
      tmp.erase(tmp.begin() + index);
    }
    return ans;
  }
  // 10/10 cases passed (112 ms)
  // Your runtime beats 37.14 % of cpp submissions
  // Your memory usage beats 12.87 % of cpp submissions (92.3 MB)
  //第一次见这种题，网上找了个参考：https://blog.csdn.net/qq_19841133/article/details/88907051
  //真没想到算法题还有这样的
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(nums);
 * vector<int> param_1 = obj->reset();
 * vector<int> param_2 = obj->shuffle();
 */

[31] 下一个排列

array

2022/03/03

class Solution {
 public:
  void nextPermutation(vector<int>& nums) {
    for (int i = nums.size() - 2; i >= 0; i--) {
      if (nums[i] < nums[i + 1]) {
        int minPos = i + 1;
        for (int j = i + 1; j < nums.size(); j++) {
          minPos = nums[j] < nums[minPos] && nums[j] > nums[i] ? j : minPos;
        }
        swap(nums[i], nums[minPos]);
        sort(nums.begin() + i + 1, nums.end());
        return;
      }
    }
    sort(nums.begin(), nums.end());
    return;
    // 265/265 cases passed (4 ms)
    // Your runtime beats 73.64 % of cpp submissions
    // Your memory usage beats 90.64 % of cpp submissions (11.6 MB)
  }
};

[48] 旋转图像

array

2022/03/04

class Solution {
 public:
  void rotate(vector<vector<int>> &matrix) {
    int n = matrix.size();
    for (int i = 0; i < n; i++) {
      for (int j = i; j < n; j++) {
        swap(matrix[i][j], matrix[j][i]);
      }
    }
    for (int i = 0; i < n / 2; i++) {
      for (int j = 0; j < n; j++) {
        swap(matrix[j][i], matrix[j][n - 1 - i]);
      }
    }
    // 21/21 cases passed (0 ms)
    // Your runtime beats 100 % of cpp submissions
    // Your memory usage beats 36.98 % of cpp submissions (6.9 MB)
    /*
    如下，非常简单
    123
    456
    789

    147
    258
    369

    741
    852
    963
    */
  }
};

[49] 字母异位词分组

hash-table | string

2022/03/04

存数字 double 是最大的！

class Solution {
 private:
  int getNum(char a) {
    switch (a) {
      case 'a':
        return 2;
      case 'b':
        return 3;
      case 'c':
        return 5;
      case 'd':
        return 7;
      case 'e':
        return 11;
      case 'f':
        return 13;
      case 'g':
        return 17;
      case 'h':
        return 19;
      case 'i':
        return 23;
      case 'j':
        return 29;
      case 'k':
        return 31;
      case 'l':
        return 37;
      case 'm':
        return 41;
      case 'n':
        return 43;
      case 'o':
        return 47;
      case 'p':
        return 53;
      case 'q':
        return 59;
      case 'r':
        return 61;
      case 's':
        return 67;
      case 't':
        return 71;
      case 'u':
        return 73;
      case 'v':
        return 79;
      case 'w':
        return 83;
      case 'x':
        return 89;
      case 'y':
        return 97;
      case 'z':
        return 101;
    }
    return 0;
  }

 public:
  vector<vector<string>> groupAnagrams(vector<string>& strs) {
    map<double, vector<string>> hashmap;
    for (auto i : strs) {
      double hashTmp = 1;
      for (auto chars : i) {
        hashTmp *= getNum(chars);
      }
      hashmap[hashTmp].push_back(i);  //没有的话自动帮创一个key
    }
    vector<vector<string>> ans;
    for (auto&& i : hashmap) {
      ans.push_back(i.second);
    }
    return ans;
    // 115/115 cases passed (24 ms)
    // Your runtime beats 93.4 % of cpp submissions
    // Your memory usage beats 89.56 % of cpp submissions (18.6 MB)
    //*double都比unsigned long long存得大，我服了
    /* vector<vector<int>> hash;
    vector<vector<string>> ans;
    for (auto i : strs) {
      vector<int> hashTmp(26, 0);
      for (auto chars : i) {
        hashTmp[chars - 'a']++;
      }
      bool flag = 1;
      for (int j = 0; j < hash.size(); j++) {
        if (hashTmp == hash[j]) {
          flag = 0;
          ans[j].push_back(i);
          break;
        }
      }
      if (flag) {
        hash.push_back(hashTmp);
        ans.push_back(vector<string>(1, i));
      }
    }
    return ans;
    //超时 */
  }
};

[56] 合并区间

array | sort

2022/03/04

双指针解法

class Solution {
 public:
  vector<vector<int>> merge(vector<vector<int>>& intervals) {
    vector<vector<int>> ans;
    vector<int> start(intervals.size()), end(intervals.size());
    for (int i = 0; i < intervals.size(); i++) {
      start[i] = intervals[i][0];
      end[i] = intervals[i][1];
    }
    sort(start.begin(), start.end());
    sort(end.begin(), end.end());
    for (int i = 0, j = 0; i < intervals.size(); i++) {
      if (i == intervals.size() - 1 || start[i + 1] > end[i]) {
        ans.push_back({start[j], end[i]});
        j = i + 1;
      }
    }
    return ans;
    // 169/169 cases passed (24 ms)
    // Your runtime beats 77.18 % of cpp submissions
    // Your memory usage beats 19.97 % of cpp submissions (18.7 MB)
    //*双指针，注意执行时候的条件
    /* sort(intervals.begin(), intervals.end(),
         [](vector<int> a, vector<int> b) { return a[0] < b[0]; });
    for (int i = 1; i < intervals.size(); i++) {
      if (intervals[i][0] <= intervals[i - 1][1]) {
        intervals[i - 1][1] = max(intervals[i][1], intervals[i - 1][1]);
        intervals.erase(intervals.begin() + i--);
      }
    }
    return intervals;
    //超时 */
  }
};

[64] 最小路径和

array | dynamic-programming

2022/03/05

很简单的动规

class Solution {
 public:
  int minPathSum(vector<vector<int>>& grid) {
    vector<vector<int>> dp(grid.size(), vector<int>(grid[0].size()));
    dp[0][0] = grid[0][0];
    for (int i = 1; i < grid.size(); i++) {
      dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    for (int i = 1; i < grid[0].size(); i++) {
      dp[0][i] = dp[0][i - 1] + grid[0][i];
    }
    for (int i = 1; i < grid.size(); i++) {
      for (int j = 1; j < grid[0].size(); j++) {
        dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
      }
    }
    return dp.back().back();
    // 61/61 cases passed (8 ms)
    // Your runtime beats 77.09 % of cpp submissions
    // Your memory usage beats 49.79 % of cpp submissions (9.8 MB)
  }
};

[75] 颜色分类

array | two-pointers | sort

2022/03/05

题目不让用库函数里的 sort，那么就只好自己手撕了，应用到了双指针和分治的思想

class Solution {
 private:
  void qsort(vector<int>& nums, int begin, int end) {
    if (begin < end) {
      int left = begin;
      int right = end;
      int key = nums[right];
      while (left < right) {
        while (left < right && nums[left] <= key) {
          left++;
        }
        if (left < right) {
          nums[right] = nums[left];
          right--;
        }
        while (left < right && nums[right] >= key) {
          right--;
        }
        if (left < right) {
          nums[left] = nums[right];
          left++;
        }
      }
      nums[right] = key;
      qsort(nums, begin, right - 1);
      qsort(nums, right + 1, end);
    }
  }

 public:
  void sortColors(vector<int>& nums) { qsort(nums, 0, nums.size() - 1); }
  // 87/87 cases passed (4 ms)
  // Your runtime beats 39.75 % of cpp submissions
  // Your memory usage beats 96.08 % of cpp submissions (7.9 MB)
};

[96] 不同的二叉搜索树

dynamic-programming | tree

2022/03/07

关于二叉查找树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树

很简单的题目，可以放到 easy 里面了

class Solution {
 public:
  int numTrees(int n) {
    vector<int> dp(n + 1);
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
      for (int j = 1; j <= i; j++) {
        dp[i] += (dp[i - j] * dp[j - 1]);
      }
    }
    return dp.back();
    // 19/19 cases passed (0 ms)
    // Your runtime beats 100 % of cpp submissions
    // Your memory usage beats 80.9 % of cpp submissions (5.8 MB)
  }
};

[98] 验证二叉搜索树

tree | depth-first-search

2022/03/07

/**
 * 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:
  int left(TreeNode *root) {
    if (!root->left) return root->val;
    return left(root->left);
  }
  int right(TreeNode *root) {
    if (!root->right) return root->val;
    return right(root->right);
  }

 public:
  bool isValidBST(TreeNode *root) {
    bool ans = 1;
    if (root->left) {
      if (root->val <= right(root->left)) {
        return 0;
      } else
        ans = ans && isValidBST(root->left);
    }
    if (root->right) {
      if (root->val >= left(root->right)) {
        return 0;
      } else
        ans = ans && isValidBST(root->right);
    }
    return ans;
    // 80/80 cases passed (12 ms)
    // Your runtime beats 51.29 % of cpp submissions
    // Your memory usage beats 99.41 % of cpp submissions (20.9 MB)
  }
};

[102] 二叉树的层序遍历

tree | breadth-first-search

2022/03/08

很简单的广搜

/**
 * 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:
  vector<vector<int>> levelOrder(TreeNode *root) {
    if (!root) return {};
    vector<vector<int>> ans;
    deque<TreeNode *> bfs;
    bfs.emplace_back(root);
    while (!bfs.empty()) {
      ans.emplace_back(0);
      int length = bfs.size();
      while (length--) {
        auto tmp = bfs.front();
        bfs.pop_front();
        if (tmp->left) bfs.emplace_back(tmp->left);
        if (tmp->right) bfs.emplace_back(tmp->right);
        ans.back().emplace_back(tmp->val);
      }
    }
    return ans;
    // 34/34 cases passed (0 ms)
    // Your runtime beats 100 % of cpp submissions
    // Your memory usage beats 37.24 % of cpp submissions (12.3 MB)
  }
};

[105] 从前序与中序遍历序列构造二叉树

array | tree | depth-first-search

2022/03/09

/**
 * 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:
  TreeNode *function(vector<int> preorder, vector<int> inorder) {
    if (inorder.empty()) return nullptr;
    int rootPos = 0;
    for (; rootPos < inorder.size(); rootPos++) {
      if (inorder[rootPos] == preorder[0]) {
        break;
      }
    }
    TreeNode *root = new TreeNode(preorder[0]);
    root->left = function(
        vector<int>(preorder.begin() + 1, preorder.begin() + rootPos + 1),
        vector<int>(inorder.begin(), inorder.begin() + rootPos));
    root->right =
        function(vector<int>(preorder.begin() + rootPos + 1, preorder.end()),
                 vector<int>(inorder.begin() + rootPos + 1, inorder.end()));
    return root;
  }

 public:
  TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
    return function(preorder, inorder);
    // 203/203 cases passed (40 ms)
    // Your runtime beats 18.57 % of cpp submissions
    // Your memory usage beats 14.97 % of cpp submissions (72.1 MB)
  }
};

[114] 二叉树展开为链表

tree | depth-first-search

2022/03/09

/**
 * 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:
  void flatten(TreeNode *root) {
    if (!root) return;
    flatten(root->left);
    flatten(root->right);
    auto tmp = root->right;
    root->right = root->left;
    root->left = nullptr;
    while (root->right) root = root->right;
    root->right = tmp;
    // 225/225 cases passed (4 ms)
    // Your runtime beats 84.61 % of cpp submissions
    // Your memory usage beats 74.92 % of cpp submissions (12.3 MB)
  }
};

[128] 最长连续序列

array | union-find

2022/03/10

感觉照着 tag 用并查集还会更慢==

class Solution {
 private:
 public:
  int longestConsecutive(vector<int>& nums) {
    if (nums.empty()) return 0;
    sort(nums.begin(), nums.end());
    int nowPath = 1, maxPath = 1;
    for (int i = 1; i < nums.size(); i++) {
      if (nums[i] == nums[i - 1] + 1) {
        nowPath++;
        maxPath = max(maxPath, nowPath);
      } else if (nums[i] > nums[i - 1]) {
        nowPath = 1;
        maxPath = max(maxPath, nowPath);
      }
    }
    return maxPath;
    // 70/70 cases passed (28 ms)
    // Your runtime beats 98.89 % of cpp submissions
    // Your memory usage beats 98.61 % of cpp submissions (21.7 MB)
  }
};

[141] 环形链表

linked-list | two-pointers

2022/03/10

/**
 * 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) {
    if (!head) return false;
    auto front = head, behind = head;
    while (front->next && front->next->next) {
      front = front->next;
      if (front == behind) return true;
      front = front->next;
      if (front == behind) return true;
      behind = behind->next;
      if (front == behind) return true;
    }
    return false;
    // 21/21 cases passed (8 ms)
    // Your runtime beats 93.51 % of cpp submissions
    // Your memory usage beats 53.45 % of cpp submissions (7.9 MB)
  }
};

[142] 环形链表 II

linked-list | two-pointers

2022/03/12

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
 public:
  ListNode *detectCycle(ListNode *head) {
    if (!head) return NULL;
    auto front = head, behind = head;
    int num = 10000;
    while (true) {
      for (int i = 0; i < num; i++) {
        if (!front->next) return NULL;
        front = front->next;
        if (front == behind) return behind;
      }
      behind = behind->next;
    }
    return NULL;
    // 16/16 cases passed (284 ms)
    // Your runtime beats 8.76 % of cpp submissions
    // Your memory usage beats 95.55 % of cpp submissions (7.3 MB)
  }
};

[146] LRU 缓存

design

2022/03/12

利用指针或者迭代器来避免排序，虽然最后结果还是很慢但至少不超时了==

class LRUCache {
 private:
  map<int, list<pair<int, int>>::iterator> cache;
  list<pair<int, int>> hash;
  int cap;

 public:
  LRUCache(int capacity) {
    cap = capacity;
    // 22/22 cases passed (452 ms)
    // Your runtime beats 14.15 % of cpp submissions
    // Your memory usage beats 6.91 % of cpp submissions (170.2 MB)
  }

  int get(int key) {
    if (cache.find(key) == cache.end()) return -1;
    hash.push_front(*cache[key]);
    hash.erase(cache[key]);
    cache[key] = hash.begin();
    return (*cache[key]).second;
  }

  void put(int key, int value) {
    if (cache.find(key) != cache.end()) {
      hash.emplace_front(key, value);
      hash.erase(cache[key]);
      cache[key] = hash.begin();
    } else {
      if (cache.size() >= cap) {
        cache.erase(hash.back().first);
        hash.pop_back();
      }
      hash.emplace_front(key, value);
      cache[key] = hash.begin();
    }
  }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

[148] 排序链表

linked-list | sort

2022/03/13

/**
 * 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:
  ListNode* sortList(ListNode* head) {
    if (!head) return nullptr;
    vector<ListNode*> list;
    while (head) {
      list.emplace_back(head);
      head = head->next;
    }
    sort(list.begin(), list.end(),
         [](ListNode* a, ListNode* b) { return a->val < b->val; });
    for (int i = 0; i < list.size() - 1; i++) {
      list[i]->next = list[i + 1];
    }
    list.back()->next = nullptr;
    return list[0];
    // 28/28 cases passed (84 ms)
    // Your runtime beats 77.51 % of cpp submissions
    // Your memory usage beats 68.35 % of cpp submissions (30.5 MB)
    //哈哈这解法太妙了，居然还是我自己想出来的
    /* if (!head) return nullptr;
    if (!head->next) return head;
    auto nextList = sortList(head->next);
    if (nextList->val >= head->val) {
      auto tmp = head;
      tmp->next = nextList;
      nextList = tmp;
    }
    auto ans = nextList;
    while (nextList->val < head->val) {
      if (nextList->next) {
        if (nextList->next->val >= head->val) {
          auto tmp = head;
          tmp->next = nextList->next;
          nextList->next = tmp;
          break;
        }
      } else {
        nextList->next = head;
        nextList->next->next = nullptr;
        break;
      }
      nextList = nextList->next;
    }
    return ans;
    // 28/28 cases passed (728 ms)
    // Your runtime beats 5 % of cpp submissions
    // Your memory usage beats 65.94 % of cpp submissions (30.6 MB) */
  }
};

[152] 乘积最大子数组

array | dynamic-programming

2022/03/13

class Solution {
 public:
  int maxProduct(vector<int>& nums) {
    vector<int> dpMax(nums.size(), 1), dpMin(nums.size(), 1);
    dpMax[0] = nums[0];
    dpMin[0] = nums[0];
    int ans = nums[0];
    for (int i = 1; i < nums.size(); i++) {
      dpMin[i] =
          min(nums[i], min(dpMin[i - 1] * nums[i], dpMax[i - 1] * nums[i]));
      dpMax[i] =
          max(nums[i], max(dpMin[i - 1] * nums[i], dpMax[i - 1] * nums[i]));
      ans = max(ans, dpMax[i]);
    }
    return ans;
    // 188/188 cases passed (4 ms)
    // Your runtime beats 92.06 % of cpp submissions
    // Your memory usage beats 21.33 % of cpp submissions (13.8 MB)
  }
};

[207] 课程表

depth-first-search | breadth-first-search | graph | topological-sort

2022/03/15

拓扑排序：

方法是重复寻找一个入度为 0 的顶点，将该顶点从图中删除（即放进一个队列里存着，这个队列的顺序就是最后的拓扑排序，具体见程序），并将该结点及其所有的出边从图中删除（即该结点指向的结点的入度减 1），最终若图中全为入度为 1 的点，则这些点至少组成一个回路。

采用邻接矩阵存储时，遍历二维数组，求各顶点入度的时间复杂度是 O(n^2)。 遍历所有结点，找出入度为 0 的结点的时间复杂度是 O(n)。对于 n 个入度为 0 的结点，删除他们的出边的复杂度为 O(n^2)。 所以总的复杂度为 O(n^2)。

对于邻接表，遍历所有边，求各顶点入度的时间复杂度是 O(e)，即边的个数。遍历所有结点，找出入度为 0 的结点的时间复杂度是 O(n)，即顶点的个数。遍历所有边，删除入度为 0 的结点的出边的复杂度为 O(e)，即边的个数。所以总的时间复杂度是 O(n+e)。

至于这道题我用了邻接矩阵的方法，感觉写起来简单

class Solution {
 public:
  bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<int> inDegree(numCourses);
    vector<vector<int>> edge(numCourses, vector<int>());
    for (auto&& i : prerequisites) {
      inDegree[i[1]]++;
      edge[i[0]].emplace_back(i[1]);
    }
    while (true) {
      bool flag = false;
      for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0 && !edge[i].empty()) {
          while (!edge[i].empty()) {
            inDegree[edge[i].back()]--;
            edge[i].pop_back();
          }
          flag = true;
          break;
        }
      }
      if (flag) {
        continue;
      } else {
        break;
      }
    }
    for (auto&& i : inDegree) {
      if (i > 0) {
        return false;
      }
    }
    return true;
    // 51/51 cases passed (36 ms)
    // Your runtime beats 12.15 % of cpp submissions
    // Your memory usage beats 89.87 % of cpp submissions (12.9 MB)
  }
};

[215] 数组中的第 K 个最大元素

divide-and-conquer | heap

2022/03/15

不明白这题想干嘛==

class Solution {
 public:
  int findKthLargest(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end());
    return nums[nums.size() - k];
    // 32/32 cases passed (8 ms)
    // Your runtime beats 72.52 % of cpp submissions
    // Your memory usage beats 85.7 % of cpp submissions (9.7 MB)
  }
};

Hard

[149] 直线上最多的点数

hash-table | math

2022/03/02

class Solution {
 public:
  int maxPoints(vector<vector<int>>& points) {
    if (points.size() <= 2) return points.size();
    int Max = 2;
    for (int i = 0; i < points.size(); i++) {
      int same = 1;
      for (int j = i + 1; j < points.size(); j++) {
        int count = 0;
        if (points[i] == points[j]) {
          same++;
        } else {
          count++;
          long long xDiff = (long long)(points[i][0] - points[j][0]);
          long long yDiff = (long long)(points[i][1] - points[j][1]);
          for (int k = j + 1; k < points.size(); k++)
            if (xDiff * (points[i][1] - points[k][1]) ==
                yDiff * (points[i][0] -
                         points[k][0]))  //利用这种方法化解公倍数，妙啊
              count++;
        }
        Max = max(Max, same + count);
      }
      if (Max > points.size() / 2) return Max;
    }
    return Max;
    // 34/34 cases passed (12 ms)
    // Your runtime beats 58.62 % of cpp submissions
    // Your memory usage beats 94.54 % of cpp submissions (6.9 MB)
    //还真就是一个一个找，我佛辣
  }
};

[10] 正则表达式匹配

string | dynamic-programming | backtracking

2022/03/02

一開始是從前向後判斷的，後來想想因爲*的緣故從後向前處理比較好，這裡運用了遞歸，效率上差動規很多

class Solution {
 public:
  bool isMatch(string s, string p) {
    int si = s.size() - 1, pi = p.size() - 1;
    cout << s << " " << p << endl;
    while (pi >= 0) {
      if (p[pi] != '*') {
        if (si < 0) return 0;
        if (s[si] == p[pi] || p[pi] == '.') {
          si--;
          pi--;
        } else {
          return 0;
        }
      } else {
        string tmpP = p.substr(0, pi - 1);
        string tmpS = s.substr(0, si + 1);
        bool flag;
        int k = tmpS.size();
        while ((flag = (!isMatch(tmpS, tmpP))) && k--) {
          tmpP = tmpP + p[pi - 1];
        }
        return !flag;
      }
    }
    return si == pi;
    /* if (p[0] == '*') return 0;
    cout << s << " " << p << endl;
    int si = 0, pi = 0;
    while (si < s.size() || pi < p.size()) {
      if (p[pi] != '*') {
        if (s[si] == p[pi] || p[pi] == '.') {
          si++;
          pi++;
        } else {
          if (pi == p.size() - 1 || p[pi + 1] != '*') {
            cout << 1 << endl;
            return 0;
          } else {
            pi++;
          }
        }
      } else {
        string tmpP = p.substr(pi + 1);
        string tmpS = s.substr(si);
        bool flag;
        int k = tmpS.size() + 1;
        while ((flag = (!isMatch(tmpS, tmpP))) && k--) {
          tmpP = p[pi - 1] + tmpP;
        }
        return !flag;
      }
    }
    return si == s.size() && pi == p.size(); */
    // 353/353 cases passed (192 ms)
    // Your runtime beats 5.29 % of cpp submissions
    // Your memory usage beats 14.13 % of cpp submissions (9.4 MB)
    //动规应该快一点
  }
};

[23] 合并 K 个升序链表

linked-list | divide-and-conquer | heap

2022/03/02

解釋一下 divide and conquer，字面意思分而治之，遞歸拆散數組，直到拆成一對或者一個，然後回溯處理

/**  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 {
 private:
  ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
    if (!l1) {
      return l2;
    }
    if (!l2) {
      return l1;
    }
    ListNode *l3;
    if (l1->val <= l2->val) {
      l3 = l1;
      l3->next = mergeTwoLists(l1->next, l2);
    } else {
      l3 = l2;
      l3->next = mergeTwoLists(l1, l2->next);
    }
    return l3;
  }

 public:
  ListNode *mergeKLists(vector<ListNode *> &lists) {
    if (lists.empty())
      return {};
    else if (lists.size() == 1)
      return lists[0];
    else if (lists.size() == 2)
      return mergeTwoLists(lists[0], lists[1]);
    vector<ListNode *> tmp;
    for (int i = 0; i < lists.size() / 2; i++) {
      tmp.push_back(lists.back());
      lists.pop_back();
    }
    return mergeTwoLists(mergeKLists(lists), mergeKLists(tmp));
    // 133/133 cases passed (16 ms)
    // Your runtime beats 94.55 % of cpp submissions
    // Your memory usage beats 5 % of cpp submissions (24.9 MB)
  }
};

[32] 最长有效括号

2022/03/03

string | dynamic-programming

用了好想的方法，不然的话时间和空间复杂度应该还可以压缩一倍

class Solution {
 public:
  int longestValidParentheses(string s) {
    if (s.empty()) return 0;
    vector<int> pos(s.size(), -1);
    for (int i = 1; i < s.size(); i++) {
      if (s[i] == ')') {
        for (int j = i - 1; j >= 0; j--) {
          if (s[j] == '(' && pos[j] == -1) {
            pos[j] = i;
            pos[i] = j;
            break;
          }
        }
      }
    }
    vector<int> length(s.size(), 0);
    length[0] = pos[0] == -1 ? 0 : 1;
    int Max = 0;
    for (int i = 1; i < s.size(); i++) {
      if (pos[i] != -1) {
        length[i] = length[i - 1] + 1;
        Max = max(Max, length[i]);
      }
    }
    return Max;
    // 231/231 cases passed (8 ms)
    // Your runtime beats 12.95 % of cpp submissions
    // Your memory usage beats 8.5 % of cpp submissions (7.5 MB)
  }
};

[42] 接雨水

2022/03/03

array | two-pointers | stack

标的是双指针，结果是靠着 DP 解的，牛 p 嗷

class Solution {
 public:
  int trap(vector<int>& height) {
    vector<int> left(height.size()), right(height.size());
    int ans = 0;
    for (int i = 1; i < height.size(); i++) {
      left[i] = max(left[i - 1], height[i - 1]);
    }
    for (int i = height.size() - 2; i >= 0; i--) {
      right[i] = max(right[i + 1], height[i + 1]);
    }
    for (int i = 0; i < height.size(); i++) {
      ans += max(0, min(right[i], left[i]) - height[i]);
    }
    return ans;
    // 321/321 cases passed (8 ms)
    // Your runtime beats 80.65 % of cpp submissions
    // Your memory usage beats 10.41 % of cpp submissions (17.8 MB)
    /* int left = 0, right = height.size() - 1;
    int ans = 0;
    while (left < right) {
      if (height[left] < height[right]) {
        for (int i = left; i <= right; i++) {
          if (height[i] < height[left]) {
            ans += (height[left] - height[i]);
            height[i] = height[left];
          }
        }
        int tmp = height[left];
        while (left < height.size() && height[left] == tmp) {
          left++;
        }
      } else {
        for (int i = left; i <= right; i++) {
          if (height[i] < height[right]) {
            ans += (height[right] - height[i]);
            height[i] = height[right];
          }
        }
        int tmp = height[right];
        while (right >= 0 && height[right] == tmp) {
          right--;
        }
      }
    }
    return ans; */
  }
};

[76] 最小覆盖子串

hash-table | two-pointers | string | sliding-window

2022/03/05

竟然是 hard，难以置信

class Solution {
 private:
  bool judge(vector<int>& hashS, vector<int>& hashT) {
    for (int i = 0; i < 58; i++) {
      if (hashT[i] > hashS[i]) {
        return 0;
      }
    }
    return 1;
  }

 public:
  string minWindow(string s, string t) {
    int left = 0, right = -1;
    int Min = INT_MAX, minLeft = 0, minRight = -1;
    vector<int> hashS(58, 0), hashT(58, 0);
    for (auto i : t) {
      hashT[i - 'A']++;
    }
    while (true) {
      if (!judge(hashS, hashT)) {
        if (right == s.size() - 1) break;
        hashS[s[++right] - 'A']++;
      } else {
        if (right - left + 1 < Min) {
          Min = right - left + 1;
          minLeft = left;
          minRight = right;
        }
        hashS[s[left++] - 'A']--;
      }
    }
    return s.substr(minLeft, minRight - minLeft + 1);
    // 266/266 cases passed (96 ms)
    // Your runtime beats 24.32 % of cpp submissions
    // Your memory usage beats 97.3 % of cpp submissions (7.4 MB)
  }
};

[84] 柱状图中最大的矩形

array | stack

2022/03/06

本题的难点主要在于如何找到某一个柱子构成矩形而所需要延伸的最大程度，利用单调栈可以实现这一点

class Solution {
 public:
  int largestRectangleArea(vector<int>& heights) {
    heights.insert(heights.begin(), 0);
    heights.push_back(0);
    stack<int> indexStack;
    int area = 0;
    for (int i = 0; i < heights.size(); i++) {
      while (!indexStack.empty() && heights[i] < heights[indexStack.top()]) {
        int height = heights[indexStack.top()];
        indexStack.pop();
        area = max(area, (i - indexStack.top() - 1) * height);
      }
      indexStack.push(i);
    }
    return area;
    // 98/98 cases passed (116 ms)
    // Your runtime beats 62.95 % of cpp submissions
    // Your memory usage beats 32.66 % of cpp submissions (75.3 MB)
    /* int heightNow = heights[0];
    int areaNow = heightNow;
    int Max = areaNow;
    for (int i = 1; i < heights.size(); i++) {
      if (heights[i] < heightNow) {
        areaNow = areaNow / heightNow * heights[i] + heights[i];
        heightNow = heights[i];
        Max = max(Max, areaNow);
      } else if (heights[i] > heightNow) {
        vector<int> newHeights(heights.begin() + i, heights.end());
        areaNow += heightNow;
        Max = max(Max, max(areaNow, largestRectangleArea(newHeights)));
      } else {
        areaNow += heightNow;
        Max = max(Max, areaNow);
      }
    }
    return Max;
    //有些不超时了，有些还是超时 */

    /* vector<int> left(heights.size()), right(heights.size());
    for (int i = 0; i < heights.size(); i++) {
      for (int j = i; j >= 0; j--)
        if (heights[j] < heights[i]) {
          left[i] = j + 1;
          break;
        } else if (j == 0)
          left[i] = 0;
      for (int j = i; j < heights.size(); j++)
        if (heights[j] < heights[i]) {
          right[i] = j - 1;
          break;
        } else if (j == heights.size() - 1)
          right[i] = heights.size() - 1;
    }
    int Max = 0;
    for (int i = 0; i < heights.size(); i++) {
      Max = max(Max, ((right[i] - left[i] + 1) * heights[i]));
    }
    return Max;
    // 两组一维dp也超时 */

    /* vector<vector<int>> dp(heights.size(),
    vector<int>(heights.size(), 0)); for (int i = 0; i <
    heights.size(); i++) { dp[i][i] = heights[i]; for (int j = i +
    1; j < heights.size(); j++) { dp[i][j] = min(dp[i][j - 1],
    heights[j]);
      }
    }
    int Max = 0;
    for (int i = 0; i < heights.size(); i++) {
      Max = max(Max, dp[i][i]);
      for (int j = i + 1; j < heights.size(); j++) {
        Max = max(Max, dp[i][j] * (j - i + 1));
      }
    }
    return Max;
    //二维dp超时 */
  }
};

[85] 最大矩形

array | hash-table | dynamic-programming | stack

2022/03/06

解法看注释

class Solution {
 private:
  int function(vector<int>& heights) {
    stack<int> indexStack;
    int area = 0;
    for (int i = 0; i < heights.size(); i++) {
      while (!indexStack.empty() && heights[i] < heights[indexStack.top()]) {
        int height = heights[indexStack.top()];
        indexStack.pop();
        area = max(area, (i - indexStack.top() - 1) * height);
      }
      indexStack.push(i);
    }
    return area;
  }

 public:
  int maximalRectangle(vector<vector<char>>& matrix) {
    int rows = matrix.size(), cols = matrix[0].size();
    int area = 0;
    vector<int> heights(cols + 2, 0);
    for (int i = 0; i < rows; i++) {
      for (int j = 0; j < cols; j++) {
        heights[j + 1] =
            matrix[i][j] == '0' ? 0 : heights[j + 1] + matrix[i][j] - '0';
      }
      area = max(area, function(heights));
    }
    return area;
    // 73/73 cases passed (32 ms)
    // Your runtime beats 90.62 % of cpp submissions
    // Your memory usage beats 54.56 % of cpp submissions (13 MB)
    /*
    每一层看作是柱状图，可以套用84题柱状图的最大面积。

    第一层柱状图的高度["1","0","1","0","0"]，最大面积为1；

    第二层柱状图的高度["2","0","2","1","1"]，最大面积为3；

    第三层柱状图的高度["3","1","3","2","2"]，最大面积为6；

    第四层柱状图的高度["4","0","0","3","0"]，最大面积为4； */
  }
};

[124] 二叉树中的最大路径和

tree | depth-first-search

2022/03/10

/**
 * 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:
  int function(TreeNode *root) {
    if (!root) return 0;
    return max(0,
               root->val + max(function(root->left), function((root->right))));
  }

 public:
  int maxPathSum(TreeNode *root) {
    if (!root) return INT_MIN;
    return max(root->val + function(root->left) + function(root->right),
               max(maxPathSum(root->left), maxPathSum(root->right)));
    // 94/94 cases passed (316 ms)
    // Your runtime beats 5.2 % of cpp submissions
    // Your memory usage beats 55.73 % of cpp submissions (27 MB)
  }
};