1. 从头到尾
算法思路
暴力模拟
我们只要从头到尾的施加法术，然后看看在n次之类能否一样即可，其中n是字符串长度。
代码
- Java
// This solution is powered by @lintcode.com
public class Solution {
/**
* @param s1: the string 1
* @param s2: the string 2
* @return: judge can s1 change to s2
*/
public boolean judge(String s1, String s2) {
s1 += s1;
return s1.indexOf(s2) != -1 && s1.length() / 2 == s2.length();
}
}- Python
# This solution is powered by @lintcode.com
class Solution:
"""
@param s1: the string 1
@param s2: the string 2
@return: judge can s1 change to s2
"""
def judge(self, s1, s2):
# write your code here
n = len(s1)
m = len(s2)
if n != m:
return False
for i in range(n):
s3 = s1[i:n] + s1[0:i]
if s3 == s2:
print(s1[0:i])
print(s2[i:n])
print(i)
return True
return FalseC++题解详见：九章solution
2. 闰年
算法思路
暴力枚举y1和y2是平年还是闰年，然后判断公式的合法性即可。根据题目的要求来输出答案。
代码
- Java
// This solution is powered by @lintcode.com
public class Solution {
/**
* @param inputQueries: input Queries, means [[m1, d1, m2, d2, x], [m1, d1, m2, d2, x],...]
* @return: guess whether y1 is leep year
*/
int[] days = {0,31,28,31,30,31,30,31,31,30,31,30,31};
boolean rui(int year)
{
if(year%100==0)
{
return year%400==0;
}
return year%4==0;
}
int getDays(int y1,int m1,int d1,int y2,int m2,int d2)
{
int ans=0;
for(int i=y1;i<=y2;i++)ans+=365+(rui(i)?1:0);
for(int i=1;i<m1;i++)
{
ans-=days[i];
if(i==2&&rui(y1))ans--;
}
ans-=d1-1;
ans-=days[m2]-d2;
if(m2==2&&rui(y2))ans--;
for(int i=m2+1;i<=12;i++)
{
ans-=days[i];
if(i==2&&rui(y2))ans--;
}
return ans-1;
}
char checkQueries(int m1,int d1,int m2,int d2,int x)
{
if(m1==2&&d1==29)return 'R';
if(m2==2&&d2==29)
{
if(m1<=2)return 'R';
else return 'P';
}
int flag1=0,flag2=0;
if(getDays(0,m1,d1,0,m2,d2)==x)flag1=1;
if(getDays(0,m1,d1,1,m2,d2)==x)flag1=1;
if(getDays(1,m1,d1,1,m2,d2)==x)flag2=1;
if(getDays(1,m1,d1,2,m2,d2)==x)flag2=1;
if(getDays(3,m1,d1,4,m2,d2)==x)flag2=1;
if(flag1==1&&flag2==1)return '?';
else if(flag1==1)return 'R';
else return 'P';
}
public String guessYear(int[][] inputQueries) {
String ans="";
for(int i=0;i<inputQueries.length;i++)
{
ans+=checkQueries(inputQueries[i][0],inputQueries[i][1],inputQueries[i][2],inputQueries[i][3],inputQueries[i][4]);
}
return ans;
}
}- Python
# This solution is powered by @lintcode.com
from datetime import date, timedelta
class Solution:
"""
@param inputQueries: input Queries, means [[m1, d1, m2, d2, x], [m1, d1, m2, d2, x],...]
@return: guess whether y1 is leep year
"""
def guessYear(self, inputQueries):
res = ""
for q in inputQueries:
res += self.f(q)
return res
def f(self, q):
m1, d1 = q[0], q[1]
m2, d2 = q[2], q[3]
x = q[4]
def _try(y):
if m1 == 2 and d1 == 29:
return y == 2020
date1 = date(y, m1, d1)
date1 += timedelta(x)
return date1.month == m2 and date1.day == d2
leagl1 = _try(2018)
leagl2 = _try(2019)
leagl3 = _try(2020)
if not leagl3 and (leagl1 or leagl2):
return 'P'
if leagl3 and not leagl1 and not leagl2:
return 'R'
return '?'C++题解详见：九章solution
3. 抽奖
算法思路
二分答案
由于概率一定是在0.01到100当中的，而且具有单调的性质，因此我们可以二分答案，找到符合要求的位置，从而计算出结果。
代码
- Java
// This solution is powered by @lintcode.com
public class Solution {
/**
* @param b:
* @param c:
* @param p:
* @return: return the a
*/
double getAns(double a,int b,int c)
{
double pp=a/100.0;
double pre=1;
int times=0;
double E=0;
while(pp+0.0001<=1.0)
{
times++;
if(times>=b)pp=Math.min(1.0,pp+0.01*c);
E+=pp*pre*times;
pre*=1-pp;
}
return E;
}
public double lotteryDraw(int b, int c, int p) {
double ans=0.000,cha=1e9;
for(double a=0.00;a<=100.00;a+=0.01)
{
double wucha=Math.abs(getAns(a,b,c)-100.0/p);
if(wucha<cha){ans=a;cha=wucha;}
}
return ans;
}
}- Python
# This solution is powered by @lintcode.com
class Solution:
"""
@param b:
@param c:
@param p:
@return: return the a
"""
def lotteryDraw(self, b, c, p):
# write your code here
left = 0.01
right = 100
while right - left >= 0.00001:
mid = (left + right) / 2
if self.calc(mid, b, c) <= p:
left = mid
else:
right = mid
return left
def calc(self, a, b, c):
ex = 0
pnow = 1
for i in range(1, b):
ex += i * pnow * a / 100
pnow *= (1 - a / 100)
# print(ex)
times = b
while a < 100:
a = min(a + c, 100)
# a = a + c
ex += times * pnow * a / 100
pnow *= (1 - a / 100)
times += 1
return 100/exC++题解详见：九章solution
4. 十字绣
算法思路
dfs+剪枝
但是普通的剪枝并不够，需要提前预处理每一行每一列的情况，固定一些格子以后再剪枝
注意这里只要唯一解即可，所以不需要考虑回溯的问题。
代码
- Java
// This solution is powered by @lintcode.com
public class Solution {
/**
* @param rowInfo: row information
* @param colInfo: col information
* @return: return the printed picture
*/
public String[] crossStitch(int[][] rowInfo, int[][] colInfo) {
// write your code here
int n = rowInfo.length;
int m = colInfo.length;
int[][] a = new int[30][30];
int[][] b = new int[30][30];
int[][] col = new int[30][30];
int[][] cgd = new int[30][30];
int[] now = new int[30];
for (int i = 0; i < n; i++) {
for (int j = 0; j < rowInfo[i].length; j++) {
a[i + 1][j + 1] = rowInfo[i][j];
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < colInfo[i].length; j++) {
b[i + 1][j + 1] = colInfo[i][j];
}
}
String[] ans = new String[n];
dfs(1, 1, 0, n, m, a, b, col, now, cgd, ans);
return ans;
}
public boolean Set(int x, int y, int n, int m, int[][] a, int[][] b, int[][] col, int[] now, int[][] cgd, String[] ans) {
now[y]++;
int i;
if (b[y][now[y]] == 0) {
now[y]--;
return false;
}
if (x + b[y][now[y]] - 1 > n) {
now[y]--;
return false;
}
col[x][y] = 2;
for (i = 1; i < b[y][now[y]] && i + x <= n; i++) {
col[x + i][y] = 2;
cgd[x + i][y] = 1;
}
if (x + i <= n) {
col[x + i][y] = 1;
cgd[x + i][y] = 1;
}
return true;
}
public void restore(int x, int y, int n, int m, int[][] a, int[][] b, int[][] col, int[] now, int[][] cgd, String[] ans) {
col[x][y] = 0;
int i;
for (i = 1; i < b[y][now[y]] && i + x <= n; i++) {
col[x + i][y] = 0;
cgd[x + i][y] = 0;
}
if (x + i <= n) {
col[x + i][y] = 0;
cgd[x + i][y] = 0;
}
now[y]--;
}
public void dfs(int i, int j, int now, int n, int m, int[][] a, int[][] b, int[][] col, int[] nowp, int[][] cgd, String[] ans) {
if (ans[0] != null)
return;
if (i > n) {
for (int x = 1; x <= n; x++) {
String tmp = "";
for (int y = 1; y <= m; y++) {
if (col[x][y] < 2)
tmp += ".";
else
tmp += "*";
}
ans[x - 1] = tmp;
}
return;
}
if (j > m) {
if (a[i][now + 1] == 0)
dfs(i + 1, 1, 0, n, m, a, b, col, nowp, cgd, ans);
return;
}
if (col[i][j] == 0 || col[i][j] == 1) {
col[i][j] = 1;
dfs(i, j + 1, now, n, m, a, b, col, nowp, cgd, ans);
if (cgd[i][j] == 0)
col[i][j] = 0;
}
int k;
if (a[i][now + 1] > 0) {
for (k = 0; k < a[i][now + 1] && j + k <= m; k++)
if (col[i][j + k] == 1)
break;
if (k < a[i][now + 1] || (j + a[i][now + 1] <= m && col[i][j + a[i][now + 1]] == 2))
return;
for (k = 0; k < a[i][now + 1]; k++)
if (cgd[i][j + k] == 0)
if (!Set(i, j + k, n, m, a, b, col, nowp, cgd, ans))
break;
if (k >= a[i][now + 1])
dfs(i, j + a[i][now + 1] + 1, now + 1, n, m, a, b, col, nowp, cgd, ans);
for (k--; k >= 0; k--)
if (cgd[i][j + k] == 0)
restore(i, j + k, n, m, a, b, col, nowp, cgd, ans);
}
}
}- Python
# This solution is powered by @lintcode.com
class Solution:
"""
@param rowInfo: row information
@param colInfo: col information
@return: return the printed picture
"""
def crossStitch(self, rowInfo, colInfo):
# write your code here
ans = []
n = len(rowInfo)
m = len(colInfo)
a = [[0] * 30 for _ in range(30)]
b = [[0] * 30 for _ in range(30)]
col = [[0] * 30 for _ in range(30)]
cgd = [[0] * 30 for _ in range(30)]
now = [0] * 30
for i in range(n):
for j in range(len(rowInfo[i])):
a[i + 1][j + 1] = rowInfo[i][j]
for i in range(m):
for j in range(len(colInfo[i])):
b[i + 1][j + 1] = colInfo[i][j]
self.dfs(1, 1, 0, n, m, a, b, col, now, cgd, ans)
return ans
def dfs(self, i, j, now, n, m, a, b, col, nowp, cgd, ans):
if (len(ans) != 0):
return
if (i > n):
for i in range(1, n + 1):
tmp = ""
for j in range(1, m + 1):
if col[i][j] < 2:
tmp += "."
else:
tmp += "*"
ans.append(tmp)
return
if (j > m):
if (a[i][now + 1] == 0):
self.dfs(i + 1, 1, 0, n, m, a, b, col, nowp, cgd, ans)
return
if (col[i][j] == 0 or col[i][j] == 1):
col[i][j] = 1
self.dfs(i, j + 1, now, n, m, a, b, col, nowp, cgd, ans)
if (cgd[i][j] == 0):
col[i][j] = 0
if (a[i][now + 1] != 0):
k = 0
while (k < a[i][now + 1] and j + k <= m):
if (col[i][j + k] == 1):
break
k += 1
if (k<a[i][now+1] or (j+a[i][now+1]<=m and col[i][j+a[i][now+1]]==2)):
return
k = 0
while k < a[i][now + 1]:
if cgd[i][j + k] == 0:
if (not self.Set(i, j + k, n, m, a, b, col, nowp, cgd, ans)):
break
k += 1
if k >= a[i][now + 1]:
self.dfs(i, j + a[i][now + 1] + 1, now + 1, n, m, a, b, col, nowp, cgd, ans)
k -= 1
while (k >= 0):
if (cgd[i][j + k] == 0):
self.restore(i, j + k, n, m, a, b, col, nowp, cgd, ans)
k -= 1
def Set(self, x, y, n, m, a, b, col, now, cgd, ans):
now[y] += 1
if (b[y][now[y]] == 0):
now[y] -= 1
return False
if x + b[y][now[y]] - 1 > n:
now[y] -= 1
return False
col[x][y] = 2
i = 1
while i < b[y][now[y]] and i + x <= n:
col[x + i][y] = 2
cgd[x + i][y] = 1
i += 1
if x + i <= n:
col[x + i][y] = 1
cgd[x + i][y] = 1
return True
def restore(self, x, y, n, m, a, b, col, now, cgd, ans):
col[x][y] = 0
i = 1
while i < b[y][now[y]] and i + x <= n:
col[x + i][y] = 0
cgd[x + i][y] = 0
i += 1
if x + i <= n:
col[x + i][y] = 0
cgd[x + i][y] = 0
now[y] -= 1
