天池×九章算法｜超級碼力線上程式設計大賽 第3場題解

1. 完美字元串

算法思路

模拟

由于我們最終要求每一個字元都是

1

，那我們就需要把所有的

變成

1

，由于一次隻能變連續的

k

個，是以我們的政策是能變就變，如果有一段

>=k

的連續的

，我們就一次變

k

個，對于現有的

1

是不需要改變的。

複雜度

時間複雜度：

O(n)

，其中

n

是字元串長度

空間複雜度：

O(1)

代碼

Java

// This solution is powered by @lintcode.com
public class Solution {
    /**
     * @param s: string need to be transformed
     * @param k: minimum char can be transformed in one operation
     * @return: minimum times of transforming all char into '1'
     */
    public int perfectString(String s, int k) {
        int ans=0;
        for(int i=0;i<s.length();i++)if(s.charAt(i)=='0')
        {
            ans++;
            int r=i;
            while(r<s.length()&&s.charAt(r)=='0'&&r-i<k)
            {
                r++;
            }
            i=r-1;
        }
        return ans;
    }
}           

Python

# This solution is powered by @lintcode.com
class Solution:
    """
    @param s: string need to be transformed
    @param k: minimum char can be transformed in one operation
    @return: minimum times of transforming all char into '1'
    """
    def perfectString(self, s, k):
        ans, now, n = 0, 0, len(s)
        for i in range(n):
            if s[i] == '0':
                now += 1
            else:
                ans += now // k
                if now % k != 0:
                    ans += 1
                now = 0
        if now != 0:
            ans += now // k
        if now % k != 0:
            ans += 1
        
        return ans           

C++題解詳見： 九章solution

2. 最大公倍數

數學

對于這個題，我們需要根據

a

和

b

的範圍來判斷答案。分為以下幾種情況讨論：

• 當

  b - a == 2

  時，此時隻有三個數

  a

  ,

  a + 1

  a + 2

  。我們隻需要對這三個數做lcm即可。

• b - a >= 3

  ，且

  b

  是奇數的時候，由于

  b

  b - 1

  b - 2

  兩兩互質，是以最終的答案就是

  b * (b - 1) * (b - 2)

• b - a >= 3

  b

  是偶數的時候，若

  b

  是3的倍數，由于

  b - 1

  b - 2

  ，

  b - 3

  (b - 1) * (b - 2) * (b - 3)

• b - a >= 3

  b

  b

  不是3的倍數，由于

  b

  b - 1

  b - 3

  b * (b - 1) * (b - 3)

O(1)

O(1)

// This solution is powered by @lintcode.com
public class Solution {
    /**
     * @param a: Left margin
     * @param b: Right margin
     * @return: return the greatest common multiple
     */
    public long greatestcommonmultiple(int a, int b) {
        if (b - a < 3) {
            long temp = (long) b * (b - 1) / gcd(b,b - 1);
            return temp * (b - 2) / gcd(temp,b - 2);
        }
        else if(b % 2 == 1) {
            return (long) b * (b - 1) * (b - 2);
        }
        else {
            if(b % 3 == 0) {
                return (long) (b - 1) * (b - 2) * (b - 3);
            }
            else {
                return (long) b * (b - 1) * (b - 3);
            }
        }
    }
    public long gcd(long a, long b){
        return b == 0 ? a:gcd(b, a % b);
    }

}           

# This solution is powered by @lintcode.com
class Solution:
    """
    @param a: Left margin
    @param b: Right margin
    @return: return the greatest common multiple
    """
    def gcd(self,a,b):
        if b == 0: return a
        return self.gcd(b, a % b)
    def greatestcommonmultiple(self, a, b):
        if b - a < 3:
            temp = b * (b - 1) / self.gcd(b,b - 1)
            return int(temp * (b - 2) / self.gcd(temp,b - 2))
        elif b % 2:
            return b * (b - 1) * (b - 2)
        else:
            if b % 3 == 0:
                return (b - 1) * (b - 2) * (b - 3)
            else:
                return b * (b - 1) * (b - 3)           

3. 字元串遊戲

Anti-nim

字元集是26個小寫字母，我們隻需要考慮沒中字母出現的次數即可。

• 如果所有字母都隻出現了

  1

  次，那麼此時一定是每個人拿一個字母，取走最後一個字母的輸，即如果是偶數種字母，先手赢，否則後手赢。
