Bootstrap+Vue 项目小结

发表于 2018-12-15

###项目简介

本次项目我们实现的是复制swapi这个网站，前端与后端需要分离实现，主要技术栈为：

前端（+UI）：typescript + bootstrap + vue
后端：go + jwt
数据库：boltdb

我负责的是部分前端与UI的编写和优化。之前有学习过原生的html、css等，但框架的使用还是比较少，所以这次算是一边学习一边进行项目的实现。

vue与bootstrap

Vue是一套用于构建用户界面渐进式框架，它被设计为可以自底向上的逐层应用。Vue可以非常方便的与第三方库进行整合，比如此次使用的bootstrap。使用bootstrap提供的简洁的html、css、js框架，加上vue提供的库，可以很方便的构建一套前端应用。

在本次项目中，主要利用到了vue的组件化特质，vue允许我们编写小型、独立的组件，以便于复用在大型应用中。在我们的项目中所有的界面都放在了同一个基本HTML下：

...
  <body>
    <noscript>
      <strong>We're sorry but swapi-web doesn't work properly without JavaScript enabled. Please enable it to continue.</strong>
    </noscript>
    <div id="app"></div>
    <!-- built files will be auto injected -->
  </body>
...

可以看到，id为app的div可以根据所在页面的不同而去自动更换组件，每个组件中可能又包含其他组件，比如主页home中，基本html被定义为：

<template>
  <div id="home">
    <HomeTitle/>
    <HomeIntro/>
    <hr/>
    <APIcaller/>
  </div>
</template>
...
@Component({
  components: {
    HomeTitle,
    HomeIntro,
    APIcaller,
  },
})

其中HomtTitle、HomeIntro、APIcaller对应了三个不同的组件。

对应到最底层的组件的编写时则用到了bootstrap提供的各种元素，这些元素经过bootstrap的渲染，达到了简洁美观的效果。其中需要提到的是pre这个元素。在原版swapi网站中就可以看到它使用了：

1	<pre class="prettyprint">

它的作用是为pre元素下的各种代码提供高亮及缩进。经过资料的查阅得到这其实是用到了google的code-prettify，使用时只需要包含它的js文件：

1	<script src="https://cdn.rawgit.com/google/code-prettify/master/loader/run_prettify.js"></script>

再在pre元素下声明class为prettyprint就可以了。

leetcode 115 不同的子串

发表于 2018-12-02

题目

Given a string S and a string T, count the number of distinct subsequences of S which equals T.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Example 1:

Input: S = "rabbbit", T = "rabbit"
Output: 3
Explanation:

As shown below, there are 3 ways you can generate "rabbit" from S.
(The caret symbol ^ means the chosen letters)

rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

Example 2:

Input: S = "babgbag", T = "bag"
Output: 5
Explanation:

As shown below, there are 5 ways you can generate "bag" from S.
(The caret symbol ^ means the chosen letters)

babgbag
^^ ^
babgbag
^^    ^
babgbag
^    ^^
babgbag
  ^  ^^
babgbag
    ^^^

解法一

题目的意思是有两个字符串：s和t，要找出s中和t一样的子串数量，可以任意增减s中的元素，得到剩下的子串。

一看到字符串匹配，就会想到使用动态规划算法，那么这一题的特征是什么呢？对每一个字符都有这样的选择：如果这个字符匹配了，那么就要兼顾选择了这个字符的情况（向后继续匹配），以及没有选择这个字符的情况（没有匹配，向后移一位），具体来说就是维护两个变量i和j，i对应字符串s，j对应字符串t。

func
设 res = 0
若 s[i] == t[j]:
	res += func(i+1, j+1)	//匹配
res += func(i+1, j)		//默认情况

实际实现：

int dp(int i, int j, string s, string t) {
    if(j == t.size()) return 1;
    if(i == s.size()) return 0;
    int res = 0;
    if(s[i] == t[j]){
        res += dp(i + 1, j + 1, s, t);
    }
    res += dp(i + 1, j, s, t);
    return res;
}

然而，这样的算法是会超时的，原因就是它使用了递归，递归相比起来花费还是比较高。

解法二

第二种解法就不再使用递归了，而是维护一个vector，在循环中实现dp。vector的size设为字符串t的size+1，外部循环对s字符串进行遍历，内部逐步的对t中每一个字符在s中的出现次数进行累计，最后得到结果。

