Saturday, March 23, 2019

POJ-1159 将字符串变成至回文串

admin    March 23, 2019    No comments



POJ 1159

最近发现做算法题最重要的是思路, 一开始的思路正确, 就会非常轻松的做出来, 反之, 会绕好长的路还不一定能出来…
这一题的关键是 最长公共子序列
我并没有想到… 然后呢, 在纸上模拟补齐, 嗯…
举个例子, Aba3bd和它的倒序db3abA, 它们的最长公共子序列是b3b, 所以只要最长的公共子序列对齐即可



1
2
A b a 3   b d
d b   3 a b A
只要对齐的字符越多, 要补的字符就越少
然后中间空出来的部分, 照抄上面的或者下面的
两边不同的部分, 直接错开对齐就行



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
#include <iostream>
#include <cstring>
using namespace std;

int main() {
    int n;
    cin >> n;
    string data;
    cin >> data;
    
    data = " " + data;
 
    static short dp[5050][5050];
    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (data[i] == data[n - j + 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
    }

    cout << n - dp[n][n] << endl;





    return 0;
}
滚动数组版



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
#include <iostream>
#include <cstring>
using namespace std;

int main() {
    int n;
    cin >> n;
    string data;
    cin >> data;
    
    data = " " + data;

    int dp[2][5050];
    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (data[i] == data[n - j + 1]) {
                dp[i % 2][j] = dp[(i+1) % 2][j - 1] + 1;
            } else {
                dp[i % 2][j] = max(dp[i % 2][j - 1], dp[(i+1) % 2][j]);
            }
        }
    }

    cout << n - dp[n % 2][n] << endl;


    return 0;
}

关于约瑟夫问题自己理解过程

admin    March 23, 2019    No comments

约瑟夫环问题

一开始我并没有完全理解这位博主的意思, 我还纳闷这公式是咋来的, 知道最后, 有一句理解这个递推式的核心在于关注胜利者的下标位置是怎么变的, 真是的一语惊醒梦中人

这里说一下我自己的理解, 一开始我其实是完全懵逼的状态, 看了WiKi上的说明, WiKi上是使用数学上的数学归纳法来推到出来的, 其实还是比较懵逼的
我们按照那位博主所说, 只关注那位幸存者, 这样问题一下就变得非常的简单, 我们假设一共有11个人, 每第3个人出局
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
我们假设f(N, M) = 最终幸存者的位置
这样f(11, 3)所表达的意思就是说, 11个人每3个人出局, 最终幸存者的位置
过程

1
2
3
4
5
6
7
8
9
10
11
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10                                                                 6
         3, 4, 5, 6, 7, 8, 9, 10, 0, 1                                                           3
                  6, 7, 8, 9, 10, 0, 1, 3, 4                                                     0
                           9, 10, 0, 1, 3, 4, 6, 7                                               6
                                     1, 3, 4, 6, 7, 9, 10                                        3
                                              6, 7, 9, 10, 1, 3                                  0
                                                       10, 1, 3, 6, 7                            3
                                                                 6, 7, 10, 1                     0
                                                                           1, 6, 7               1
                                                                                   1, 6          1
                                                                                          6      0
通过这种方式, 每次让出局的那个人的后面那个人出局, 可以让每次都是新的题目, 状态和上下都没有关系了
比如第一次, 是11个人, 每3个出局
到第二次, 就是10个人, 每3个出局, 单独来看的话, 结果是跟上面的没有关系的
不清楚有没有表达清楚
比如, 就拿第二次来说, 我继续从0开始写, 就是0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 这样的话, 状态是和上一次有关系的, 因为再下一次出局的人是5, 而这个5排在第4个位置(从0开始数), 那我写成上面那样的话, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 这样话, 我就相当与重新开始这样
这样, 每次出局一人, 我们就可以理解成每次人数减去1, 幸存者往前移动M个位置
f(N-1, M) = f(N, M) - M
这样公式大体就出来了, 然后, 我们需要再考虑下f(N, M) - M是负数的情况
于是公式就变成了这样
f(N-1, M) = (f(N, M) - M) % (N-1)
然后, 我们用逆向思维, 倒过来
f(N, M) = (f(N-1, M) + M) % N

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
using namespace std;

int main() {
    // f(1, M) = 0
    int r = 0, n = 11, m = 3;
    for (int i = 2; i <= n; ++i) {
        r = (r + m) % i;
    }
    cout << r << endl;

    return 0;
}

Thursday, March 21, 2019

在Pull requests上添加commits

admin    March 21, 2019    No comments

自己的Pull requests, 在Pull requests后, 如何再次添加commits上去

Pull requests是绑定你Pull requests的那个分支的, 所以说只要你push commits到你Pull requests上的那个分支就可以了
比如, 你在分支patch-1上修改了内容, 然后Pull requests到别人的仓库, 接下来, 你想继续修改, 直接commits到patch-1这个分支即可

如何添加commits到别人的Pull requests上

只要Contributor没有取选Allow edits from maintainers就可以修改, 一般情况没人会取选

第一种方式: 通过网页来修改

非常简单, 点进commit里去, 右上角有个像笔一样的图标直接点进去修改提交即可

第二种方式: 通过命令行来修改

这个问题我一直想解决, Google了很多, 都没有发现有详细解决的
首先明确一点, 如果说Contributor没有取选Allow edits from maintainers, 那么默认maintainers 就可以修改Pull requests绑定的那一个分支
这样的话, 直接提交到那个分支即可
这里写下自己的命令, 使用了hub, 比用git省很多事, 不用复制用户名, 分支名啥的

1
2
3
4
hub pr list        # 列出PR
hub pr checkout xx # 要切换到的PR
xxx                # 这里修改然后commit
hub push           # push
这样就可以了
Subscribe to: Posts (Atom)