LeetCode周赛180

作者 Lucyyang 日期 2020-03-15
LeetCode周赛180

自从很久之前打了周赛之后就一蹶不振,打算现在开始恢复参加周赛。暂时的水平是保二冲三,阶段目标的是稳做出前三道题。今天25分钟做完了前两道,但第三题卡太久了,究其原因还是对树的概念和写法不够熟练,打算接下来开个树的专题。下面先对这次比赛的题目进行分析。

第一道题

矩阵中的幸运数字

题目:返回一个矩阵中所有在行中为最小值,列中为最大值的元素。

方法:该题比较easy,看了下讨论里面大家做的复杂度也基本是O(NM),那就直接说说我的解法。我先扫描每一行,并用最小值更新复制矩阵的每一行;接着扫描每一列,找到每一列最大值,当发现最大值与该最小值重合时即把答案添加到结果中。

代码:

class Solution {
public:
vector<int> luckyNumbers (vector<vector<int>>& matrix) {
vector<vector<int>> new_matrix(matrix);
int n = matrix.size();
vector<int> ans;
if(n == 0)
return ans;
int m = matrix[0].size();
//扫描行
for(int i = 0; i < n; i++) {
int min_ele = INT_MAX;
for(int j = 0; j < m; j++) {
min_ele = min(min_ele, matrix[i][j]);
}
for(int j = 0; j < m; j++) {
new_matrix[i][j] = min_ele;
}
}
//扫描列
for(int j = 0; j < m; j++) {
int max_ele = INT_MIN;
for(int i = 0; i < n; i++) {
max_ele = max(max_ele, matrix[i][j]);
}
for(int i = 0; i < n; i++) {
if(max_ele == new_matrix[i][j]) {
ans.push_back(max_ele);
break;
}
}
}
return ans;
}
};

第二道题

设计能够增加值的栈,一道设计题目。

题目:设计一个容量为capacity的栈,给定increment(int k, int val)方法时,会将最底部的k个元素全部加val。

方法:比赛中我直接用了stack进行模拟,但是现在想想同vector可能会更加方便,直接pop_back(),实现增加函数的时候也很方便数个数。

方法:

class CustomStack {
private:
int maxSize;
stack<int> mystack;
public:
CustomStack(int maxSize):maxSize(maxSize) {}
void push(int x) {
if(mystack.size() < maxSize){
mystack.push(x);
}
}
int pop() {
if(mystack.empty())
return -1;
int x = mystack.top();
mystack.pop();
return x;
}
void increment(int k, int val) {
int n = mystack.size();
stack<int> tmp;
int diff = abs(k - n);
for(int i = n; i >= 1; i--) {
int x = mystack.top();
mystack.pop();
if(i <= k)
x = x+val;
tmp.push(x);
}
while(!tmp.empty()){
mystack.push(tmp.top());
tmp.pop();
}
}
};
/**
* Your CustomStack object will be instantiated and called as such:
* CustomStack* obj = new CustomStack(maxSize);
* obj->push(x);
* int param_2 = obj->pop();
* obj->increment(k,val);
*/

采用vector后,代码更加方便:

class CustomStack {
private:
int maxSize;
vector<int> myv;
public:
CustomStack(int maxSize):maxSize(maxSize) {}
void push(int x) {
if(myv.size() < maxSize){
myv.push_back(x);
}
}
int pop() {
if(myv.empty())
return -1;
int x = myv.back();
myv.pop_back();
return x;
}
void increment(int k, int val) {
int n = myv.size();
for(int i = 0; i < min(n,k); i++){
myv[i] += val;
}
}
};
/**
* Your CustomStack object will be instantiated and called as such:
* CustomStack* obj = new CustomStack(maxSize);
* obj->push(x);
* int param_2 = obj->pop();
* obj->increment(k,val);
*/

第三道题

平衡一个搜索二叉树,对我来说比较难,赛场上搞了很久。

先解释几个概念:

  • 搜索二叉树:对于每个节点,左子树的值小于根的值,右子树的值大于根的值
  • 平衡二叉树:对于一棵树的每个节点,左子树和右子树的深度之差小于等于1
  • 平衡搜索二叉树:满足以上两个特性

看题的时候一定要看清,不然会白费功夫。

题目:给一棵搜索二叉树,请转换为平衡搜索二叉树

方法:先对搜索二叉树进行中序遍历,这样得到了一个增序数组。接着按照类似merge的方式,从该数组中间取值,将该值返回给根节点,再将数组前一个数的值返回给左节点,后一个数返回右节点,递归进行。

代码:

class Solution {
public:
vector<int> sortedArr;
TreeNode* balanceBST(TreeNode* root) {
inorderTraverse(root);
return sortedArrayToBST(0, sortedArr.size() - 1);
}
void inorderTraverse(TreeNode* root) {
if (root == NULL) return;
inorderTraverse(root->left);
sortedArr.push_back(root->val);
inorderTraverse(root->right);
}
TreeNode* sortedArrayToBST(int start, int end) {
if (start > end) return NULL;
int mid = (start + end) / 2;
TreeNode* root = new TreeNode(sortedArr[mid]);
root->left = sortedArrayToBST(start, mid - 1);
root->right = sortedArrayToBST(mid + 1, end);
return root;
}
};

Lucyyang下周再接再厉呀!