1. 完美字符串
算法思路
模拟
由于我们最终要求每一个字符都是1，那我们就需要把所有的0变成1，由于一次只能变连续的k个，所以我们的策略是能变就变，如果有一段>=k的连续的0，我们就一次变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 ansC++题解详见：九章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)
代码
Java
// 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);
}
}Python
# 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)C++题解详见：九章solution
3. 字符串游戏
算法思路
Anti-nim
字符集是26个小写字母，我们只需要考虑没中字母出现的次数即可。
- 如果所有字母都只出现了
1次，那么此时一定是每个人拿一个字母，取走最后一个字母的输，即如果是偶数种字母，先手赢，否则后手赢。 - 如果有字母出现了
2次以上，那么只要最后字母出现的异或和>0，则先手胜，否则先手败。
复杂度
时间复杂度：O(n)，其中n是字符串长度
空间复杂度：O(26)，其中26是字符集大小
代码
Java
// 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));
}
}Python
# 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 > 0C++题解详见：九章solution
4. 房屋染色
算法思路
动态规划
令dp[i][j][k]表示在前i个物资，最后一个屋子颜色是j，此时步行街长度为k的时候的最小花费。
此时我们就要分情况进行转移，从而得到最后的结果。转移方程较为复杂，需要分类思考。
复杂度
时间复杂度：O(nkt)
空间复杂度：O(nkt)
代码
Java
// 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;
}
}Python
# 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