大根堆/小根堆的实现

#include <iostream>
#include <vector>

using namespace std;

template<typename P>

class Heap {
private:
    vector<P> heap_elem{-1};//堆容器, 使得堆的编号从1开始
    int maxmin_heap;//选择大\小根堆

    void up_adjust(int now) {//上浮调整(默认大根堆)
        while (now > 1 && heap_elem[now] > heap_elem[now / 2]) {
            swap(heap_elem[now], heap_elem[now / 2]);
            now = now / 2;
        }
    };

    void down_adjust(P &top, int now) {//下沉调整
        heap_elem[now] = top;
        int next;
        while (now * 2 <= heap_elem.size() - 1) {
            if (now * 2 + 1 > heap_elem.size() - 1) {
                next = now * 2;
            } else {
                next = heap_elem[now * 2] > heap_elem[now * 2 + 1] ? now * 2 : now * 2 + 1;
            }
            if (heap_elem[next] > heap_elem[now]) {
                swap(heap_elem[next], heap_elem[now]);
                now = next;
            } else {
                break;
            }
        }
    };

public:
    Heap(int m) {//构造堆
        maxmin_heap = m;//default max_heap
    };

    P getTop() {//弹获取堆顶元素
        if (heap_elem.size() > 1)
            return heap_elem[1] * maxmin_heap;
        return heap_elem[0];//堆为空
    }

    bool empty() {//判断堆空
        return heap_elem.size() == 1;
    }

    void push(P x) {//送元素入堆
        heap_elem.push_back(x * maxmin_heap);
        int now = heap_elem.size() - 1;
        up_adjust(now);
    };

    P pop() {//堆顶元素弹出
        P res = getTop();
        P top = heap_elem.back();
        heap_elem.pop_back();
        int now = 1;
        down_adjust(top, now);
        cout << "pop " << res << " successfully." << endl;
        return res;
    };

    int size() {
        return heap_elem.size() - 1;
    }

    void print() {
        for (int i = 1; i < heap_elem.size(); i++) {
            cout << heap_elem[i] * maxmin_heap << ' ';
        }
        cout << endl;
    }

};

int main() {
    //Topk测试没问题
    int max_heap = 1, min_heap = -1;
    Heap<int> h(min_heap);//可更改为min_heap,来构建小根堆
    int x;
    for (int i = 0; i < 10; ++i) {
        x = rand() % 100;
        h.push(x);
        cout << "x: " << x << endl;
        h.print();
    }
    h.pop();
    h.print();
    return 0;
}

 

[Hard]鸡蛋掉落

887. 鸡蛋掉落

你将获得 K 个鸡蛋,并可以使用一栋从 1 到 N  共有 N 层楼的建筑。

每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再把它掉下去。

你知道存在楼层 F ,满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎,从 F 楼层或比它低的楼层落下的鸡蛋都不会破。

每次移动,你可以取一个鸡蛋(如果你有完整的鸡蛋)并把它从任一楼层 X 扔下(满足 1 <= X <= N)。

你的目标是确切地知道 F 的值是多少。

无论 F 的初始值如何,你确定 F 的值的最小移动次数是多少?

 

示例 1:

输入:K = 1, N = 2
输出:2
解释:
鸡蛋从 1 楼掉落。如果它碎了,我们肯定知道 F = 0 。
否则,鸡蛋从 2 楼掉落。如果它碎了,我们肯定知道 F = 1 。
如果它没碎,那么我们肯定知道 F = 2 。
因此,在最坏的情况下我们需要移动 2 次以确定 F 是多少。
示例 2:

输入:K = 2, N = 6
输出:3
示例 3:

输入:K = 3, N = 14
输出:4
 

提示:

1 <= K <= 100
1 <= N <= 10000
class Solution {
   public:
    //方法一:暴力动规(超时),比较好理解
    int superEggDrop(int K, int N) {
        vector<vector<int>> dp(K + 1, vector<int>(N + 1, 0));
        //初始化
        for (int i = 1; i <= K; i++) {
            for (int j = 1; j <= N; j++) {
                dp[i][j] = j;
            }
        }
        for (int i = 2; i <= K;) {
            for (int j = 1; j <= N; j++) {
                for (int k = 1; k < j; k++) {
                    /**
                     * 最坏情况下的最少扔鸡蛋次数
                     * 当前鸡蛋总数为i,楼层总数为j,在第k层楼扔鸡蛋时,鸡蛋碎了往楼下走(dp[i-
                     * 1][k - 1],鸡蛋没碎dp[i][j - k],在第k层扔得算1次
                     */
                    dp[i][j] =
                        min(dp[i][j], max(dp[i - 1][k - 1], dp[i][j - k]) + 1);
                }
            }
        }
        return dp[K][N];
    }

    //方法二:数学动规,重新定义dp
    int superEggDrop2(int K, int N) {
        /**
         * dp[k][m]:当前状态为 k 个鸡蛋,尝试扔 m 次鸡蛋,
         * 返回这个状态下最高的确认楼层数
         */
        vector<vector<int>> dp(K + 1, vector<int>(N + 1, 0));
        int m = 0;
        while (dp[K][m] < N) {
            m++;
            for (int k = 1; k <= K; k++)
                /**
                 * 1. 鸡蛋没碎: dp[k][m - 1] 就是楼上的楼层数,因为鸡蛋个数 k
                 * 不变,扔鸡蛋次数 m 减一;
                 * 2. 鸡蛋碎了: dp[k - 1][m - 1]
                 * 就是楼下的楼层数,因为鸡蛋个数 k 减一,同时扔鸡蛋次数 m
                 * 减一;
                 * 3.是当前楼层数
                 *
                 */
                dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1;
        }
        return m;
    }
}

 

