头像

Stella-W


访客:2562

在线 



#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;
}




活动打卡代码 AcWing 1275. 最大数

#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天前

题目描述

一道枚举方案数的题,和算法提高课的枚举互质数很像,涉及知识点为DFS+剪枝

剪枝有:
优化搜索顺序:先对数组按照从大到小排序,减少搜索分支
可行性剪枝:若当前组内数大于target,返回
排除等效冗余:在同一组内,从start开始搜。当开了新的一组后,从0开始搜。这种方法搜出来的方案每组是按照组合而不是排列。

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天前

题目描述

标准DFS,分为3种情况

(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天前

题目描述

找出数组中只出现一次的元素,要求用logn的时间。

本题在二分模板2基础上,只搜索满足条件的偶数位置。

对于合法的序列,例如 11 33 44, 可以发现偶数下标i对应的数nums[i] 等于nums[i + 1]

而不合法序列 如 11 22 3 44 可以发现出现3之后的偶数位置不满足了nums[i] 等于nums[i + 1]这个性质

那么用模板2搜索满足nums[i] != nums[i + 1]的最小下标,可以发现此时的结果就是单个元素的位置。

有一点要注意,就是要保证mid也是偶数,如果是奇数就-1。因为要保证位置最小,所以不能用++。

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天前

题目描述

用一个哈希表记录 节点->父节点的映射
再用一个哈希表,记录状态。

由于已经有了第一个哈希表,直接从target节点开始搜索, 搜索三个方向,俩儿子和父亲。

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:对于同一位置的元素,较小的排在前面
由于用到了排序,时间复杂度为O(nlogn)

顺便通过这道题学会了定义比较函数,当然可以参照wzc大佬的代码每次把y+1而不是-1,自己写的时候没想到

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天前

题目描述

所有元素遍历常数次,时间复杂度为O(n);

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;

    }
};