实际实现：

int numDistinct(string s, string t) {
    vector<int> dp(t.size() + 1, 0);
    dp[0] = 1;
    for(int i = 1; i <= s.size(); ++i){
        int min_ = min(i, (int)t.size());
        for(int j = min_; j >= 1; j--){
            if(s[i - 1] == t[j - 1]){
                dp[j] += dp[j - 1];
            }
        }
    }
    return dp[t.size()];
}

leetcode-97 Interleaving String

发表于 2018-11-14

题目

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

Example 1:

1 2	Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" Output: true

Example 2:

1 2	Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" Output: false

解法

描述相当简略的一道题。大概意思是字符串s3可由s1与s2间的内容拼接而成，而且可以是s1、s2分成许多段来拼接，只要最后选择的字串段仍旧按照s1、s2本来的字符顺序就可以。

很快能够想到这题可以使用动态规划的方法来做：子问题即每次选择字符进行拼接时选择s1或s2。那么如何来评估这个子问题呢？这里选择维护一个二维vector，假设为f。f[i][j]就代表已选择了s1中i个元素，s2中j个元素的情况下能否拼接成功（拼接成s3中前i+j个元素）。根据前面计算过的值来计算本次的f[i][j]。若两字符串s1、s2的长度分别为m、n，s3的长度为k，那么最后只需判断f[m][n]是否为1就行了（若m+n不等于k则一定无法拼接成功）。

实际实现如下：

bool isInterleave(string s1, string s2, string s3) {
    vector<vector<int>> dp(s1.size() + 1, vector<int>(s2.size() + 1, 0));
    int dir[2][2] = {{-1, 0}, {0, -1}};
    if(s1.size() + s2.size() == s3.size()){
        dp[0][0] = 1;
    }
    for(int i = 0; i < dp.size(); ++i){
        for(int j = 0; j < dp[0].size(); ++j){
            if(i == 0 && j == 0) continue;
            for(int m = 0; m < 2; ++m){
                int x = i + dir[m][0], y = j + dir[m][1];
                if(x < 0 || y < 0) continue;
                if(dp[x][y] == 1){
                    if(x < i && s1[i-1] == s3[i+j-1]){
                        dp[i][j] = 1;
                    }
                    if(y < j && s2[j-1] == s3[i+j-1]){
                        dp[i][j] = 1;
                    }
                }
            }
        }
    }
    return dp[s1.size()][s2.size()];
}

leetcode 32 最长括号匹配题解

发表于 2018-11-08 | 更新于 2018-11-09

题目

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

1
2
3

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

1
2
3

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

解法一

首先观察一下这道题目，要找到最长的满足括号匹配的字串，那么首先要想到的是，什么时候是不匹配的呢？假设有一段满足匹配的字串s，如果在它之后的第一个元素是)，那么这时一定不匹配，如果是(，则可能会向后匹配。这样一来就能够想到，使用一个栈来存储字串的下标，用一个flag记录上一个不匹配的元素位置（初始设为-1）。每当遇到一个(时，存储这个下标，如果遇到)，则如果此时栈为空，记录flag，否则出栈一个元素再看栈是否为空，若为空则将此时位置与flag的差值作为长度备选，否则将此时位置减去栈顶位置作为长度备选（如(())的情况）。

实际实现：

int longestValidParentheses(string s) {
    if(s == "") return 0;
    stack<int> st;
    int flag = -1, length = 0;
    for(int i = 0; i < s.size(); ++i){
        if(s[i] == '('){
            st.push(i);
        }
        else{
            if(st.empty()){
                flag = i;
            }
            else{
                st.pop();
                if(st.empty()){
                    length = (i - flag > length) ? i - flag : length;
                }
                else{
                    length = (i - st.top() > length) ? i - st.top() : length;
                }
            }
        }
    }
    return length;
}

解法二

第二种方法就是使用动态规划了，维护一个dp数组，只在元素为)时赋值（只有此时可能是一段匹配字串的结束）。注意到每遇到一对()，长度可以增加2，而如果遇到))时，此时可能匹配（即((()))这种情况），这时赋给dp的值就可以用到之前计算过的值了，比如此时的位置为i，那么就取dp[i - 1] + dp[i - dp[i - 1] - 2] + 2赋给dp[i]。

具体实现：

