LeetCode刷题笔记(2022-07,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 {
#ifndef max
#define max(x, y) x > y ? x : y
#endif
private:
  int maxDiameter = 0;
  void dfsCalc(TreeNode *root) {
    if (!root)
      return;
    dfsCalc(root->left);
    dfsCalc(root->right);
    int leftLength = root->left ? root->left->val + 1 : 0;
    int rightLength = root->right ? root->right->val + 1 : 0;
    root->val = max(leftLength, rightLength);
    maxDiameter = max(maxDiameter, leftLength + rightLength);
  }

public:
  /**
   * @brief
   * 104/104 cases passed (4 ms)
   * Your runtime beats 94.78 % of cpp submissions
   * Your memory usage beats 92.52 % of cpp submissions (19.6 MB)
   * @param root
   * @return int
   */
  int diameterOfBinaryTree(TreeNode *root) {
    if (!root)
      return 0;
    dfsCalc(root);
    return maxDiameter;
  }
};

class Solution {
public:
  /**
   * @brief
   * 92/92 cases passed (120 ms)
   * Your runtime beats 5.86 % of cpp submissions
   * Your memory usage beats 22.15 % of cpp submissions (42.7 MB)
   * @ref
   * https://leetcode.cn/problems/subarray-sum-equals-k/solution/bao-li-jie-fa-qian-zhui-he-qian-zhui-he-you-hua-ja/
   * @param nums
   * @param k
   * @return int
   */
  int subarraySum(vector<int> &nums, int k) {
    map<int, int> preSumFreq;
    preSumFreq[0] = 1;
    int preSum = 0;
    int count = 0;
    for (auto num : nums) {
      preSum += num;
      if (preSumFreq.find(preSum - k) != preSumFreq.end())
        count += preSumFreq[preSum - k];
      preSumFreq[preSum] = preSumFreq[preSum] + 1;
    }
    return count;
  }
};

class Solution {
public:
  /**
   * @brief
   * 307/307 cases passed (36 ms)
   * Your runtime beats 16.41 % of cpp submissions
   * Your memory usage beats 97.24 % of cpp submissions (25.7 MB)
   * @ref
   * https://leetcode.cn/problems/shortest-unsorted-continuous-subarray/comments/
   * @author chengeyouyou
   * @param nums
   * @return int
   */
  int findUnsortedSubarray(vector<int> &nums) {
    if (nums.size() < 2)
      return 0;
    int Max = INT_MIN;
    int Min = INT_MAX;
    int R = 0;
    int L = 0;
    for (int i = 0; i < nums.size(); i++) {
      if (Max > nums[i])
        R = i;
      Max = max(Max, nums[i]);
    }
    for (int i = nums.size() - 1; i >= 0; i--) {
      if (Min < nums[i])
        L = i;
      Min = min(Min, nums[i]);
    }
    return R == L ? 0 : R - L + 1;
  }
};

class Solution {
private:
  inline char findMostChar(map<char, int> &hash) {
    auto mostChar = 'A';
    for (auto i = 'A'; i <= 'Z'; i++) {
      if (hash[i] > hash[mostChar]) {
        mostChar = i;
      }
    }
    return mostChar;
  }

public:
  /**
   * @brief
   * 71/71 cases passed (52 ms)
   * Your runtime beats 75.87 % of cpp submissions
   * Your memory usage beats 10.03 % of cpp submissions (33.7 MB)
   * @param tasks
   * @param n
   * @return int
   */
  int leastInterval(vector<char> &tasks, int n) {
    map<char, int> hash;
    for (auto task : tasks) {
      hash[task]++;
    }
    char mostChar;
    int length = 0, mostTasks = 0;
    for (; hash[mostChar = findMostChar(hash)];) {
      if (!mostTasks) {
        mostTasks = hash[mostChar];
        length = hash[mostChar] * (n + 1) - n;
      } else {
        if (hash[mostChar] == mostTasks) {
          length++;
        }
      }
      hash[mostChar] = 0;
    }
    return max(length, (int)tasks.size());
  }
};

class Solution {
public:
  /**
   * @brief
   * 47/47 cases passed (204 ms)
   * Your runtime beats 5.14 % of cpp submissions
   * Your memory usage beats 67.54 % of cpp submissions (86.7 MB)
   * @param temperatures
   * @return vector<int>
   */
  vector<int> dailyTemperatures(vector<int> &temperatures) {
    auto answer = vector<int>(temperatures.size(), 0);
    auto stack = std::stack<int>();
    stack.push(0);
    for (int i = 1; i < temperatures.size(); i++) {
      for (; !stack.empty() && temperatures[i] > temperatures[stack.top()];) {
        answer[stack.top()] = i - stack.top();
        stack.pop();
      }
      stack.push(i);
    }
    return answer;
  }
};

class Solution {
public:
  /**
   * @brief
   * 就这？
   * 67/67 cases passed (4 ms)
   * Your runtime beats 83.28 % of cpp submissions
   * Your memory usage beats 85.87 % of cpp submissions (8 MB)
   * @param words
   * @return vector<string>
   */
  vector<string> stringMatching(vector<string> &words) {
    auto ans = vector<string>();
    for (int i = 0; i < words.size(); i++) {
      for (int j = 0; j < words.size(); j++) {
        if (i == j)
          continue;
        if (words[i].length() > words[j].length())
          continue;
        if (words[j].find(words[i]) != string::npos) {
          ans.push_back(words[i]);
          break;
        }
      }
    }
    return ans;
  }
};

class MySolution {
private:
  vector<string> split(const string &s, char delim) {
    vector<string> result;
    stringstream ss(s);
    string item;
    while (getline(ss, item, delim)) {
      result.push_back(item);
    }
    return result;
  }
  inline tuple<int, bool, int> logHandler(string log) {
    auto strs = split(log, ':');
    return {stoi(strs[0]), strs[1] == "start", stoi(strs[2])};
  }

public:
  /**
   * @brief
   * 120/120 cases passed (56 ms)
   * Your runtime beats 5.67 % of cpp submissions
   * Your memory usage beats 5.55 % of cpp submissions (21.3 MB)
   * @param n
   * @param logs
   * @return vector<int>
   */
  vector<int> exclusiveTime(int n, vector<string> &logs) {
    vector<int> ans(n, 0);
    stack<pair<int, int>> stk;
    for (auto log : logs) {
      auto [functionId, isStart, time] = logHandler(log);
      if (stk.empty()) {
        stk.push({functionId, time});
        continue;
      }
      auto [fId, T] = stk.top();
      if (isStart) {
        ans[fId] += time - T;
        stk.push({functionId, time});
      } else {
        ans[functionId] += time - T + 1;
        stk.pop();
        if (!stk.empty()) {
          stk.top().second = time + 1;
        }
      }
    }
    return ans;
  }
};

class Solution {
public:
  /**
   * @brief
   * 120/120 cases passed (16 ms)
   * Your runtime beats 75.65 % of cpp submissions
   * Your memory usage beats 48.75 % of cpp submissions (12.9 MB)
   * 原理一样，他这个处理使用的工具更快
   * @param n
   * @param logs
   * @return vector<int>
   */
  vector<int> exclusiveTime(int n, vector<string> &logs) {
    stack<pair<int, int>> st; // {idx, 开始运行的时间}
    vector<int> res(n, 0);
    for (auto &log : logs) {
      char type[10];
      int idx, timestamp;
      sscanf(log.c_str(), "%d:%[^:]:%d", &idx, type, &timestamp);
      if (type[0] == 's') {
        if (!st.empty()) {
          res[st.top().first] += timestamp - st.top().second;
          st.top().second = timestamp;
        }
        st.emplace(idx, timestamp);
      } else {
        auto t = st.top();
        st.pop();
        res[t.first] += timestamp - t.second + 1;
        if (!st.empty()) {
          st.top().second = timestamp + 1;
        }
      }
    }
    return res;
  }
};

/**
 * @brief
 * 51/51 cases passed (28 ms)
 * Your runtime beats 36.53 % of cpp submissions
 * Your memory usage beats 12.26 % of cpp submissions (16.6 MB)
 */
class MyCircularDeque {
private:
  int maxNum;
  int num;
  struct DqNode {
    int val;
    DqNode *next;
    DqNode *before;
    DqNode(int val, DqNode *next, DqNode *before)
        : val(val), next(next), before(before){};
  };
  DqNode *front;
  DqNode *rear;

public:
  MyCircularDeque(int k) {
    this->maxNum = k;
    this->num = 0;
    front = nullptr;
    rear = nullptr;
  }
  ~MyCircularDeque() {
    for (; front;) {
      auto tmp = front;
      front = front->next;
      delete tmp;
    }
  }

  bool insertFront(int value) {
    if (num == maxNum) {
      return false;
    }
    if (num == 0) {
      front = new DqNode(value, nullptr, nullptr);
      rear = front;
    } else {
      front->before = new DqNode(value, front, nullptr);
      front = front->before;
    }
    this->num++;
    return true;
  }

  bool insertLast(int value) {
    if (num == maxNum) {
      return false;
    }
    if (num == 0) {
      rear = new DqNode(value, nullptr, nullptr);
      front = rear;
    } else {
      rear->next = new DqNode(value, nullptr, rear);
      rear = rear->next;
    }
    this->num++;
    return true;
  }

  bool deleteFront() {
    if (num == 0) {
      return false;
    }
    if (num == 1) {
      delete front;
      front = nullptr;
      rear = nullptr;
    } else {
      auto tmp = front;
      front = front->next;
      delete tmp;
      front->before = nullptr;
    }
    this->num--;
    return true;
  }

  bool deleteLast() {
    if (num == 0) {
      return false;
    }
    if (num == 1) {
      delete rear;
      front = nullptr;
      rear = nullptr;
    } else {
      auto tmp = rear;
      rear = rear->before;
      delete tmp;
      rear->next = nullptr;
    }
    this->num--;
    return true;
  }

  int getFront() { return front ? front->val : -1; }

  int getRear() { return rear ? rear->val : -1; }

  bool isEmpty() { return this->num == 0; }

  bool isFull() { return this->num == this->maxNum; }
};

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque* obj = new MyCircularDeque(k);
 * bool param_1 = obj->insertFront(value);
 * bool param_2 = obj->insertLast(value);
 * bool param_3 = obj->deleteFront();
 * bool param_4 = obj->deleteLast();
 * int param_5 = obj->getFront();
 * int param_6 = obj->getRear();
 * bool param_7 = obj->isEmpty();
 * bool param_8 = obj->isFull();
 */

/**
 * 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:
  /**
   * @brief
   * 39/39 cases passed (88 ms)
   * Your runtime beats 65.02 % of cpp submissions
   * Your memory usage beats 27.3 % of cpp submissions (60.4 MB)
   * @param root
   * @return int
   */
  int deepestLeavesSum(TreeNode *root) {
    std::queue<TreeNode *> bfs;
    bfs.push(root);
    for (; !bfs.empty();) {
      auto num = bfs.size();
      int ans = 0;
      for (; num--;) {
        auto fr = bfs.front();
        bfs.pop();
        ans += fr->val;
        if (fr->left) {
          bfs.push(fr->left);
        }
        if (fr->right) {
          bfs.push(fr->right);
        }
      }
      if (bfs.size() == 0) {
        return ans;
      }
    }
    return 0;
  }
};

/**
 * @brief
 * 101/101 cases passed (68 ms)
 * Your runtime beats 100 % of cpp submissions
 * Your memory usage beats 48.34 % of cpp submissions (81.7 MB)
 */
class OrderedStream {
private:
  int num;
  int ptr = 0;
  vector<string> container;

public:
  OrderedStream(int n) {
    this->num = n;
    vector<string>(n).swap(container);
  }

  vector<string> insert(int idKey, string value) {
    idKey--;
    container[idKey] = value;
    if (ptr == idKey) {
      vector<string> ans;
      for (; ptr < this->num && !container[ptr].empty();) {
        ans.push_back(container[ptr]);
        ptr++;
      }
      return ans;
    } else {
      return {};
    }
  }
};

/**
 * Your OrderedStream object will be instantiated and called as such:
 * OrderedStream* obj = new OrderedStream(n);
 * vector<string> param_1 = obj->insert(idKey,value);
 */