Stella-W

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 500010;

int n, m;
int w[N];
struct Node
{
int l, r;
int sum, lmax, rmax, tmax;
}tr[N * 4];

void pushup(Node &u, Node &l, Node &r)
{
u.sum = l.sum + r.sum;
u.lmax = max(l.lmax, l.sum + r.lmax);
u.rmax = max(r.rmax, r.sum + l.rmax);
u.tmax = max(max(l.tmax, r.tmax), l.rmax + r.lmax);
}

void pushup(int u)
{
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r)
{
if (l == r) tr[u] = {l, r, w[r], w[r], w[r], w[r]};
else
{
tr[u].l = l, tr[u].r = r;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}

int modify(int u, int x, int v)
{
if (tr[u].l == x && tr[u].r == x) tr[u] = {x, x, v, v, v, v};
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
pushup(u);
}
}

Node query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u];
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (r <= mid) return query(u << 1, l, r);
else if (l > mid) return query(u << 1 | 1, l, r);
else
{
auto left = query(u << 1, l, r);
auto right = query(u << 1 | 1, l, r);
Node res;
pushup(res, left, right);
return res;
}
}
}

int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++) scanf("%d", &w[i]);
build(1, 1, n);

int k, x, y;
while (m --)
{
scanf("%d%d%d", &k, &x, &y);
if (k == 1)
{
if (x > y) swap(x, y);
printf("%d\n", query(1, x, y).tmax);
}
else modify(1, x, y);
}
return 0;
}



#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 200010;

int m, p;
struct Node
{
int l, r;
int v;
}tr[N * 4];

void pushup(int u)
{
tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}

void build(int u, int l, int r)
{
tr[u] = {l, r}; // 结构体初始化是按照顺序赋值
if (l == r) return;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

int query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;
int mid = tr[u].l + tr[u].r >> 1;
int v = 0;
if (l <= mid) v = query(u << 1, l, r);
if (r > mid) v = max(v, query(u << 1 | 1, l, r));
return v;
}

void modify(int u, int x, int v)
{
if (tr[u].l == x && tr[u].r == x) tr[u].v = v;
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
pushup(u);
}
}

int main()
{
int n = 0, last = 0;
scanf("%d%d", &m, &p);
build(1, 1, m);

int x;
char op[2];
while (m --)
{
scanf("%s%d", op, &x);
if (*op == 'Q')
{
last = query(1, n - x + 1, n);
printf("%d\n", last);
}
else
{
modify(1, n + 1, (last + x) % p);
n ++;
}
}
return 0;
}



Stella-W
12天前

题目描述

DFS加回溯，每次找出两个数进行枚举，同时按照组合来枚举，详见代码注释

C++ 代码

class Solution {
public:
vector<char> operations = {'+', '-', '*', '/'};

bool judgePoint24(vector<int>& nums)
{
vector<double> vec;
for(auto n : nums)
{
vec.push_back(n * 1.0);
}
return find24(vec);
}

bool find24(vector<double> vec)
{
if(vec.size() == 1)
{
return abs(vec[0] - 24.0) <= 1e-5;
}

for (int i = 0; i < vec.size(); i ++){  // 每次用两个数枚举
for (int j = 0; j < vec.size(); j ++){
if(i == j) continue;
vector<double> res;
for (int k = 0; k < vec.size(); k ++)
{
if(k != i && k != j)
res.push_back(vec[k]);
}   // 添加4个数
for (auto op : operations)
{
if ((op == '+' || op == '*') && i > j) continue;// 只计算一种顺序
if (op == '/'  && vec[j] == 0.0) continue;
switch(op)
{
case '+': res.push_back(vec[i] + vec[j]); break;
case '-': res.push_back(vec[i] - vec[j]); break;
case '*': res.push_back(vec[i] * vec[j]); break;
case '/': res.push_back(vec[i] / vec[j]); break;
}
if (find24(res)) return true;
res.pop_back();// 回溯
}
}
}
return false;
}
};


Stella-W
15天前

题目描述

C++ 代码

class Solution {
public:
int n;
bool canPartitionKSubsets(vector<int>& nums, int k) {
int sum = accumulate(nums.begin(), nums.end(),0);
if(sum % k != 0) return false;
n = nums.size();
sort(nums.rbegin(),nums.rend());
vector<bool> st(n,false);
return dfs(nums, k, sum/k, 0, 0, st);
}

bool dfs(vector<int>&nums, int k, int target, int start, int cursum,
vector<bool> &st)
{
if(k == 1) return true;
if(cursum > target) return false;
if(cursum == target) return dfs(nums, k-1, target, 0, 0, st);

for(int i = start; i < n; i++)
{
if(st[i]) continue;
st[i] = true;
if (dfs(nums, k, target, i + 1, cursum + nums[i], st)) return true;
st[i] = false;
}
return false;
}
};