int longestValidParentheses(string s) {
    if(s == "") return 0;
    vector<int> dp(s.size(), 0);
    if(s[0] == '(' && s[1] == ')'){
        dp[1] = 2;
    }
    for(int i = 2; i < s.size(); ++i){
        if(s[i] == ')'){
            if(s[i - 1] == '('){
                dp[i] = dp[i - 2] + 2;
            }
            else{
                if(i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '('){
                    if(i - dp[i - 1] - 1 == 0){
                        dp[i] = dp[i - 1] + 2;
                    }
                    else{
                        dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2;
                    }
                }
            }
        }
    }
    return *max_element(dp.begin(), dp.end());
}

leetcode 72+213 题解

发表于 2018-11-04

1. Edit Distance

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

Insert a character
Delete a character
Replace a character

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

解法

这题首先注意到，在做字符匹配时，我们一共有三种操作：插入、编辑和删除，因此可能存在非常多的对齐方式，这里使用动态规划来解决这一问题。

对于动态规划来说，最重要的是定义子问题，之后就按照子问题规模递增的顺序逐个求解。那么对于这道题来说如何定义子问题呢？大目标是寻找字符串x[1,...m]与y[1,...,n]间的编辑距离，将这个问题记为E(m, n)，我们可以尝试找到三种操作下的最小的E(i, j)，其中i，j比m，n规模更小，这样逐步推导下去就可以到达底层了。也就是说对每一个E(i, j)，将它分解为：E(i, j) = min{1 + E(i - 1, j), 1 + E(i, j - 1), diff(i, j) + E(i - 1, j - 1)}，这里diff(i, j)在i，j相同时为0，否则为1。

实现在这里没有选择递归，而是采用了填表的做法，实际效果是一样的：

int minDistance(string word1, string word2) {
    int m = word1.size() + 1, n = word2.size() + 1;
    vector<vector<int>> E(m, vector<int>(n, 0));
    for(int i = 0; i < m; ++i){
        E[i][0] = i;        
    }
    for(int j = 1; j < n; ++j){
        E[0][j] = j;        
    }
    for(int i = 1; i < m; ++i){
        for(int j = 1; j < n; ++j){
            int diff = word1[i - 1] == word2[j - 1] ? 0 : 1;
            E[i][j] = min(min(1 + E[i - 1][j], 1 + E[i][j - 1]), diff + E[i - 1][j - 1]);
        }
    }
    return E[m - 1][n - 1];
}

##2. House Robber Ⅱ

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
             because they are adjacent houses.

Example 2:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

解法

题目意思即在数组中取数，相邻的数不能一起取，同时头和尾不能一起取。可以想到，当我们从前往后取时，取了一个数后下一个数的位置一定是现在的位置加2或加3，先不考虑头尾相邻，那么就可以得到我们的算法了：对数组每个位置i，填充dp[i] += (dp[i - 2] > dp[i - 3] ? dp[i - 2] : dp[i - 3]);，前三位则独立讨论，这样在给数组赋值的过程中就是在进行子问题的计算。最后，因为一定会到达倒数第一个位置或第二个位置，那么就返回这两个中更大的那个。

对于头和尾不能同时取的问题，只需要分成不包含头和不包含尾的两部分分开求解，最后返回更大的就行了。

具体实现：

int rob(vector<int>& nums) {
    if(nums.empty()) return 0;
    int n = nums.size(), i = 0;
    if(nums.size() == 1){
        return nums[0];
    }
    vector<int> dp1(n - 1, 0);
    vector<int> dp2(n - 1, 0);
    for(int j = 0; j < nums.size() - 1; ++j){
        dp1[j] = nums[j];
        dp2[j] = nums[j + 1];
    }
    return max(find(dp1), find(dp2));
}
int find(vector<int>& dp){
    int i = 0;
    if(dp.size() == 1){
        return dp[0];
    }
    if(dp.size() == 2){
        return max(dp[0], dp[1]);
    }
    if(dp.size() == 3){
        return max(dp[1], dp[0] + dp[2]);
    }
    dp[2] += dp[0];
    for(i = 3; i < dp.size(); ++i){
        dp[i] += (dp[i - 2] > dp[i - 3] ? dp[i - 2] : dp[i - 3]);
    }
    return dp[i - 1] > dp[i - 2] ? dp[i - 1] : dp[i - 2];
}

