Welcome to BeckoninGshy's Bolg

使用python实现一个ping小程序
network

在看《计算机网络：自顶向下方法》第四章的时候，有一个编程作业是用python编写一个ping小程序，我在实现的时候加深了一写对python的了解和对IP报文头部和ICMP报文头部信息有了一定理解，故记录一下。

阅读更多
JVM OOM异常种类测试和解决方案总结
JVM

本文为学习《深入理解java虚拟机》书中2.4节实战部分的整理总结。

jvm中能引起Out of memory Error 的运行时内存存储区域大致可以分为：

  • java堆区溢出
  • java虚拟机栈和本地方法栈溢出
  • 方法区和运行时常量池溢出
  • 本机直接内存溢出
阅读更多
LeetCode-10-正则表达式匹配

10. 正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

1
2
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

说明:

  • s 可能为空，且只包含从 a-z 的小写字母。
  • p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

    示例 1:

1
2
3
4
5
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

1
2
3
4
5
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3:

1
2
3
4
5
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例 4:

1
2
3
4
5
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5:

1
2
3
4
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

思路：

可以使用动态规划来解此题。

首先定义状态，有过求LCS和LIC的经验，我们很轻易类似的写出该题的状态定义：

1
dp[i][j] 串S以i结尾，串P以j结尾是否能够匹配。

我们考虑状态转移方程：
先分类考虑：

  • s[i] != p[j] && p[j] != ‘.’ && p[j] != ‘*’

  • s[i] == p[j]

  • p[j] == ‘.’
  • p[j] == ‘*’

第一种情况显然是false。

第二种情况是说明可以匹配，所以由S前i-1，P前j-1匹配的情况决定。

第三种情况把’.’看做s[i]可以和第二种情况合并

重点是第四种情况，p[j]为’*’ 的情况：

单独一个‘ ’是不构成语义的，所以出现‘ ’就要看前一个字符，而前面有可能出现的又有‘.’和字母两种情况。
前面说过了，我们遇见‘.’直接把他当作与s[i]相等的字符即可。不需要做特殊处理。

所以就只剩下了‘*’ 前面是字母的
而分成的两种情况：

  • ‘*’前面的字母和s[i-1]不匹配。
  • ‘*’前面的字母和s[i-1]匹配。

第一种情况由于’*’可以代表零个之前的字符。例如：

1
2
aabc
ad*abc

是可以匹配的。
所以我们遇到’*’前面的字母和s[i-1]不匹配就可以跳过这两个字符。即

1
dp[i][j] = dp[i][j-2]

最后’*’前面的字母和s[i-1]匹配：

那么就有按照‘*’的语义，又需要划分三种情况：

  • *加上前面的字符不与s[i-1]匹配。
  • 加上前面的字符只与s[i-1]匹配 即 作废。
  • *加上前面的字符可以与多个s[i-1]匹配。

前两种情况其实与我们之前分析的不加‘*’的情况基本一致。
那么与多个字符匹配怎么转移呢？

我们确定匹配多个字符可以一个一个来，只要dp[i-1][j]可以匹配。那么只要[j]是，则dp[i][j]一定可以匹配上。（别忘了，我们的前提条件是 和之前的字母匹配）

1
2
3
4
5
6
7
8

###b
###b* 
匹配。

###bb
###b*
一定能匹配。

至此我们就将所有情况分析完毕。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.size(), m = p.size();
        vector<vector<int>> dp(n+1,vector<int>(m+1));
        dp[0][0] = 1;
        //处理 aa 和c*c*c*aa 匹配的情况。前缀可以忽略。
        for(int i = 1; i <= m; i++){
            if(i-2 >= 0 && dp[0][i-2] && p[i-1] == '*') dp[0][i] = 1;
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                //单个字符匹配。
                if(s[i-1] == p[j-1] || (p[j-1] == '.')){
                    dp[i][j] = dp[i-1][j-1];
                //单个字符不匹配
                }else if(p[j-1] == '*'){
                    // baa bc*aa 形式
                    if(p[j-2] != s[i-1] && p[j-2] != '.'){
                        dp[i][j] = dp[i][j-2];
                    }else{
                    // 否则是前一个字符可以匹配
                    // 三种情况，
                    // 忽略这个匹配的字符，dp[i][j] = dp[i][j-2];
                    // 只匹配这个字符 dp[i][j] = dp[i][j-1];
                    // 匹配多个字符，即看i之前的字符和当前能不能匹配上，dp[i][j] = dp[i-1][j];
                    // ###b 和 ###b* 如果能匹配上， ###bb 和 ###b* 也能匹配上。
                        dp[i][j] = (dp[i][j-2] || dp[i][j-1] || dp[i-1][j]);
                    }
                }
            }
        }
        return dp[n][m];
    }
};