Stella-W
16天前

题目描述

（1）如果当前点为地雷，修改为X，直接返回
（2）若不为地雷，看周围是否有其他地雷，如果没有就修改为B，然后dfs周围可遍历点
（3）若不为地雷，同时周围有地雷，修改为对应数字

C++ 代码

class Solution {
public:
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int n, m;
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
n = board.size(), m = board[0].size();
vector<vector<bool>> st(n, vector<bool> (m, false));
dfs(board, st, click[0], click[1]);
return board;
}

bool dfs(vector<vector<char>>& board, vector<vector<bool>>& st, int x, int y)
{
st[x][y] = true;
if (board[x][y] == 'M')
{
board[x][y] = 'X';
return true;
}
int cnt = 0;
for (int i = 0; i < 8; i ++)
{
int a = x + dx[i], b = y + dy[i];
if (a < 0 || b < 0 || a >= n || b >= m || st[a][b]) continue;
if (board[a][b] == 'M') cnt ++;
}

if (cnt != 0) board[x][y] = cnt + '0';
else
{
board[x][y] = 'B';
for (int i = 0; i < 8; i ++)
{
int a = x + dx[i], b = y + dy[i];
if (a < 0 || b < 0 || a >= n || b >= m || st[a][b]) continue;
if (dfs(board, st, a, b)) return true;
}
}
return false;

}
};


Stella-W
17天前

题目描述

dfs+回溯，path存储当前方案

C++ 代码

class Solution {
public:
vector<vector<int>> res;
int target;
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<int> path;
target = sum;
dfs(root, 0, path);
return res;
}

void dfs(TreeNode* root, int s, vector<int>& path)
{
if (!root) return;
path.push_back(root->val);
s += root->val;
if (s == target && !root->left && !root->right) res.push_back(path);
dfs(root->left, s, path);
dfs(root->right, s, path);
path.pop_back();
}
};


Stella-W
19天前

题目描述

C++ 代码

class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int l = 0;
int r = nums.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (mid % 2 == 1) mid --;
if (nums[mid] != nums[mid + 1]) r = mid;
else l = mid + 2;

}
return nums[l];

}
};


Stella-W
20天前

题目描述

C++ 代码

class Solution {
public:
vector<int> ans;
unordered_map<TreeNode*, TreeNode*> parent;  // son=>parent
unordered_map<TreeNode*, int> visit;    //record visied node

void findParent(TreeNode* node){
if (!node) return;
if (node->left)
{
parent[node->left] = node;
findParent(node->left);
}
if (node->right)
{
parent[node->right] = node;
findParent(node->right);
}
}

vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
if (!root) return {}; // 原函数
findParent(root);              // 记录所有son和parent
dfs(target, K);                // 从target进行
return ans;
}

void dfs(TreeNode* node, int K)
{                                       // 唯一逻辑
if(visit[node])
return;
visit[node] ++;
if(K == 0)
{
ans.push_back(node->val);
return;
}
if(node->left){
dfs(node->left, K - 1);
}
if(node->right){
dfs(node->right, K - 1);
}
TreeNode* p = parent[node];
if(p)
dfs(p, K - 1);
}
};


Stella-W
20天前

题目描述

1：对于同一个X要自上到下返回元素
2：对于同一位置的元素，较小的排在前面

C++ 代码

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
unordered_map<int, vector<pair<int, int>>> hash;
int m = 100;
static bool myfunction3 (pair<int , int> i,pair<int , int> j)
{
if (i.first != j.first)
return (i.first > j.first);
else
return i.second < j.second;
}

vector<vector<int>> verticalTraversal(TreeNode* root) {
vector<vector<int>> res;
dfs(root, 0, 0);
int cnt = 0;
for (int i = m; cnt < hash.size(); i ++)
{
vector<int> tmp;
sort(hash[i].begin(), hash[i].end(), myfunction3);

for (int j = 0; j < hash[i].size(); j ++)
{
tmp.push_back(hash[i][j].second);
}
res.push_back(tmp);
cnt ++;
}
return res;
}

void dfs(TreeNode* root, int u, int y)
{
if (!root) return;
hash[u].push_back({y, root->val});
m = min(m, u);
dfs(root->left, u - 1, y - 1);
dfs(root->right, u + 1, y - 1);
}
};


Stella-W
20天前

题目描述

C++ 代码

class Solution {
public:
int islandPerimeter(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
int res = 0, cnt = 0, tmp = 0;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++)
{
if (grid[i][j] == 0) continue;
else
{
cnt ++;
for (int k = 0; k < 4; k ++)
{
int a = i + dx[k], b = j + dy[k];
if (a >= 0 && a < n && b >= 0 && b < m && grid[a][b]) tmp ++;
}
}
}
res = 4 * cnt - tmp;
return res;

}
};