leetcode-63 Unique Paths Ⅱ 题解

发表于 2018-10-27

题目

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Note: m and n will be at most 100.

Example 1:

Input:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

解法

首先分析一下这道题，问的是从左上角走到终点即右下角总共有多少条路径，而且每次只能往右走一步或者往下走一步，如果某个位置的值为1那么就算为障碍，此时是不能走这里的。那么要计算路径的时候，可以分成对每个位置进行处理，这就成为一个DP问题了。对每一个位置来说，它最多就只有两个前置位，也就是它上方与左方的位置，如果该位置处于边界的话那么只有一个前置位。

现在来讨论一下路径数目的计算，对于一个位置(i, j)来说，我们记录了到达它的两个前置位置(i, j -1)与(i - 1, j)的路径数，那么到达(i, j)的路径数就应该是两前置位置的路径数之和，这就是路径的计算方法。

实现如下：

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    int m = obstacleGrid.size(), n = obstacleGrid[0].size();
    vector<vector<int>> path(obstacleGrid.size(), vector<int>(obstacleGrid[0].size(), 0));	//记录到达(i, j)的路径数
    int dir[2][2] = {{-1, 0}, {0, -1}};
    path[0][0] = obstacleGrid[0][0] == 1 ? 0 : 1;	//起点的初始路径数
    for(int i = 0; i < m; ++i){
        for(int j = 0; j < n; ++j){
            if(obstacleGrid[i][j] == 1){
                path[i][j] = 0;
            }
            else{
                for(int k = 0; k < 2; ++k){
                    int newi = i + dir[k][0], newj = j + dir[k][1];
                    if(newi >= 0 && newi < m && newj >= 0 && newj < n){
                        path[i][j] += path[newi][newj];
                    }
                }
            }
        }
    }
    return path[m - 1][n - 1];
}

POW共识机制介绍

发表于 2018-10-21

PoW，即Proof-of-Work，工作量证明，本质上是一种经济手段，它要求请求资源方提供一些“工作”来证明它没有恶意，因为这些工作需要花费一定的资源（时间或金钱），所以可以用来解决如ddos攻击、垃圾信息等问题。相应地，这些工作必须有如下特点：对于资源请求方来说难于立即解决（不过是可解的），但对于资源提供方来说是容易验证的。

对于比特币来说，它使用的是一种叫hashcash（哈希现金）的工作量证明，它最初被用于做邮件过滤，对于正常的邮件来说，因为一般来说短时间内发送量不会很高，相应的工作量证明也不会占用很多时间。但对于垃圾邮件来说，因为需要发送的量很大，占用的计算资源也就很大，这样做是得不偿失的，所以也就能够过滤掉垃圾邮件。

在比特币中，hashcash则是用来产生区块的。在一个区块被添加至链上之前，矿工必须完成工作量证明。这里又存在一个问题，矿工为什么会想要去完成工作量证明呢（耗费计算资源）？这是因为产生区块的过程实际上是在记账，是把交易记录、时间、账本序号、上一个区块的hash值一起hash打包的过程，而对于记账成功的矿工是提供比特币奖励的，这就激发了矿工争相记账，但最后能够完成工作量证明成功记帐的矿工只有一个。

矿工在进行工作量证明之前，要做如下工作：

收集广播中还没有被记录的交易信息
检查每个交易信息中付款地址的余额信息
检查交易签名
打包验证通过的交易信息
添加一个奖励交易（新区快的首个交易）：给自己的地址增加12.5个比特币（奖励）

之后就开始进行工作量证明（散列算法一般选择SHA256）：

把上个块的hash值与当前帐页信息一起进行hash处理
设置一个随机值nonce
nonce递增，并对nonce，和第一步得到的字符串一起做hash，得到满足前置0个数的结果，就是正确的nonce

可见“工作”就是找到随机数的过程，当然这个工作的难度会根据区块产生的速度自动调节，一般是10分钟左右诞生一区块，难度调节则是通过设置前置0的个数。当一个矿工成功完成工作后，就会广播发布区块，收到区块的网络节点进行验证，验证通过则不再竞争，而是再此区块后进行工作。如果同时收到多个区块，则先在最先收到的区块后进行工作，保留其余收到的区块，若后续发现另一条链更长则更换区块。

从上述过程我们可以发现POW机制的优缺点都比较显著：

优点：

