侯瑞哲的博客

Ruizhe's Blog

0%

阿里云天池 9月26日 日常周赛

发表于 Valine：

1. K步编辑

描述

给出一个只含有小写字母的字符串的集合以及一个目标串(target)，输出所有可以经过不多于 k 次操作得到目标字符串的字符串。

你可以对字符串进行一下的3种操作:

  • 加入1个字母
  • 删除1个字母
  • 替换1个字母

思路：一个应用编辑距离的问题，使用python语言会超时。

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
38
39
40
41
42
43
44
class Solution {
public:
    /**
     * @param words: a set of stirngs
     * @param target: a target string
     * @param k: An integer
     * @return: output all the strings that meet the requirements
     */

    int minDistance(string word1, string word2, int k) {
        int m = word1.size();
        int n = word2.size();
        if (m - n > k || n - m > k) return k + 1;
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1[i - 1] == word2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1];
                else {
                    dp[i][j] = 1 + min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j]));
                }
            }
        }
        return dp[m][n];
    }

    vector<string> kDistance(vector<string> &words, string &target, int k) {
        // write your code here
        vector<string> res;
        for (auto &word: words) {
            if (minDistance(word, target, k) <= k) {
                res.push_back(word);
            }
        }
        return res;
    }
};

2. 折纸

描述

折纸，每次都是将纸从右向左对折，凹痕为 0，凸痕为 1，求折 n 次后，将纸展开所得折痕组成的 01 序列。

1<=n<=20

思路：类似中序遍历，加入一个是正是反的变量，模拟折纸过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    """
    @param n: The folding times
    @return: the 01 string
    """

    def getString(self, n):
        # Write your code here
        def printProcess(i, N, down):
            if i > N:
                return
            printProcess(i + 1, N, True)
            if down is True:
                res.append('0')
            else:
                res.append('1')
            printProcess(i + 1, N, False)

        res = []
        printProcess(1, n, True)
        return "".join(res)

3. 字符串的不同排列

描述

给出一个字符串，找到它的所有排列，注意同一个字符串不要打印两次。 请以字典序从小到大输出。 0<=n<=20

思路：提前去重，输出排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    """
    @param str: A string
    @return: all permutations
    """

    def stringPermutation(self, s):
        # write your code here
        li = list(s)
        li.sort()
        q, nq = [""], []
        for char in li:
            for ans in q:
                for i in range(len(ans), -1, -1):
                    if i < len(ans) and char == ans[i]:
                        break
                    nq.append(ans[:i] + char + ans[i:])
            q, nq = nq, []
        q.sort()
        return q

4. 硬币排成线

描述

有 n 个硬币排成一条线, 第 i 枚硬币的价值为 values[i].

两个参赛者轮流从任意一边取一枚硬币, 直到没有硬币为止. 拿到硬币总价值更高的获胜.

请判定 第一个玩家 会赢还是会输.

1<=n<=2000 0<=value[i]<=1e7

思路：一个常见的dp问题

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:
    """
    @param values: a vector of integers
    @return: a boolean which equals to true if the first player will win
    """

    def firstWillWin(self, values):
        # write your code here
        n = len(values)
        dp = [[[0, 0] for _ in range(n)] for _ in range(n)]
        for i in range(n):
            dp[i][i][0] = values[i]
        for gap in range(1, n):
            for i in range(n - gap):
                j = i + gap
                left = dp[i + 1][j][1] + values[i]
                right = dp[i][j - 1][1] + values[j]
                if left > right:
                    dp[i][j][0] = left
                    dp[i][j][1] = dp[i + 1][j][0]
                else:
                    dp[i][j][0] = right
                    dp[i][j][1] = dp[i][j - 1][0]
        return dp[0][n - 1][0] > dp[0][n - 1][1]

PS: 今天第一次答阿里云，阿里云的罚时有点多，罚时时间还没有写出来，要注意有十足的保证再提交