分类：Codes

Contribution guide

1. 规范commit
feat: add hat wobble
^--^  ^------------^
|     |
|     +-> Summary in present tense.
|
+-------> Type: chore, docs, feat, fix, refactor, style, or test.


build: Changes that affect the build system or external dependencies (example scopes: gulp, broccoli, npm)
ci: Changes to our CI configuration files and scripts (example scopes: Travis, Circle, BrowserStack, SauceLabs)
docs: Documentation only changes
feat: A new feature
fix: A bug fix
perf: A code change that improves performance
refactor: A code change that neither fixes a bug nor adds a feature
style: Changes that do not affect the meaning of the code (white-space, formatting, missing semi-colons, etc)
test: Adding missing tests or correcting existing tests
chore: updating grunt tasks etc; no production code change
2. 提PR步骤
1. 自己的本地repo主分支（这是是develop）保持和官方远程repo的最新代码一致
git remote add upstream https://github.com/PaddlePaddle/PaddleNLP # 添加官方repo为remote源，名为upstream
git pull upstream develop

2. 从主分支创建呢新的分支，用于增加feature或者bugfix
git checkout -b bugfix

3. 格式化源代码钩子
pip install pre-commit
pre-commit install

4. 在本地bugfix分支做修改，提交commit，然后push到自己的远程repo bugfix分支
git push origin bugfix

5. github端提交PR

6. PR合入后删除远程分支
github界面删除 或者
git push origin :bugfix

7.删除本地分支
git checkout develop
git branch -d bugfix



其他:
origin是个人repo作为remote
upstream是官方repo作为remote
可以通过git remote -v查看
(base) B000000365184D:text_simultaneous_translation gongenlei$ git remote -v
origin	https://github.com/gongel/PaddleNLP (fetch)
origin	https://github.com/gongel/PaddleNLP (push)
upstream	https://github.com/PaddlePaddle/PaddleNLP (fetch)
upstream	https://github.com/PaddlePaddle/PaddleNLP (push)
3. 常用的命令
git reset --hard commit_id 版本回退，HEAD后退，暂存区/工作区全部清空
git reset --soft commit_id 版本回退，HEAD后退，暂存区/工作区不变，并把HEAD后退带来的文件差异加入到暂存区
git reset --mixed commit_id 版本回退，HEAD后退，暂存区清空，并把HEAD后退带来的文件差异加入到工作区
git reflog 查看所有分支的所有操作记录（包括已经被删除的 commit 记录和 reset 的操作）
git checkout -b bugfix remotes/origin/bugfix 根据远程分支来创建本地分支
4. 常用术语
    • WIP   Work in progress, do not merge yet. // 开发中
    • LGTM Looks good to me. // Riview 完别人的 PR ，没有问题
    • PTAL Please take a look. // 帮我看下，一般都是请别人 review 自己的 PR
    • CC Carbon copy // 一般代表抄送别人的意思
    • RFC  —  request for comments. // 我觉得这个想法很好, 我们来一起讨论下
    • IIRC  —  if I recall correctly. // 如果我没记错
    • ACK  —  acknowledgement. // 我确认了或者我接受了,我承认了
    • NACK/NAK — negative acknowledgement. // 我不同意
5.  github加速处理
方法一 
# 设置代理 
export https_proxy=https://xx 
export http_proxy=http://xx 

方法二 
# 修改hosts文件 
sudo vim /etc/hosts 
# 刷新DNS缓存 
sudo killall -HUP mDNSResponder
6. 参考
0

表达式求值

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

  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