打怪兽

小Q打算穿越怪兽谷,他不会打怪,但是他有钱。

他知道,只要给怪兽一定的金币,怪兽就会一直护送着他出谷。

在谷中,他会依次遇见N只怪兽,每只怪兽都有自己的武力值和要“贿赂”它所需的金币数。

如果小Q没有“贿赂”某只怪兽,而这只怪兽“武力值”又大于护送他的怪兽武力之和,这只怪兽就会攻击他。

小Q想知道,要想成功穿越怪兽谷而不被攻击,他最少要准备多少金币。

输入格式
第一行包含整数N,表示怪兽的数量。

第二行包含N个整数d1,d2,…,dn,表示每只怪兽的武力值。

第三行包含N个整数p1,p2,…,pn,表示收买N只怪兽所需的金币数。

输出格式
输出一个整数,表示所需最小金币数。

https://www.acwing.com/problem/content/description/605/
/**
 * dp[i][j] = max(dp[i-1][j],dp[i-1][j-coin[i]]+force[i]);
 * 其中dp[i][j]表示包含第i个怪兽的情况下,用j个金币所能获得的最大武力值
 * 初始条件:
 * dp[0][j]=0;//0个怪兽始终获得武力0
 * dp[i][0]=-1;//用0个金币贿赂怪兽不可行
 * dp[i][j]=-1;//表示用j个硬币贿赂前i个怪兽不可行。如上面的例子:dp[1][1]=8。dp[3][1]=-1,用1个金币贿赂3个怪兽显然不可行。
 * 答案:
 * 找到第一个不为-1的dp[n][j],这个j即为所求。
 */

int main() {
    int n;//n个怪兽
    cin >> n;
    int force[100];
    int coin[100];
    int dp[101][101];
    for (int i = 1; i <= n; i++)
        cin >> force[i];
    for (int i = 1; i <= n; i++)
        cin >> coin[i];
    memset(dp, -1, sizeof(dp));
    memset(dp[0], 0, sizeof(dp[0]));
//    fill(dp[0], dp[0] + sizeof(dp[0]) / dp[0][0], 0);//0个怪兽始终获得武力0
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= 100; ++j) {
            //只有满足 不用贿赂怪兽i时的最大武力值 > 怪兽i的武力值时,才可以不用贿赂怪兽i,即dp[i-1][j]
            if (dp[i - 1][j] >= force[i]) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j]);//
            }
            //只有当前金币j大于贿赂怪兽i所需金币coin[i],并且剩余的金币j-coin[i]可以保证足够贿赂i之前的怪兽时才可以贿赂怪兽i,
            // 即dp[i-1][j-coin[i]];
            if (j >= coin[i] && dp[i - 1][j - coin[i]] != -1) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - coin[i]] + force[i]);
            }
        }
    }
    int res = 0;
    for (int j = 1; j <= 100; ++j) {
        if (dp[n][j] != -1) {
            res = j;
            break;
        }
    }
    cout << res << endl;
    return 0;
}

 

KMP和朴素匹配BF

  1. KMP和朴素匹配算法BF

class Solution {
public:
    int kmp(string ts, string ps) {
        int i = 0;
        int j = 0;
        vector<int> next(ps.size());
        get_next(ps, next);
        while (i < (int) ts.size() && j < (int) ps.size()) {//string::size()返回的是一个无符号的整数,当与负数比较会出错
            if (j == -1 || ts[i] == ps[j]) {
                ++i;
                ++j;
            } else {
                j = next[j];
            }
        }
        if (j == ps.size())
            return i - j;
        else
            return -1;
    }

    void get_next(string ps, vector<int> &next) {
        next[0] = -1;
        int k = -1;
        int j = 0;
        while (j < (int) ps.size() - 1) {
            if (k == -1 || ps[j] == ps[k]) {
                next[++j] = ++k;
            } else
                k = next[k];
        }
    }

    int bf(string ts, string ps) {//朴素搜索
        int i = 0;
        int j = 0;
        while (i < (int) ts.size() && j < (int) ps.size()) {
            if (ts[i] == ps[j]) {
                i++;
                j++;
            } else {
                i = i - j + 1;//回溯
                j = 0;
            }
        }
        if (j == (int) ps.size())
            return i - j;
        else
            return -1;
    }
};

2.KMP原理

寻找最长前缀后缀

假设现在文本串S匹配到 i 位置,模式串P匹配到 j 位置

  • 如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++,继续匹配下一个字符;
  • 如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]。此举意味着失配时,模式串P相对于文本串S向右移动了j – next [j] 位。
    • 换言之,当匹配失败时,模式串向右移动的位数为:失配字符所在位置 – 失配字符对应的next 值,即移动的实际位数为:j – next[j],且此值大于等于1。

字符串查找之KMP

C++ size()

vector, string,等的size()返回的都是无符号的整数,跟负数比较会出问题,比如

vector<int> a{1, 4, 3};
int i = -1;
while (i < a.size()) {
    cout << "great" << endl;//并不会输出
    break;
}

#必须改成
while (i < (int)a.size()) {