lc267
回文排列
lc311
稀疏矩阵
预处理标记非0+二分
class Solution {
public:
vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
if (A.size() < 1 || B.size() < 1 || B[0].size() < 1) return {};
int m = A.size();
int n = A[0].size();
int k = B[0].size();
vector<vector<int>> a(m);
vector<vector<int>> b(k);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (A[i][j] != 0) a[i].push_back(j);
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < k; ++j) {
if (B[i][j] != 0) b[j].push_back(i);
}
}
vector<vector<int>> res(m, vector<int>(k, 0));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < k; ++j) {
if (a[i].size() < 1 || b[j].size() < 1) continue;
auto ai = a[i].begin();
auto bi = b[j].begin();
//int cur_max = 0;
int sum = 0;
while (ai != a[i].end() && bi != b[j].end()) {
//cur_max = max(*ai, *bi);
if (*ai == *bi) {
sum += A[i][*ai] * B[*bi][j];
ai++;
bi++;
}
else {
if (*ai > *bi) bi = lower_bound(bi, b[j].end(), *ai);
else ai = lower_bound(ai, a[i].end(), *bi);
}
}
res[i][j] = sum;
}
}
return res;
}
};
暴力
//行列 对应位置 的乘积 和
res[r][c] += (mat1[r][j] * mat2[j][c]);
class Solution
{
public:
vector<vector<int>> multiply(vector<vector<int>>& mat1, vector<vector<int>>& mat2)
{
int r1 = mat1.size(), r2 = mat2.size();
if (r1 == 0 || r2 == 0)
return vector<vector<int>>{};
int c1 = mat1[0].size(), c2 = mat2[0].size();
vector<vector<int>> res(r1, vector<int>(c2, 0));
for (int r = 0; r < r1; r ++)
{
for (int c = 0; c < c2; c ++)
{
for (int j = 0; j < c1; j ++)//行列 对应位置 的乘积 和
{
res[r][c] += (mat1[r][j] * mat2[j][c]);
}
}
}
return res;
}
};
simd写法
行列遍历+跳过零元素+并行transform
逐元素累加实现矩阵乘法，计算ans[i][j] = mat1[i][l]*mat2[l][j]总和。
#include <execution>
class Solution {
public:
vector<vector<int>> multiply(vector<vector<int>>& mat1, vector<vector<int>>& mat2) {
int n = mat1.size(), k = mat2.size(), m = mat2[0].size();
vector ans(n, vector(m, 0));
for (int i = 0; i < n; ++i) {
for (int l = 0; l < k; ++l) {
int val = mat1[i][l];
if (!val) continue;
transform(execution::unseq, mat2[l].begin(), mat2[l].end(), ans[i].begin(), ans[i].begin(), [val](auto&& a, auto&& b) {return b + val * a;});
// ranges::transform(mat2[l], ans[i], ans[i].begin(), [val](auto&& a, auto&& b) { return b + val * a; });
}
}
return ans;
}
};
lc294
博弈论 memo 翻转
hash包装器
size_t h = hash<string>()(cur);
笔记一下没找到，大概就是注意无冲突的情况下，可以使用hash<string>()包装string
class Solution {
unordered_map<size_t, bool> memo;
public:
bool canWin(string &cur) {
size_t h = hash<string>()(cur);
if (memo.count(h))
return memo[h];
for (int i = 1; i < cur.size(); i++)
{
if (cur[i] == '+' && cur[i - 1] == '+')
{
cur[i] = cur[i - 1] = '-';
bool ans = canWin(cur);
cur[i] = cur[i - 1] = '+';//回溯
if (!ans)
return memo[h]=true;
//下一个不存在答案 那么上一个就为true
//博弈论
}
}
return memo[h]=false;
}
};
lc156
从下到上 重连后 记得置空
tnode* dfs 在找最左节点的过程中重连
class Solution {
public:
TreeNode* upsideDownBinaryTree(TreeNode* root)
{
if(!root || !root->left) return root;
auto dfs=[&](this auto&& dfs,TreeNode* node)->TreeNode*
{
if(!node->left)
return node;
auto mxl=dfs(node->left);
node->left->left=node->right;
node->left->right=node;
//从下到上 连好了后置空
node->left=nullptr;
node->right=nullptr;
return mxl;
};
return dfs(root);
//最左边 节点为根
}
};
