- 矩阵中的幸运数
给你一个 m * n 的矩阵，矩阵中的数字 各不相同 。请你按 任意 顺序返回矩阵中的所有幸运数。
幸运数 是指矩阵中满足同时下列两个条件的元素：
在同一行的所有元素中最小
在同一列的所有元素中最大
遍历查找并且保存即可，但是这不是最佳做法。本题其实挖掘以后可以发现，最多只可能有一个解。若某个位置值X是幸运数，假设另一个位置的值Y也是幸运数，X与Y一定不在同一行或同一列。假设Y上方和X同行的数，以及Y左侧和X同列的数，分别为X+A，X-B，则Y>X+A且Y<X-B，A<-B，明显无解。
class Solution {
public:
vector<int> luckyNumbers (vector<vector<int>>& matrix)
{
std::set<int> line_min;
vector<int> ret;
for (auto v : matrix) {
int min_n = INT_MAX;
for (auto n : v) {
min_n = min(min_n, n);
}
line_min.insert(min_n);
}
int m = matrix.size();
int n = matrix[0].size();
for (int j = 0; j < n; ++j) {
int max_n = INT_MIN;
for (int i = 0; i < m; ++i) {
max_n = max(max_n, matrix[i][j]);
}
if (line_min.count(max_n))
ret.push_back(max_n);
}
return ret;
}
};
class Solution {
public:
vector<int> luckyNumbers (vector<vector<int>>& matrix) {
int m = matrix.size();
int rowMax = 0, k;
for (int i = 0; i < m; i++) {
int c = min_element(matrix[i].begin(), matrix[i].end()) - matrix[i].begin();
if (rowMax < matrix[i][c]) {
rowMax = matrix[i][c];
k = c;
}
}
for (int i = 0; i < m; i++) {
if (rowMax < matrix[i][k]) {
return {};
}
}
return {rowMax};
}
};
- 将二叉搜索树变平衡
给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。如果有多种构造方法，请你返回任意一种。如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是 平衡的 。
构造中序遍历的序列，然后递归生成树。
/**
* 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> inorderSeq;
void getInorder(TreeNode* o) {
if (o->left) {
getInorder(o->left);
}
inorderSeq.push_back(o->val);
if (o->right) {
getInorder(o->right);
}
}
TreeNode* build(int l, int r) {
int mid = (l + r) >> 1;
TreeNode* o = new TreeNode(inorderSeq[mid]);
if (l <= mid - 1) {
o->left = build(l, mid - 1);
}
if (mid + 1 <= r) {
o->right = build(mid + 1, r);
}
return o;
}
TreeNode* balanceBST(TreeNode* root) {
getInorder(root);
return build(0, inorderSeq.size() - 1);
}
};
- 最大的团队表现值
给定两个整数 n 和 k，以及两个长度为 n 的整数数组 speed 和 efficiency。现有 n 名工程师，编号从 1 到 n。其中 speed[i] 和 efficiency[i] 分别代表第 i 位工程师的速度和效率。从这 n 名工程师中最多选择 k 名不同的工程师，使其组成的团队具有最大的团队表现值。团队表现值 的定义为：一个团队中「所有工程师速度的和」乘以他们「效率值中的最小值」。请你返回该团队的最大团队表现值，由于答案可能很大，请你返回结果对 10^9 + 7 取余后的结果
采用「动一个，定一个」的策略——即我们可以枚举效率的最小值 e，在所有效率大于 e
的工程师中选取不超过 k−1个，让他们的速度和最大
class Solution {
public:
using LL = long long;
struct Staff {
int s, e;
bool operator < (const Staff& rhs) const {
return s > rhs.s;
}
};
int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
vector<Staff> v;
priority_queue<Staff> q;
for (int i = 0; i < n; ++i) {
v.push_back({speed[i], efficiency[i]});
}
sort(v.begin(), v.end(), [] (const Staff& u, const Staff& v) { return u.e > v.e; });
LL ans = 0, sum = 0;
for (int i = 0; i < n; ++i) {
LL minE = v[i].e;
LL sumS = sum + v[i].s;
ans = max(ans, sumS * minE);
q.push(v[i]);
sum += v[i].s;
if (q.size() == k) {
sum -= q.top().s;
q.pop();
}
}
return ans % (int(1E9) + 7);
}
};
- 两个数组间的距离值
给你两个整数数组 arr1 ， arr2 和一个整数 d ，请你返回两个数组之间的 距离值 。「距离值」 定义为符合此距离要求的元素数目：对于元素 arr1[i] ，不存在任何元素 arr2[j] 满足 |arr1[i]-arr2[j]| <= d 。
本题直接暴力求解即可，更优雅的做法是对arr2进行排序，然后取最接近arr1[i]的两个数，因为他们是最重要的两个数，然后将这两个数和arr1[i]做差取绝对值，都>d则ok。
class Solution {
public:
int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d)
{
int cnt = 0;
for (auto n : arr1) {
bool find = true;
for (auto arr2_num : arr2) {
if (std::abs(n - arr2_num) <= d) {
find = false;
break;
}
}
if (find) {
cnt++;
}
}
return cnt;
}
};
- 安排电影院座位
如上图所示，电影院的观影厅中有 n 行座位，行编号从 1 到 n ，且每一行内总共有 10 个座位，列编号从 1 到 10 。给你数组 reservedSeats ，包含所有已经被预约了的座位。比如说，reservedSeats[i]=[3,8] ，它表示第 3 行第 8 个座位被预约了。请你返回 最多能安排多少个 4 人家庭 。4 人家庭要占据 同一行内连续 的 4 个座位。隔着过道的座位（比方说 [3,3] 和 [3,4]）不是连续的座位，但是如果你可以将 4 人家庭拆成过道两边各坐 2 人，这样子是允许的。
很容易想到用位操作+掩码的方式解题，比较有趣的是1和10两个位置是无关紧要的，因此直接忽略，剩下8个刚好一字节
class Solution {
public:
int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {
int left = 0b11110000;
int middle = 0b11000011;
int right = 0b00001111;
unordered_map<int, int> occupied;
for (const vector<int>& seat: reservedSeats) {
if (seat[1] >= 2 && seat[1] <= 9) {
occupied[seat[0]] |= (1 << (seat[1] - 2));
}
}
int ans = (n - occupied.size()) * 2;
for (auto& [row, bitmask]: occupied) {
if (((bitmask | left) == left) || ((bitmask | middle) == middle) || ((bitmask | right) == right)) {
++ans;
}
}
return ans;
}
};