• 如果有字母出現了

  2

  次以上，那麼隻要最後字母出現的異或和

  >0

  ，則先手勝，否則先手敗。

O(n)

n

O(26)

26

是字元集大小

// This solution is powered by @lintcode.com
public class Solution {
    /**
     * @param s: a string for this game 
     * @return: return whether Alice can win this game
     */
    public boolean stringGame(String s) {
        // Write your code here
        int[] count = new int[26];
        int n = s.length();
        
        for(int i = 0; i < n; i++) {
            count[s.charAt(i) - 'a']++;
        }
        
        int xor_sum = 0;
        boolean flag = false; // 判斷是否存在出現兩次以上的字元
        for(int i = 0; i < 26; i++) {
            xor_sum ^= count[i];
            flag = flag || (count[i] >= 2);
        }
        return ((flag && xor_sum > 0) || (!flag && xor_sum == 0));
        
    }
}           

# This solution is powered by @lintcode.com
class Solution:
    """
    @param s: a string for this game 
    @return: return whether Alice can win this game
    """
    def stringGame(self, s):
        num = [0] * 26
        flag = 0
        for i in range(len(s)):
            num[ord(s[i]) - ord('a')] += 1
            if num[ord(s[i]) - ord('a')] > 1:
                flag = 1
        if flag == 0:
            return len(s) % 2 == 0
        xor = 0
        for i in num:
            xor ^= i
        return xor > 0           

4. 房屋染色

動态規劃

令

dp[i][j][k]

表示在前

i

個物資，最後一個屋子顔色是

j

，此時步行街長度為

k

的時候的最小花費。

此時我們就要分情況進行轉移，進而得到最後的結果。轉移方程較為複雜，需要分類思考。

O(nkt)

O(nkt)

// This solution is powered by @lintcode.com
public class Solution {
    /**
     * @param costs: costs of paint ith house into color j
     * @param t: maximum length of street
     * @return: minimum costs of painting all houses
     */
    public int paintHouseIII(int[][] costs, int t) {
        int n=costs.length,k=costs[0].length;
        int[][][] dp = new int[n][k][2];
        int[][] sum = new int[n][k];
        int[][] min1 = new int[n][2],min2 = new int[n][2];
        for(int i=0;i<k;i++)
        {
            sum[0][i]=costs[0][i];
            for(int j=1;j<n;j++)sum[j][i]=sum[j-1][i]+costs[j][i];
        }
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<k;j++)dp[i][j][0]=dp[i][j][1]=1000000000;
        }
        min1[0][0]=min1[0][1]=min2[0][0]=min2[0][1]=1000000000;
        for(int i=0;i<k;i++)
        {
            dp[0][i][0]=costs[0][i];
            if(t==1)dp[0][i][1]=costs[0][i];
            if(dp[0][i][0]<min1[0][0]){min2[0][0]=min1[0][0];min1[0][0]=dp[0][i][0];}
            else if(dp[0][i][0]<min2[0][0])min2[0][0]=dp[0][i][0];
            if(dp[0][i][1]<min1[0][1]){min2[0][1]=min1[0][1];min1[0][1]=dp[0][i][1];}
            else if(dp[0][i][1]<min2[0][1])min2[0][1]=dp[0][i][1];
        }
        for(int i=1;i<n;i++)
        {
            min1[i][0]=min1[i][1]=min2[i][0]=min2[i][1]=1000000000;
            for(int j=0;j<k;j++)
            {
                if(dp[i-1][j][0]==min1[i-1][0])dp[i][j][0]=Math.min(dp[i][j][0],min2[i-1][0]+costs[i][j]);
                else dp[i][j][0]=Math.min(dp[i][j][0],min1[i-1][0]+costs[i][j]);
                if(dp[i-1][j][1]==min1[i-1][1])dp[i][j][1]=Math.min(dp[i][j][1],min2[i-1][1]+costs[i][j]);
                else dp[i][j][1]=Math.min(dp[i][j][1],min1[i-1][1]+costs[i][j]);
                if(i<t)
                {
                    dp[i][j][1]=Math.min(dp[i][j][1],sum[i][j]);
                }
                for(int w=Math.max(i-t,0);w<=i-1;w++)
                {
                    if(dp[w][j][0]==min1[w][0])dp[i][j][1]=Math.min(dp[i][j][1],min2[w][0]+sum[i][j]-sum[w][j]);
                    else dp[i][j][1]=Math.min(dp[i][j][1],min1[w][0]+sum[i][j]-sum[w][j]);
                }
                if(dp[i][j][0]<min1[i][0]){min2[i][0]=min1[i][0];min1[i][0]=dp[i][j][0];}
                else if(dp[i][j][0]<min2[i][0])min2[i][0]=dp[i][j][0];
                if(dp[i][j][1]<min1[i][1]){min2[i][1]=min1[i][1];min1[i][1]=dp[i][j][1];}
                else if(dp[i][j][1]<min2[i][1])min2[i][1]=dp[i][j][1];
            }
        }
        int ans=1000000000;
        for(int i=0;i<k;i++)ans=Math.min(ans,Math.min(dp[n-1][i][0],dp[n-1][i][1]));
        return ans;
    }
}           

