分类：Codes

表达式求值

中缀表达式转后缀表达式。对于普通中缀表达式的计算，我们可以将其转化为后缀表达式再进行计算。转换方法也十分简单。只要建立一个用于存放运算符的栈，扫描该中缀表达式：

  1. 如果遇到数字，直接将该数字输出到后缀表达式（以下部分用「输出」表示输出到后缀表达式）；
  2. 如果遇到左括号，入栈；
  3. 如果遇到右括号，不断输出栈顶元素，直至遇到左括号（左括号出栈，但不输出）；
  4. 如果遇到其他运算符，不断去除栈顶所有运算优先级大于等于当前运算符的运算符，输出。最后，新的符号入栈；
  5. 把栈中剩下的符号依次输出，表达式转换结束。

对于一个后缀表达式，只需要 维护一个数字栈，每次遇到一个运算符，就取出两个栈顶元素，将运算结果重新压入栈中 。最后，栈中唯一一个元素就是该后缀表达式的运算结果时间复杂度  。

class Solution {
    //适用于个位数，加减乘除
public:
    int calculate(string s) {
        stack<char> sign;//运算符栈
        vector<char> postfix;//后缀表达式
        for (auto ch :s) {
            if (ch == ' ')
                continue;
            else if (isdigit(ch)) {
                postfix.push_back(ch);
            } else if (ch == '(') {
                sign.push(ch);
            } else if (ch == ')') {
                while (!sign.empty() && sign.top() != '(') {
                    postfix.push_back(sign.top());
                    sign.pop();
                }
                sign.pop();
            } else {
                while (!sign.empty() && get_priority(sign.top()) >= get_priority(ch)) {//只要栈顶运算符的优先级不低于新运算符，就不断取出栈顶并输出
                    postfix.push_back(sign.top());
                    sign.pop();
                }
                sign.push(ch);
            }
        }
        while (!sign.empty()) {
            postfix.push_back(sign.top());
            sign.pop();
        }
        //遇到运算符就计算
        stack<int> nums;
        for (auto item:postfix) {
            if (isdigit(item))
                nums.push(item - '0');
            else {
                int one = nums.top();
                nums.pop();
                int two = nums.top();
                nums.pop();
                if (item == '+') {
                    nums.push(one + two);
                } else if (item == '-') {
                    nums.push(two - one);
                } else if (item == '*') {
                    nums.push(one * two);
                } else if (item == '/') {
                    nums.push(two / one);
                }
            }

        }
        return nums.top();
    }

    int get_priority(char ch) {
        if (ch == '+' || ch == '-')
            return 0;
        else if (ch == '*' || ch == '/')
            return 1;
        else
            return -1;
    }
};
0

大根堆/小根堆的实现

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

 

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

 

0

蓄水池抽样

蓄水池抽样算法

蓄水池抽样算法随机算法的一种，用来从 N 个样本中随机选择 K 个样本，其中 N 非常大（以至于 N 个样本不能同时放入内存）或者 N 是一个未知数。其时间复杂度为 O(N)

解法

算法首先创建一个长度为 k 的数组（蓄水池）用来存放结果，初始化为 S 的前 k 个元素。然后从 k+1 个元素开始迭代直到数组结束，在 S 的第 i + 1个元素，算法生成一个随机数 𝑗∈[0,𝑖]， 如果 j < k， 那么蓄水池的第 j 个元素被替换为 S 的第 i 个元素。

vector<int> ReservoirSampling(vector<int> data, int k) {
    int n = data.size();
    assert(k <= n);
    // init: fill the first k elems into reservoir
    vector<int> reservoir(data.begin(), data.begin() + k);
    for (int i = k; i < data.size(); i++) {
        int j = rand() % (i + 1);// inclusive range [0, i]
        if (j < k) {
            reservoir[j] = data[i];
        }
    }
    return reservoir;
}

证明

证明：首先，对于任意的 i，第 i 个元素进入蓄水池的概率为 k / i；而在蓄水池内每个元素被替换的概率为 1 / k; 因此在第 i 轮第j个元素被替换的概率为 (k / i ) * (1 / k) = 1 / i。 接下来用数学归纳法来证明，当循环结束时每个元素进入蓄水池的概率为 k / n.

假设在 (i-1) 次迭代后，任意一个元素进入 蓄水池的概率为 k / (i-1)。有上面的结论，在第 i 次迭代时，该元素被替换的概率为 1 / i， 那么其不被替换的概率则为 1 – 1/i = (i-1)/i；在第i 此迭代后，该元素在蓄水池内的概率为 k / (i-1) * (i-1)/i = k / i. 归纳部分结束。

因此当循环结束时，每个元素进入蓄水池的概率为 k / n. 命题得证。

参考

蓄水池抽样算法 (Reservoir Sampling Algorithm)

0

打怪兽

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

 

0