天池線上程式設計 2020年9月26日日常周賽題解

文章目錄

1. K步編輯

給出一個只含有小寫字母的字串的集合以及一個目標串(target)，輸出所有可以經過不多於 k 次操作得到目標字串的字串。

你可以對字串進行一下的3種操作:

加入1個字母
刪除1個字母
替換1個字母

考查動態規劃：最短編輯距離

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
     */
    vector<string> kDistance(vector<string> &words, string &target, int k) {
        // write your code here
        vector<string> ans;
        for(auto& w : words)
        {
            if(minDistance(w, target) <= k)
                ans.push_back(w);
        }
        return ans;
    }
    int minDistance(string word1, string word2) {
        int n1 = word1.size(), n2 = word2.size(), i, j;
        if(n1==0 || n2==0) 
            return max(n1,n2);
        int dp[n1+1][n2+1];

        for(i = 0; i < n1+1; i++)
            dp[i][0] = i;
        for(j = 0; j < n2+1; j++)
            dp[0][j] = j;

        // DP
        int left, up, left_up;
        for(i = 1; i < n1+1; i++) 
        {
            for(j = 1; j < n2+1; j++) 
            {
                left    = dp[i-1][j];
                up      = dp[i][j-1];
                left_up = dp[i-1][j-1];
                if(word1[i-1] != word2[j-1]) 
                    dp[i][j] = 1 + min(left, min(up, left_up));
                else// word1[i-1] == word2[j-1]
                    dp[i][j] = left_up;
            }
        }
        return dp[n1][n2];
    }
};

2. 摺紙

摺紙，每次都是將紙從右向左對摺，凹痕為 0，凸痕為 1，求折 n 次後，將紙展開所得摺痕組成的 01 序列。
$1 < = n < = 20$

找規律，拿張紙，折幾次就會發現規律了。下一個序列是在前一個序列的基礎上插空加入010101...

class Solution {
public:
    /**
     * @param n: The folding times
     * @return: the 01 string
     */
    string getString(int n) {
        // Write your code here
        if(n==1) return "0";
        string ans, temp = "0";
        while(--n)
        {
            int flag = 0;
            for(int i = 0; i < temp.size(); i++)
            {
                ans += string(1, flag+'0')+temp[i];
                flag = (flag==0 ? 1 : 0);
            }
            ans += "1";
            temp = ans;
            ans = "";
        }
        return temp;
    }
};

3. 字串的不同排列

給出一個字串，找到它的所有排列，注意同一個字串不要列印兩次。請以字典序從小到大輸出。 0<=n<=20

排列組合，回溯+剪枝

class Solution {
public:
    /**
     * @param str: A string
     * @return: all permutations
     */
    vector<string> ans;
    vector<string> stringPermutation(string &str) {
        // write your code here
        sort(str.begin(), str.end());
        vector<bool> vis(str.size(), false);
        string s;
        dfs(str, s, 0, vis);
        return ans;
    }
    void dfs(string &str, string &s, int idx, vector<bool> &vis)
    {
        if(idx == str.size())
        {
            ans.push_back(s);
            return;
        }
        for(int i = 0; i < str.size(); i++)
        {
            if(vis[i])
                continue;
            if(i >= 1 && !vis[i-1] && str[i-1] == str[i])
                continue;//剪枝，去重
            s += str[i];
            vis[i] = true;
            dfs(str, s, idx+1, vis);
            vis[i] = false;
            s.pop_back();
        }
    }
};

4. 硬幣排成線

有 n 個硬幣排成一條線, 第 i 枚硬幣的價值為 values[i].

兩個參賽者輪流從任意一邊取一枚硬幣, 直到沒有硬幣為止. 拿到硬幣總價值更高的獲勝.

請判定第一個玩家會贏還是會輸. $1 < = n < = 2000$

博弈動態規劃，dp[i][j] 表示剩餘硬幣為 [i,j] 時，我跟對手的最大差值

class Solution {
public:
    /**
     * @param values: a vector of integers
     * @return: a boolean which equals to true if the first player will win
     */
    bool firstWillWin(vector<int> &values) {
        // write your code here
        int n = values.size(), i, j;
    	vector<vector<int>> dp(n, vector<int>(n, INT_MIN));
    	for(i = 0; i < n; ++i)
    		dp[i][i] = values[i];
    	for(int len = 1; len < n; ++len)
    	{
    		for(i = 0; i+len < n; ++i)
    		{
    			dp[i][i+len] = max(values[i]-dp[i+1][i+len], values[i+len]-dp[i][i+len-1]);
    		}
    	}
    	return dp[0][n-1] > 0;
    }
};

我的CSDN部落格地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！