# This solution is powered by @lintcode.com
class Solution:
    """
    @param costs: costs of paint ith house into color j
    @param t: maximum length of street
    @return: minimum costs of painting all houses
    """
    def paintHouseIII(self, costs, t):
        n = len(costs)
        k = len(costs[0])
        dp = [[[0, 0] for i in range(k)]for j in range(n)]
        summ = [[0] * k for i in range(n)]
        min1 = [[0, 0] for i in range(n)]
        min2 = [[0, 0] for i in range(n)]
        for i in range(k):
            summ[0][i] = costs[0][i]
            for j in range(1, n):
                summ[j][i] = summ[j - 1][i] + costs[j][i]
        for i in range(n):
            for j in range(k):
                dp[i][j][0] = dp[i][j][1] = float('inf')
        min1[0][0] = float('inf')
        min1[0][1] = float('inf')
        min2[0][0] = float('inf')
        min2[0][1] = float('inf')
        for i in range(k):
            dp[0][i][0] = costs[0][i]
            if t == 1:
                dp[0][i][1] = costs[0][i]
            if dp[0][i][0] < min1[0][0]:
                min2[0][0] = min1[0][0]
                min1[0][0] = dp[0][i][0]
            elif dp[0][i][0] < min2[0][0]:
                min2[0][0] = dp[0][i][0]
            if dp[0][i][1] < min1[0][1]:
                min2[0][1] = min1[0][1]
                min1[0][1] = dp[0][i][1]
            elif dp[0][i][1] < min2[0][1]:
                min2[0][1] = dp[0][i][1]
        for i in range(1, n):
            min1[i][0], min1[i][1] = float('inf'), float('inf')
            min2[i][0], min2[i][1] = float('inf'), float('inf')
            for j in range(k):
                if dp[i - 1][j][0] == min1[i - 1][0]:
                    dp[i][j][0] = min(dp[i][j][0], min2[i - 1][0] + costs[i][j])
                else:
                    dp[i][j][0] = min(dp[i][j][0], min1[i - 1][0] + costs[i][j])
                if dp[i - 1][j][1] == min1[i - 1][1]:
                    dp[i][j][1] = min(dp[i][j][1], min2[i - 1][1] + costs[i][j])
                else:
                    dp[i][j][1] = min(dp[i][j][1], min1[i - 1][1] + costs[i][j])
                if i < t:
                    dp[i][j][1] = min(dp[i][j][1], summ[i][j])
                for w in range(max(i - t, 0), i):
                    if dp[w][j][0] == min1[w][0]:
                        dp[i][j][1] = min(dp[i][j][1], min2[w][0] + summ[i][j] - summ[w][j])
                    else:
                        dp[i][j][1] = min(dp[i][j][1], min1[w][0] + summ[i][j] - summ[w][j])
                if dp[i][j][0] < min1[i][0]:
                    min2[i][0] = min1[i][0]
                    min1[i][0] = dp[i][j][0]
                elif dp[i][j][0] < min2[i][0]:
                    min2[i][0] = dp[i][j][0]
                if dp[i][j][1] < min1[i][1]:
                    min2[i][1] = min1[i][1]
                    min1[i][1] = dp[i][j][1]
                elif dp[i][j][1] < min2[i][1]:
                    min2[i][1] = dp[i][j][1]
        ans = float('inf')
        for i in range(k):
            ans = min(ans, min(dp[n - 1][i][0], dp[n - 1][i][1]))
        return ans