头像

challow


访客:2753

离线:9小时前



challow
13天前

理论基础

down 的操作就相当于每次找出root root->left root->right 这三个元素中的最小值,如果不是root则进行交换。然后从新的位置递归进行 down 操作

wULHde.png

代码实现


#include <iostream>
#include <cstdio>

using namespace std;

const int N = 100010;

int h[N];
int n, m;
int numsize;

void down(int u)
{
    int t = u; // 存储的最小元素的下标
    if(u * 2 <= numsize && h[u * 2] < h[t]) t = u * 2; // 保证元素有左右儿子的情况下判断左儿子是否小于根节点的值
    if(u * 2 + 1 <= numsize && h[u * 2 + 1] < h[t]) t = u * 2 + 1;

    if(u != t) // 如果当前最小值的位置不是根节点,那么进行元素交换并递归操作
    {
        swap(h[u], h[t]);
        down(t);
    }
}

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


    for (int i = n / 2; i; i -- ) down(i); // O(n) 时间复杂度建立堆

    while(m -- )
    {
        printf("%d ", h[1]);
        h[1] = h[numsize];
        numsize -- ;
        down(1);
    }
}



活动打卡代码 LeetCode 125. 验证回文串

challow
14天前
class Solution:
    def isPalindrome(self, s: str) -> bool:
        i, j = 0, len(s) - 1
        while i < j:
            while i < j and not s[i].isalnum(): 
                i += 1
            while i < j and not s[j].isalnum(): 
                j -= 1
            if i < j:
                if s[i].upper() != s[j].upper():
                    return False
                else:
                    i += 1
                    j -= 1 
        return True





challow
14天前

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.res = -0x3f3f3f3f
        self.dfs(root)
        return self.res

    def dfs(self, root) -> int:
        if not root:
            return 0
        left = max(0, self.dfs(root.left))
        right = max(0, self.dfs(root.right))

        self.res = max(self.res, left + root.val + right)

        return root.val + max(left, right)




challow
14天前

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        f = [0] * (n + 2)
        minp = 0x3f3f3f3f

        for i in range(1, n + 1):
            f[i] = max(f[i - 1], prices[i - 1] - minp)
            minp = min(minp, prices[i - 1])

        res = 0
        maxp = 0
        for i in range(n, 0, -1):
            res = max(res, maxp - prices[i - 1] + f[i - 1])
            maxp = max(maxp, prices[i - 1])
        return res




challow
14天前

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        for i in range(len(prices) - 1):
            res += max(0, prices[i + 1] - prices[i])
        return res




challow
14天前

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        maxp = 0x3f3f3f3f
        for i in range(len(prices)):
            res = max(prices[i] - maxp, res)
            maxp = min(maxp, prices[i])
        return res



活动打卡代码 LeetCode 216. 组合总和 III

challow
14天前

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(1, k, n);
        return res;
    }
    void dfs(int u, int k, int n)
    {
        if(k == 0 && n == 0)
        {
            res.push_back(path);
        }
        for (int i = u; i <= 9; i ++ )
        {
            if(n - i >= 0)
            {
                path.push_back(i);
                dfs(i + 1, k - 1, n - i);
                path.pop_back();
            }
        }
    }
};



活动打卡代码 AcWing 876. 快速幂求逆元

challow
19天前

#include <iostream>

typedef long long LL;

using namespace std;

int qmi(int a, int k, int p)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = (LL) res* a % p;
        k >>= 1;
        a = (LL)a* a %p;
    }
    return res;
}

int main()
{
    int n;
    scanf("%d", &n);
    while(n -- )
    {
        int a, k, p;
        scanf("%d%d", &a, &p);

        int res = qmi(a, p - 2, p);
        if(a % p)
            printf("%d\n", res);
        else 
            printf("impossible\n");
    }
    return 0;
}




活动打卡代码 AcWing 875. 快速幂

challow
19天前

#include <iostream>

typedef long long LL;

using namespace std;

int qmi(int a, int k, int p)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = (LL) res* a % p;
        k >>= 1;
        a = (LL)a* a %p;
    }
    return res;
}

int main()
{
    int n;
    scanf("%d", &n);
    while(n -- )
    {
        int a, k, p;
        scanf("%d%d%d", &a, & k, &p);

        printf("%d\n", qmi(a, k, p));
    }
    return 0;
}



活动打卡代码 AcWing 1174. 受欢迎的牛

challow
23天前

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

using namespace std;

const int N = 10010, M = 50010;

int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt, Size[N];
int dout[N];

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[++ top] = u, in_stk[u]  = true;
    for (int i = h[u]; i != -1 ;i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if(in_stk[j]) low[u] = min(low[u], dfn[j]);
    }

    if(dfn[u] == low[u])
    {
        ++ scc_cnt;
        int y;
        do {
           y = stk[top -- ];
           in_stk[y] = false;
            id[y] = scc_cnt;
            Size[scc_cnt] ++;
        } while(y != u);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    while(m -- )
    {
        int a, b;
        scanf("%d%d",&a, &b);
        add(a, b);
    }

    for (int i = 1;i <= n ; i ++ )
        if(!dfn[i])
            tarjan(i);

    for (int i = 1; i <= n; i ++ )
        for (int j = h[i]; j != -1; j = ne[j])
        {
            int k = e[j];
            int a = id[i], b = id[k];
            if (a != b) dout[a] ++;
        }

    int zeros = 0, sum = 0;
    for (int i = 1; i <= scc_cnt; i ++ )
        if (!dout[i])
        {
            zeros ++;
            sum += Size[i];
            if(zeros > 1)
            {
                sum = 0;
                break;
            }
        }

    printf("%d\n", sum);
    return 0;
}