这里有一个点必须初始化，因为下标是从1开始的，无法访问到0，当遇到处理 aa 和c c c* aa 匹配的情况时，是需要访问到0的位置的，所以需要预处理。前缀可以为空的情况。

阅读更多
HDOJ102-Ma-Su-Plu-Plus

Max Sum Plus Plus

题目描述

Now I think you have got an AC in Ignatius.L’s “Max Sum” problem. To be a brave ACMer, we always challenge ourselves to more difficult problems. Now you are faced with a more difficult problem.

Given a consecutive number sequence S1, S2, S3, S4 … Sx, … Sn (1 ≤ x ≤ n ≤ 1,000,000, -32768 ≤ Sx ≤ 32767). We define a function sum(i, j) = Si + … + Sj (1 ≤ i ≤ j ≤ n).

Now given an integer m (m > 0), your task is to find m pairs of i and j which make sum(i1, j1) + sum(i2, j2) + sum(i3, j3) + … + sum(im, jm) maximal (ix ≤ iy ≤ jx or ix ≤ jy ≤ jx is not allowed).

But I`m lazy, I don’t want to write a special-judge module, so you don’t have to output m pairs of i and j, just output the maximal summation of sum(ix, jx)(1 ≤ x ≤ m) instead. ^_^

输入

Each test case will begin with two integers m and n, followed by n integers S1, S2, S3 … Sn.
Process to the end of file.

输出

Output the maximal summation described above in one line.

输入示例

1 3 1 2 3
2 6 -1 4 -2 3 -2 3

输出示例

6
8

Hint

Huge input, scanf and dynamic programming is recommended.

题目大意：

给定n个数，让其划分为k个不重叠的区间（不要求连续），求其中的最大值。

思路：

因为给定一个区间，它的最大值是确定的，所以具有无后效性，所以我们考虑使用dp来解此题。

我们首先定义状态表示，很自然的想到：

1
dp[i][j] = dp[i][j] 表示将前i个数字分成j段的最大子段和。

接下来考虑状态转移方程：

我们将状态转移分为：

  • 与前面划分的区间不合并，即自成一组。
  • 与前面划分的区间合并为一组。

第二种转移方程比较好考虑：

1
dp[i][j] = dp[i-1][j] + v[i];

自成一组需要找上一组从哪里转移。由于不需要保证连续性，所以就需要从第一段一直到j-1段都要考虑到。

1
dp[i][j] = max{dp[k][j-1](1 <= k < i)}

由于只有k个长度的字符才能分成k段。所以这里取值范围应该改为:

1
dp[i][j] = max{dp[k][j-1](j-1 <= k < i)} + v[i]

综合一下就是：

1
dp[i][j] =max( dp[i-1][j], max{dp[k][j-1](j-1 <= k < i)} ) + v[i]

分析工作准备完毕，我们准备写代码时发现，这个数组范围比较大，会O（n2）的算法会超时，所以要优化。

第二种转移方程没什么好优化的，我们转移到第一种上，它在转移上依赖了他之上的好多行的数组，列却只依赖一列。这里想象为二维数组，我们把行，列的含义互换，想象这个二维数组逆时针旋转了90度。
就得到了如下的转移方程：

1
dp[i][j] = dp[i][j] 表示将前j个数字分成i段的最大子段和。
1
dp[i][j] =max( dp[i][j-1], max{dp[i-1][k](i-1 <= k < j)} ) + v[j]

我们可以将 max{dp[i-1]k} 这个O(n)的时间，在上一层的d[i-1][j]计算结果时用一个变量来记录，使其优化为O(1)。

具体编程还是有些难度，需要好好思考。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*
 * @Date: 2020-01-24 10:42:12
 * @LastEditors  : BeckoninGshy
 * @LastEditTime : 2020-01-25 11:37:00
 */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN =1e6+10;
int dp[MAXN],v[MAXN],numax[MAXN]; //保存上一层dp的最大值。

int main(){
    int k,n;
    while(cin >> k >> n){
        for(int i = 1; i <= n; i++){
            cin >> v[i];
            dp[i] = numax[i] = 0;
        }
        dp[0] = numax[0] = 0;
        int lastmax = INT_MIN;
        for(int i = 1; i <= k; i++){
            lastmax = INT_MIN; //保存上一层dp的最大值
            for(int j = i; j <= n; j++){
            	//先利用之前的上一层最大值更新当前状态， 
                dp[j] = max(dp[j-1],numax[j-1]) + v[j];
                //再将j-1的最大值更新到上一层的最大值数组中， 将在i+1层循环中使用，当前循环不使用
                numax[j-1] = lastmax;
                //存储当前层的最大值 
                lastmax = max(lastmax,dp[j]); 
            }
        }
        cout << lastmax << endl;
    }
    return 0;
}
阅读更多
LeetCode-1320-二指输入的的最小距离

1320. 二指输入的的最小距离

二指输入法定制键盘在 XY 平面上的布局如上图所示，其中每个大写英文字母都位于某个坐标处，例如字母 A 位于坐标 (0,0)，字母 B 位于坐标 (0,1)，字母 P 位于坐标 (2,3) 且字母 Z 位于坐标 (4,1)。

给你一个待输入字符串 word，请你计算并返回在仅使用两根手指的情况下，键入该字符串需要的最小移动总距离。坐标 (x1,y1) 和 (x2,y2) 之间的距离是 |x1 - x2| + |y1 - y2|。

注意，两根手指的起始位置是零代价的，不计入移动总距离。你的两根手指的起始位置也不必从首字母或者前两个字母开始。

示例 1：

1
2
输入：word = "CAKE"
输出：3

解释：
使用两根手指输入 “CAKE” 的最佳方案之一是：
手指 1 在字母 ‘C’ 上 -> 移动距离 = 0
手指 1 在字母 ‘A’ 上 -> 移动距离 = 从字母 ‘C’ 到字母 ‘A’ 的距离 = 2
手指 2 在字母 ‘K’ 上 -> 移动距离 = 0
手指 2 在字母 ‘E’ 上 -> 移动距离 = 从字母 ‘K’ 到字母 ‘E’ 的距离 = 1
总距离 = 3

示例 2：

1
2
输入：word = "HAPPY"
输出：6

解释：
使用两根手指输入 “HAPPY” 的最佳方案之一是：
手指 1 在字母 ‘H’ 上 -> 移动距离 = 0
手指 1 在字母 ‘A’ 上 -> 移动距离 = 从字母 ‘H’ 到字母 ‘A’ 的距离 = 2
手指 2 在字母 ‘P’ 上 -> 移动距离 = 0
手指 2 在字母 ‘P’ 上 -> 移动距离 = 从字母 ‘P’ 到字母 ‘P’ 的距离 = 0
手指 1 在字母 ‘Y’ 上 -> 移动距离 = 从字母 ‘A’ 到字母 ‘Y’ 的距离 = 4
总距离 = 6

示例 3：

1
2
输入：word = "NEW"
输出：3

示例 4：

1
2
输入：word = "YEAR"
输出：7

提示：
2 <= word.length <= 300
每个 word[i]。都是一个大写英文字母。

Solution1（记忆化）：

我们首先要定义一个递归方程，思考后发现有两类主要元素：第一类是要记录到哪个字符，第二类是两个手指当前的位置。

然后发现“记录到哪个字符”这个状态不太好与两个手指进行关联（只能和一个手指进行绑定），所以我们转化一下思路，将记录到哪个字符转变为从第i个字符起，到字符串的末尾这整个区间，然后记录两个手指的状态。这样就得到了如下的递归函数参数：

1
2
3
4
// i: [i:w.size()]区间内花费的最小距离，
// l: 上一个第一个手指的位置。
// r: 上一个第二个手指的位置
dfs(int i, int l, int r)

转移方程为：

1
dfs(i,l,c) = min(dfs(i+1,l,c)+cost(r,c),dfs(i+1,c,r)+cost(l,c));

然后添加记忆化数组，整理就得到了下面的解决方案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:

    int mem[310][27][27];
    int cost(int i, int j){
        if(i == 26 || j == 26) return 0;
        return abs(i/6-j/6)+abs(i%6-j%6);
    }
    string w;
    // i: [i:w.size()]区间内花费的最小距离，
    // l: 上一个第一个手指的位置。
    // r: 上一个第二个手指的位置。
    int dfs(int i, int l, int r){
        if(i == w.size()) return 0;
        if(mem[i][l][r]) return mem[i][l][r];
        int c = w[i]-'A';
        return mem[i][l][r] = min(dfs(i+1,l,c)+cost(r,c),dfs(i+1,c,r)+cost(l,c));
    }
    int minimumDistance(string word) {
        w = word;
        //计算整个字符串的区间，初始两指从悬空状态开始。
        return dfs(0,26,26);
    }
};

Solution2（DP）：

我们可以试着将记忆化搜索转化为dp求解，很明显，状态表示和递归函数的状态是一致的，都是三维表示。

1
int dp[i][j][k]; //第一个手指一动到i，第二个手指移动到j，已经移动了k个字符的最小代价。

这里与记忆化搜索定义的字符区间范围正好相反，递归中用的是从i到n的区间，而这里由于天然的记忆化过程，可以直接表示从0到k。

接着写状态转移方程：

1
2
3
4
//从上一个字符移动到当前字符使用第一个手指，计算的最小价值。
dp[c][j][k] = min(dp[c][j][k],dp[i][j][k-1] + cost);
//从上一个字符移动到当前字符使用第二个手指，计算的最小价值。
dp[i][c][k] = min(dp[i][c][k],dp[i][j][k-1] + cost);

最后我们查看手指停在任何字符上的代价取最小即为答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    int Cost(int i, int j){
        //悬空状态，代价为0
        if(i == 26 || j == 26) return 0;
        return abs(i/6-j/6)+abs(i%6-j%6);
    }
    int dp[27][27][301]; //第一个手指一动到i，第二个手指移动到j，已经移动了k个字符的最小代价。
    int minimumDistance(string word) {
        memset(dp,0x3f3f3f3f,sizeof(dp));
        // 初始化悬空状态
        dp[26][26][0] = 0;
        int n = word.size();
        for(int k = 1; k <= n; k++){
            int c = word[k-1]-'A';
            //a
            int cost = 0;
            for(int i = 0; i <= 26; i++){
                for(int j = 0; j <= 26; j++){
                    cost = Cost(i,c);
                    //从上一个字符移动到当前字符使用第一个手指，计算的最小价值。
                    dp[c][j][k] = min(dp[c][j][k],dp[i][j][k-1] + cost);
                    cost = Cost(j,c);
                    //从上一个字符移动到当前字符使用第二个手指，计算的最小价值。
                    dp[i][c][k] = min(dp[i][c][k],dp[i][j][k-1] + cost);
                }
            }
        }
        int ans = 0x3f3f3f3f;
        for(int i = 0; i <= 26; i++){
            for(int j = 0; j <= 26; j++){
                ans = min(ans,dp[i][j][n]);
            }
        }
        return ans;
    }
};
阅读更多
LeetCode-89-格雷编码

89. 格雷编码

格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。

给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。格雷编码序列必须以 0 开头。

示例 1:

1
2
3
4
5
6
7
输入: 2
输出: [0,1,3,2]
解释:
00 - 0
01 - 1
11 - 3
10 - 2

对于给定的 n，其格雷编码序列并不唯一。
例如，[0,2,3,1] 也是一个有效的格雷编码序列。

1
2
3
4
00 - 0
10 - 2
11 - 3
01 - 1

示例 2:

1
2
3
4
5
输入: 0
输出: [0]
解释: 我们定义格雷编码序列必须以 0 开头。
     给定编码总位数为 n 的格雷编码序列，其长度为 2n。当 n = 0 时，长度为 20 = 1。
     因此，当 n = 0 时，其格雷编码序列为 [0]。

Solution1

动态规划法：

格雷码可以通过在当前的部分格雷码通过复制这一部分上下翻转次序后，使翻转后的部分通过新增加的最高位都转换为1来得到。

例如当前的部分序列为：

1
2
00
01

翻转后为

1
2
01
00

往每个数字前面增加一位前导零组合成新的部分格雷码：

1
2
3
4
000
001
001
000

将翻转后的数字的前导零置为1：

1
2
3
4
000
001
101
100

这一新的序列也是格雷码序列。

通过翻转n次，将得到长度为n全部的格雷码序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ans;
        ans.push_back(0);
        for(int k = 0; k < n; k++){
            int c = ans.size();
            for(int j = c, i = 1; j < 2*c; j++, i++){
                ans.push_back(ans[c-i]|(1<<k));
            }
        }
        return ans;
    }
};

Solution2：

直接构造法：

维基百科中生成格雷码的步骤为：

以二进制为 0 值的格雷码为第零项，第一项改变最右边的位元，第二项改变右起第一个为1的位元的左边位元，第三、四项方法同第一、二项，如此反复，即可排列出n个位元的格雷码。

以3为例：

1
2
3
4
5
6
7
8
000 初始值
001 改变右起第一项
011 改变右起第一个为1的位元的左边位元
010 改变右起第一项
110 改变右起第一个为1的位元的左边位元
111 改变右起第一项
101 改变右起第一个为1的位元的左边位元
100 改变右起第一项

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ans;
        ans.push_back(0);
        for(int k = 1; k < 1<<n; k++){
            // 改变右起第一项。
            if(k%2) ans.push_back(ans[k-1]^1);
            // 改变右起第一个为1的位元的左边位元
            else{
                int c = 0;
                int pre = ans[k-1];
                while(((pre>>c) & 1) == 0) c++;
                c++;
                ans.push_back(pre^(1<<c));
            }
        }
        return ans;
    }
};

Solution3：

公式法：

当前第i项的二进制数的最高位保留，其它位是当前位和它的高一位进行异或操作。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ans;

        for(int k = 0; k < 1<<n; k++){
            //每一项与当前数右移后异或得到。
            ans.push_back(k^(k>>1));
        }
        return ans;
    }
};
阅读更多
首页 归档 标签 关于 搜索