去中心化，做的工作越多，得到的越多，而且相对公平，即使算力更大也只是获得收益的概率变大，难以达到垄断。
安全性高，理论上来说要做attacker必须具有压倒性的算力优势（>50%），而且对于一般attacker来说，诚实挖矿的收益还更高，所以一般不会出现欺诈的现象。

缺点：

资源浪费。目前比特币的价格十分高昂，吸引了越来越多的人投入这一领域。大批矿池、矿机进行军备竞赛，加快挖矿的速度。但因为比特币系统的调节，新区块产生的速度越快，计算问题的难度就会更大，以至于形成了恶性循环，许多计算资源就这样浪费掉了。
交易确认时间过长。随着节点的增加，区块链更容易产生分叉，选择最长的主链后其他的分支都要舍弃。目前区块确认的共识周期长达十分钟，每秒交易量也很低。

对于资源浪费这一点，可以引入一些更有价值的问题，如寻找大的素数等数学、物理乃至其他学科上的计算问题，而不只是单纯进行hash值寻找。但实际上，要完成这一点还是很难的，因为这些问题可能相对难以快速验证，也没有好的方法去控制问题难度。

对于POW的缺点，另一种共识机制：POS（Proof of stake）提供了很好的解决方案：

不需要消耗庞大的算力，节省电力：如在BFT-style的POS中，不再根据计算工作来证明自己，而是每个人都被随机的选择去创建块，但块的确认是通过多轮的投票来决定的，这就避免了资源消耗。
POS机制会对节点持币以及维持节点给予少量的奖励，然而恶意交易所受到的惩罚会千百倍于奖励，这就防止了持币多的人进行恶意操作，防止中心化。

当然，POS也存在自己的缺点，以至于近来还出现了POW-POS混合机制。想必在不远的未来，区块链共识机制会更加的成熟，更加的稳定。

leetcode 55 题解

发表于 2018-10-16

题目：

Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

1
2
3

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.

题解：

这是一道标明为Greedy类型的题目，可以用贪心算法来解，问题就在于如何判断对这道题目来说何为“局部最优解”。

这道题的意思是从下标为0的位置开始，每个位置上有这次可以跳跃的最长距离，问能否达到终点。一开始我想到的方法是找此次跳跃距离覆盖的位置中跳跃距离最长的位置，但这个方法是错误的，当输入为[4 2 0 0 1 1 4 4 4 0 4 0]时，它在判断第一步跳到哪里的时候会选择位置1（元素2）而不是位置4（元素1），这就导致了当它从新的位置进行跳跃时，其后两个元素都为0，于是就判断无法达到终点了，然而实际是可以的。

从上述例子可以发现，尽管1小于2，但它所能达到的位置与终点的距离比2更近，所以在这道题中局部最优应该是选择能够达到的位置距离终点最短的元素作为此次跳跃的目的地。代码实现如下：

bool canJump(vector<int>& nums) {
    int size = nums.size();
    if(nums.size() == 1) return true;
    for(int i = 0; i < size; i++){
        if(nums[i] == 0){
            return false;
        }
        int min = size - nums[i + 1] - i - 1, pos = i + 1;
        for(int j = i + 1; j <= i + nums[i]; j++){
            if(j == size - 1){
                return true;
            }
            pos = (size - nums[j] - j) <= min ? j : pos;
            min = (size - nums[j] - j) <= min ? size - nums[j] - j : min;
        }
        i = pos - 1;
    }
}

升级

做完这道题后我发现了一道名为Jump Game Ⅱ的题目，原来是这道题的升级版，要求不仅给出判断能否达到终点，还要给出跳跃的步数。因为实际上我们刚才找到的就是最短的路径了，所以只需要稍微修改一下代码就行：

int jump(vector<int>& nums) {
    int count = 0;
    int size = nums.size();
    if(nums.size() == 1) return 0;
    for(int i = 0; i < size; i++){
        count++;
        if(nums[i] == 0){
            return false;
        }
        int min = size - nums[i + 1] - i - 1, pos = i + 1;
        for(int j = i + 1; j <= i + nums[i]; j++){
            if(j == size - 1){
                return count;
            }
            pos = (size - nums[j] - j) <= min ? j : pos;
            min = (size - nums[j] - j) <= min ? size - nums[j] - j : min;
        }
        i = pos - 1;
    }
}

Eadric

Eadric的博客